INTRODUCTION TO THE KEISLER ORDER

By KYLE GANNON

Abstract. In this paper, we introduce the basic denitions and concepts necessary to dene the Keisler Order. We will prove the order is well-dened as well as the existence of a maximal class with respect to the order.

Contents

1. Introduction 1

2. Notation and Basic Denitions 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 rst introduced by H. Jerome Keisler in 1967. Currently, this order is known to be a pre-order on (countable) rst-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 classication of rst-order theories is both a classic and modern program in model theory. Shelah’s stability program, the most famous type of classication framework, organizes theories relative to the number of denable types over subsets of a model. While the stability program has had great success, the program also leaves unstable theories in some unclassiable 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 denitions 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 rst-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 quantication) ∀,∃. 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 xed 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 xed 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 nite intersection property if and only if any nite 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 nite subsets of A. Finally, we have some more formal denitions and theorems which we will be referring to. Denition 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.

Denition 2.2. A collection of sentences, , is said to be satisfiable if there exists a model A such that A |= . is said to be nitely satisable if every nite subset of is satisable.

Theorem 2.3. (Completeness): A set of sentences is consistent if and only if it is satisable.

Theorem 2.4. (Compactness): A set of sentences is satisable if and only if it is nitely satisable. Denition 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 |= . Denition 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 xed 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 rst 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 dene ultrapowers, we have to rst get an intuition for ultralters and ultraproducts.

Denition 3.1. Let I be an indexing set. We say that D is a lter 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 ultralter 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 ultralters without the countable intersection property are valuable and are central to our study.

Denition 3.2. Let D be a lter over I. We say that D is a principal lter if there exists X ⊂ I such that D = {Y ⊆ I : X ⊂ Y}. We call any lter which is not principal a nonprincipal (or free) lter. Example 3.3. (Principal Ultralter): Let I = N and let D = {X ⊆ N : 3 ∈ X}. Then, D is a principal ultralter over I.

Example 3.4. (Nonprincipal Ultralter): It is provable that one cannot construct an example (since the existence of a nonprincipal ultralter is equivalent to a weak version of choice). There are models of ZF where there do not exist any nonprincipal ultralters. 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 ultralter will be a nonprincipal ultralter. Furthermore, we will assume the full power of ZFC and thus never worry about the existence of ultralters (in general). The next two facts follow quickly from the denitions and are left unproven.

Proposition 3.5. No free ultralter contains any nite sets.

Proposition 3.6. Let A be a collection of subsets of I such that A has the nite intersection property. Then A can be extended to an ultralter 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 lter, then ≡D is an equivalence relation overQi∈I Ai.

4 KYLE GANNON

Denition 3.8. (Ultraproduct): Let I be an indexing set and let D be an ultralter over I. An ultraproduct of L−structures is dened as, Y i∈I A/D = {fD : f ∈Y i∈I Ai} For notational purposes, we will always have our I’s xed 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 ultralter 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 (rst-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 innite 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 eld are rst-orderizable in the language L = {0,1,+,×}. We will denote ACF to mean algebraically closed eld while ACFp will mean algebraically closed eld of characteristic p. Let P denote the set of standard primes. Furthermore, let Ap |= ACFp and so each model, Ap is an algebraically closed eld of characteristic p. Let D be a nonprincipal ultralter 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 eld. We will now nd this eld’s characteristic. By proposition 3.5, there is no nite set in D. Since D is an ultralter, this means that D contains all conite sets. Dene 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 conite subset of P. Therefore,QD Ai cannot have characteristic i for any i ∈ N 2. SinceQD Ai is a eld and must have some characteristic, it has characteristic 0. Denition 3.11. (Ultrapower): If I is an indexing set and D is an ultralter 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 dierentiation we will simply write ultrapowers asQD A when I is xed. This construction, in relation to ultraproducts, might seem a little odd at rst. We already know the exact set of rst-order sentences thatQD A satises. The proof thatQD A ≡ A 2Recall that elds 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 dierent 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 ultralter 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 conite 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 nd an innite 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 nitely many steps, since if it did, then f would be some standard natural number. SinceQD A has an innite 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 dene regular ultralters. Denition 3.13. Let D be a nonprincipal ultralter over some innite indexing set I. We say that D is a (β,α)−regular ultralter 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 ultralter 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 ultralter we actually need for the denition of the Keisler Order, we will prove that D regular ultralters exist. Lemma 3.14. (Regular Ultralter Existence): For every innite cardinal κ, there exists a regular ultralter over κ. Proof. Let Pℵ0(κ) be the set of all nite subsets of κ. Note that |Pℵ0(κ)| = κ. Let f : Pℵ0(κ) → κ be a bijection and for each β ∈ κ, dene Yβ = {i ∈ I : β = f−1(i)}. Now, consider A = {Yβ : β ∈ κ}. It is clear that |A| = κ. Recall that if A has the nite intersection property, then A can be extended to an ultralter. Consider: n \ j=1 Yβj = n \ j=1 {i ∈ I : βj ∈ f−1(i)d} 3Note that S can be dened in the language {≤}. We have added S to our language to simplify our arguments.

6 KYLE GANNON

By denition, 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 nite intersection property and may be extended into an ultralter. It should also be clear that the intersection of countable subsets of A are empty and so A is our regular subset of its ultralter extension. 

4. Saturation and Satisfaction

While ultrapowers are necessary for understanding the Keisler Order, this topic alone is not sucient. Another key ingredient of the Keisler Order is saturation. This concept, along with satisfaction, will bring the Keisler Order into view. Denition 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 nite 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 xed 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)} . Denition 4.2. (Satisfaction of 1-Types): Let ρ be a complete 1−type in one free variable. We say that ρ is satised/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 denition can be clearly extended to n−types and has corresponding collections, Sn(X).

Denition 4.4. (κ - Saturation): Let κ be some innite 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 denition 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 nd 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 denable 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 dierent (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 nitely satisable. By the compactness theorem, we note that ρξ is consistent. Therefore, it must be satised in our ℵ1−saturated model (since it is denable over a countable subset of our underlying set). Let a be the element of D which satises 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 dened 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.

Denition 5.1. (Countably Incomplete Ultralter): An ultralter is said to be countably incomplete if there exists a subset X of D such that |X| = ℵ0 and TX = ∅. These ultralters are much weaker than regular lters, so our theorem will be very general. We are going to show that any ultrapower, using a countably incomplete ultralter, is ℵ1−saturated. However, we will need the following lemma rst.

Lemma 5.2. Let D be a countably incomplete ultralter. Then, there exists a countable descending chain I = I0 ⊂ I1 ⊂ I2 ⊂ ..., such thatTn∈ω In = ∅. Proof. Since D is an ultralter, 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. Dene

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 denable 1−types over a countable set in a countable language.

8 KYLE GANNON

Since D is closed under intersection, it is closed under nite 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 ultralter over some innite 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 suces to show that if each nite subset of (x) is satised inQD Ai, then (x) is realized inQD Ai. Suppose that each nite 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 dene Xn = In ∩{i ∈ I : Ai |= (∃x)(δ1 ∧...∧δn)} Recall that we assumed that every nite subset of (x) is satised 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 denition of a lter 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 nd an elementQD Ai which satises (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 satises (x) inQD Ai. We have nished the proof.   Remark 5.4. Note that every regular ultralter is countably incomplete.

INTRODUCTION TO THE KEISLER ORDER 9 Corollary 5.5. If D is a nonprincipal ultralter over N and {Ai}i∈N is a collection of L−structures, thenQD A is ℵ1−saturated. Proof. By the theorem above, it suces to show that every nonprincipal ultralter over N is countably incomplete. Recall that since D is nonprincipal, it contains all conite sets. Let C be the collection of all conite sets in D. Recall also that |Pℵ0(N)| = ℵ0. We have a natural bijection f : Pℵ0(N) → C dened by: f(S) = N−S Now, let I0 = N and dene 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 denition, 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 denitions in place, we can nally dene the Keisler Order. Denition 6.1. (Keisler Order): We say that a theory T1 Eκ T2 if for any A1 |= T1, A2 |= T2, and regular ultratler D over κ, we have that ifQD A2 is κ+−saturated thenQD A1 must be κ+−saturated. Now we say that T1 E T2 if for every innite cardinal, κ, we have that T Eκ T2. This second denition, E, is the Keisler Order. Note that the ultralter construction is model theoretic while the order is on the theories of the models. Therefore, we still need to show that this denition is well dened (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 ultralter 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 nitely satisable in (QD A,α) and || ≤ α. It suces to show that is realized in (QD A,α) Since ||≤|X| = α, let h be an injection from Σ into X. We dene (i) = {δ ∈ : i ∈ h(δ)} and X(i) = h((i)) = {h(δ) : δ ∈ (i)} Note that (i) is nite. If (i) were innite, then we could nd a innite 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 nite 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 rst-order sentences since (i) is nite. Γ(i) is simply every possible subcollection of sentences in (i). Since Γ(i) is nite 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 nitely satisable in (QD B,b). Let δ1,...,δn ∈ and let = (∃x) ^ 1≤j≤n δj Note that {i ∈ I : ∈ Γ(i)} ∈ D. Since is nitely satisable 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 nitely satisable 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) satises δ is( Bi,b(i)). Since T(i) is nitely satisable in (Bi,b(i)), it is also nitely satisable in (A,a(i)). Note that since T(i) is nite, we can nd 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 satises in (QD Ai,a).Let δ ∈ . Then δ ∈ (i) on a large set. Also, g/D satises δ in (QD B,b), so g(i)satises δ 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) satises δ in (Ai,a(i)) for a large subset of D, and therefore, f/D satises 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 dene the concept of saturation. The theories encode the idea of saturation. Note that the following proof provides a sucient condition for maximality. Denition –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. Denition 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 rst 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 ultralter and suppose thatQD A is α+−saturated. It suce 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 nitely satisable 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 nite 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 satised in (QD A,a) and the set Φ = {δ : δ ∈ } is nitely satisable 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

satises δ whenever δ ∈ (i) and g(i) satises φδ. Then for each δ ∈ , f(i) satises δ on a large set, therefore f/D satises 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 sucient 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 Ultralters.” 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