Ramsey Quantifiers – MOPA Seminar

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).

Athar Abdul-Quader

Mathematical Logic / Models of Arithmetic

Ramsey Quantifiers – MOPA Seminar

The Lattice $B_2$

Leave a Reply Cancel reply

The Lattice

Share this:

Like this:

Leave a Reply Cancel reply

The Lattice $B_2$