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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s