Difference between revisions of "Lattices of elementary substructures."

Revision as of 12:49, 18 January 2013

Let $L$ be a lattice. Is $L$ isomorphic to ${\rm{Lt}(M)}=(\{K: K\prec M\},\prec)$, for some $M\models PA$?

There is a vast literature on the problem and many special cases remain open. Here are basic references:

Paris, J. B. On models of arithmetic. Conference in Mathematical Logic—London '70 (Bedford Coll., London, 1970), pp. 251–280. Lecture Notes in Math., Vol. 255, Springer, Berlin, 1972.

Gaifman, Haim, Models and types of Peano's arithmetic. Ann. Math. Logic 9 (1976), no. 3, 223–306.

Paris, J. B. Models of arithmetic and the 1−3−1 lattice. Fund. Math. 95 (1977), no. 3, 195–199.

Schmerl, James H., Extending models of arithmetic. Ann. Math. Logic 14 (1978), 89–109.

Mills, George Substructure lattices of models of arithmetic. Ann. Math. Logic 16 (1979), no. 2, 145–180

Wilkie, A. J. On models of arithmetic having non-modular substructure lattices. Fund. Math. 95 (1977), no. 3, 223–237.

A chapter of Kossak, Roman; Schmerl, James H. The structure of models of Peano arithmetic. Oxford Logic Guides, 50. Oxford Science Publications. The Clarendon Press, Oxford University Press, Oxford, 2006, is devoted to the lattice problem.

Most recent: Schmerl, James H. Infinite substructure lattices of models of Peano arithmetic. J. Symbolic Logic 75 (2010), no. 4, 1366–1382.

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}$.

If $M\prec N$, then ${\rm Lt}(N/M)=(\{K: M\prec K\prec M\},\prec)$.

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$ (Wilkie 1977), but no $M\models PA$ at all has an elementary end extension such that ${\rm Lt}(N/M) \cong {\bf M}_3$ (Paris 1977).

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$?