Lattices of elementary substructures

From Peano's Parlour
Revision as of 10:08, 6 February 2013 by Jschmerl (Talk | contribs) (→‎First-order theory of ${\rm Lt}(N/M)$.)

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.

References

  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
Main library

Retrieved from "http://modelsofpa.info/index.php?title=Lattices_of_elementary_substructures&oldid=236"