Lattices of elementary substructures

From Peano's Parlour
Revision as of 20:51, 29 March 2013 by Jschmerl (Talk | contribs) (Diversity and Nondiversity)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

For $M\models PA$ let ${\rm{Lt}(M)}=(\{K: K\prec M\},\prec)$ and for $M\prec N$, let ${\rm Lt}(N/M)=(\{K: M\prec K\prec M\},\prec)$.

In general, the lattice problem is: Which lattices can be represented as ${\rm Lt}(N/M)=(\{K: M\prec K\prec M\},\prec)$, for some $M\prec N$?

There is a vast literature on the problem and many special cases remain open. Here are basic references: [1, 2, 3, 4, 5, 6]. Chapter 4 of [7] is devoted to the lattice problem.

Finite lattices

Is every finite lattice lattice a substructure lattice of a model of $PA$?

By a result of Schmerl the answer is positive for all ${\bf M}_n$, where $n=q+1$ or $n=q+2$ and $q$ is a power of a prime. ${\bf M}_n$ is the lattice with a top element, bottom element, and $n$ incomparable elements in between. The simplest lattice for which the problem is open is ${\bf M}_{16}$.

Every countable $M\models PA$ has an elementary end extension $N$ such that ${\rm Lt}(N/M)$ is isomorphic to the pentagon lattice ${\bf N}_5$ [6], but no $M\models PA$ at all has an elementary end extension such that ${\rm Lt}(N/M) \cong {\bf M}_3$ [4].

Schmerl has asked: What finite lattices $L$ are such that every $M\models PA$ has an elementary end extension $N$ such that ${\rm}Lt(N/M) \cong L$? What finite lattices $L$ are such that every countable $M\models PA$ has an elementary end extension $N$ such that ${\rm Lt}(N/M) \cong L$?

First-order theory of ${\rm Lt}(N/M)$

Suppose $M_1\prec_{cof} N_1$, $M_2\prec_{cof} N_2$, and $(N_1,M_1)\equiv (N_2,M_2)$. Is ${\rm Lt}(N_1/M_1)$ elementarily equivalent to ${\rm Lt}(N_2/M_2)$? The problem is motivated by a result from [8] showing that the answer is positive for lattices of finitely generated interstructures.

Diversity and Nondiversity

A model is diverse if no two distinct elementary substructures are isomorphic and is nondiverse otherwise. It was shown in [9] that if $M$ is not a model of True Arithmetic and $L \cong {\rm Lt}(M)$ is a finite lattice, then there is a diverse $N \equiv M$ such that ${\rm Lt}(N) \cong L$. Obtaining nondiverse models seems more difficult ([10]). For example, the answer to the following question is, at present, unknown: Is there a nondiverse $M$ such that ${\rm Lt}(M) \cong {\bf M}_3$ or ${\rm Lt}(M) \cong {\bf N}_5$?


  1. Haim Gaifman. Models and types of Peano's arithmetic. Ann. Math. Logic 9(3):223--306, 1976. MR   bibtex
  2. George Mills. Substructure lattices of models of arithmetic. Ann. Math. Logic 16(2):145--180, 1979. www   DOI   MR   bibtex
  3. J. B. Paris. On models of arithmetic. Conference in Mathematical Logic---London '70 (Bedford Coll., London, 1970), pp. 251--280. Lecture Notes in Math., Vol. 255, Berlin, 1972. MR   bibtex
  4. J. B. Paris. Models of arithmetic and the 1-3-1 lattice. Fund. Math. 95(3):195--199, 1977. MR   bibtex
  5. James H. Schmerl. Extending models of arithmetic. Ann. Math. Logic 14:89--109, 1978. www   DOI   MR   bibtex
  6. A. J. Wilkie. On models of arithmetic having non-modular substructure lattices. Fund. Math. 95(3):223--237, 1977. MR   bibtex
  7. Roman Kossak and James H. Schmerl. The structure of models of Peano arithmetic. Vol. 50, The Clarendon Press Oxford University Press, Oxford, 2006. (Oxford Science Publications) www   DOI   MR   bibtex
  8. Roman Kossak and James H. Schmerl. On cofinal extensions and elementary interstices. Notre Dame J. Formal Logic 53(3):267--287, 2012. www   bibtex
  9. James H. Schmerl. Diversity in substructures. 361:145--161, Providence, RI, 2004. www   DOI   MR   bibtex
  10. James H. Schmerl. Nondiversity in substructures. J. Symbolic Logic 73(1):193--211, 2008. www   DOI   MR   bibtex
Main library