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 on a set is an injection (where Eq(A) is the set of equivalence relations on the set A), such that for each , is the trivial relation and is the discrete relation . Given and a set , the function is defined by for each . Two representations of the same lattice, are called isomorphic if there is a bijection respecting the equivalence relations; that is, for each and , .
The Lattice
The lattice is the Boolean Algebra on a 2 element set: (with and ). Gaifman proved that every model has an elementary end extension such that the interstructure lattice is isomorphic to (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 .
Given a model , there is a particularly simple representation on the set of pairs of elements of , denoted . This representation is defined by letting be the equivalence relation determined by equality on the first coordinate, and be the equivalence relation determined by equality on the second coordinate. This representation is definable in , 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 on , there is a definable subset of such that is either discrete, trivial, or , and . The underlying combinatorics here is a generalization of Ramsey’s theorem for pairs, first proved by Erdős and Rado: given any equivalence relation on , there is an infinite set such that is either discrete, trivial, or . Note that this is just an infinite set of numbers, not of pairs.
This is similar to the key lemma needed when constructing minimal extensions. If is a model, a minimal extension is an elementary extension such that there are no proper intermediate elementary structures (that is, if , then or ). In that case, we consider any infinite definable set and show that for any definable equivalence relation on , there is an infinite definable such that that 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 on which is discrete or trivial can be expressed in the language of first order arithmetic:
.
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 such that either (i) for all , , (ii) for all , if and only if , (iii) for all , if and only if , or (iv) for all , if and only if . 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 . This quantifier extends the language of first order logic by binding two variables. The intended interpretation of is “There is an infinite set such that for all , 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).