Difference between revisions of "Lattices of elementary substructures"
(→First-order theory of ${\rm Lt}(N/M)$.) |
|||
| Line 24: | Line 24: | ||
| − | == First-order theory of ${\rm Lt}(N/M)$ | + | == 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 <cite> kossakschmerl2012:oncofinal </cite> showing that the answer is positive for lattices of finitely generated interstructures. | 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 <cite> kossakschmerl2012:oncofinal </cite> 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 <cite> schmerl2006:diverse </cite> that if $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. 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$? | ||
| + | |||
{{References}} | {{References}} | ||
Revision as of 11:13, 6 February 2013
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.
Contents
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 $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. 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$?
References
- Haim Gaifman. Models and types of Peano's arithmetic. Ann. Math. Logic 9(3):223--306, 1976. MR bibtex
- George Mills. Substructure lattices of models of arithmetic. Ann. Math. Logic 16(2):145--180, 1979. www DOI MR bibtex
- 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
- J. B. Paris. Models of arithmetic and the 1-3-1 lattice. Fund. Math. 95(3):195--199, 1977. MR bibtex
- James H. Schmerl. Extending models of arithmetic. Ann. Math. Logic 14:89--109, 1978. www DOI MR bibtex
- A. J. Wilkie. On models of arithmetic having non-modular substructure lattices. Fund. Math. 95(3):223--237, 1977. MR bibtex
- 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
- Roman Kossak and James H. Schmerl. On cofinal extensions and elementary interstices. Notre Dame J. Formal Logic 53(3):267--287, 2012. www bibtex
- Error: entry with key = schmerl2006:diverse does not exist
