2 Preliminaries

This section presents all basic notions and results that will be needed for the discussion that follows. Some concepts are illustrated by simple examples and some preliminary results. A full introduction to the model theory of $\mathsf {PA}$ is Richard Kaye’s [Reference Kaye9] and all details directly related to the lattice problem can be found in [Reference Kossak and Schmerl13, Chapter 4].

Let $\mathcal {L}$ be the language of $\mathsf {PA}$ . Given an expansion $\mathcal {L}^\prime $ of $\mathcal {L}$ , $\mathsf {PA}^*$ is the theory consisting of the axioms of $\mathsf {PA}$ along with the induction schema for all formulas in $\mathcal {L}^\prime $ . That is, $\mathsf {PA}^*$ is not a single theory, but many, one for each such expansion. With one notable exception [Reference Schmerl30, Theorems 3 and 4], all results about models of $\mathsf {PA}$ in this article also hold for $\mathsf {PA}^*$ in any countable language. This also applies to the last section in which we discuss recursively saturated models, but there we need to add the assumption that the language is computable.

A model $\mathcal {K}$ in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is finitely generated if $\mathcal {K}=\operatorname {\mathrm {Scl}}^{\mathcal {N}}(M\cup A)$ , for some finite $A\subseteq N$ . Each finite tuple in a model of $\mathsf {PA}$ is coded by a single element; hence, if $\mathcal {M}\prec \mathcal {N}$ , for every finitely generated over $\mathcal {M}$ model $\mathcal {K}$ in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ there is an $a\in N$ such that $\mathcal {K}=\mathcal {M}(a)$ .

Let L be a lattice. An element $x \in L$ is called compact if whenever $x \leq \bigvee X$ for $X \subseteq L$ , then $x \leq \bigvee X^\prime $ for some finite $X^\prime \subseteq X$ . It is easy to verify that the compact elements of $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ are the finitely generated over $\mathcal {M}$ elementary submodels.

The set of compact elements of $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ forms a join-semilattice, which we denote as $\operatorname {\mathrm {Lt}}_0(\mathcal {N} / \mathcal {M})$ and $\operatorname {\mathrm {Lt}}_0(\mathcal {N})$ will denote $\operatorname {\mathrm {Lt}}_0(\mathcal {N}/\mathcal {N}_{\mathrm {{min}}})$ . For $a, b \in N$ , $\mathcal {M}(a) \vee \mathcal {M}(b) = \mathcal {M}(\langle a, b \rangle )$ , where $\langle x, y \rangle $ is Cantor’s pairing function. It is not obvious that the intersection of two finitely generated models may not be finitely generated. Various examples can be shown, one is given shortly below.

A complete lattice L is algebraic if each element of L is the supremum of a set of compact elements. A lattice is $\kappa $ -algebraic if it is algebraic and each compact element has less than $\kappa $ many compact elements below it. The domain of any $\mathcal {K} \in \operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is the union of the domains of all models $\mathcal {M}(a)$ , for $a\in K$ ; thus $\mathcal {K}$ is the supremum of the set of compact elements below it in the lattice.

It follows from the remarks above that for any $\mathcal {M} \models \mathsf {PA}$ , $\operatorname {\mathrm {Lt}}(\mathcal {M})$ is $\aleph _1$ -algebraic, and for any $\mathcal {M}$ and $\mathcal {N}$ , if $\mathcal {M}\prec \mathcal {N}$ then $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is $|M|^+$ -algebraic. Moreover, if $\operatorname {\mathrm {Lt}}_0(\mathcal {N}/ \mathcal {M}) \cong \operatorname {\mathrm {Lt}}_0(\mathcal {N}_1 / \mathcal {M}_1)$ , then $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong \operatorname {\mathrm {Lt}}(\mathcal {N}_1 / \mathcal {M}_1)$ . Thus, in order to realize a lattice as an interstructure lattice, we need only to ensure that we have control over the compact elements. Of course, if $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is finite, all elements of it are compact.

2.3 End-extensional and minimal types

This subsection is a brief summary of some of the results from [Reference Gaifman6]. The results are interesting on their own. They found many applications in the model theory of $\mathsf {PA}$ and the notion of definable type became standard in general model theory. Here we will just list some definitions and results that play a major role in the solution to the lattice problem for distributive lattices that is the subject of the next section.

Let T be a completion of $\mathsf {PA}$ and let $\mathcal {M}_T$ be the prime model of T. When we say that $p(x)$ is a type of T, we mean that $p(x)$ is in the language of T and it is consistent with T. A type $p(x)$ of T is unbounded if $t<x$ is in $p(x)$ for each constant Skolem term t of T.

For a model $\mathcal {M}$ , by $\mathcal {L}(\mathcal {M})$ we will denote $\mathcal {L}$ with added constant symbols for all elements of M. An ${\mathcal {L}}(\mathcal {M})$ -type is a type in ${\mathcal {L}}(\mathcal {M})$ that is finitely realizable in $\mathcal {M}$ . Thanks to the availability of a definable pairing function, for most of the results we will discuss, it is enough to consider 1-types.

An ${\mathcal {L}}(\mathcal {M})$ -type is unbounded if $(a<x)\in p(x)$ for all $a\in M$ . So, for a completion T of $\mathsf {PA}$ , an $\mathcal {L}$ -type $p(x)$ is unbounded if it is an unbounded ${\mathcal L}(\mathcal {M}_T)$ -type.

For every model $\mathcal {M}\models T$ , every unbounded type of T extends to an unbounded ${\mathcal {L}}(\mathcal {M})$ -type [Reference Gaifman6, Proposition 2.7].

Definition 3 [Reference Gaifman6].

For a model $\mathcal {M}$ , an ${\mathcal {L}}(\mathcal {M})$ -type $p(x)$ is definable if for every $\mathcal L$ -formula $\varphi (x,y)$ there exists an $\mathcal L$ -formula $\sigma _\varphi (y)$ such that for all $a\in M$ ,

$$\begin{align*}\varphi(x,a)\in p(x) \text{ iff } \mathcal{M}\models\sigma_\varphi(a). \end{align*}$$

A type of a completion T is definable if it is a definable ${\mathcal L}(\mathcal {M}_T)$ -type.

It is easy to see that $\mathcal {N}$ is a conservative extension of $\mathcal {M}$ if and only if for every $a\in N\setminus M$ , $\operatorname {\mathrm {tp}}(a/M)$ is definable. If $p(x)$ is a complete ${\mathcal {L}}(\mathcal {M})$ -type then by $\mathcal {M}(p)$ we denote the unique up to isomorphism Skolem closure of $M\cup \{b\}$ in an elementary extension of $\mathcal {M}$ in which b realizes $p(x)$ .

Definition 4 [Reference Gaifman6].

Let T be a completion of $\mathsf {PA}$ , and let $p(x)$ be a type of T. Then,

1. (1) $p(x)$ is end-extensional if for every $\mathcal {M}\models T$ and every unbounded complete ${\mathcal {L}}(\mathcal {M})$ -type $q(x)$ , if $p(x)\subseteq q(x)$ , then $\mathcal {M}(q)$ is an end extension of $\mathcal {M}$ .

2. (2) $p(x)$ minimal if for every $q(x)$ as above, $\mathcal {M}(q)$ is a minimal extension of $\mathcal {M}$ , i.e., $\operatorname {\mathrm {Lt}}(\mathcal {M}(q)/\mathcal {M})$ has exactly two elements: bottom $\mathcal {M}$ and top $\mathcal {M}(q)$ .

Gaifman proved that every minimal type is end-extensional, that every end-extensional type is definable, and that minimal and end-extensional types exist in abundance: for every completion T of $\mathsf {PA}$ there are continuum many independent minimal types of T.Footnote ² If p and q are such types, then for all $\mathcal {M}$ , $\mathcal {M}(p)$ and $\mathcal {M}(q)$ are not isomorphic. From the existence of minimal types for every completion of $\mathsf {PA}$ it follows that every model of $\mathsf {PA}$ has a minimal (conservative) elementary end extension.

Example 5. Let $p(x)$ be a minimal type of T. For $\mathcal {M}\models T$ , let $\mathcal {N}=\mathcal {M}(a)(b)(c)=\mathcal {M}(\langle a,b,c\rangle )$ , where $a, b, c$ all realize $p(x)$ . Let $\mathcal {K}$ be the supremum of $\mathcal {M}(a)$ in $\mathcal {M}(\langle a,c\rangle )$ .

$$\begin{align*}\overbrace{-----)==a==)}^{\mathcal{K}}\underbrace{--b--)}_{\mathcal{M}(b)\setminus M}\overbrace{==c==)}^{\mathcal{M}(\langle a,c\rangle)\setminus { K}} \end{align*}$$

Then, it follows from the facts about minimal types proved in [Reference Gaifman6] that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})\cong ({\mathcal P}(\{a,b,c\}),\subseteq )$ , $\operatorname {\mathrm {tp}}(\langle a,b\rangle )=\operatorname {\mathrm {tp}}(\langle a,c\rangle )$ , and both types are definable. The example shows that there are definable types which are not end-extensional. In particular, $\operatorname {\mathrm {tp}}(\langle a,b\rangle )$ is such a type, because $\mathcal {M}(b)(\langle a,c\rangle )$ is not an end extension of $\mathcal {M}(b)$ .

The technique of minimal and end-extensional types uses infinitary combinatorics of unbounded definable sets in models of $\mathsf {PA}$ and does not apply to cofinal extensions. Cofinal extensions are obtained by realizing bounded types for which combinatorial arguments about unbounded definable sets are replaced by their analogs involving bounded definable sets satisfying suitable notions of largeness. This makes a difference. For example, while we know that every model $\mathcal {M}$ has a minimal elementary end extension, we can only prove that that every countable nonstandard model has a minimal cofinal extension. This was proved by Blass (see [Reference Kossak and Schmerl13, Corollary 2.1.6]). It is a long-standing open question whether every model of $\mathsf {PA}$ has a minimal cofinal extension.

The example of minimal extensions shows that a lattice—in this example the two element lattice $L=\{{\mathbf 0_L},{\mathbf 1_L}\}$ —can be realized as $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ in two much different ways. For a countable nonstandard $\mathcal {M}$ , $\mathcal {N}$ can be either an elementary end extension or elementary cofinal extension (by Gaifman’s splitting theorem, it cannot be a mixed extension).

3 Distributive lattices

Two of the main results about the lattice problem from Gaifman’s [Reference Gaifman6] are:

1. (1) For any set I, every model $\mathcal {M}$ has a (conservative) elementary end extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {M})$ is isomorphic to the Boolean algebra of all subsets of I [Reference Gaifman6, Theorem 4.10].

2. (2) For every countable linearly ordered set $(J,<)$ , every model $\mathcal {M}$ has a (conservative) elementary end extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}_0(\mathcal {N} / \mathcal {M})$ is isomorphic to $(J,<)$ [Reference Gaifman6, Corollary 5.3].

The proof of (1) uses an iteration of elementary end extensions generated by a minimal type, as we showed in Example 5 above. The result in (2) is a corollary of a theorem about the existence of a particular end-extensional type that is used to get an extension of $\mathcal {N}$ in one step. The proof of that theorem is difficult and it takes 15 pages. Gaifman stresses that in both results one gets a uniform operator that produces the required extension $\mathcal {N}$ in a uniform way. Notice that in both cases the interstructure lattice is distributive.

Soon after [Reference Gaifman6] appeared, Mills managed to generalize Gaifman’s results by extending the notions of end-extensional and minimal types to types with infinitely many variables. His main result is the following theorem.

The equivalence of (1) and (3) was proved independently by Paris [Reference Paris18]. The proof of Mills’ theorem is difficult and it involves many technical details.

In [Reference Mills17], Mills follows the statement of Theorem 6 with an instructive example. Let L be the ordered unit interval $([0,1],\leq )$ . L is a complete distributive lattice, but it is not $\aleph _1$ -algebraic. Every element of L is compact; hence for every nonzero element, there are continuum many compact elements below it. Let $L'$ be the closely related lattice of initial segments in the set of rational numbers in [0,1] ordered by inclusion. In $L'$ , the compact elements are closed intervals $[0,p]$ . Because each $[0, p]$ contains only countably many compact segments, by Mills’ theorem, $L'$ is isomorphic to a substructure lattice.

All results about end-extensional types and their applications to the lattice problem in [Reference Gaifman6] hold for $\mathsf {PA}^*$ in a countable language. Gaifman asked if they hold for uncountable languages as well. In response, Mills gave a construction of a model of $\mathsf {PA}^*$ in a language with $\aleph _1$ function symbols that has no elementary end extension [Reference Mills16].

In terminology of Mills [Reference Mills17], a definable type $p(x)$ of T produces a lattice L if for every model $\mathcal {M}$ of T, $\operatorname {\mathrm {Lt}}(\mathcal {M}(p)/\mathcal {M})$ is isomorphic to L. For example, minimal types produce the two element lattice. It is a special feature of Gaifman’s technique that his special types produce prescribed lattices for all models of T, not just the countable ones. This is reminiscent of the MacDowell–Specker theorem, which says that every model of $\mathsf {PA}$ has an elementary end extension. The proof of this fact for countable models follows by a relatively straightforward omitting types argument. The types that produce $\mathcal {M}(p)$ given $\mathcal {M}$ and $p(x)$ do it for all models $\mathcal {M}$ regardless of the cardinality of their domains.

Gaifman conjectured that for every completion T of $\mathsf {PA}$ and every finite distributive lattice that has a unique atom, there is an end-extensional type $p(x)$ of T that produces D. The conjecture was confirmed by Schmerl [Reference Schmerl20] and by a different construction by Mills [Reference Mills17]. Mills also proved the following variant of Theorem 6 that fully characterizes all distributive lattices that can be produced by end-extensional types.

In conclusion, for every model $\mathcal {M}$ and every distributive lattice D that can be realized as an interstructure lattice, D can be realized as $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {M})$ , where $\mathcal {N}$ is an elementary conservative end extension of $\mathcal {M}$ . This completely solves the general representation problem for the distributive lattices, but one can still ask more specific questions about the extension $\mathcal {N}$ for which $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {M})$ is isomorphic to a given lattice D. In the distributive case this adds more depth to the subject. In the nondistributive case it turns out to be necessary, because there are nondistributive lattices which cannot be realized as $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {M})$ , where $\mathcal {N}$ is an end, or even mixed, extension of $\mathcal {M}$ .

4 Nondistributive lattices

By ${\mathbf {B_n}}$ we denote the Boolean algebra of all subsets of an n-element set. For every n, ${\mathbf {B_n}}$ is distributive and so are all of its sublattices. The following are examples of nondistsibutive lattices: for all $n>2$ , ${\mathbf {M_n}}$ which is the lattice with $n+2$ elements that has a top, a bottom, and n incomparable elements in between, the pentagon lattice ${\mathbf {N_5}}$ , and the hexagon lattice $\mathbf H$ . Dedekind proved that a lattice is distributive if and only if it has no sublattice that is isomorphic to either ${\mathbf {M_3}}$ or ${\mathbf {N_5}}$ (for a proof, see [Reference Grätzer7, Theorem 102]).

All lattices $\mathbf {B_n}$ , as well as $\mathbf {M_3}$ , $\mathbf {N_5}$ and $\mathbf H$ can be represented as interstructure lattices, but the general results about how this is achieved are strikingly different. Here they are:

1. (1) (Gaifman [Reference Gaifman6]) For each n, every model $\mathcal {M}$ has an elementary end extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})\cong \mathbf {B_n}$ ;

2. (2) (Wilkie [Reference Wilkie32]) Every countable model $\mathcal {M}$ has an elementary end extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})\cong {\mathbf {N_5}}$ .

3. (3) (Schmerl [Reference Schmerl21]) Let L be either $\mathbf {M_3}$ or $\mathbf H$ . Then every countable nonstandard model $\mathcal {M}$ has an elementary cofinal extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})\cong L$ .

Independently, Gaifman [Reference Gaifman6] and Paris [Reference Paris18] showed that if $\mathcal {M}\prec _{\mathsf {end}} \mathcal {N}$ then $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is not isomorphic to $\mathbf {M_3}$ . Here is a short proof. Let $L=\mathbf {M_3}$ , and let $\rho $ be a rank on L that satisfies the Blass Condition. We will show that $\rho ({\mathbf 0}_L)=\rho ({\mathbf 1}_L)$ . Suppose $a, b, c$ are the three incomparable elements of L. Because the rankset of a ranked lattice is linearly ordered, only one of these elements can be in the rankset of $(L,\rho )$ . Suppose it is c. Then, by condition (1) in the definition of rank, $\rho (a)=\rho (b)={\mathbf 1}_L$ . By the Blass Condition, $\rho (a)=\rho (a\land b)=\rho ({\mathbf 0}_L)$ ; hence $\rho ({\mathbf 0}_L)=\rho ({\mathbf 1}_L)$ . Thus, if $\mathbf {M_3}$ is represented as $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ , then $\mathcal {M}\prec _{\mathsf {cof}} \mathcal {N}$ .

Figure 1

The lattices $\mathbf {B}_2$ and $\mathbf {M}_3$ .

Figure 2

The lattices $\mathbf {N}_5$ and $\mathbf {H}$ .

Wilkie [Reference Wilkie32] proved that if $\mathcal {M}\prec _{\mathsf {end}} \mathcal {N}$ then $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is not isomorphic to the hexagon lattice $\mathbf H$ . A short argument, due to Schmerl, using both the Blass and Gaifman conditions is given in [Reference Kossak and Schmerl13, Proposition 4.2.13].

It is shown in [Reference Kossak and Schmerl13, Theorem 4.6.5] that if $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is isomorphic to $\mathbf {N_5}$ , then $\mathcal {N}$ is not a conservative extension of $\mathcal {M}$ . Because there are uncountable models all of whose elementary end extensions are conservative (the rather classless models), this shows that Wilkie’s theorem about $\mathbf {N_5}$ cannot be generalized to the uncountable case.

In the positive direction, much of what is known today about lattices that can be represented as $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ rests on applications of a powerful technique of representations of lattices introduced by Schmerl in [Reference Schmerl21]. Section 5 is devoted to such representations. Here let us just note that for all lattices ${\mathbf M}_{q+1}$ , where $q=p^k$ for a prime p and $1\leq k$ , every nonstandard countable model $\mathcal {M}$ has a cofinal extension $\mathcal {N}$ such that L is isomorphic to $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ . Using this and other results about finite lattice representations, it can be shown that the smallest number n for which $\mathbf {M_n}$ is not known to have an interstructure lattice representation is 16 [Reference Kossak and Schmerl13, p. 134].

The results above show that certain finite lattices can only be represented as $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ only when $\mathcal {N}$ is a cofinal extension of $\mathcal {M}$ . The following theorem shows that there are no finite lattices that can only be represented by interstructure lattices of end extensions.

5 Representations

Over the last 40 years, in several papers, Schmerl developed a special technique of constructing elementary extensions with prescribed interstructure lattices. It is based on particular representations of lattices as lattices of equivalence relations. In this section, we give basic definitions and motivate them with examples.

Oftentimes, realizing a particular finite lattice as an interstructure lattice requires choosing an appropriate representation of the lattice and proving some combinatorial lemmas about this representation. Before describing important properties of representations that are involved in these kinds of constructions, let us examine a motivating example.

Example 11. Let $\mathcal {M} \models \mathsf {PA}$ and $\mathcal {M} \prec \mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong \mathbf {B}_2$ . Then there are $a, b \in N$ such that $\mathcal {N} = \mathcal {M}(\langle a, b \rangle )$ and $\mathcal {M}(a)\not =\mathcal {M}(b)$ (see Figure 1). Let $\pi _1$ and $\pi _2$ be the projection functions, so that

$$ \begin{align*}\mathsf{PA} \vdash \forall x \forall y (\pi_1(\langle x, y \rangle) = x \wedge \pi_2(\langle x, y \rangle) = y).\end{align*} $$

Then for any $c \in N$ , there is an $\mathcal {M}$ -definable $f : N \longrightarrow N$ such that $\mathcal {N} \models f(\langle a, b \rangle ) = c$ . Let us fix such c and f and define a subset of M as follows. There are four possibilities:

• • $c \in M$ . In this case, let $X = \{ \langle x, y \rangle : \mathcal {M} \models f(\langle x, y \rangle ) = c \}$ . Clearly, $\mathcal {M} \models \forall n, m \in X (f(n) = f(m))$ .

• • $c \in \mathcal {M}(a) \setminus \mathcal {M}$ . In this case, there are $\mathcal {M}$ -definable $g_1, g_2$ such that

  $$ \begin{align*}\mathcal{N} \models g_1(a) = c \wedge g_2(c) = a.\end{align*} $$
  Let $X = \{ \langle x, y \rangle : \mathcal {M} \models f(\langle x, y \rangle ) = g_1(x) \wedge g_2(f(\langle x, y \rangle )) = x \}$ . Notice that $\mathcal {M} \models \forall n, m \in X (f(n) = f(m) \Longleftrightarrow \pi _1(n) = \pi _1(m))$ .

• • $c \in \mathcal {M}(b) \setminus \mathcal {M}$ . Similarly, there are $\mathcal {M}$ -definable $g_1, g_2$ such that

  $$ \begin{align*}\mathcal{N} \models g_1(b) = c \wedge g_2(c) = b.\end{align*} $$
  Let $X = \{ \langle x, y \rangle : \mathcal {M} \models f(\langle x, y \rangle ) = g_1(y) \wedge g_2(f(\langle x, y \rangle )) = y \}$ . Again, one observes that $\mathcal {M} \models \forall n, m \in X (f(n) = f(m) \Longleftrightarrow \pi _2(n) = \pi _2(m))$ .

• • $c \in \mathcal {N} \setminus (\mathcal {M}(a) \cup \mathcal {M}(b))$ . In this case, there is $\mathcal {M}$ -definable g such that

  $$ \begin{align*}\mathcal{N} \models g(c) = \langle a, b \rangle.\end{align*} $$
  Let $X = \{ \langle x, y \rangle : \mathcal {M} \models g(f(\langle x, y \rangle )) = \langle x, y \rangle \}$ . Here we observe that $\mathcal {M} \models \forall n, m \in X (f(n) = f(m) \Longleftrightarrow n = m)$ ; that is, f is one to one on X.

In each of these cases, X is an infinite, $\mathcal {M}$ -definable, set and $\mathcal {N} \models \langle a, b \rangle \in X$ . Let us refer to an infinite, $\mathcal {M}$ -definable X such that $\langle a, b \rangle \in X^{\mathcal {N}}$ as large.

Given any set X, we define the pseudo-representation $\alpha _X : \mathbf {B}_2 \longrightarrow \operatorname {\mathrm {Eq}}(X)$ :

• • $\alpha _X(0)$ is trivial,

• • $(n, m) \in \alpha _X(a)$ iff $\pi _1(n) = \pi _1(m)$ ,

• • $(n, m) \in \alpha _X(b)$ iff $\pi _2(n) = \pi _2(m)$ , and

• • $\alpha _X(1)$ is discrete.

Notice that whenever f is an $\mathcal {M}$ -definable function, we can find $r \in \mathbf {B}_2$ and a large set X such that

$$\begin{align*}\mathcal{M} \models \forall n, m \in X (f(n) = f(m) \Longleftrightarrow (n, m) \in \alpha_X(r)).\end{align*}$$

We summarize the above as follows. Suppose $p(x) = \operatorname {\mathrm {tp}}(\langle a, b \rangle / \mathcal {M})$ and let f be an $\mathcal {M}$ -definable function. Then there is $\phi (x) \in \mathcal {L}(\mathcal {M})$ defining a “large” set X and $r \in \mathbf {B}_2$ such that $\phi (x) \in p(x)$ and

$$\begin{align*}\mathcal{M} \models \forall x, y [(\phi(x) \wedge \phi(y)) \Longrightarrow (f(x) = f(y) \Longleftrightarrow (x, y) \in \alpha_X(r))].\end{align*}$$

Examples like this one provide the motivation for the following definitions. They were first introduced by Schmerl in [Reference Schmerl21], and they have been refined over the years.

Using these definitions, let us examine Example 11 once more from the other direction. Let $\mathcal {M} \models \mathsf {PA}$ and $X = [M]^2 = \{ \langle x, y \rangle : x < y \}$ . Then the representation $\alpha : \mathbf {B}_2 \longrightarrow \operatorname {\mathrm {Eq}}(X)$ given in Example 11 is n-CPP for each $n \in \omega $ . To see this, first recall the canonical Ramsey theorem for pairs ( $\mathsf {CRT}^2$ ): for every $f : [\omega ]^2 \longrightarrow \omega $ , there is an infinite $X \subseteq \omega $ such that f is canonical on $[X]^2$ . That is, one of the following holds:

• • f is one to one on $[X]^2$ ,

• • f is constant on $[X]^2$ ,

• • for all $\langle x_1, y_1 \rangle , \langle x_2, y_2 \rangle \in [X]^2$ , $f(x_1, y_1) = f(x_2, y_2)$ if and only if $x_1 = x_2$ , or

• • for all $\langle x_1, y_1 \rangle , \langle x_2, y_2 \rangle \in [X]^2$ , $f(x_1, y_1) = f(x_2, y_2)$ if and only if $y_1 = y_2$ .

This result is due to Erdős and Rado [Reference Erdős and Rado5], and is a consequence of Ramsey’s theorem for 4-tuples. One can formalize this result in $\mathsf {PA}^*$ , so that if $\mathcal {M} \models \mathsf {PA}$ and $f : [M]^2 \longrightarrow M$ is $\mathcal {M}$ -definable, there is an $\mathcal {M}$ -definable, unbounded Y such that f is canonical on $[Y]^2$ . Notice, then, that for such a set Y, $\alpha | [Y]^2 \cong \alpha $ .

Clearly, $\alpha $ is $0$ -CPP. Moreover, if $\alpha $ is n-CPP, then by $\mathsf {CRT}^2$ , for each $\Theta \in \operatorname {\mathrm {Eq}}(X)$ , there is $Y \subseteq X$ such that $\alpha \cong \alpha | Y$ and $\Theta \cap Y^2$ is canonical for $\alpha | Y$ . Since $\alpha | Y \cong \alpha $ , then $\alpha | Y$ is n-CPP, and therefore $\alpha $ is $(n+1)$ -CPP.

Given this $\alpha $ , one can construct an elementary extension $\mathcal {N}$ of $\mathcal {M}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong \mathbf {B}_2$ . The idea is to construct a type $p(x)$ ensuring that, for each $\mathcal {M}$ -definable function f, there is some definable $Y \subseteq X$ such that the equivalence relation induced by f is canonical for $\alpha $ on Y, and that the defining formula for Y is in $p(x)$ .

To construct this type, we will construct an infinite descending sequence of “large” sets. Let $X_0 = [M]^2$ . Enumerate the $\mathcal {M}$ -definable equivalence relations $\Theta _0, \Theta _1, \ldots $ . Given $\alpha | X_i$ and $\Theta _i$ , we use $\mathsf {CRT}^2$ to find $X_{i+1} \subseteq X_i$ such that $\alpha | X_{i_1} \cong \alpha | X_i$ and $\Theta _i$ is canonical for $\alpha | X_{i+1}$ . Finally, we let $p(x)$ be the type

$$ \begin{align*}\{ \phi(x) \in \mathcal{L}(\mathcal{M}) : \text{there is } i \in \omega \text{ such that } \mathcal{M} \models \forall x (x \in X_i \rightarrow \phi(x)) \}.\end{align*} $$

We show that that $p(x)$ is a complete type. This is, essentially, due to the fact that each $\alpha | X_i$ is 0-CPP. That is, given $\phi (x) \in \mathcal {L}(\mathcal {M})$ , consider the equivalence relation $\Theta $ given by $(x, y) \in \Theta $ iff $\mathcal {M} \models \phi (x) \Longleftrightarrow \phi (y)$ . Let $\Theta = \Theta _i$ , and notice that since $\Theta $ is canonical for $\alpha | X_{i+1}$ and $\Theta $ has at most two equivalence classes, it must be the case that $\Theta \cap X_{i+1}^2$ is trivial.

Let c realize $p(x)$ . We show why $\operatorname {\mathrm {Lt}}(\mathcal {M}(c) / \mathcal {M}) \cong \mathbf {B}_2$ . Because the pairing function is one to one, there are a and b such that $\mathcal {M}(c) \models c = \langle a, b \rangle $ . We use the same names as in the lattice $\mathbf {B}_2$ (see Figure 1) suggestively. For each $d \in \mathcal {M}(c)$ , let f be an $\mathcal {M}$ -definable function such that $\mathcal {M}(c) \models f(c) = d$ , and let $\Theta $ be the equivalence relation induced by f. Then there is a simple argument that exactly one of the following must hold:

• • $\mathcal {M}(d) = \mathcal {M}$ ,

• • $\mathcal {M}(d) = \mathcal {M}(a)$ ,

• • $\mathcal {M}(d) = \mathcal {M}(b)$ , or

• • $\mathcal {M}(d) = \mathcal {M}(c)$ .

This is proved case by case by finding r and i such that $\Theta \cap X_i^2 = \alpha (r) \cap X_i^2$ (by canonicity). Moreover, it is clear that $\mathcal {M} \prec \mathcal {M}(a), \mathcal {M}(b) \prec \mathcal {M}(c)$ . One checks that $\mathcal {M}(a) \cap \mathcal {M}(b) = \mathcal {M}$ .

The definitions used above relativize to a model $\mathcal {M} \models \mathsf {PA}$ . Suppose $X \subseteq M$ is $\mathcal {M}$ -definable and $\alpha : L \longrightarrow \operatorname {\mathrm {Eq}}(X)$ is a representation. Then $\alpha $ is an $\mathcal {M}$ -representation if $\alpha $ is $\mathcal {M}$ -definable. If $X \in \operatorname {\mathrm {Def}}(\mathcal {M})$ , then by $\operatorname {\mathrm {Eq}}^{\mathcal {M}}(X)$ we mean the lattice of $\mathcal {M}$ -definable equivalence relations on X. Similarly, the notion of n-CPP representations formalizes in ${\mathcal {L}}_{\mathsf {PA}}$ as well; in such cases, one only considers representations over $\mathcal {M}$ -finite sets, and we quantify over the equivalence relations $\Theta \in \operatorname {\mathrm {Eq}}^{\mathcal {M}}(X)$ . That is, there is an ${\mathcal {L}}_{\mathsf {PA}}$ -formula $cpp_L(x)$ asserting that L has an ( $\mathcal {M}$ -finite) x-CPP representation.

In the construction of the type $p(x)$ above, the two important ingredients needed at each step are:

• • ensure that each $\alpha | X_i$ is $0$ -CPP, and

• • ensure that each $\Theta _i$ is canonical for $\alpha | X_{i+1}$ .

This observation naturally leads to the following definitions and results in [Reference Schmerl30] by James Schmerl, further refining the technique.

Returning to Example 11, we notice that if $\mathcal {C}$ is the collection of $\alpha | Y$ such that Y is infinite, $\mathcal {M}$ -definable and $\alpha | Y \cong \alpha $ , then $\mathcal {C}$ is an $\mathcal {M}$ -correct set of representations of $\mathbf {B}_2$ . Additionally, one observes that $\mathsf {PA} \vdash cpp_{\mathbf {B}_2}(n)$ for each $n \in \omega $ . If $\mathcal {M} \models \mathsf {PA}$ is nonstandard, by overspill there is a nonstandard c such that $\mathcal {M} \models cpp_{\mathbf {B}_2}(c)$ . Then the collection of all $\mathcal {M}$ -representations of $\mathbf {B}_2$ that are x-CPP for some nonstandard x is also $\mathcal {M}$ -correct.

6 Representations of Ranked Lattices

In this section, we extend the definition of $\mathcal {M}$ -correct sets of representations of a lattice to ranked lattices as in Section 2.2. Let us first consider Example 11 in the context of ranked lattices.

Let $\mathcal {M} \prec \mathcal {N}$ be such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong \mathbf {B}_2$ , and let $a, b \in N$ be such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) = \{ \mathcal {M}, \mathcal {M}(a), \mathcal {M}(b), \mathcal {M}(a, b) = \mathcal {N} \}$ (as we did previously, we use a and b suggestively to correspond with $a, b \in \mathbf {B_2}$ ). Because the rankset is linearly ordered, it must be the case that either $\mathcal {M}(a) \prec _{\text {cof}} \mathcal {N}$ or $\mathcal {M}(b) \prec _{\text {cof}} \mathcal {N}$ . Without loss of generality, assume that $\mathcal {M}(b) \prec _{\text {cof}} \mathcal {N}$ . Therefore, the possible ranksets of $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ are:

• • $ \{ \mathcal {N} \}$ (if $\mathcal {M} \prec _{\text {cof}} \mathcal {N}$ ),

• • $\{ \mathcal {M}, \mathcal {M}(a), \mathcal {N} \}$ (if $\mathcal {M} \prec _{\text {end}} \mathcal {M}(a) \prec _{\text {end}} \mathcal {N}$ ), or,

• • $\{ \mathcal {M}(a), \mathcal {N} \}$ (if $\mathcal {M} \prec _{\text {cof}} \mathcal {M}(a) \prec _{\text {end}} \mathcal {N}$ ).

To study an example of a mixed extension, we consider the case where $\mathcal {M} \prec _{\text {cof}} \mathcal {M}(a) \prec _{\text {end}} \mathcal {N}$ , and $\mathcal {M}(b) \prec _{\text {cof}} \mathcal {N}$ . Recall that we referred to a set X as large if it is infinite, $\mathcal {M}$ -definable, and $\langle a, b \rangle \in X^{\mathcal {N}}$ . We look for properties to motivate a notion of “largeness” in a mixed extension.

Let $X = \{ \langle x, y \rangle : x < y \}$ and $\alpha _X$ be as defined in Example 11. That is, $\alpha _X : \mathbf {B_2} \to \operatorname {\mathrm {Eq}}(A)$ is defined so that $\alpha _X(a)$ is the equivalence relation induced by $\pi _1$ (the projection onto the first coordinate, i.e., $\langle x, y \rangle \mapsto x$ ), and $\alpha _X(b)$ is the equivalence relation induced by $\pi _2$ (projection onto the second coordinate). Then there is an infinite, $\mathcal {M}$ -definable $Y \subseteq A$ such that, letting $\alpha _Y$ be $\alpha _X | Y$ :

1. (1) There is a bounded set of representatives of the collection of all $\alpha _Y(a)$ -classes.

2. (2) There is an unbounded $\alpha _Y(a)$ -class (that is, a class which contains unboundedly many $\alpha _Y(1)$ -classes).

3. (3) Every $\alpha _Y(b)$ -class is $\mathcal {M}$ -finite.

To see these, notice that since $\mathcal {M} \prec _{\text {cof}} \mathcal {M}(a)$ , then there is $m \in M$ such that $\mathcal {M} \models a < m$ . Let $Y = \{ \langle x, y \rangle : x < m$ and $x < y \}$ . The following statements are easily verified:

• • There are (exactly) $m \alpha _Y(a)$ -classes (one for each $x < m$ ),

• • each $\alpha _Y(a)$ -class is unbounded, and,

• • each $\alpha _Y(b)$ -class has at most m elements.

Moreover, since $\mathcal {N} \models a < m$ and $a < b$ , then $\mathcal {N} \models \langle a, b \rangle \in Y^{\mathcal {N}}$ . Similarly to Example 11, if we define a set Y to be large if it is $\mathcal {M}$ -definable, satisfies properties $(1)-(3)$ and $\mathcal {N} \models \langle a, b \rangle \in Y^{\mathcal {N}}$ , then whenever Y is large and $\Theta \in \operatorname {\mathrm {Eq}}^{\mathcal {M}}(Y)$ , there is large $Z \subseteq Y$ such that $\Theta $ is canonical for $\alpha _Z$ .

We point out here some specific features of this representation that follow from properties (1)–(3). These features, it turns out, need to be present for any representation of the ranked lattice $(\mathbf {B_2}, \rho )$ , where the rankset of $\rho $ is $\{ a, 1 \}$ . First, $0 < a = \rho (0)$ . In every representation, $\alpha (0)$ is trivial. In this case, notice that, in a sense, the lone $\alpha _Y(0)$ -class (Y) splits into boundedly many $\alpha _Y(a)$ -classes; we will make this notion more precise in the below definition. It is easy to see that each $\alpha _Y(a)$ -class is of the form $\{ \langle x, y \rangle : x < y \}$ for some fixed $x \in M$ such that $\mathcal {M} \models x < m$ and that Y is the union of all of these classes.

Secondly, $0 < b$ but $b \not < \rho (0)$ . Notice now that Y is not the union of an $\mathcal {M}$ -bounded set of $\alpha _Y(b)$ -classes. Again, we can see this because each $\alpha _Y(b)$ -class is of the form $\{ \langle x, y \rangle : x < y \}$ for some fixed $y \in M$ .

Lastly, $b < 1 = \rho (b)$ ; again, see that each $\alpha _Y(b)$ -class splits into boundedly many $\alpha _Y(1)$ -classes; in other words, each $\alpha _Y(b)$ -class is $\mathcal {M}$ -finite.

Notice that in the above example, whenever $X \subseteq A$ is large, $\alpha _X$ is an $\mathcal {M}$ -representation of $(\mathbf {B_2}, \rho )$ , where $\rho $ is the ranking whose rankset is $\{ a, 1 \}$ .

We turn now to an example of an $\mathcal {M}$ -correct set of representations of $\mathbf {M_3}$ (see Figure 1). First we define a representation $\alpha : \mathbf {M_3} \to \operatorname {\mathrm {Eq}}(3)$ , where $3$ is the set $\{ 0, 1, 2 \}$ . Define this representation as follows:

• • the equivalence classes of $\alpha (a)$ are $\{0 \}$ and $\{ 1, 2 \}$ ,

• • the equivalence classes of $\alpha (b)$ are $\{ 0, 2 \}$ and $\{ 1 \}$ , and,

• • the equivalence classes of $\alpha (c)$ are $\{ 0, 1 \}$ and $\{ 2 \}$ .

Let $\mathcal {M}$ be a countable, nonstandard model and $m \in M$ (standard or nonstandard). Let $3^m$ refer to the set of (codes of) $\mathcal {M}$ -finite sequences s whose length is m and, for each $i < m$ , $(s)_i \in \{ 0, 1, 2 \}$ . Define $\alpha ^m : \mathbf {M_3} \to \operatorname {\mathrm {Eq}}(3^m)$ by letting $(s, t) \in \alpha ^m(r)$ if and only if $((s)_i, (t)_i) \in \alpha (r)$ for each $i < m$ . Notice that each of these representations is a representation of $(\mathbf {M_3}, \rho )$ where $\rho (r) = 1$ for each $r \in \mathbf {M_3}$ (that is, there are $\mathcal {M}$ -boundedly many $\alpha ^m(a)$ classes, each one is $\mathcal {M}$ -bounded, etc).

It turns out that the set of $\alpha ^m$ when m is nonstandard forms an $\mathcal {M}$ -correct set of representations of $(\mathbf {M_3}, \rho )$ . This is not obvious: one appeals to a generalization of the Hales–Jewett theorem due to Prömel and Voigt. In fact, this phenomenon can be generalized to any finite lattice L which can be represented as a congruence lattice of a finite algebra.

7 Diversity

The early results of Gaifman and Mills mentioned in Section 3 relied heavily on applications of minimal and end-extensional types. For a given $\mathcal {M}$ , if $\mathcal {N}$ is generated over $\mathcal {M}$ by a set A of elements realizing the same minimal ${\mathcal {L}}(\mathcal {M})$ -type, then $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is isomorphic to the Boolean algebra of subsets of A and the isomorphism type over $\mathcal {M}$ of each model in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is determined by the cardinality of its set of generators. In particular, if A is finite of cardinality n, then there are exactly $n+1$ isomorphism types of models in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ . If $\mathcal {N}$ is generated over $\mathcal {M}$ by a finite set of elements realizing mutually independent minimal types, then no pair of distinct models in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ are isomorphic.

In [Reference Schmerl23] Schmerl asked if there is more that can be said about the diversity of isomorphism types in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ . He called a model diverse if no two of its elementary submodels are isomorphic, and called an extension $\mathcal {N}$ of $\mathcal {M}$ diverse if no two models in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ are isomorphic over $\mathcal {M}$ .

In [Reference Schmerl23], Schmerl observes that $\mathcal {M}$ is diverse if and only if no two distinct elements have the same type. For such structures (for any language) Ali Enayat coined the name Leibnizian. His article [Reference Enayat4] is devoted to Leibnizian models of set theory.

All results in the rest of this section are from [Reference Schmerl23]. Schmerl notes that the first theorem suggests that constructing models that are not diverse is more difficult than constructing diverse ones.

Because a model is diverse just in case it is a diverse extension of its prime elementary submodel, (1) above is an easy consequence of the second. The proof of (2) involves the full power of the CPP-representations theory, invoking at one point a canonical partition theorem of Prömel and Voigt (see [Reference Kossak and Schmerl13, p. 118] for the statement of the theorem).

If E is an equivalence relation on a lattice L, then $(L,E)$ is called an equivalenced lattice. By $\operatorname {\mathrm {Lt}}^+(\mathcal {M})$ we denote $(\operatorname {\mathrm {Lt}}(\mathcal {N}), E)$ , where E is the isomorphism relation, and $\operatorname {\mathrm {Lt}}^+(\mathcal {N} / \mathcal {M})$ is $(\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}), E)$ , where E is the isomorphism relation for the isomorphisms that fix M pointwise. With this notation, the basic lattice problem gets generalized to

Right from the start one can see that some equivalenced lattices cannot be represented as substructure and interstructure lattices for obvious reasons. For example if L is $\mathbf {N_5}$ and $(b,c)\in E$ (Figure 2), then, as Schmerl writes: “it would not be at all reasonable to expect such models.” This leads to the definition of reasonable equivalenced lattice.

Before stating the definition, let us observe that each model of the form $\mathcal {M}(a)$ is rigid over $\mathcal {M}$ . This is a consequence of Ehrenfeucht’s lemma [Reference Ehrenfeucht3] (see [Reference Kossak and Schmerl13, Theorem 1.7.2]), which says that for all $b\in \mathcal {M}(a)$ , if $\operatorname {\mathrm {tp}}(a/M)=\operatorname {\mathrm {tp}}(b/M)$ then $a=b$ . It follows that if $\mathcal {M}(a_1)$ and $\mathcal {M}(a_2)$ in $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ are isomorphic over $\mathcal {M}$ and $\operatorname {\mathrm {tp}}(a_1/M)=\operatorname {\mathrm {tp}}(a_2/M)$ , then there is a unique isomorphism $F:\mathcal {M}(a_1)\longrightarrow \mathcal {M}(a_2)$ such that $F(a_1)=a_2$ .

If $(L,E)$ is a finite equivalenced lattice and $F:L\longrightarrow \operatorname {\mathrm {Lt}}^+(\mathcal {N} / \mathcal {M})$ is an isomorphism, then we can define a linear order $\lhd $ of L as follows. For each $r\in L$ select a generator $a_r$ of $F(r)$ over $\mathcal {M}$ so that for all r and s, if $(r,s)\in E$ , then $\operatorname {\mathrm {tp}}(a_r/M)=\operatorname {\mathrm {tp}}(a_s/M)$ and define $r\lhd s$ iff $a_r<a_s$ .

Schmerl calls an equivalenced lattice $(L,E)$ reasonable if there is a linear ordering $\lhd $ on L such that whenever $(a,b)\in E$ and I and J are the principal ideals of L generated by a and b respectively, then there is an isomorphism $f:(I,\lhd \cap I^2)\longrightarrow (J,\lhd \cap J^2)$ such that $(x,f(x))\in E$ for all $x\in I$ . One can directly check that if $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M})$ is finite, then $\operatorname {\mathrm {Lt}}^+(\mathcal {N} / \mathcal {M})$ is reasonable.

The definition given above is from the later Schmerl’s paper [Reference Schmerl25]. Under a less restrictive definition given in [Reference Schmerl23], Schmerl proves that for every reasonable equivalenced Boolean lattice $(\mathbf {B_n},E)$ , every nonstandard model $\mathcal {M}$ has a cofinal extension such that $\operatorname {\mathrm {Lt}}^+(\mathcal {N} / \mathcal {M})$ is isomorphic to $(\mathbf {B_n},E)$ . In [Reference Schmerl25] this is generalized to: under the revised definition given above, for every reasonable equivalenced distributive lattice $(L,E)$ , every nonstandard model $\mathcal {M}$ has a cofinal extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}^+(\mathcal {N} / \mathcal {M})$ is isomorphic to $(L,E)$ .

Among many open problems about diversity, this is probably the simplest:

8 Coded sets and distributive lattices

Recall that if $\mathcal {N}$ is an end extension of $\mathcal {M}$ , then $\operatorname {\mathrm {Cod}}(\mathcal {N} / \mathcal {M})$ is $\{ X \cap M : X \in \operatorname {\mathrm {Def}}(\mathcal {N}) \}$ . We referred to this as the family of coded sets in the extension. Schmerl [Reference Schmerl28] characterized exactly which families of subsets of a model of $\mathsf {PA}$ (of arbitrary cardinality) can appear as $\operatorname {\mathrm {Cod}}(\mathcal {N} / \mathcal {M})$ when $\mathcal {N}$ is a minimal elementary end extension of $\mathcal {M}$ ; i.e., an extension where $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong \mathbf {2}$ .

Previously, Schmerl [Reference Schmerl27] characterized the families of sets that can appear as $\operatorname {\mathrm {Cod}}(\mathcal {N} / \mathcal {M})$ in any countably generated elementary end extension $\mathcal {N}$ of a model $\mathcal {M}$ , so this result completes the picture for minimal extensions.

A simple constructionFootnote ⁴ shows that the same characterization of those coded sets holds for any finite distributive lattice D. That is:

Before we describe Schmerl’s proof of this result, we need the following facts about finite distributive lattices (see [Reference Kossak and Schmerl13, Section 4.3]). Let L be a lattice and $a \in L$ . The a-doubling extension of L is the sublattice $L^\prime $ of $L \times \mathbf {2}$ (ordered lexicographically; i.e., $(r, i) \leq (s, j)$ iff $r \leq s$ and $i \leq j$ ) defined as $\{ (r, i) \in L \times \mathbf {2} : i = 0$ or $r \geq a \}$ . [Reference Kossak and Schmerl13, Theorem 4.3.6] states that a finite lattice L is distributive if and only if there is sequence $L_0, \ldots , L_n$ of lattices such that $L_0$ is the one-element lattice, $L_n \cong L$ , and each $L_{i+1}$ is a doubling extension of $L_i$ .

Note that if $\mathcal {M}$ is countable and $\mathfrak {X} = \operatorname {\mathrm {Def}}(\mathcal {M})$ , the conclusion to (1) holds since every countable model has conservative minimal elementary end extensions. Since the pentagon lattice $\mathbf {N}_5$ cannot be realized as the interstructure lattice of a conservative end extension, we do not have the same characterization for non-distributive lattices.

9 Countable recursively saturated models

Up to this point, this survey was about the the problem of finding, for a given lattice L, a substructure or interstructure lattice representation of L with or without some additional properties. In this section we will briefly discuss a dual problem for a particular class of models. Given a countable recursively saturated model, what can we say about its substructure lattice?

A model $\mathcal {M}$ is recursively saturated if it is saturated with the respect to computable types with finite numbers of parameters. The standard system of a model $\mathcal {M}$ , $\operatorname {\mathrm {SSy}}(\mathcal {M})$ , is the set of standard parts of the definable subsets of $\mathcal {M}$ , i.e., $\operatorname {\mathrm {SSy}}(\mathcal {M})=\operatorname {\mathrm {Cod}}(\mathcal {M}/\mathbb N)$ , where $\mathbb N$ is the standard model. It is not difficult to prove that any two countable recursively saturated models are isomorphic if and only if they are elementarily equivalent and they have the same standard system.

For the rest of this section, let $\mathcal {M}$ be countable and recursively saturated.

The lattice $\operatorname {\mathrm {Lt}}(\mathcal {M})$ is immense. If the domain of a model $\mathcal {K}$ in $\operatorname {\mathrm {Lt}}(\mathcal {M})$ is an initial segment of M we call $\mathcal {K}$ an elementary cut. Henryk Kotlarski proved that the set of elementary cuts of $\mathcal {M}$ ordered by inclusion is isomorphic to $2^\omega $ with the lexicographic ordering. Moreover, he proved that the set of elementary cuts that are recursively saturated is uncountable, dense, and is closed under infinite unions but not under infinite intersections [Reference Kotlarski15]. All recursively saturated elementary cuts have the same standard system; hence, they are isomorphic to one another. Yet, there are continuum many first-order theories of pairs $(\mathcal {M}, K)$ , where $\mathcal {K}$ is a recursively saturated elementary cut [Reference Smoryński31].

An elementary cut of $\mathcal {M}$ is not recursively saturated if and only if it is a closure under initial segment of the Skolem closure of single element of M. Every recursively saturated model realizes countably many mutually independent minimal types. It follows that there are countably many isomorphism types of elementary cuts that are not recursively saturated. Moreover, each cut that is not recursively saturated, except for the closure under initial segment of $\operatorname {\mathrm {Scl}}(0)$ , has countably many automorphic images; hence the isomorphism relation of $\operatorname {\mathrm {Lt}}(\mathcal {M})$ restricted to such cuts has countably many countable equivalence classes.

Elementary cuts are linearly ordered by inclusion; hence they form a distributive sublattice of $\operatorname {\mathrm {Lt}}(\mathcal {M})$ . To show that $\operatorname {\mathrm {Lt}}(\mathcal {M})$ is not distributive we will use some facts about cofinal extensions.

In [Reference Schmerl24], Schmerl calls the extension $\mathcal {M}\prec \mathcal {N}$ almost minimal if $\mathcal {N}$ is an end extension and for every $\mathcal {K}$ , if $\mathcal {M}\prec \mathcal {K}\prec \mathcal {N}$ , then $\mathcal {K}{\prec _{\mathsf {cof}}}\mathcal {N}$ . For a lattice L, ${\mathbf 2}\oplus L$ is the extension of L obtained by adding with a new 0 element appended below ${\mathbf 0}_L$ . By the Blass condition, if $\mathcal {N}$ is an almost minimal extension of $\mathcal {K}$ and $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {K})$ is finite, then $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {L})\cong {\mathbf 2}\oplus L$ for some finite lattice L. The following is an abridged version of [Reference Schmerl24, Corollary 3.3].

For our discussion here it is important that if $\mathcal {N}$ is an almost minimal extension of a nonstandard $\mathcal {K}$ then $\operatorname {\mathrm {SSy}}(\mathcal {K})=\operatorname {\mathrm {SSy}}(\mathcal {N})$ . In particular, if $\mathcal {K}$ and $\mathcal {N}$ are countable and recursively saturated, then $\mathcal {K}\cong \mathcal {N}$ , which shows that ${\mathbf 2}\oplus L$ in (2) embeds into $\operatorname {\mathrm {Lt}}(\mathcal {K})$ .

We are going back to our countable recursively saturated model $\mathcal {M}$ . Let S be an inductive partial satisfaction class on $\mathcal {M}$ (see [Reference Kossak and Schmerl13, Definition 1.9.1]) and let $\mathcal {M}^*$ be $(\mathcal {M},S)$ . Let L be a finite lattice satisfying (1) in the $\mathsf {PA}^*$ version of Theorem 22, i.e., for $\mathcal {K}=\mathcal {M}^*$ , and let $\mathcal {N}^*$ be an almost minimal extension of $\mathcal {M}^*$ given by (2). By the remarks following the theorem, we get that ${\mathbf 2}\oplus L$ embeds into $\operatorname {\mathrm {Lt}}(\mathcal {N}^*)$ , hence it also embeds into $\operatorname {\mathrm {Lt}}(\mathcal {N})$ . Applying this to $L=\mathbf {M_3}$ , we get the following corollary.

It seems that the argument given above to prove Corollary 23 is an overkill. More directly, one can construct a type $p(x) \in \operatorname {\mathrm {SSy}}(\mathcal {M})$ , formalizing [Reference Kossak and Schmerl13, Theorem 4.5.21], such that if $a \in M$ realizes $p(x)$ , then $\operatorname {\mathrm {Lt}}(\operatorname {\mathrm {Scl}}(a)) \cong \mathbf {2} \oplus \mathbf {M_3}$ .

Much more can be said about cofinal submodels of $\mathcal {M}$ . Here is a sample. It follows from [Reference Kossak and Schmerl14, Theorem 7.1] that there is a set $\mathcal C$ of continuum many cofinal submodels of $\mathcal {M}$ such that for all $\mathcal {K}\in \mathcal C$ :

• • $\mathcal {K}$ is isomorphic to $\mathcal {M}$ ;

• • $\operatorname {\mathrm {Lt}}(\mathcal {M}/\mathcal {K})$ is the three-element lattice $\mathbf 3$ ;

• • for each pair of distinct $\mathcal {K}_1$ , $\mathcal {K}_2$ in $\mathcal C$ , $\operatorname {\mathrm {Th}}(\mathcal {M},K_1)\not =\operatorname {\mathrm {Th}}(\mathcal {M},K_2)$ .

In the recent paper [Reference Schmerl29], after much work, Schmerl improves this by replacing $\mathbf 3$ by $\mathbf 2$ , i.e., for each $\mathcal {K}$ , $\mathcal {M}$ is a minimal extension of $\mathcal {K}$ .

At the end of [Reference Kotlarski15], Kotlarski posed a general problem to describe the structure of $\operatorname {\mathrm {Lt}}(\mathcal {M})$ for countable recursively saturated $\mathcal {M}$ . In particular, he asked whether $\operatorname {\mathrm {Lt}}(\mathcal {M})$ depends on $\mathcal {M}$ .

A partial answer to Kotlarski’s question is given in [Reference Kossak and Schmerl11, Section 5]. It solves the problem for arithmetically saturated models. A recursively saturated model of $\mathsf {PA}$ is arithmetically saturated if its standard system is closed under arithmetic comprehension. It is shown in [Reference Kossak and Schmerl11] that if $\mathcal {M}$ and $\mathcal {N}$ are countable arithmetically saturated models of the same completion of $\mathsf {PA}$ , then $\mathcal {M}\cong \mathcal {N}$ if and only if $\operatorname {\mathrm {Lt}}(\mathcal {M})\cong \operatorname {\mathrm {Lt}}(\mathcal {N})$ . For the proof, Schmerl introduced a family of countably infinite, distributive lattices $D(X)$ , one for each set of natural numbers X, such that:

1. (1) if X and Y are distinct then $D(X)$ and $D(Y)$ are not isomorphic;

2. (2) if $\mathcal {M}$ is arithmetically saturated and there is $b\in M$ such that $D(X)\cong \operatorname {\mathrm {Lt}}(\operatorname {\mathrm {Scl}}(b))$ , then $X\in \operatorname {\mathrm {SSy}}(\mathcal {M})$ ;

3. (3) if $\mathcal {M}$ is recursively saturated and X is in the standard system of $\mathcal {M}$ , then there is $b\in M$ such that $D(X)\cong \operatorname {\mathrm {Lt}}(\operatorname {\mathrm {Scl}}(b))$ .

This proves the following theorem.

For arithmetically saturated models, (2) and (3) above could be stated as an equivalence. The reason for their separation is that while the proof of (2) is relatively easy, it seems to require the full strength of arithmetic saturation. The fact (3) above holds for all recursively saturated models, but its proof heavily depends on the methods developed by Schmerl in [Reference Schmerl21] and [Reference Schmerl22] and is not easy. It is an open question whether Theorem 24 holds for all recursively saturated models.

In another direction, it is observed in [Reference Kossak and Schmerl14, Lemma 7.2] that for all $\mathcal {N}$ and $\mathcal {K}$ , if $\mathcal {K}{\prec _{\mathsf {cof}}}\mathcal {N}$ , then $\operatorname {\mathrm {Lt}}_0(\mathcal {N}/\mathcal {K})$ is interpretable in $(\mathcal {N},K)$ . This follows from the fact that cofinal Skolem closures over $\mathcal {K}$ of single elements of N have a particularly simple definition. For all a, b in N, $a\in \mathcal {K}(b)$ if and only if $a=(u)_b$ for some $u\in \mathcal {K}$ .Footnote ⁵ Let $m\in K$ be such that $b<m$ and suppose that for a Skolem term $t(x)$ , $a=t(b)$ . Let $u\in K$ be such that for all $x<m$ , $(u)_x=~t(x)$ . Then $(u)_b=a$ . This shows that the relation $\{\langle x, y \rangle :\mathcal {K}(x)\preccurlyeq \mathcal {K}(y)\}$ is definable in $(\mathcal {N},K)$ . It follows that if for $i=1,2$ , $\mathcal {K}_i{\prec _{\mathsf {cof}}}\mathcal {N}_i$ , and $(\mathcal {N}_1,{K}_1)$ and $(\mathcal {N}_2,K_2)$ are elementarily equivalent, then $\operatorname {\mathrm {Lt}}_0(\mathcal {N}_1/{K}_1)$ and $\operatorname {\mathrm {Lt}}_0(\mathcal {N}_2/K_2)$ are elementarily equivalent, and it was asked in [Reference Kossak and Schmerl14] if in this statement $\operatorname {\mathrm {Lt}}_0$ can be replaced by $\operatorname {\mathrm {Lt}}$ . It turns out that it can not. A counterexample, in which $\operatorname {\mathrm {Lt}}_0(\mathcal {N}_1,\mathcal {K}_1)$ is an $(\omega +1)$ -chain and $(\mathcal {N}_2,\mathcal {K}_2)$ is a recursively saturated pair elementarily equivalent to $(\mathcal {N}_1, {K}_1)$ , is given in [Reference Schmerl24].

It follows from Theorem 24 and the main result of [Reference Kossak and Schmerl12] that if $\mathcal {M}$ and $\mathcal {N}$ are countable arithmetically saturated models of $\mathsf {PA}$ , then

(*) $$ \begin{align} \operatorname{\mathrm{Lt}}(\mathcal{M})\cong\operatorname{\mathrm{Lt}}(\mathcal{N}) \text{ if and only if }\operatorname{\mathrm{Aut}}(\mathcal{M})\cong\operatorname{\mathrm{Aut}}(\mathcal{N}). \end{align} $$

In the proof of Theorem 24, it is shown that the left part of the equivalence in $(*)$ is equivalent to $\operatorname {\mathrm {SSy}}(\mathcal {M})=\operatorname {\mathrm {SSy}}({N})$ , and in the proof of the main theorem of [Reference Kossak and Schmerl12] the corresponding equivalence for the automorphism groups is shown to hold for the right part of $(*)$ . This leads to the following problem.

10 Open Questions

There are many questions which remain open about the lattice problem. The following selection is due to Schmerl via private communication. All relevant definitions can be found in [Reference Kossak and Schmerl13, Chapter 4].

1. (1) Is every finite lattice L which can appear as an interstructure lattice the congruence lattice of some finite algebra? That is, if L is a finite lattice for which there are $\mathcal {M} \prec \mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong L$ , is L a congruence lattice of a finite algebra?

2. (2) Is there a finite lattice L for which there are countable, nonstandard $\mathcal {M}_0$ and $\mathcal {M}_1$ for which there is $\mathcal {N}_0 \succ \mathcal {M}_0$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N}_0 / \mathcal {M}_0) \cong L$ , but for no $\mathcal {N}_1 \succ \mathcal {M}_1$ is $\operatorname {\mathrm {Lt}}(\mathcal {N}_1 / \mathcal {M}_1) \cong L$ ?

3. (3) It is known that if L is a finite lattice that is the congruence lattice of a finite algebra, then so is its dual $L^d$ . Does the same result hold for finite lattices L such that there are $\mathcal {M} \prec \mathcal {N}$ where $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong L$ ? That is, if L is a finite interstructure lattice, is its dual also an interstructure lattice?

4. (4) Every finite lattice in the variety generated by $\mathbf {M_3}$ is the congruence lattice of a finite algebra. For every $\aleph _0$ -algebraic lattice L in this variety and every countable, nonstandard $\mathcal {M}$ , is there $\mathcal {N} \succ \mathcal {M}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong L$ ?

5. (5) For countable $\mathcal {M}$ , what are the possible $\mathfrak {X} \subseteq \mathcal {P}(\mathcal {M})$ for which there is an elementary end extension $\mathcal {N}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N} / \mathcal {M}) \cong \mathbf {N_5}$ and $\operatorname {\mathrm {Cod}}(\mathcal {N} / \mathcal {M}) = \mathfrak {X}$ ?

6. (6) Is the set of finite lattices for which given (some, all, or a specific) countable, nonstandard $\mathcal {M}$ , there is $\mathcal {N} \succ \mathcal {M}$ such that $\operatorname {\mathrm {Lt}}(\mathcal {N}/\mathcal {M}) \cong L$ computable?