# Difference between revisions of "Lattices of elementary substructures"

(→Diversity and Nondiversity) |
m (→Diversity and Nondiversity) |
||

Line 34: | Line 34: | ||

It was shown in <cite> schmerl2004:diversity </cite> that if $L \cong {\rm Lt}(M)$ is a finite | It was shown in <cite> schmerl2004:diversity </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 | 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 | + | nondiverse models seems more difficult (<cite> schmerl2008:nondiversity </cite>). For example, the answer to the following |

question is, at present, unknown: Is there a nondiverse $M$ such that | 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$? | ${\rm Lt}(M) \cong {\bf M}_3$ or ${\rm Lt}(M) \cong {\bf N}_5$? |

## Revision as of 11:28, 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 ([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$?

## 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 - James H. Schmerl.
*Diversity in substructures.*361:145--161, Providence, RI, 2004. www DOI MR bibtex - James H. Schmerl.
*Nondiversity in substructures.*J. Symbolic Logic 73(1):193--211, 2008. www DOI MR bibtex