substructure lattices

I will be speaking at the Models of Peano Arithmetic seminar on Wednesday, September 21, 2016 on “Ramsey Quantifiers”. The abstract is listed on the NYLogic site, but for context I wanted to provide some thoughts on why I am digging up this older topic.

This theory piqued my interest while I was studying the lattice problem for models of PA. In studying this problem, it became apparent that certain combinatorial properties of representations of lattices were important. Let me preface this by saying that much of this information is in The Structure of Models of Peano Arithmetic, by Kossak and Schmerl, in Chapter 4 on Substructure Lattices.

A representation of a lattice $L$ on a set $A$ is an injection $\alpha : L \to \textrm{Eq}(A)$ (where Eq(A) is the set of equivalence relations on the set A), such that for each $r, s \in L, \alpha(r \vee s) = \alpha(r) \wedge \alpha(s)$ , $\alpha(0)$ is the trivial relation and $\alpha(1)$ is the discrete relation . Given $\alpha : L \to \textrm{Eq}(A)$ and a set $B \subseteq A$ , the function $\alpha | B$ is defined by $(\alpha | B)(r) = \alpha(r) \cap B^2$ for each $r \in L$ . Two representations of the same lattice, $\alpha : L \to \textrm{Eq}(A), \beta : L \to \textrm{Eq}(B)$ are called isomorphic if there is a bijection $f : A \to B$ respecting the equivalence relations; that is, for each $r \in L$ and $x, y \in A$ , $(x, y) \in \alpha(r) \leftrightarrow (f(x), f(y)) \in \beta(r)$ .

The Lattice $B_2$

The lattice $B_2 = \{0, a, b, 1\}$ is the Boolean Algebra on a 2 element set: (with $0 < a < 1$ and $0 < b < 1$ ). Gaifman proved that every model $\mathcal{M} \models \textsf{PA}$ has an elementary end extension $\mathcal{N}$ such that the interstructure lattice $\textrm{Lt}(\mathcal{N} / \mathcal{M}) = \{ \mathcal{K} : \mathcal{M} \preceq \mathcal{K} \preceq \mathcal{N} \}$ is isomorphic to $B_2$ (in fact, Gaifman’s proof works for every finite Boolean algebra). But we can also form such an elementary extension by studying the appropriate representation of the lattice $B_2$ .

Given a model $\mathcal{M} \models \textsf{PA}$ , there is a particularly simple representation on the set of pairs of elements of $M$ , denoted $[M]^2$ . This representation is defined by letting $\alpha(a)$ be the equivalence relation determined by equality on the first coordinate, and $\alpha(b)$ be the equivalence relation determined by equality on the second coordinate. This representation is definable in $\mathcal{M}$ , by using the normal coding of pairs of numbers (Cantor’s pairing function) and the induced projection functions.

The key lemma we need to construct the elementary extension is that for any definable equivalence relation $\Theta$ on $[\mathcal{M}]^2$ , there is a definable subset $A$ of $[\mathcal{M}]^2$ such that $\Theta \cap A$ is either discrete, trivial, $\alpha(a) \cap A$ or $\alpha(b) \cap A$ , and $\alpha | A \cong \alpha$ . The underlying combinatorics here is a generalization of Ramsey’s theorem for pairs, first proved by Erdős and Rado: given any equivalence relation $\Theta$ on $[\mathcal{M}]^2$ , there is an infinite set $X \subseteq \mathcal{M}$ such that $\Theta \cap [X]^2$ is either discrete, trivial, $\alpha(a) \cap [X]^2$ or $\alpha(b) \cap [X]^2$ . Note that this $X$ is just an infinite set of numbers, not of pairs.

This is similar to the key lemma needed when constructing minimal extensions. If $\mathcal{M}$ is a model, a minimal extension $\mathcal{M} \prec \mathcal{N}$ is an elementary extension such that there are no proper intermediate elementary structures (that is, if $\mathcal{M} \preceq \mathcal{K} \preceq \mathcal{N}$ , then $\mathcal{M} = \mathcal{K}$ or $\mathcal{K} = \mathcal{N}$ ). In that case, we consider any infinite definable set $A$ and show that for any definable equivalence relation $\Theta$ on $A$ , there is an infinite definable $B \subseteq A$ such that that $\Theta \cap B^2$ is either discrete or trivial. The main difference between these two cases is the first order expressibility of these statements. Stating that there is an infinite subset $B \subseteq A$ on which $\Theta$ is discrete or trivial can be expressed in the language of first order arithmetic:

$[\exists x \in A \forall w \exists y \in A (y > w \wedge (x, y) \in \Theta)] \vee [\forall w \exists y > w (y \in A \wedge \forall x < y (x \in A \rightarrow (x, y) \not \in \Theta))]$ .

Even though it appears, at first, we want to say “There is an infinite set” where something holds (which would appear to be a second-order quantifier), we can state this in first order (because by “infinite” we really mean “unbounded”).

In the Erdős-Rado result, something appears to be significantly different, however. We must state: “there is an infinite set $X$ such that either (i) for all $x_1 < x_2, y_1 < y_2 \in X$ , $( (x_1, x_2), (y_1, y_2)) \in \Theta$ , (ii) for all $x_1 < x_2, y_1 < y_2 \in X$ , $( (x_1, x_2), (y_1, y_2)) \in \Theta$ if and only if $x_1 = y_1$ , (iii) for all $x_1 < x_2, y_1 < y_2 \in X$ , $( (x_1, x_2), (y_1, y_2)) \in \Theta$ if and only if $x_2 = y_2$ , or (iv) for all $x_1 < x_2, y_1 < y_2 \in X$ , $( (x_1, x_2), (y_1, y_2)) \in \Theta$ if and only if $(x_1, x_2) = (y_1, y_2)$ . In this case, we cannot replace the second-order quantifier with first order ones asserting unboundedness of some property, because we wish to quantify over pairs of elements from that (unbounded) set.

After thinking about this for awhile, my advisor mentioned a section in Chapter 10 of The Structure of Models of Peano Arithmetic, which discusses an extra quantifier called a “Ramsey quantifier”, denoted $Q^2$ . This quantifier extends the language of first order logic by binding two variables. The intended interpretation of $Q^2 x, y \phi(x, y)$ is “There is an infinite set $X$ such that for all $x \neq y \in X$ , $\phi(x, y)$ holds.” This is exactly the kind of extension to the language that I needed, and I hope to talk about some of the basic results in the theory of Peano Arithmetic in this augmented language (with induction for all formulas in the extended language).

diagram_transparent

I will be contributing a session at the ASL 2016 North American Annual Meeting, on Wednesday, May 25 at 4:45 PM.

Abstract: Simpson used arithmetic forcing to show that every countable model $\mathcal{M} \models \textsf{PA}$ has an expansion $(\mathcal{M}, X) \models \textsf{PA}^*$ that is pointwise definable. The natural question then is whether this method can be used to obtain expansions of (countable models) with the property that the definable elements of the expansion coincide with the definable elements of the original model. Enayat later showed that this is impossible. He proved that there are models with the property that every expansion upon adding a predicate for an undefinable class is pointwise definable. We call models with this property Enayat models. It is easy to iterate Enayat’s construction and obtain other models with this property. Elementary submodels of any Enayat model formed in this way are well-ordered by inclusion. I will present a construction of an Enayat model whose elementary substructures form an infinite descending chain.

Slides from this talk.

Athar Abdul-Quader

Mathematical Logic / Models of Arithmetic

Lattices and Coded Sets – AMS Spring Eastern Sectional Meeting

Ramsey Quantifiers – MOPA Seminar

The Lattice $B_2$

Enayat Models – ASL 2016