Introduction to the Keisler order

INTRODUCTION TO THE KEISLER ORDER
By KYLE GANNON
Abstract. In this paper, we introduce the basic definitions and concepts necessary to define the Keisler Order. We will prove the order is well-defined as well as the existence of a maximal class with respect to the order.
Contents
1. Introduction 1 
2. Notation and Basic Definitions 2 
3. Ultrapowers 3 
4. Saturation and Satisfaction 6 
5. An Early Application 7 
6. The Order 9 
7. Existence of a Maximal Class 10 Acknowledgments 12 
References 12
1. Introduction
The Keisler Order was first introduced by H. Jerome Keisler in 1967. Currently, this order is known to be a pre-order on (countable) first-order theories which, broadly speaking, ranks classes of theories by complexity. Stronger theorems have been proven for stable theories (e.g. the Keisler Order on stable theories is linear [5]), while the complete structure of the Keisler Order is still an open problem. The classification of first-order theories is both a classic and modern program in model theory. Shelah’s stability program, the most famous type of classification framework, organizes theories relative to the number of definable types over subsets of a model. While the stability program has had great success, the program also leaves unstable theories in some unclassifiable purgatory. Work on the Keisler Order has shed light on dividing lines between classes of unstable theories. Additionally, one of the major results in a paper by Malliaris and Shelah [4] shows that theories, which have the SOP2−property, are maximal. This result was important in proving p = t, the oldest open problem in cardinal invariants. We will begin with many definitions as well as examples to provide the reader with some intuition. We will leave most of the proofs which relate to the Keisler Order to the last two sections. The two big theorems we prove at the end can be found in Keisler’s original paper on the topic [3].
Date: AUGUST 29, 2014.
1
2 KYLE GANNON
2. Notation and Basic Definitions
This paper will assume at least one course in basic first-order model theory. However, in this section, we will go over some of the necessary terminology and theorems required to understand this paper. A language L = {f1,f2,...,R1,R2,...,c1,c2,..} is a collection of (n-ary) function, (n-ary) relation, and constant symbols (sometimes called non-logical symbols). Languages also contain logical symbols, i.e. ∧,∨,¬,→, equality, and parentheses, as well as (object-level quantification) ∀,∃. A formula in a language is simply a grammatically coherent string of logical symbols which may or may not have free variables (for instance, x = x or (∃x)(S(x) = ¯ y) where ¯ y is a tuple of free variables and x is bounded). A theory T is a set of logical sentences with symbols from some fixed language L. A complete theory is a maximally consistent set of sentences. A model, or a L−structure, is some set-sized mathematical object with an interpretation for each non-logical symbol in the language. 0 |=0 is a (semantic) binary relation between L-structures and sentences in the language L. We say a sentence ϕ is true in a model A by writing A |= ϕ. The following will be our notational habits. An arbitrary model will be denoted as A or B. Usually, we will denote indexing sets as I,J, and cardinals as α,β,κ. Every theory T will have a corresponding fixed language L where the size of the underlying language is at most countable. The underlying set of a model A is formally written as dom(A). However, we will usually write A for dom(A), B for dom(B), etc. The terms power and cardinality are interchangable. A set X has the finite intersection property if and only if any finite intersection of elements is not empty. If A is a set, then P(A) is the power set of A and Pℵ0(A) is the collection of all finite subsets of A. Finally, we have some more formal definitions and theorems which we will be referring to. Definition 2.1. Let A be an L-structure. We let X ⊂ A. Then, (A,X), sometimes written (A,x)x∈X, is a model (in the expanded language L ∪X) where we treat the elements of X as constant symbols. Formally, this is known as a diagram 1.
Definition 2.2. A collection of sentences, ∆, is said to be satisfiable if there exists a model A such that A |= ∆. ∆ is said to be finitely satisfiable if every finite subset of ∆ is satisfiable.
Theorem 2.3. (Completeness): A set of sentences ∆ is consistent if and only if it is satisfiable.
Theorem 2.4. (Compactness): A set of sentences ∆ is satisfiable if and only if it is finitely satisfiable. Definition 2.5. If A and B are two L−structures, we say that A is elementarily equivalent to B (written A ≡ B) if for any ϕ in L, we have A |= ϕ if any only if B |= ϕ. Definition 2.6. Let A, B be two L−structures. We say that A is isomorphic to B if there exists a bijection f : A → B such that f preserves functions, relations, and constant symbols.
1When X is some arbitrary subset of some fixed size α, we will sometimes just write (A,α) and L(α) for the expanded model and language respectively.
INTRODUCTION TO THE KEISLER ORDER 3
For a more detailed introduction, we refer the reader to the first few sections of any basic model theory text (e.g. Chang & Keisler [2]).
3. Ultrapowers
Ultrapower constructions are one of the two central concepts necessary to un–––derstanding the Keisler Order. However, before we can define ultrapowers, we have to first get an intuition for ultrafilters and ultraproducts.
Definition 3.1. Let I be an indexing set. We say that D is a filter over I if D is a non-empty subset of P(I) with the following properties: 1. If X ∈ D and Z ⊃ X, then Z ∈ D. 2. If X,Y ∈ D, then X ∩Y ∈ D. Furthermore, we call D an ultrafilter if for any X ⊆ I, we have (exclusively) either X ∈ D or I − X ∈ D. Intuitively, we can think of D as a mathematical object that makes decisions about which subsets of I are large. D thinks the entire set is large, any set containing a large set is large, and the intersection of any two large sets is large. Note, D may not think that the countable/uncountable intersection of large sets is large. We will see later that ultrafilters without the countable intersection property are valuable and are central to our study.
Definition 3.2. Let D be a filter over I. We say that D is a principal filter if there exists X ⊂ I such that D = {Y ⊆ I : X ⊂ Y}. We call any filter which is not principal a nonprincipal (or free) filter. Example 3.3. (Principal Ultrafilter): Let I = N and let D = {X ⊆ N : 3 ∈ X}. Then, D is a principal ultrafilter over I.
Example 3.4. (Nonprincipal Ultrafilter): It is provable that one cannot construct an example (since the existence of a nonprincipal ultrafilter is equivalent to a weak version of choice). There are models of ZF where there do not exist any nonprincipal ultrafilters. However, the constructions of these models of ZF require complex forcing arguments not suitable for this paper [1].
For the remainder of this paper, every ultrafilter will be a nonprincipal ultrafilter. Furthermore, we will assume the full power of ZFC and thus never worry about the existence of ultrafilters (in general). The next two facts follow quickly from the definitions and are left unproven.
Proposition 3.5. No free ultrafilter contains any finite sets.
Proposition 3.6. Let A be a collection of subsets of I such that A has the finite intersection property. Then A can be extended to an ultrafilter over I. Let I be an indexing set of cardinality α and let{A}i∈I be a collection of models.Let Qi∈I A be the cartesian product of these models. Note that the elements ofQ i∈I A can be seen as functions from I into {A}i∈I or as an α−termed sequences of elements where the ηth term (for η < α) is an element of Aη. If f,g are elements ofQi∈I Ai, we say that f is D−equivalent to g (written as f ≡D g) if and only if f and g agree on a large set. Formally, f ≡D g ⇐⇒ {i ∈ I : f(i) = g(i)}∈ D Proposition 3.7. If D is a filter, then ≡D is an equivalence relation overQi∈I Ai.
4 KYLE GANNON
Definition 3.8. (Ultraproduct): Let I be an indexing set and let D be an ultrafilter over I. An ultraproduct of L−structures is defined as, Y i∈I A/D = {fD : f ∈Y i∈I Ai} For notational purposes, we will always have our I’s fixed and so we will writeQ i∈I Ai/D asQD Ai. In some sense, ultraproducts are similar to quotient spaces in topology. We are simply taking elements in our Cartesian product and gluing them together. Now, the following theorem demonstrates the strength of ultraproducts in model theory.
Theorem 3.9. (Los’s Theorem): Let D be an ultrafilter over I. Then, for any f1,...,fn ∈QD Ai, we have that Y D Ai |= ϕ(f1,...,fn) ⇐⇒ {i ∈ I : Ai |= ϕ(f1(i),...,fn(i))}∈ D So what does this theorem actually mean? First of all, note that if each Ai agrees on some (first-order) sentences in L, thenQD Ai also agrees on that sentence. In fact, if D thinks some subset of I is large, and all the models of the large set agree (disagree) on some sentence, thenQD Ai also agrees (disagrees) on that sentence. Free ultraproducts can be thought of as averaging on an infinite set. They pick up on what is happening in general while forgetting about small perturbations and outliers. We will consider the following example to give an intuition on how ultraproducts work.
Example 3.10. First note that the axioms of an algebraically closed field are first-orderizable in the language L = {0,1,+,×}. We will denote ACF to mean algebraically closed field while ACFp will mean algebraically closed field of characteristic p. Let P denote the set of standard primes. Furthermore, let Ap |= ACFp and so each model, Ap is an algebraically closed field of characteristic p. Let D be a nonprincipal ultrafilter of P. Now, we consider the objectQD Ai. Note that since Ai |= ACF for all i ∈ P, it follows thatQD Ai |= ACF and soQD Ai is an algebraically closed field. We will now find this field’s characteristic. By proposition 3.5, there is no finite set in D. Since D is an ultrafilter, this means that D contains all cofinite sets. Define ϕi, for all i ∈N as follows: ϕi ≡¬(1 + 1 + 1... + 1 | {z } i = 0) For i ∈N, Aj |= ϕi for j 6= i. Hence, we know that ϕi is true on a cofinite subset of P. Therefore,QD Ai cannot have characteristic i for any i ∈ N 2. SinceQD Ai is a field and must have some characteristic, it has characteristic 0. Definition 3.11. (Ultrapower): If I is an indexing set and D is an ultrafilter over I, thenQD Ai is an ultrapower if for any i,j ∈ I, we have that Ai ∼ = Aj. Since the indexing of our models no longer provides a method of differentiation we will simply write ultrapowers asQD A when I is fixed. This construction, in relation to ultraproducts, might seem a little odd at first. We already know the exact set of first-order sentences thatQD A satisfies. The proof thatQD A ≡ A 2Recall that fields cannot have composite characteristic anyway.
INTRODUCTION TO THE KEISLER ORDER 5
is a trivial corollary to Los’s theorem. The following example begins to show how ultrapowers can be different from the models used to construct them. Example 3.12. Let A = (N;≤,S) where ≤ has its normal interpretation and S is interpreted as the unary successor function 3. We let I be countable and let D be a nonprincipal ultrafilter over I. Note that (N;≤,S) is well-ordered. We will show thatQD A is not. Consider the element f = (1,2,3,4,...) ∈QD A. Notice that for every m ∈ N, m ≤ f(i) is true on a cofinite set and as a result, true on a large set. Therefore, the element f is larger than every standard natural number. Furthermore, it is easy to show that N |= (∀x)(x 6= 0 → (∃y)(S(y) = x)). This statement simply reads: Every element not equal to 0 has a direct predecessor. Thus, we can find an infinite descending chain beginning with f. The chain begins like this: (1,2,3,4,5,...) (0,1,2,3,4,...) (0,0,1,2,3,...) . . . We know that this chain does not terminate after finitely many steps, since if it did, then f would be some standard natural number. SinceQD A has an infinite descending chain, we know thatQD A is not well ordered. Now, if you know some basic logic, you should be making a connection with the compactness theorem. Ultrapowers and ultraproducts are tools which apply the compactness theorem. However, while compactness simply proves that a certain model exists, ultrapowers and ultraproducts give us much more control over the models we are constructing. Finally, in this section, we will define regular ultrafilters. Definition 3.13. Let D be a nonprincipal ultrafilter over some infinite indexing set I. We say that D is a (β,α)−regular ultrafilter if there is a subset X of D such that 1. |X| = α. 2. For any subset Y of X such that |Y| = β, we have thatTY = ∅. We drop the (β,α) notation and just call an ultrafilter D regular if β = ω and α = |I|. We also call X a regular subset of D if the above properties holds for X. Since this is the type of ultrafilter we actually need for the definition of the Keisler Order, we will prove that D regular ultrafilters exist. Lemma 3.14. (Regular Ultrafilter Existence): For every infinite cardinal κ, there exists a regular ultrafilter over κ. Proof. Let Pℵ0(κ) be the set of all finite subsets of κ. Note that |Pℵ0(κ)| = κ. Let f : Pℵ0(κ) → κ be a bijection and for each β ∈ κ, define Yβ = {i ∈ I : β = f−1(i)}. Now, consider A = {Yβ : β ∈ κ}. It is clear that |A| = κ. Recall that if A has the finite intersection property, then A can be extended to an ultrafilter. Consider: n \ j=1 Yβj = n \ j=1 {i ∈ I : βj ∈ f−1(i)d} 3Note that S can be defined in the language {≤}. We have added S to our language to simplify our arguments.
6 KYLE GANNON
By definition, we have
= {i ∈ I : β1,...,βn ∈ f−1(i)}6= ∅ The inequality follows from the fact that f is a bijection from Pℵ0(κ) to κ. Therefore, A has the finite intersection property and may be extended into an ultrafilter. It should also be clear that the intersection of countable subsets of A are empty and so A is our regular subset of its ultrafilter extension.  
4. Saturation and Satisfaction
While ultrapowers are necessary for understanding the Keisler Order, this topic alone is not sufficient. Another key ingredient of the Keisler Order is saturation. This concept, along with satisfaction, will bring the Keisler Order into view. Definition 4.1. Let A be a model in a language L. Let X ⊆ A. We say that ρ is an n−type over X in A if 1. ρ is a collection of formulas in n free variables in the language L∪X (i.e. ρ is of the form ∪i∈I{ϕi(y1,...,yn)} where ϕi(y1,...,yn) are in L∪X). 2. For any finite subset ρ0 of ρ, there is some (c1,...,cn) ∈ A such that A |= ϕi(c1,...,cn) for all ϕi ∈ ρ0. We say that an n−type ρ is complete if and only if it is maximally consistent. Equivalently, ρ is a complete n−type if for any formula ψ(y1,...,yn) in n free variables, (exclusively) either ψ(y1,...,yn) ∈ ρ or ¬ψ(y1,...,yn) ∈ ρ. Note that every element of a model has a corresponding complete 1-type (over X ⊂ A). In fact, every fixed n−tuple in any model has a corresponding complete n−type (over X ⊂ A). To demonstrate this, consider the following: if we let (a1,...,an) be a tuple of elements in A, let ρ ≡{φ(y1,...,yn) : (A,x,a1,...,an)x∈X |= φ(a1,...,an)} . Definition 4.2. (Satisfaction of 1-Types): Let ρ be a complete 1−type in one free variable. We say that ρ is satisfied/realized in A if there exists an a in A such that (A,a) |= ϕ(a) for all ϕ(x) ∈ ρ. We let S1(X) be the collection of all (consistent) complete 1-types over X ⊂ A Remark 4.3. Note that the above definition can be clearly extended to n−types and has corresponding collections, Sn(X).
Definition 4.4. (κ - Saturation): Let κ be some infinite cardinal. We say that a structure A is κ−saturated if for every X ⊆ A with |X| < κ, all the types in S1(X) are realized in A. Proposition 4.5. If A is κ−saturated and |X| < κ, then every type in Sn(X) is realized in A.
Proposition 4.6. Not every theory has a saturated model in every cardinality.
Before we go any further with our definition building, we will give an indepth example.
INTRODUCTION TO THE KEISLER ORDER 7 Example 4.7. ((Q;<)): Let us consider Q in the language {<}. We will find that there does not exist an ℵ1−saturated model of size ℵβ for ℵ0 ≤ ℵβ < 2ℵ0. The problem here is that we have continuum many 1-types which are definable in L over Q. Better yet, we are showing that S1(Q) = 2ℵ0 4. Consider any two (distinct, irrational) real numberes, s and r. We will write ρr and ρs as their complete corresponding 1−types over Q. Without loss of generality, we assume that s < r. Since s 6= r and Q is dense inside the reals, we have that there exists q ∈Q such that (x < q) ∈ ρs and (x > q) ∈ ρr. Hence, every real number corresponds to a different (complete) 1-type over a countable subset of the model (where the countable subset is the entire model itself). Therefore, the ℵ1−saturated model is at least size 2ℵ0 (since |R| = 2ℵ0). However, (R;<) is not a ℵ1−saturated model of the theory of Th(Q,<). Let( D,<) be a ℵ1−saturated model. We will show that (D,<) realizes a type over Q that (R,<) does not realize. Consider the type ρξ = {x < q : q ∈ Q}∪{x > 0}. First note, that since the rationals are dense in themselves, no elements of Q realize this type. However, one can easily show that ρ is finitely satisfiable. By the compactness theorem, we note that ρξ is consistent. Therefore, it must be satisfied in our ℵ1−saturated model (since it is definable over a countable subset of our underlying set). Let a be the element of D which satisfies this type. Note that for any q ∈Q, we have that q < 0 or q > a. Suppose that r ∈R and r = a. Since the rationals are dense in the reals, then there must be some p ∈Q such that 0 < p < r. But this a contradiction. Hence, (R,<) is not ℵ1−saturated.
5. An Early Application
We have just defined a lot of new machinery, but it is probably still unclear how ultrapowers and saturation relate to one another. This section is dedicated to exhibiting the interaction of the two.
Definition 5.1. (Countably Incomplete Ultrafilter): An ultrafilter is said to be countably incomplete if there exists a subset X of D such that |X| = ℵ0 and TX = ∅. These ultrafilters are much weaker than regular filters, so our theorem will be very general. We are going to show that any ultrapower, using a countably incomplete ultrafilter, is ℵ1−saturated. However, we will need the following lemma first.
Lemma 5.2. Let D be a countably incomplete ultrafilter. Then, there exists a countable descending chain I = I0 ⊂ I1 ⊂ I2 ⊂ ..., such thatTn∈ω In = ∅. Proof. Since D is an ultrafilter, we know that I ∈ D. Since D is countably incomplete, we know that there exists a set X ⊂ D such that |X| = ℵ0 andTX = ∅. Let {Y1,...,Yn,...} be a well-ordering of the elements of X. Define
Jn =
n \ i=1
Yi
4We are actually showing that S1(Q) ≥ 2ℵ0. The other direction follows from the fact that there are at most 2ℵ0−many definable 1−types over a countable set in a countable language.
8 KYLE GANNON
Since D is closed under intersection, it is closed under finite intersection. Therefore, Jn ∈ D for all n < ω. Furthermore, it is clear that Jn ⊇ Jn+1 and that we have the following equality \ i∈ω Jn = ∅ We also know that for each Jn, there exists some Jm such that Jn ) Jm, for some m > n. If this was not the case, thenTi∈ω Ji = Jm. Now, we can choose a subsequence of {Ji}i∈ω such that Ji+1 is a proper subset of Ji for each i. By well-ordering this set in the obvious way, we have found the collection that we are looking for.   Theorem 5.3. Let L be countable and let D be a countably incomplete ultrafilter over some infinite set I. Then, for any collection {Ai}i∈I of L−structures, we have thatQD Ai is ℵ1−saturated. Proof. Let ∆(x) be a set of formulas (with one free variable) in the language L1 = L(ℵ0). It suffices to show that if each finite subset of ∆(x) is satisfied inQD Ai, then ∆(x) is realized inQD Ai. Suppose that each finite subset of ∆(x) is realized inQD Ai. Because L1 is countable, we know that ∆(x) is countable. Therefore, we can well order our elements of ∆(x) as follows; ∆(x) = {δ1(x),δ2(x),...} Since D is countably incomplete, we know that there exists a descending chain I = I0 ⊃ I1 ⊃ I2 ⊃ ... such thatTn∈ω In = ∅. Now, we let X0 = I0 and define Xn = In ∩{i ∈ I : Ai |= (∃x)(δ1 ∧...∧δn)} Recall that we assumed that every finite subset of ∆(x) is satisfied in QD Ai. Therefore, by Los’s Theorem, we have that {i ∈ I : Ai |= (∃x)(δ1∧...∧δn)} is large (hence, it is in D). Since In is also in D, we know by definition of a filter that Xn is in D for each n ∈N. Further note thatTn∈ω Xn = ∅ because of the following \ n∈ω Xn = \ n∈ω (In ∩{i ∈ I : Ai |= (∃x)(δ1 ∧...∧δn)}) = \ n∈ω (In)∩\ n∈ω ({i ∈ I : Ai |= (∃x)(δ1 ∧...∧δn)}) ∅∩\ n∈ω ({i ∈ I : Ai |= (∃x)(δ1 ∧...∧δn)}) = ∅ Furthermore, we also know that Xn ⊃ Xn+1. Now, for all i ∈ I, there is a largest n(i) < ω such that i ∈ Xn(i) Now, we find an elementQD Ai which satisfies ∆(x). We are constructing a function f. If n(i) = 0, let f(i) be any arbitrary a in Ai. If n(i) > 0, choose f(i) ∈ Ai such that Ai |= δ1(f(i))∧...∧δn(i)(f(i)) Note that for any i ∈ Xn, we have that n ≤ n(i) and therefore Ai |= δ(f(i)). Since this is a large set, by Los’s theorem, we have thatQD Ai |= δn(fD) for all n > 0. Therefore, fD satisfies ∆(x) inQD Ai. We have finished the proof.   Remark 5.4. Note that every regular ultrafilter is countably incomplete.
INTRODUCTION TO THE KEISLER ORDER 9 Corollary 5.5. If D is a nonprincipal ultrafilter over N and {Ai}i∈N is a collection of L−structures, thenQD A is ℵ1−saturated. Proof. By the theorem above, it suffices to show that every nonprincipal ultrafilter over N is countably incomplete. Recall that since D is nonprincipal, it contains all cofinite sets. Let C be the collection of all cofinite sets in D. Recall also that |Pℵ0(N)| = ℵ0. We have a natural bijection f : Pℵ0(N) → C defined by: f(S) = N−S Now, let I0 = N and define In+1 = In −n It is clear that In ∈ D and that In ⊃ In+1 for n ∈ ω. Finally, for sake of condtradiction, suppose that \ n∈ω In 6= ∅ Then, there exists some x in the natural numbers such that x ∈Tn∈ω In. However, consider Ix+1. By definition, Ix+1 = Ix −x which shows that x 6∈Tn∈ω In. Hence, we have a contradiction and soTn∈ω In = ∅. Therefore, D must be countably incomplete and soQD Ai is ℵ1−saturated by the previous theorem.   6. The Order
Now that we have all the necessary definitions in place, we can finally define the Keisler Order. Definition 6.1. (Keisler Order): We say that a theory T1 Eκ T2 if for any A1 |= T1, A2 |= T2, and regular ultrafitler D over κ, we have that ifQD A2 is κ+−saturated thenQD A1 must be κ+−saturated. Now we say that T1 E T2 if for every infinite cardinal, κ, we have that T Eκ T2. This second definition, E, is the Keisler Order. Note that the ultrafilter construction is model theoretic while the order is on the theories of the models. Therefore, we still need to show that this definition is well defined (i.e. that it is not dependent on our choice of model).
Theorem 6.2. Fix some language L and some indexing set I. Furthermore, suppose that A ≡ B over L and D is a regular ultrafilter over I. Then we have thatQD A is α+−saturated if and only ifQD B is α+−saturated. Proof. First note that the two directions have the same proof. Assume, without loss of generality, thatQD B is α+−saturated. Let X = {Yi}i∈I be a regular subset of D. Let ∆ be a collection of formulas in one free variable (in the expanded language L(α)) such that ∆ is finitely satisfiable in (QD A,α) and |∆| ≤ α. It suffices to show that ∆ is realized in (QD A,α) Since |∆|≤|X| = α, let h be an injection from Σ into X. We define ∆(i) = {δ ∈ ∆ : i ∈ h(δ)} and X(i) = h(∆(i)) = {h(δ) : δ ∈ ∆(i)} Note that ∆(i) is finite. If ∆(i) were infinite, then we could find a infinite collection of elements in X such that their intersection would be non-empty. Finding this collection would contradict the regularity of X.
10 KYLE GANNON
Also, since X(i) is the image of an injection from a finite set, we have that |X(i)| = |∆(i)| < ω. Let a =  ai i∈I/D, and for each i let a(i) = ai. Let Γ(i) be the set of all sentences of L(α) of the form {(∃x)^ j∈s δj : s 6= 0,s ∈P(∆(i)),δj ∈ ∆(i)} Note that Γ(i) is a valid collection of first-order sentences since ∆(i) is finite. Γ(i) is simply every possible subcollection of sentences in ∆(i). Since Γ(i) is finite and Ai ≡ Bi we can choose b(i) in Bi such that Γ(i)∩Th(Ai,a(i)) = Γ(i)∩Th(Bi,b(i)) for all i ∈ I. Therefore, we have chosen our b(i)’s such that each subset of ∆(i) is realized in (Ai,a(i)) if and only if it is realized in (Bi,b(i)). Let b = bi i∈I/D. Therefore, b is an element ofQD B. We will now show that ∆ is finitely satisfiable in (QD B,b). Let δ1,...,δn ∈ ∆ and let ϕ = (∃x) ^ 1≤j≤n δj Note that {i ∈ I : ϕ ∈ Γ(i)} ∈ D. Since ∆ is finitely satisfiable in (QD A,a), ϕ holds inQD A and therefore, ϕ holds in (Ai,a(i)) on a large set. Now, from above, we have that for every i ∈ I such that (Ai,a(i)) |= ϕ, we have that (Bi,b(i)) |= ϕ. Therefore, ϕ holds in (Bi,b(i)) for a large subset of D. Then{i ∈ I : (Bi,b(i)) |= ϕ} is a large set and so ϕ holds in (QD B,b). Because ∆ is finitely satisfiable in (QD B,b), ∆ has power at most α, andQD Bis α+−saturated, there exists an element g/D ∈QD B such that g/D realizes ∆. For each i ∈ I, we let T(i) be the set of all δ ∈ ∆(i) such that g(i) satisfies δ is( Bi,b(i)). Since T(i) is finitely satisfiable in (Bi,b(i)), it is also finitely satisfiable in (A,a(i)). Note that since T(i) is finite, we can find an element f(i) ∈ Ai such that f(i) realizes T(i) in (A,a(i)). Finally, we must now show that f/D = f(i) i∈I/D satisfies ∆ in (QD Ai,a).Let δ ∈ ∆. Then δ ∈ ∆(i) on a large set. Also, g/D satisfies δ in (QD B,b), so g(i)satisfies δ in (Bi,b(i)) for on a large subset of D. Thus, we have that δ ∈ T(i) fora large subset of D. It follows that f(i) satisfies δ in (Ai,a(i)) for a large subset of D, and therefore, f/D satisfies ∆ inQD A.   7. Existence of a Maximal Class
In this section, we will prove the existence of a maximal class. The theories we will show are maximal, in some sense, can define the concept of saturation. The theories encode the idea of saturation. Note that the following proof provides a sufficient condition for maximality. Definition –7.1. (Weak Ideals): Let n ∈N. We say that T is a weak ideal over n if 1. T ⊆P(n) and T 6= ∅. 2. If t ∈ T and ∅6= s ⊂ t, then s ∈ T. The following example is the key concept to keep in mind when understanding why weak ideals are important.
INTRODUCTION TO THE KEISLER ORDER 11
Example 7.2. Let ∆ = {δ1,...,δn}. Suppose that A |= δi1 ∧...∧δim where m ≤ n. Then, if we let, T = {s ∈P(n) : A |=^ k∈s δk} then, T is a weak ideal over n. Definition 7.3. (Versatile Formula): Let ϕ(x0, ¯ x) be some formula in a language L. We say that ϕ(x0, ¯ x) is a versatile formula in some L−structure, A, if for everyn ∈N and every weak ideal T over n, we have that A |= (∃x0, ¯ x)  ^ t∈T (∃x0)^ m∈t ϕ(x0, ¯ x) ∧ ^ t6∈T ¬(∃x0)^ m∈t ϕ(x0, ¯ x)   At first glance, the versatile formula might seem a little daunting. Note that in the standard model of arithmetic, (N;+,×,0,1), the formula, ϕ(x0,x1) ≡ (∃z)[(z×x0 = x1)∧(x0 6= 1)] is a versatile formula. ϕ just states that x0 is a non-trivial divisor of x1. Theorem 7.4. There exists a maximal class with respect to the Keisler Order.
Proof. We show that if A has a versatile formula, the A is maximal. Let D be a regular ultrafilter and suppose thatQD A is α+−saturated. It suffice to show that for any (countable) language L0 and any L0−structure B,QD B is α+−saturated. Let b be an α−termed sequence inQD Bi. Let ∆ be a collection of formulas in one free variable (in the language L(α)) such that |∆|≤ α. Also, suppose that ∆ is finitely satisfiable in (QD B,b). Let X be a regular subset of D. Let h : ∆ → X be an injection. Again, set ∆(i) = {δ ∈ ∆ : i ∈ h(δ)} Notice that each ∆(i) is finite for the same reason as the previous theorem. Note also that (Y D Bi,b) =Y D (Bi,b(i)) Now, for i ∈ I we can write ∆(i) = {δ1,...,δn}. Let T = {t ⊂ n : t 6= 0,(Bi,b(i)) |= (∃x)^ m∈t (∃x0)δm} Then, we know that T is a weak ideal over n. Let ϕ(x0, ¯ x) be a versatile formula for A. Now, for each i ∈ I, we let a(δm,i) be the tuple of elements of Ai which satisfy ¯ x. Now, for every δ ∈ ∆, choose fδ to be a function from I intoQD A suchthat whenever δ ∈ ∆(i), fδ = a(δ,i). Finally, we set aδ = fδ/D.Since ∆ has size α, we the elements aδ can be put into correspondence with the constants in L(α). For every δ ∈ ∆, let ϕδ be the one-variable formula of L(α) generated by replacing x by aδ. It is now the case that for any i ∈ I and δ1,...,δn ∈ ∆(i), δ1 ∧...∧δm holds in( B,b(i)) if and only if ϕδ1 ∧...∧ϕδn holds (A,a(i)). Since δ1 ∧...∧δm holds on a large subset of D, we also know that ϕδ1 ∧...∧ϕδn holds on a large subset of D. Therefore, ϕδ1 ∧...∧ϕδn is satisfied in (QD A,a) and the set Φ = {ϕδ : δ ∈ ∆} is finitely satisfiable in (QD A,a). SinceQD A is α+−saturated, Φ is realized in QD A. Let g/D satisfy Φ. Now choose, for each i, and element f(i) ∈ B which
12 KYLE GANNON
satisfies δ whenever δ ∈ ∆(i) and g(i) satisfies φδ. Then for each δ ∈ ∆, f(i) satisfies δ on a large set, therefore f/D satisfies ∆ in (QD B,b). Hence,QD B is α+−saturated.   Note that by our theorem in the last section, we now know that the theory of arithmetic is maximal with respect to the Keisler Order. However, a necessary and sufficient condition for maximality is still unknown. As stated at the beginning of the paper, the complete order type of the Keisler Order is still unknown. It is known that there exists a minimal class, at least two non-minimal and non-maximal classes, and a maximal class.
Acknowledgments. It is a pleasure to thank my mentors, Nir Gadish and Jonny Stephenson, for their patience and guidance throughout this project. This project would have been near impossible without them. Furthermore, I would also like to thank Professor Maryanthe Malliaris for suggesting the topic as well as her lectures at the REU program this summer. The lectures gave direction to my project as a whole.
References
[1] Blass, A. ”A Model Without Ultrafilters.” Bull. Acad. Polon. Sci., Ser. Sci. Math. Astronom. Pyhs. 25 (1977), no. 4, 329-331. [2] Chang, C. C., and H. J. Keisler. Model Theory. Amserdam: North-Holland Pub., 1973. Print. [3] Keisler, H. J. ”Ultraproducts which are not Saturated.” The Journal of Symbolic Logic, Vol. 32, No. 1 (Mar., 1967), pp. 23-46 [4] Malliaris, M. and S. Shelah. ”General Topology Meets Model Theory, on P and T.” Proceedings of the National Academy of Sciences 110.33 (2013): 13300-3305. Web. [5] S. Shelah. Classification Theory and the number of non-isomorphic models, rev. ed. NorthHolland