Title: Daniel's Flashcards / Year 4 / Term 2 / Model Theory

html: Definition 1.1 (T models a sentence). Let T be an L-theory, φ an L-sentence. Then T ⊨ φ if every model of T is a model of φ.
nothing: True

html: Definition 1.2 (Complete theory). An L-theory T is complete if for every L-sentence φ, either T ⊨ φ or T ⊨ ¬ ⁡ φ.
nothing: True

html: Definition 1.4 (Theory of M). Let M be an L-structure. Then the theory of M
T h L ( M ) = { φ : φ is an L -sentence, and M ⊨ φ } .
(can be written T h ( M ) when L is clear).
nothing: True

html: Definition 1.6 (Elementarily equivalent). Two L-structures are elementarily equivalent if their theories are equal.
Given L-structures M , N, we write M ≡ L N to mean T h L ( M ) = T h L ( N ).
nothing: True

html: Theorem 1.8 (Los-Vaught test). Assuming that:
- T is an L-theory
- T has no finite models
- There exists some K ≥ | L | + ℵ 0 such that any two models of T of cardinality κ are elementarily equivalent
Then T is complete.
proof: Proof. Assume T is not complete, i.e. there is some L-sentence σ such that T ∪ { σ } and T ∪ { ¬ ⁡ σ } are both satisfiable.
So we have M ⊨ T ∪ { σ }, N ⊨ T ∪ { ¬ ⁡ σ }.
From (a) we know M , N are infinite. By Lowenheim-Skölem, we know we have M ′ ⊨ T ∪ { σ } and N ′ ⊨ T ∪ { ¬ ⁡ σ } with | M ′ | = | N ′ | = κ, contradicting (b). □
nothing: True

html: Definition 2.1 (Homomorphism). Let M , N be L-structures. A function h : M → N is an L-homomorphism if:
- (i) For an n-ary function symbol f, and a 1 , … , a n ∈ M we have
h ( f M ( a 1 , … , a n ) ) = f N ( h ( a 1 ) , … , h ( a n ) ) .
- (ii) For an n-ary relation symbol R, and a 1 , … , a n ∈ M we have
( a 1 , … , a n ) ∈ R m iff ( h ( a 1 ) , … , h ( a n ) ) ∈ R N .
- (iii) For any constant symbol c, h ( c M ) = c N.
We write h : M → N if h is an L-homomorphism.
If h is also injective then this is called an L-embedding.
If h is also bijective then this is called an L-isomorphism.
nothing: True

html: Theorem 2.2. Assuming that:
- h : M → N is an L-isomorphism
- φ ( x 1 , … , x n ) an L-formula
- a 1 , … , a n ∈ M
Then
M ⊨ φ ( a 1 , … , a n ) iff N ⊨ φ ( h ( a 1 ) , … , h ( a n ) ) .
proof: Proof. Let a ¯ = ( a 1 , … , a n ).
Step 1: Terms. Proof by induction on term complexity. For the base case:
- For t a constant, we have h ( t M ) = h ( c M ) = c N = t N.
- For t a variable: h ( t M ( x i ) ) = h ( a i ) = t N ( h ( a i ) ).
For the inductive step: Let f be an m-ary function symbol. Assume that the claim holds for t 1 , … , t m whose free variables are amongst x 1 , … , x n.
Suppose t = f ( t 1 , … , t m ). Given a 1 , … , a n ∈ M, we have
h ( t M ( a 1 , … , a n ) ) = h ( f M ( t 1 M ( a 1 , … , a n ) , … , t m M ( a 1 , … , a n ) ) ) = f N ( h ( t 1 M ( a ¯ ) ) , … , h ( t m M ( a ¯ ) ) ) ( f N is an L - isomorphism ) = f N ( t 1 N ( h 1 ( a ¯ ) ) , … , t m N ( h ( a ¯ ) ) ) (inductive step) = t N ( h ( a ¯ ) )
Step 2: Formulas. Base case: atomic formulas. Suppose φ is t 1 = t 2. Then:
M ⊨ φ ( a ¯ ) iff t 1 M ( a ¯ ) = t 2 M ( a ¯ ) iff h ( t 1 M ( a ¯ ) ) = h ( t 2 M ( a ¯ ) ) by bijectivity iff t 1 N ( h ( a ¯ ) ) = t 2 N ( h ( a ¯ ) ) using step 1 iff N ⊨ φ ( a ¯ )
Case where φ is R ( t 1 , … , t m ) left as an exercise.
Inductive step: Assume statement holds for φ and ψ.
- φ ∧ ψ, ¬ ⁡ φ left as an exercise.
- ∀ ⁡ x n φ ( x 1 , … , x n − 1 , x n ) (then ∃ ⁡ will follow since it can be expressed using ∀ ⁡).
Let a 1 , … , a n − 1 ∈ M. Then
M ⊨ ∀ ⁡ x n φ ( a 1 , … , a n − 1 , x n ) iff for all b ∈ M , M ⊨ φ ( a 1 , … , a n − 1 , b ) iff for all b ∈ M , N ⊨ φ ( h ( a 1 ) , … , h ( a n − 1 ) , h ( b ) ) iff for all c ∈ N , N ⊨ φ ( h ( a 1 ) , … , h ( a n − 1 ) , c ) iff N ⊨ ∀ ⁡ x n φ ( h ( a 1 ) , … , h ( a n − 1 ) , x n ) □
cloze1: True

html: Corollary 2.4. h : M → N is an L-embedding if and only if the conclusion of Theorem 2.2 holds for all quantifier free formulas φ ( x 1 , … , x n ).
proof: Proof.
- ⇒ Clear from proof of Theorem 2.2.
- ⇐ Exercise (see Example Sheet 1). □
cloze1: True

html: Definition 2.5 (Elementary embedding). An L-homomorphism h : M → N is an elementary L-embedding if for any L-formula φ ( x ¯ ) and any a ¯ ∈ M (with | x ¯ | = | a ¯ |) we have
M ⊨ φ ( a ¯ ) iff N ⊨ φ ( h ( a ¯ ) ) .
nothing: True

html: Definition 2.6 (Substructure). Let M and N be L-structures with M ⊆ N. Let h : M ↪ N be the inclusion map. Then we say that M is a substructure (respectively elementary substructure) of N, written M ⊆ N (respectively M ≼ N) if h is an L-embedding (respectively elementary L-embedding).
We may also say N is an extension (respectively elementary extension) of M.
nothing: True

html: Theorem 2.8 (Tarski-Vaught Test). Assuming that:
- h : M → N is an L-embedding
Then the following are equivalent:
- (i) h is an elementary L-embedding
- (ii) For every first order formula φ ( y , x 1 , … , x n ) and every a 1 , … , a n ∈ M, if there exists y ∈ N such that N ⊨ φ ( y , h ( a 1 ) , … , h ( a n ) ) then there exists y ∈ M such that N ⊨ φ ( h ( y ) , h ( a 1 ) , … , h ( a n ) ).
proof: Proof. Example Sheet 1. □
nothing: True

html: Definition 3.1 (k a p p a-categorical). An L-theory is κ-categorical if it has a unique model of size κ up to isomorphism.
nothing: True

html: Theorem (Morley’s Categoricity Theorem 1965). Assuming that:
- T is a complete theory in a countable language
- T is κ-categorical for some uncountable κ
Then it is κ-categorical for all uncountable κ.
proof: Proof. Let M , N ⊨ DLO with M , N countable. We need to construct an L-isomorphism h : M → N, i.e. an order preserving bijection.
We will use the back and forth method.
Let M = { a 1 , a 2 , … } and N = { b 1 , b 2 , … }.
We construct a series of functions ( h n ) n = 0 ∞ such that:
- (i) h n : X n → Y n is an order-preserving bijection.
- (ii) X n ⊆ X n + 1 , Y n ⊆ Y n + 1 , h n ⊆ h n + 1 for each n.
- (iii) a n ∈ X n, b n ∈ Y n.
Once we have done this, h = ⋃ ⁡ n = 0 ∞ h n is an order-preserving bijection h : M → N (i.e. an L-isomorphism).
Use induction.
Base case: X 0 = { x 0 }, Y 0 = { b 0 }, h 0 ( a 0 ) = b 0.
Inductive step: Suppose h n : X n → Y n as required.
“Forth”: Construct an order preserving bijection h ∗ : X ∗ → Y ∗ extending h n with a n + 1 ∈ X ∗. Enumerate X n = { x 1 , … , x k } with x 1 < M x 2 < M x 3 < M ⋯ < M x k. Let y i = h ( x i ) so that y 1 < M y 2 < M ⋯ < M y k.
Define h ∗ = h n ∪ { ( a n + 1 , b ) } where b ∈ N is chosen according to the following cases:
- If a n + 1 = x i for some i ∈ { 1 , … , k }, then put b = x i.
- If a n + 1 < x i for all i ∈ { 1 , … , k } then choose b such that b < y i for all i ∈ { 1 , … , k } (possible since no endpoints).
- If x i < a n + 1 for all i ∈ { 1 , … , k }, then choose b such that y i < b for all i ∈ { 1 , … , k } (possible since no endpoints).
- If there is some i ∈ { 1 , … , k − 1 } such that x i < a n + 1 < x i + 1, then choose b such that y i < b < y i + 1 (possible since M is dense).
Then h ∗ is an order-preserving bijection and a n + 1 ∈ X n + 1 as desired.
“Back”: We need to construct an order-preserving map h n + 1 → Y n + 1 extending h ∗ with b n + 1 ∈ Y n + 1.
Exercise.
Then h n + 1 satisfies the conditions. □
nothing: True

html: Definition 3.3 (Theory of dense linear orders). Let L = { < }. We define the theory in axioms:
- (i)
Irreflexive: ∀ ⁡ x , ¬ ⁡ ( x < x ).
- (ii)
Transitive: ∀ ⁡ x , ∀ ⁡ y , ∀ ⁡ z , ( ( x < y ∧ y < z ) → x < z ).
- (iii)
Antisymmetric: ∀ ⁡ x , ∀ ⁡ y , ( x ≠ y → ( x < y ∨ y < x ) ).
- (iv)
Dense: ∀ ⁡ x , ∀ ⁡ y , ( x < y → ( ∃ ⁡ z ( x < z < y ) ).
- (v)
No endpoints: ∀ ⁡ x , ∃ ⁡ y , ∃ ⁡ z , ( z < x < y ).
nothing: True

html: Theorem 3.4 (Cantor 1895). DLO is ℵ 0-categorical.
proof: Proof. Let M , N ⊨ DLO with M , N countable. We need to construct an L-isomorphism h : M → N, i.e. an order preserving bijection.
We will use the back and forth method.
Let M = { a 1 , a 2 , … } and N = { b 1 , b 2 , … }.
We construct a series of functions ( h n ) n = 0 ∞ such that:
- (i) h n : X n → Y n is an order-preserving bijection.
- (ii) X n ⊆ X n + 1 , Y n ⊆ Y n + 1 , h n ⊆ h n + 1 for each n.
- (iii) a n ∈ X n, b n ∈ Y n.
Once we have done this, h = ⋃ ⁡ n = 0 ∞ h n is an order-preserving bijection h : M → N (i.e. an L-isomorphism).
Use induction.
Base case: X 0 = { x 0 }, Y 0 = { b 0 }, h 0 ( a 0 ) = b 0.
Inductive step: Suppose h n : X n → Y n as required.
“Forth”: Construct an order preserving bijection h ∗ : X ∗ → Y ∗ extending h n with a n + 1 ∈ X ∗. Enumerate X n = { x 1 , … , x k } with x 1 < M x 2 < M x 3 < M ⋯ < M x k. Let y i = h ( x i ) so that y 1 < M y 2 < M ⋯ < M y k.
Define h ∗ = h n ∪ { ( a n + 1 , b ) } where b ∈ N is chosen according to the following cases:
- If a n + 1 = x i for some i ∈ { 1 , … , k }, then put b = x i.
- If a n + 1 < x i for all i ∈ { 1 , … , k } then choose b such that b < y i for all i ∈ { 1 , … , k } (possible since no endpoints).
- If x i < a n + 1 for all i ∈ { 1 , … , k }, then choose b such that y i < b for all i ∈ { 1 , … , k } (possible since no endpoints).
- If there is some i ∈ { 1 , … , k − 1 } such that x i < a n + 1 < x i + 1, then choose b such that y i < b < y i + 1 (possible since M is dense).
Then h ∗ is an order-preserving bijection and a n + 1 ∈ X n + 1 as desired.
“Back”: We need to construct an order-preserving map h n + 1 → Y n + 1 extending h ∗ with b n + 1 ∈ Y n + 1.
Exercise.
Then h n + 1 satisfies the conditions. □
nothing: True

html: Corollary 3.5. DLO is complete.
proof: Proof. No finite models (because of the no end points axiom).
If M , N ⊨ DLO, with both countable, then M ≅ N and hence M ≡ N.
So by Los-Vaught test, DLO is complete. □

html: Definition 4.1 (Filter). Let J be a set. A filter F on J is a non-empty subset of P ( J ) such that:
- ∅ ∉ F.
- ∀ ⁡ A , B ∈ F , A ∩ ∈ F (“closed under finite intersections”).
- ∀ ⁡ A ∈ F, if A ⊆ B ⊆ B ⊆ J, then B ∈ F (“closed under super set”).
nothing: True

html: Definition 4.3 (Ultrafilter). Let J be an infinite set and F a filter on J. We say F is an ultrafilter if every filter G on J satisfying F ⊆ G also satisfies G = F.
nothing: True

html: Proposition 4.4. Assuming that:
- J a set
- F a filter on J
Then F is an ultrafilter if and only if for every A ⊆ J either A ∈ F or J ∖ A ∈ F.
proof: Proof. Example Sheet 1. □
cloze1: True

html: Proposition 4.5. Assuming that:
- J is a set
- F a filter on J
Then there is an ultrafilter U such that F ⊆ U.
proof: Proof (sketch). Let X be the set of filters extending F, and partially order it by inclusion. Note every chain has an upper bound (take the union), so by Zorn’s lemma we have a maximal element, which is a ultrafilter (by definition). □
cloze1: True

html: Definition 5.3. Let ( A j ) j ∈ J be a non-empty family of non-empty sets and U an ultrafilter on J.
- Write ∏ ⁡ j ∈ J A j ∕ U to be ∏ ⁡ j ∈ J A j ∕ ∼ (where ∼ is defined as in Definition 5.1).
- [ ( a j ) j ∈ J ] U is the equivalence class of ( a j ) j ∈ J with respect to ∼.
- Let B j ⊆ A j for every j ∈ J. Then
[ ( B j ) j ∈ J ] U = { [ ( a j ) j ∈ J ] ∈ ∏ j ∈ J A j ∕ U : { j ∈ J : a j ∈ B j } ∈ U } .
cloze1: True

html: Proposition 5.4. Assuming that:
- ( A j ) j ∈ J, ( B j ) j ∈ J satisfy B j ⊆ A j for all j
- ( a j ) j ∈ J , ( b j ) j ∈ J ∈ ∏ ⁡ j ∈ J A j satisfying ( a j ) j ∈ J ∼ ( b j ) j ∈ J
Then { j ∈ J : a j ∈ B j } ∈ U if and only if { j ∈ J : b j ∈ B j } ∈ U.
proof: Proof. Know ( a j ) j ∈ J ∼ ( b j ) j ∈ J. Define
U = { j ∈ J : a j = b j } ∈ U V = { j ∈ J : a j ∈ B j } W = { j ∈ J : b j ∈ B j }
Note U ∩ V ⊆ W and U ∩ W ⊆ V.
If V ∈ U then U ∩ V ∈ U so W ∈ U. Similarly, if W ∈ U then V ∈ U. □
cloze1: True

html: Proposition 5.5. Assuming that:
- ( A j ) j ∈ J, U, ∼ as usual.
- B j , C j ⊆ A j
Then
- (1) [ ( B j ) j ∈ J ] ∩ [ ( C j ) j ∈ J ] = [ ( B j ∩ C j ) j ∈ J ].
- (2) [ ( B j ) j ∈ J ] ∪ [ ( C j ) j ∈ J ] = [ ( B j ∪ C j ) j ∈ J ].
- (3) [ ( B j ) j ∈ J ] ∖ [ ( C j ) j ∈ J ] = [ ( B j ∖ C j ) j ∈ J ].
proof: Proof. Example Sheet 1. □
cloze1: True

html: Proposition 5.8. Assuming that:
- ( A j ) j ∈ J, U, ∼ as usual
- n ∈ ℕ
- for each j we have B j , C j ⊆ A j n
Then
- (1) [ ( B j ) j ∈ J ] ∩ [ ( C j ) j ∈ J ] = [ ( B j ∩ C j ) j ∈ J ]
- (2) [ ( B j ) j ∈ J ] ∪ [ ( C j ) j ∈ J ] = [ ( B j ∪ C j ) j ∈ J ]
- (3) [ ( B j ) j ∈ J ] ∖ [ ( C j ) j ∈ J ] = [ ( B j ∖ C j ) j ∈ J ]
- (4) If n > 0, k ∈ { 1 , … , n } then
π k ( [ ( B j ) j ∈ J ] ) = [ ( π k ( B j ) ) j ∈ J ] .
proof: Proof. (1) - (3): Straightforward. See Example Sheet.
(4): Let n > 0, k ∈ { 1 , … , n }. Let
α = ( [ ( a j 1 ) j ∈ J ] , … , [ ( a j k − 1 ) j ∈ J ] , [ ( j j k + 1 ) j ∈ J ] , … , [ ( a j n ) j ∈ J ] ) ∈ π k ( [ ( B j ) j ∈ J ] ) .
So we have some [ ( a j k ) j ∈ J ] such that
( [ ( a j 1 ) j ∈ J ] , … , [ ( a j n ) j ∈ J ] ) ∈ [ ( B j ) j ∈ J ] .
So U = { j ∈ J : ( a j 1 , … , a j n ) ∈ B j } ∈ U.
Consider
V = { j ∈ J : ( a j 1 , … , a j k − 1 , a j k + 1 , … , a n ) ∈ π ( B j ) } ⊇ U .
So α ∈ [ ( π k ( B j ) ) j ∈ J ], i.e. π k [ ( B j ) j ∈ J ] ⊆ [ ( π k ( B j ) ) j ∈ J ].
Showing [ ( π k ( B j ) ) j ∈ J ] ⊆ π ( [ ( B j ) j ∈ J ] ) is similar (do it as an exercise). □
cloze1: True

html: Theorem 5.10. Assuming that:
- A U be as above
- J = ℕ
- { C ⊆ ℕ : ℕ ∖ C is finite } ⊆ U
- n ∈ ℕ
- for each m ∈ ℕ, let B m ⊆ A n satisfying:
  - (1) [ B m ] ≠ ∅ ∀ ⁡ m ∈ ℕ
  - (2) [ B k ] ⊆ [ B m ] for all m , k ∈ ℕ with m ≤ k
Then ⋂ ⁡ m ∈ ℕ [ B m ] ≠ ∅.
proof: Proof. Omitted. For n = 1, this is a potential presentation topic. □
cloze1: True

html: Definition 6.1. Let M j = ( M j , I j ) be L-structures for each j ∈ J. Let U be an ultraproduct on J. Define an interpretation I U of L on ∏ ⁡ j ∈ J M j ∕ U. Let S ∈ L.
- If S is an n-ary relation:
I U ( S ) = [ ( I j ( S ) ) j ∈ J ] ⊆ ( ∏ j ∈ J M j ∕ U ) n .
- If S is a constant:
I U ( S ) = [ ( I j ( S ) ) j ∈ J ] ∈ ∏ j ∈ J M ∕ U .
- Functions are a bit less clear. However, we can always turn a function into a relation by looking at its graph (i.e. f : M n → M has graph R f = { ( x ¯ , y ) ∈ M n + 1 : f ( x ¯ ) = y }).
So if S is a function: for each j ∈ J, define the graph of I j ( S ) as
G j ( S ) = { ( a 1 , … , a n , b ) ∈ M j n + 1 : I j ( S ) ( a 1 , … , a n ) = b } .
Then [ ( G j ( S ) ) j ∈ J ] is the graph of a function
( ∏ j ∈ J M j ∕ U ) n → ∏ j ∈ J M j ∕ U .
(Checking this is left as an exercise). Now define I U ( S ) to be the function corresponding to [ ( G j ( S ) ) j ∈ J ].
cloze1: True

html: Theorem 7.1 (Los Lemma). Assuming that:
- L a language
- φ an L-formula
- ( M j ) j ∈ J = ( M j , I j ) j ∈ J a non-empty family of L-structures
- U an ultrafilter on J
- M = ( ∏ ⁡ j ∈ J M j ∕ U , I U )
Then
φ ( M ) = [ φ ( M j ) j ∈ J ] .
proof: Proof (sketch). Induction on
- Complexity of terms
- Formulas
(essentially Proposition 5.8). □
nothing: True

html: Corollary 7.2. Assuming that:
- σ an L-sentence
- ( M j ) j ∈ J a family of non-empty L-structures
- U an ultrafilter on J
- M = ∏ ⁡ j ∈ J M j ∕ U
Then M ⊨ σ if and only if { j ∈ J : M j ⊨ σ } ∈ U.
proof: Proof.
- ⇒ Suppose M ⊨ σ. Then σ ( M ) is a non-empty subset of M 0, i.e. its the empty tuple (). So { [ ( σ ( M j ) ) j ∈ J ] } = { ( ) }. So
{ j ∈ J : ( ) ∈ σ ( M j ) } = { j ∈ J : M j ⊨ σ } .
Since the LHS is in U, we get that the RHS is too.
- ⇐ Similar □
cloze1: True

html: Theorem 7.3 (Compactness – ultraproduct proof). Assuming that:
- L a language
- Σ a set of L-sentences
Then Σ is consistent if and only if every finite subset of Σ is consistent.
proof: Proof.
- ⇒ Clear.
- ⇐ Assume every finite subset of Σ is consistent. Let J be the set of all finite subsets of Σ. For each j ∈ J, let
ĵ ĵ = { k ∈ J : j ⊆ k } .
Let ĵ B = { ĵ : j ∈ J } and let
F = { A ⊆ J : ∃ ⁡ B ∈ B , B ⊆ A } .
Exercise: F is a filter.
Let U be an ultrafilter extending F. For each j ∈ J, let M j ⊨ j. Let M = ( ∏ ⁡ j ∈ J M j ∕ U ).
Claim: M ⊨ Σ.
Let σ ∈ Σ. Then { σ } ∈ J and { σ } ^ ⊆ { j ∈ J : M j ⊨ σ }.
So { j ∈ J : M j ⊨ σ } ∈ U, so M ⊨ σ.
So: ∀ ⁡ σ ∈ Σ , M ⊨ σ. □
nothing: True

html: Definition 8.1 (Generated by). Given an L-structure M, a non-empty A ⊆ M, the substructure generated by A is the intersection of all substructures containing A.
nothing: True

html: Definition 8.2 (Chain, Elementary chain). Let α be a limit ordinal.
A collection ( M i ) i < α of L-structures is a chain if M i ⊆ M j (substructure) for all i < j, and is an elementary chain if M i ≼ M j for all i < j.
If ( M i ) i < α is a chain then ⋃ ⁡ i < α M j is a well-defined L-structure.
nothing: True

html: Definition (Algebraically closed). Suppose ( K , + , ⋅ ) is a field (in L rings). It is algebraically closed if every non-constant polynomial over K has a root in K.
nothing: True

html: Definition 9.1 (ACF). ACF ⁡ is the L rings theory axiomatising algebraically closed fields. It consists of:
- field axioms
- for every d ≥ 1, we add an axiom:
∀ ⁡ v 0 , … , v d , ∃ ⁡ x ( v d ≠ 0 ⟹ v 0 + v 1 x + ⋯ + v d x d = 0 ) .
nothing: True

html: Definition 9.2 (ACF with characteristic). For n ≥ 1, let χ n be the sentence
1 + ⋯ + 1 ⏟ n times = 0 .
Set
ACF ⁡ 0 = ACF ⁡ ∪ { ¬ ⁡ χ n : n ∈ ℕ } ACF ⁡ p = ACF ⁡ ∪ { χ p } (for p a prime)
nothing: True

html: Theorem 9.3. ACF ⁡ 0 and ACF ⁡ p are κ-categorical for κ > ℵ 0.
proof: Proof. The Transcendence degree of k ⊨ ACF ⁡ (and algebraically closed field) is the cardinality of the largest algebraically independent subset of k.
For example,
trdeg ⁡ ℚ ( ℚ ¯ ) = 0 trdeg ⁡ ℚ ( ℚ ( π ) ¯ ) = 1 trdeg ⁡ ℚ ( ℂ ) = 2 ℵ 0 trdeg ⁡ ℚ ( ℚ ( x i ) i < κ ¯ ) = κ
From algebra we know:
- (1) If k , k ′ ⊨ ACF ⁡ then k ≅ k ′ if and only if
  - trdeg ⁡ ( k ) = trdeg ⁡ ( k ′ )
  - char ⁡ ( k ) = char ⁡ ( k ′ )
  - | k | = | k ′ |
- (2) If k ⊨ ACF ⁡, λ = trdeg ⁡ ℚ ( k ), then | κ | = ℵ 0 + λ. Thus if k , k ′ ⊨ ACF ⁡ 0 or ACF ⁡ p are uncountable and | k | = | k ′ | then trdeg ⁡ ℚ ( k ) = trdeg ⁡ ℚ ( k ′ ) so k ≅ k ′. □
cloze1: True

html: Definition 9.5 (Polynomial map). Let k be a field. We say a function ϕ : K m → K m is a polynomial map if
Φ ( x ¯ ) = ( p 1 ( x 1 , … , x m ) , … , p n ( x 1 , … , x m ) )
where each p 1 , … , p n is a polynomial.
nothing: True

html: Theorem 9.6 (Ax-Grothendieck). Assuming that:
- k an algebraically closed field
- Φ : K n → K n an injective polynomial map
Then Φ is surjective.
proof: Proof. First suppose K = 𝔽 p ¯ for some prime p. 𝔽 p ¯ = ⋃ ⁡ k 𝔽 p k. Fix an m such that the coefficients of Φ all lie in 𝔽 p m. Note: 𝔽 p ¯ = ⋃ ⁡ k 𝔽 p m k.
For any k ≥ 1, Φ induces an injective polynomial map 𝔽 p k m → 𝔽 p k m which has to be surjective (as finite field). Hence
Φ ( 𝔽 p ¯ n ) = Φ ( ⋃ k 𝔽 p m k n ) = ⋃ k Φ ( 𝔽 p m k n ) = ⋃ k 𝔽 p m k n = 𝔽 p ¯ n
So Φ is surjective.
Given n , d ≥ 1, let ψ n , d be the L-sentence expressing “every injective polynomial map with n-coordinates, each of which is a polynomial in n variables with degree at most d, is surjective”.
Exercise: Show that this is a first order L rings sentence.
Now 𝔽 p ¯ ⊨ ψ n , d for all n , d ≥ 1 and p prime.
ACF ⁡ p is complete, so ACF ⁡ p ⊨ ψ n , d. Now consider ACF ⁡ 0. Suppose for contradiction that ACF ⁡ 0 ⁄ ⊨ ψ n , d for some n , d, so ACF ⁡ 0 ⊨ ¬ ⁡ ψ n , d.
By compactness, there exists Σ ⊆ ACF ⁡ 0 finite such that Σ ⊨ ¬ ⁡ ψ n , d.
In particular, Σ ⊆ ACF ⁡ ∪ { ¬ ⁡ χ 0 , … , ¬ ⁡ χ m } for some m. Choose a prime p such that p > m and ACF ⁡ p ⊢ Σ.
So must have ACF ⁡ p ⊨ ¬ ⁡ ψ n , d, contradiction. □
nothing: True

html: Theorem 9.7 (Lipschiptz principal). Assuming that:
- ϕ an L rings sentence
Then the following are equivalent:
- (1) ACF ⁡ 0 ⊨ ϕ, i.e. ϕ in every k ⊨ ACF ⁡ 0
- (2) ACF ⁡ 0 ∪ { ϕ } is consistent
- (3) there exists some n > 0 such that ACF ⁡ p ⊨ ϕ for any p > n
- (4) for all n > 0, there exists some p > n such that ACF ⁡ p ∪ { ϕ } is consistent
proof: Proof. We use Corollary 2.4. Let φ ( x 1 , … , x n ) be a quantifier-free L-formula, and fix a 1 , … , a n ∈ M. Then
M ⊨ φ ( a 1 , … , a n ) ⟺ φ ( a 1 ̲ , … , a n ̲ ) ∈ D ( M ) ⟺ N ∗ ⊨ φ ( a 1 ̲ , … , a n ̲ ) ⟺ N ⊨ φ ( h ( a 1 ) , … , h ( a n ) )
Therefore h is an L-embedding.
“Moreover” is similar. □
nothing: True

html: Definition 10.2 (Diagram). The diagram of M (respectively elementary diagram), D ( M ), is the set of quantifier-free L M-sentences (respectively all L M-sentences) true in M.
nothing: True

html: Proposition 10.3. Assuming that:
- M is an L-structure
- N ∗ an L M-structure such that N ∗ ⊨ D ( M )
- let N be the L-reduct of N ∗ to L (means throw away L M ∖ L sentences)
- define h : M → N such that h ( a ) = a ̲ = a N.
Then h is an L-embedding. Moreover, if N ∗ ⊨ T h M ( M ) then h is an elementary L-embedding.
proof: Proof. We use Corollary 2.4. Let φ ( x 1 , … , x n ) be a quantifier-free L-formula, and fix a 1 , … , a n ∈ M. Then
M ⊨ φ ( a 1 , … , a n ) ⟺ φ ( a 1 ̲ , … , a n ̲ ) ∈ D ( M ) ⟺ N ∗ ⊨ φ ( a 1 ̲ , … , a n ̲ ) ⟺ N ⊨ φ ( h ( a 1 ) , … , h ( a n ) )
Therefore h is an L-embedding.
“Moreover” is similar. □
cloze1: True

html: Definition (Definable set). Let T be an L-theory and M ⊨ T. Then X ⊆ M n is definable is there is some L-formula φ ( x 1 , … , x n ) such that
X = { a ¯ ∈ M n : M ⊨ φ ( a ¯ ) } .
nothing: True

html: Definition 11.1 (Theory has quantifier elimination). An L-theory T has quantifier elimination (QE) if for any L-formula φ ( x 1 , … , x n ) ther eis a quantifier free formula ψ ( x 1 , … , x n ) such that
T ⊨ ∀ ⁡ x ¯ ( φ ( x ¯ ) ↔ ψ ( x ¯ ) ) .
(i.e. they define the same set in all models).
nothing: True

html: Lemma 11.3. Assuming that:
- T is an L-theory
- for any quantifier-free formula φ ( x 1 , … , x n , y ) there is a quantifier-free formula ψ ( x 1 , … , x n ) such that
T ⊨ ∀ ⁡ x ¯ ( ∃ ⁡ y φ ( x ¯ , y ) ↔ ψ ( x ¯ ) ) .
Then T has quantifier elimination.
proof: Proof. Exercise: induction on the complexity of formulas. □
cloze1: True

html: Theorem 11.4. Assuming that:
- T an L-theory
Then the following are equivalent:
- (i) T has quantifier elimination
- (ii) Let M , N ⊨ T, A ⊆ M, A ⊆ N (substructures). For any quantifier-free formula φ ( x 1 , … , x n , y ) and tuple a ¯ ∈ A, if M ⊨ ∃ ⁡ y , φ ( a ¯ , y ) then N ⊨ ∃ ⁡ y , φ ( a ¯ , y ).
- (iii) For any L-structure A, T ∪ D ( A ) is a complete L A-theory.
proof: Proof.
- (i) ⟹ (iii) Assume T has quantifier elimination, and let A be an L-structure. Suppose M , N ⊨ T ∪ D ( A ). We want to show M ≡ L A N.
Let σ be an L A-sentence, and suppose that M ⊨ σ. Then σ can be written as φ ( a ¯ ) where φ ( x ¯ ) is an L-formula and a ¯ ∈ A.
By quantifier elimination, we have ψ ( x ¯ ) such that
T ⊨ ∀ ⁡ x ¯ ( φ ( x ¯ ) ↔ ψ ( x ¯ ) ) .
Now M ⊨ T, so M ⊨ ∀ ⁡ x ¯ ( φ ( x ¯ ) ↔ ψ ( x ¯ ) ), and M ⊨ φ ( a ¯ ). So M ⊨ ψ ( a ¯ ). Now ψ ( a ¯ ) ∈ D ( A ) as M ⊨ D ( A ). So N ⊨ ψ ( a ¯ ), as N ⊨ D ( A ). Hence N ⊨ φ ( a ¯ ) as N ⊨ T (i.e. N ⊨ ∀ ⁡ x ¯ ( φ ( x ¯ ) ↔ ψ ( x ¯ ) )). So N ⊨ σ.
- (iii) ⟹ (ii) Let M , N ⊨ T, A ⊆ M, A ⊆ N. Let φ ( x ¯ , y ) be a quantifier free formula and let a ¯ ∈ A such that M ⊨ ∃ ⁡ y φ ( a ¯ , y ).
As A ⊆ M, A ⊆ N, we have M , N ⊨ T ∪ D ( A ), so by (iii) we have M ≡ L A N so N ⊨ ∃ ⁡ φ ( a ¯ , y ).
- (ii) ⟹ (i) We want to show quantifier elimination.
By Lemma 11.3, it is sufficient to show for φ ( x ¯ , y ) quantifier free, we can find ψ ( x ¯ ) quantifier free such that
T ⊨ ∀ ⁡ x ¯ ( ∃ ⁡ y , φ ( x ¯ , y ) ↔ ψ ( x ¯ ) ) .
Let L ∗ = L ∪ { c 1 , … , c n } where each c i is a new constant (with n = | x ¯ |). Let
Γ = { ψ ( x ¯ ) : ψ ( x ¯ ) quantifier free formula such that T ⊨ ∀ ⁡ x ¯ , ( ∃ ⁡ y , φ ( x ¯ , y ) → ψ ( x ¯ ) ) } .
In definable sets:
Claim: T ∪ Γ ⊨ ∃ ⁡ y , φ ( x ¯ , y ).
Proof: Suppose not. Then there is an L ∗-structure
N ⊨ T ∪ Γ ∪ { ¬ ⁡ ∃ ⁡ y , φ ( 𝜀 , y ) } .
Let a i = c i N, and let A ⊆ N be the substructure generated by a 1 , … , a n in N.
Then N ⊨ T, A ⊆ N, N ⊨ ¬ ⁡ ∃ ⁡ y , φ ( c ¯ , y ). Any b ∈ A is of the form t N ( a ¯ ) for an L-term t (exercise).
So D ( A ) can be viewed as an L ∗-structure by replacing b ̲ (b = t N ( a ¯ )) with t ( c ¯ ) in L ∗. Let
Σ = T ∪ D ( A ) ∪ { ∃ ⁡ y , φ ( x ¯ , y ) } .
IDEA: build M ⊨ Σ, M ⊨ T ∪ D ( A ) and M ⊨ ∃ ⁡ y , φ ( a ¯ , Y ), contradicting (ii).
Suffices to prove Σ is consistent.
Assume Σ is inconsistent. Then by compactness we have ψ 1 ( x ¯ ) , … , ψ n ( x ¯ ) quantifier free L-formulas with
  - ψ 1 ( c ¯ ) , … , ψ m ( c ¯ ) ∈ D ( A ).
  - T ∪ { ∧ ⁡ i = 1 m ψ i ( c ¯ ) } ∪ { ∃ ⁡ y , φ ( c ¯ , y ) } is unsatisfiable.
In definable sets:
Let ψ ( x ¯ ) be ¬ ⁡ ∧ ⁡ i = 1 m ψ i ( x ¯ ), then T ⊨ ∃ ⁡ y , φ ( c ¯ , y ) → ψ ( c ¯ ).
So T ⊨ ∀ ⁡ x ¯ ( ∃ ⁡ y , φ ( x ¯ , y ) → ψ ( x ¯ ) ) so ψ ( c ¯ ) ∈ Γ. So N ⊨ ψ ( c ¯ ) but also N ⊨ D ( A ) (A ⊆ N). Then
N ⊨ ∧ i = 1 m ψ i ( c ¯ ) ⏟ ∈ D ( A ) = ¬ ⁡ ψ ( c ¯ )
contradiction. So by compactness, Σ is consistent.
This proves the claim.
Reminder: the claim was that T ∪ Γ ⊨ ∃ ⁡ y , φ ( x ¯ , y ). So by compactness, there are ψ 1 ( x ¯ ) , … , ψ m ( x ¯ ) quantifier free such that
T ∪ { ψ ( c ¯ ) , … ⁡ , ψ m ( c ¯ ) } ⏟ ⊆ Γ ⊨ ∃ ⁡ y , φ ( x ¯ , y ) .
Recall
T ⊨ ∀ ⁡ x ¯ ( ∃ ⁡ y , φ ( x ¯ , y ) → ∧ i = 1 m ψ i ( x ¯ ) )
by choice of n. Let
ψ ( x ¯ ) = ∧ i = 1 m ψ i ( x ¯ ) .
Then
T ⊨ ψ ( c ¯ ) → ∃ ⁡ y , φ ( c ¯ , y )
hence
T ⊨ ∀ ⁡ x ¯ ( ψ ( x ¯ ) → ∃ ⁡ y , φ ( x ¯ , y ) ) .
Thus T ⊨ ∀ ⁡ x ¯ , ( ψ ( x ¯ ) ↔ ∃ ⁡ y , φ ( x ¯ , y ) ). □
cloze1: True

html: Theorem 12.1. ACF ⁡ has quantifier elimination.
proof: Proof. We will show that condition Theorem 11.4(iii) holds.
So we need to show that for any finitely generated A, T ∪ D ( A ) is complete.
Fix a finitely generated L-structure A and show ACF ⁡ ∪ D ( A ) is complete. Use Los-Vaught test. Fix K 1 , K 2 ⊨ ACF ⁡ ∪ D ( A ) uncountable, wiht | K 1 | = | K 2 |. A is a finitely generated integral domain contained in K 1 , K 2.
So since A contains 1, it determines the characteristic. So char ⁡ ( K 1 ) = char ⁡ ( K 2 ). So K 1 ≅ K 2 (in L rings).
Need an L A-isomorphism, i.e. an isomorphism Φ : K 1 → K 2 preserving A. Consider F i the fraction field of A in K i. The field of fractions of an integral domain is unique up to isomorphism, i.e. ∃ ⁡ τ : F 1 → F 2 preserves A pointwise.
A is finitely generated (hence finite trdeg ⁡), so trdeg ⁡ ( K 1 ∕ F 1 ) = trdeg ⁡ ( K 2 ∕ F 2 ). Therefore τ extends to τ ∗ : K 1 → K 2 fixing A pointwise. So K 1 ≅ L A K 2. □
cloze1: True

html: Definition 12.2 (Constructible). Let F be a field. We say that X ⊆ F n is constructible if it is a boolean combination of subsets of F n defined by p ( x 1 , … , x n ) = 0 for p ( x ¯ ) ∈ F [ x ¯ ].
nothing: True

html: Corollary 12.3 (Chevalley’s Theorem). Assuming that:
- K ⊨ ACF ⁡
- X ⊆ K n a constructible set
Then the projection
Y = { ( a 1 , … , a n − 1 ) ∈ K n − 1 : ( a ¯ , b ) ∈ X for some b ∈ K }
of X is also constructible.
proof: Proof. Option 1: Show R G ∪ D ( A ), with A a finite graph is complete.
Option 2: Use (ii) of Theorem 11.4. Fix M , N ⊨ R G, A ⊆ M ∩ N. Fix a quantifier-free formula φ ( x 1 , … , x n , y ), a ¯ ∈ A n. Assume that there exists b ∈ M, M ⊨ φ ( a ¯ , b ). Want to show ∃ ⁡ c ∈ N such that N ⊨ φ ( a ¯ , c ).
Write φ ( x ¯ , y ) in disjunction normal form:
∨ s = 1 k ∧ t = 1 l s 𝜃 s , t ( x ¯ , y )
where 𝜃 s , t ( x ¯ , y ) is atomic or negated atomic. There is some s ⊆ k such that M ⊨ ∧ ⁡ t = 1 l s 𝜃 s , t ( a ¯ , b ).
Each of 𝜃 s , t ( x ¯ , y ) is one of x i = x j, x i = y, E ( x i , x j ), E ( x i , y ) and negations.
If x i = y appears then b = a i ∈ A ⊆ N and so N ⊨ φ ( a ¯ , b ).
We may assume x i = y does not appear in 𝜃 s , t. Let
X = { a i : M ⊨ E ( a i , b ) } ⊆ a ¯ Y = { a i : M ⊨ ¬ ⁡ E ( a i , b ) } ⊆ a ¯
Then X and Y are finite and disjoint. So we have c ∈ N such that
N ⊨ E ( a i , c ) ∀ ⁡ a i ∈ X N ⊨ ¬ ⁡ E ( a i , c ) ∀ ⁡ a i ∈ Y c ∉ { a i , … , a n }
So N ⊨ ∧ ⁡ t = 1 l s 𝜃 s , t ( a ¯ , c ) and thus N ⊨ φ ( a ¯ , c ). □
nothing: True

html: Definition 12.4 (Rado graph). Let L = { E }, with E a binary relation. A Rado or Random graph is a graph ( V , E ) such that V ≠ ∅ and for any finite disjoint X , Y ⊆ V there is some v ∈ V such that:
- E ( v , x ) for all x ∈ X
- ¬ ⁡ ( v , y ) for all y ∈ Y
We denote the theory of Rado graphs as R C. It consists of
- Graph axioms (irreflexive and symmetric).
- For any k ≥ 1 and l ≥ 1,
∀ ⁡ x 1 , … , x k , ∀ ⁡ y 1 , … , y l ( ∧ i , j x i ≠ y j → ∃ ⁡ v ( ∧ i , j E ( v , x i ) ∧ ¬ ⁡ E ( v , y j ) ) ) .
nothing: True

html: Theorem 12.5. R G has quantifier elimination.
proof: Proof. Option 1: Show R G ∪ D ( A ), with A a finite graph is complete.
Option 2: Use (ii) of Theorem 11.4. Fix M , N ⊨ R G, A ⊆ M ∩ N. Fix a quantifier-free formula φ ( x 1 , … , x n , y ), a ¯ ∈ A n. Assume that there exists b ∈ M, M ⊨ φ ( a ¯ , b ). Want to show ∃ ⁡ c ∈ N such that N ⊨ φ ( a ¯ , c ).
Write φ ( x ¯ , y ) in disjunction normal form:
∨ s = 1 k ∧ t = 1 l s 𝜃 s , t ( x ¯ , y )
where 𝜃 s , t ( x ¯ , y ) is atomic or negated atomic. There is some s ⊆ k such that M ⊨ ∧ ⁡ t = 1 l s 𝜃 s , t ( a ¯ , b ).
Each of 𝜃 s , t ( x ¯ , y ) is one of x i = x j, x i = y, E ( x i , x j ), E ( x i , y ) and negations.
If x i = y appears then b = a i ∈ A ⊆ N and so N ⊨ φ ( a ¯ , b ).
We may assume x i = y does not appear in 𝜃 s , t. Let
X = { a i : M ⊨ E ( a i , b ) } ⊆ a ¯ Y = { a i : M ⊨ ¬ ⁡ E ( a i , b ) } ⊆ a ¯
Then X and Y are finite and disjoint. So we have c ∈ N such that
N ⊨ E ( a i , c ) ∀ ⁡ a i ∈ X N ⊨ ¬ ⁡ E ( a i , c ) ∀ ⁡ a i ∈ Y c ∉ { a i , … , a n }
So N ⊨ ∧ ⁡ t = 1 l s 𝜃 s , t ( a ¯ , c ) and thus N ⊨ φ ( a ¯ , c ). □
cloze1: True

html: Definition (L-formula with parameters from A). Given a language L, an L-structure M and a subset A ⊆ M, we call an L A-formula an L-formula with parameters from A.
Write these as φ ( x ¯ , a ¯ ) for φ ( x ¯ , y ¯ ) an L-formula, and a ¯ ∈ A (identify with a ̲ M).
nothing: True

html: Definition 13.2 (n-type). Let M be an L-structure and A ⊆ M. An n-type over A with respect to M is a set of L-formulas with parameters from A, in free variables x 1 , … , x n such that p ∪ T h A ( M ) is consistent.
An n-type is complete if for every L A-formula with n variables ϕ, either ϕ ∈ p or ¬ ⁡ ϕ ∈ p.
Let S n M ( A ) denote the set of all complete n-types over A with respect to M.
nothing: True

html: Definition 13.3 (t p M). Given a 1 , … , a n ∈ M, let t p M ( a 1 , … , a n ∕ A ) be the set of all L A-formulas ϕ ( x 1 , … , x n ) such that M ⊨ ϕ ( a 1 , … , a n ) (usually a i ∉ A).
t p M ( a ¯ ∕ A ) ∈ S n M ( A ) and a ¯ ⊨ t p M ( a ¯ ∕ A ).
nothing: True

html: Proposition 13.4. Assuming that:
- p ∈ S n M ( A )
Then there is N ≽ M with a ¯ ∈ N n such that p = t p N ( a ¯ ∕ A ).
proof: Proof. By assumption p ∪ T h A ( M ) is consistent.
Need to show p ∪ T h M ( M ) is consistent.
Fix Σ ⊆ p ∪ T h M ( M ) finite. Σ ⊆ p ∪ { φ 1 , … , φ t }, φ i an L M-sentence with M ⊨ φ i.
Let φ ∗ be ∧ ⁡ i = 1 t φ i, then φ ∗ can be written φ ∗ ( b 1 , … , b m ) where b 1 , … , b m ∈ M ∖ A and φ ∗ ( x 1 , … , x m ) an L A-formula.
Since M ⊨ φ ∗ ( b 1 , … , b m ) we get M ⊨ ∃ ⁡ v ¯ , φ ∗ ( v 1 , … , v m ), so ∃ ⁡ v ¯ φ ∗ ( v ¯ ) ∈ T h A ( M ).
So as T h A ( M ) ∪ p is consistent, we have N ⊨ T h A ( M ) ∪ p with
- c ¯ ∈ N m with N ⊨ φ ∗ ( c ¯ ).
- a ¯ ∈ N m with N ⊨ p ( a ¯ ).
Expand N to an L M-structure, i.e. let
- b i N = c i for i ∈ { 1 , … , m }.
- b ¯ N arbitary for b ∈ M ∖ ⟨ ( A ∪ { b 1 , … , b m } ) ⟩.
Then N ⊨ φ ( b 1 , … , b m ). So N ⊨ φ ∗, so N ⊨ Σ. □
cloze1: True

html: Definition. Let M be an L-structure, A ⊆ M. Given an L A-formula φ ( x 1 , … , x n ), define
[ φ ( x 1 , … , x n ) ] = { p ∈ S n M ( A ) : φ ( x 1 , … , x n ) ∈ p } .
cloze1: True

html: Theorem 14.1. S n M ( A ) is a totally disconnected compact Hausdorff space.
proof: Proof. Showing that it is a topology is left as an exercise.
Hausdorff: Fix p , q ∈ S n M ( A ) distinct. Then there is a φ ( x ¯ ) L A-formula such that φ ( x ¯ ) ∈ p and ¬ ⁡ φ ( x ¯ ) ∈ q. Then p ∈ [ φ ( x ¯ ) ] and q ∈ [ ¬ ⁡ φ ( x ¯ ) ] – these are disjoint.
Compactness: Sufficient to consider open covers consisting of basic open sets. SUppose we have L A-formulas ( φ i ( x ¯ ) ) i ∈ I such that S n M ( A ) = ⋃ ⁡ i ∈ I [ φ i ( x ¯ ) ]. Let Σ = { ¬ ⁡ φ i ( x ¯ ) : i ∈ I }.
Claim: Σ ∪ T h A ( M ) is inconsistent.
Proof of claim: Otherwise N ⊨ T h A ( M ), a ¯ ∈ N n such that a ¯ ⊨ Σ. Let p = t p N ( a ¯ ∕ A ) ∈ S n M ( A ). But p ∉ [ φ i ( x ¯ ) ] ∀ ⁡ i ∈ I, contradiction.
So by compactness we have finite I 0 ⊆ I with
{ ¬ ⁡ φ i ( x ¯ ) : i ∈ I 0 } ∪ T h A ( M ) (∗)
inconsistent.
Claim: S n M ( A ) = ⋃ ⁡ i ∈ I 0 [ φ i ( x ¯ ) ].
Proof: Fix p ∈ S n M ( A ). We can realise p in some N ⊨ T h A ( M ), i.e. we have a ¯ ∈ N n with a ¯ ⊨ p.
By (∗), we have N ⊨ φ i ( a ¯ ) for some i ∈ I 0. So φ i ( x ¯ ) ∈ p, so p ∈ [ φ i ( x ¯ ) ].
Totally disconnected: In a compact Hausdorff space, we have totally disconnected if and only if two points are separated by a clopen set. All basic sets are clopen, so totally disconnected. □
cloze1: True

html: Definition 15.3 (Partial elementary / homogeneous). Let M , N be L-structures, A ⊆ M, B ⊆ N. A function f : A → B is partial elementary if for every L-formulas φ ( x 1 , … , x n ) and a 1 , … , a n ∈ A we have
M ⊨ φ ( a ¯ ) ⟺ N ⊨ φ ( f ( a ¯ ) ) .
Given κ ≥ | L | + ℵ 0, M is κ-homogeneous if for any A ⊆ M with | A | < κ, any partial elementary map f A → M and any c ∈ M there is some d ∈ M with f ∪ { ( c , a ) } partial elementary. In other words, “partial elementary maps can be extended”.
nothing: True

html: Proposition 15.5. Assuming that:
- T a complete L-theory with infinite models
- M ⊨ T
Then M is ℵ 0-saturated if and only if M is ℵ 0-homogeneous and M realises all types in S n ( T ), n ≥ 1.
proof: Proof.
- ⇒ Assume M is ℵ 0-saturated. In particular, M realises all types in S n ( T ) (∅ is finite).
Fix some finite A ⊆ M, and a partial elementary map f : A → M. (Aim: find d ∈ M such that f ∪ { ( c , d ) } is partial elementary). Given c ∈ M, define p ∈ S 1 M ( f ( A ) ) to be such that
φ ( x , f ( a ¯ ) ) ⟺ M ⊨ φ ( c , a ¯ )
(for all φ ( y , x ¯ ) L-formulas and a ¯ ∈ A). Write p = f ( t p M ( c ∕ a ¯ ) ).
To show p ∈ S 1 M ( f ( A ) ), consider φ ( x , a ¯ ) ∈ p. Then M ⊨ φ ( c , a ¯ ), so M ⊨ ∃ ⁡ x , φ ( x , a ¯ ), os M ⊨ ∃ ⁡ φ ( x , f ( a ¯ ) ) as f is partial elementary.
So p is finitely satisfiable, and completeness follows from t p M ( c ∕ A ) being complete. So as M is κ-saturated we have d ⊨ p for some d ∈ M. Then f ∪ { ( c , d ) } is a partial elementary map.
- ⇐ Fix a 1 , … , a n ∈ M, p ∈ S 1 M ( { a 1 , … , a n } ). We want to show p is realised in M.
Set
q = { φ ( y , x 1 , … , x n ) : φ ( y , a ¯ ) ∈ p } ∈ S n + 1 M ( T ) .
So by assumption, we have d , b 1 , … , b n with ( d , b ¯ ) ⊨ q.
Consider t p ( a ¯ ∕ ∅ ) = t p ( b ¯ ∕ ∅ ). So f : b i → a i is partial elementary. Let c ∈ M such that f ∪ { ( d , c ) } is partial elementary. Then t p M ( c , a ¯ ) = t p M ( d , b ¯ ). So ( c , a ¯ ) ⊨ q and t p ( c ∕ a ¯ ) = p. □
cloze1: True

html: Lemma 15.6. Assuming that:
- T a complete L-theory with infinite models
- M ⊨ T
Then there is an N ≽ M with | N | ≤ | M | + | L | and N is ℵ 0-homogeneous.
proof: Proof. First claim: For any M ⊨ T, there is N ≽ M with | N | ≤ | M | + | L | and for any a ¯ , b ¯ , c from M such that a ¯ ≡ M b ¯ there is some d ∈ N with a ¯ c ≡ N b ¯ d.
Proof of claim: Enumerate all ( a ¯ , b ¯ , c ¯ ) as ( a ¯ α , b ¯ α , c ¯ α ) α ≤ | M |. Now let M 0 = M, and use transfinite induction to form a chain ( M α ) α < | M |.
- α is a limit ordinal: set M α = ⋃ ⁡ i < α M i (then | M α | ≤ | α | ( | M | + | L | ) = | M | + | L | as α ≤ | M |).
- Given α (not a limit ordinal), look at ( a α , b α , c α ). Assume a ¯ α ≡ M α b ¯ α so f α : a ¯ α → b ¯ α partial elementary. Then we apply Proposition 13.4 (Note the elementary super structure construnted here is of size ≤ | M | + | L |) to find M α + 1 ≽ M α with | M α + 1 | ≤ | M α | + | L | ≤ | M | + | L | with a d ∈ M α + 1 realising f α ( t p ( c α ∕ a α ) ). Then by construction, ( a ¯ α c ) ≡ M α + 1 ( b ¯ α d ).
Now let N = ⋃ ⁡ α < | M | M α. Note that we might have introduced new elements. Note | N | ≤ | M | ( | M | + | L | ) = | M | + | L |.
We build a new chain M = N 0 ≼ N 1 ≼ N 2 ≼ ⋯ of countably many steps with | N 1 | ≤ | M | + | L | and such that for any a ¯ , b ¯ , c ¯ ∈ N, if a ¯ ≡ M b ¯ then there is d ∈ N i + 1 such that a ¯ c ≡ N i + 1 b ¯ d. We do this by iterating the claim.
FInally let N = ⋃ ⁡ i < ℵ 0 N i. Then:
  - | N | ≤ | M | + | L |.
  - N is ℵ 0-homogeneous as any a ¯ , b ¯ , c from N lie in N i for some i.
□
cloze1: True

html: Definition 15.7 (Saturated). We say M is saturated if it is | M |-saturated.
nothing: True

html: Theorem 15.8. Assuming that:
- T a complete L-theory with infinite models
- L is countable
Then T has a countable saturated model if and only if S n ( T ) is countable for every n ≥ 1.
proof: Proof.
- ⇒ M ⊨ T countable, saturated.
  - M n is countable for all n ∈ ℕ.
  - We have a map p → a ¯ ⊨ p (p ∈ S n ( T ), a ¯ some realisation). This is map since M saturated, and injective (because complete types).
So S n ( T ) is countable.
- ⇐ Enumerate ⋃ ⁡ n ≥ 1 S n ( T ) = { p 1 , p 2 , p 3 , … }. Fix a countable M 0 ⊨ T, and build a chain M 0 ≼ M 1 ≼ M 2 ≼ ⋯ such that M i realises p i and is countable, using Proposition 13.4.
Get N = ⋃ ⁡ i ∈ ℕ M i. Then N ⊨ T and is countable. N realises all types over ∅.
Apply Lemma 15.6 to get M ≽ N countable and ℵ 0-homogeneous structure.
So by Proposition 15.5 is is ℵ 0-saturated. □
cloze1: True

html: Proposition 15.11. Assuming that:
- T a complete L-theory with infinite models
- M ≡ N are both countable and saturated
Then M ≅ N.
proof: Proof. Exercise (use back and forth argument). □
cloze1: True

html: Proposition 16.2. Assuming that:
- p ∈ S n M ( A ).
Then the following are equivalent:
- (i)
p is isolated
- (ii)
{ p } = [ φ ( z ) ] for some L A-formula φ ( x ¯ ). In this case we say φ ( x ¯ ) isolates p.
- (iii)
There is an L A-formula φ ( x ¯ ) ∈ p such that for any ψ ( x ¯ ) ∈ p,
T h A ( M ) ⊨ ∀ ⁡ x ( φ ( x ¯ ) → ψ ( x ¯ ) ) .
proof: Proof. (i) ⟺ (ii): Obvious.
(ii) ⟹ (iii): Assume φ ( x ¯ ) isolates p. Fix an L A-formula ψ ( x ¯ ). We want to show M ⊨ ∀ ⁡ x ¯ ( φ ( x ¯ ) → ψ ( x ¯ ) ). So suppose M ⊨ φ ( a ¯ ). Then t p M ( a ¯ ∕ A ) ∈ [ φ ( x ¯ ) ] = { p }.
So t p M ( a ¯ ∕ A ) = p, hence M ⊨ ψ ( a ¯ ).
(iii) ⟹ (ii): By assumption, for every L A-formula we have ψ ( x ¯ ) ∈ p, [ φ ( x ¯ ) ] ⊆ [ ψ ( x ¯ ) ]. Thus if q sin ⁡ [ φ ( x ¯ ) ], a ∈ [ ψ ( x ¯ ) ]. So ψ ( x ¯ ) ∈ q, so p ⊆ q, so p = q. □
cloze1: True

html: Proposition 16.3. Assuming that:
- T is complete and consistent
- p ∈ S n ( T ) is isolated
Then p is realised in every M ⊨ T.
proof: Proof. Fix p ∈ S n ( T ), isolated by φ ( x ¯ ). Fix M ⊨ T.
By Proposition 13.4, there is some N ≽ M realising p.
So N ⊨ ∃ ⁡ x ¯ φ ( x ¯ ), so M ⊨ ∃ ⁡ x ¯ φ ( x ¯ ).
Fix a ¯ ∈ M n such that M ⊨ φ ( a ¯ ). Then a ¯ ⊨ p as for any φ ( x ¯ ) ∈ p we have
M ⊨ ∀ ⁡ x ¯ ( φ ( x ¯ ) → ψ ( x ¯ ) ) .
So M ⊨ φ ( a ¯ ). □
cloze1: True

html: Theorem 16.4 (Omitting Types Theorem). Assuming that:
- L is countable
- p ∈ S n ( T ) is non-isolated
Then there is a countable M ⊨ T such that p is not realised in M (M omits p).
proof: Proof. Let L ∗ = L ∪ C, with C a countably infinite set of new constants.
An L ∗-theory has the witness property if for any L ∗-formula φ ( x ¯ ) there is a constant c ∈ C such that T ∗ ⊨ ∃ ⁡ x φ ( x ) → ψ ( c ).
Fact: Suppose T ∗ is a complete, satisfiable L ∗-theory with the witness property.
Define ∼ on C such that c ∼ d if and only if T ∗ ⊨ c = d. Let M = C ∕ ∼, and define an L ∗-structure on M such that:
- c M = [ c ]
- f M ( [ c 1 ] , … , [ c n ] ) = [ d ] if and only if
T ∗ ⊨ f ( c 1 , … , c n ) = d .
- R M = { ( [ c 1 ] , … , [ c n ] ) ∈ M n : T ∗ ⊨ R ( c 1 , … , c n ) }.
Then M is a well-defined L ∗-structure and M ⊨ T ∗.
Note we have M ⊨ φ ( [ c 1 ] , … , [ c n ] ) if and only if T ∗ ⊨ φ ( c 1 , … , c n ). We call M the Henkin model of T ∗.
Fix p ∈ S n ( T ) non-isolated.
Aim: build a complete, satisfiable L ∗-theory T ∗ ⊇ T, with the witness property, .
Such that for all c 1 , … , c n ∈ C there is some φ ( x ¯ ) ∈ p such that T ∗ ⊨ ¬ ⁡ φ ( c 1 , … , c n ). Then the Henkin model of T ∗ omits p.
Enumerate all the L ∗-sentences φ 0 , φ 1 , … and all c ( n = { c ¯ 1 , c ¯ 2 , … }. We build a satisfiable L ∗-theory T ∪ { 𝜃 1 , 𝜃 2 , … } such that
- (0) ⊨ 𝜃 i → 𝜃 j for all i > j.
- (0) (Completeness): Either ⊨ 𝜃 3 i + 1 → φ i or ⊨ 𝜃 3 i + 1 → ¬ ⁡ φ i.
- (0) (Witnessing property): If φ i is ∃ ⁡ v ψ ( v ) for some ψ and ⊨ 𝜃 3 i + 1 → φ i then ⊨ 𝜃 3 i + 2 → ψ ( c ) for some c. (check this does ensure the witness property).
- (0) (Omit p): ⊨ 𝜃 3 i + 3 → ¬ ⁡ ψ ( c i ) for some ψ ( x ¯ ) ∈ p.
Let 𝜃 0 be ∀ ⁡ v ( v = v ), and suppose we have 𝜃 0 , … , 𝜃 m.
Case 1: m + 1 = 3 i + 1 for some i.
If T ∪ { 𝜃 m , φ i } is satisfiable then 𝜃 m + 1 = 𝜃 m ∧ φ i. Otherwise 𝜃 m + 1 = 𝜃 m ∧ ¬ ⁡ φ.
So T ∪ { 𝜃 m + 1 } is satisfiable by construction.
Case 2: m + 1 = 3 i + 2 for some i.
Suppose φ i is ∃ ⁡ v , ψ ( v ) for some ψ an L ∗-formula, and ⊨ 𝜃 i → φ i (otherwise, let 𝜃 m + 1 = 𝜃 m).
Choose a c ∈ C not used in 𝜃 m. Let 𝜃 m + 1 be 𝜃 m ∧ ψ ( i ).
Exercise: check T ∪ { 𝜃 m + 1 } is satisfiable.
Case 3: m + 1 = 3 i + 3 for some i.
Let c ¯ i = ( c 1 , … , c n ). Without loss of generality assume x 1 , … , x n not used in 𝜃 m. We build an L-formula as follows:
- Replace c t by x t (t ∈ { 1 , … , n }).
- Replace any c ∈ C ∖ { c 1 , … , c n } by new variables v c and add ∃ ⁡ v c to the front.
Then φ ( x ¯ ) doesn’t isolated p.
By Proposition 16.2, there is some ψ ( x ¯ ) ∈ p with
T ⁄ ⊨ ∀ ⁡ x ( φ ( x ¯ ) → ψ ( x ¯ ) ) .
Let 𝜃 m + 1 be 𝜃 m ∧ ¬ ⁡ ψ ( c 1 , … , c n ). Check 𝜃 m + 1 is satisfiable.
TODO □
nothing: True

html: Definition 16.5 (Atomic, prime). Fix M ⊨ T.
- We say M is atomic if every n-type over ∅ realised in M is isolated.
- We say M is prime if for any N ⊨ T there is an elementary embedding M → N.
nothing: True

html: Theorem 16.6. Assuming that:
- L countable
Then the following are equivalent:
- (i)
T has a prime model.
- (ii)
T has an atomic model.
- (iii)
For all n ≥ 1, the isolated types are dense.
proof: None
cloze1: True

html: Theorem 16.7.
- (a)
Suppose | S n ( T ) | < 2 ℵ 0 for all n. Then T has a prime model and a countable saturated model.
- (b)
If T has a countable saturated model, then it has a prime model.
proof: None
cloze1: True

html: Theorem 16.9 (Ryll-Nardsewski / Engeler / Svenonius 59). Assuming that:
- L countable
- T is a complete L-theory with infinite models
Then the following are equivalent:
- (i) T is ℵ 0-categorical.
- (ii) For all n ≥ 1, every type in S n ( T ) is isolated.
- (iii) For all n ≥ 1, S n ( T ) is finite.
- (iv) For all n ≥ 1, the number of L-formulas with x 1 , … , x n free variables is finite, modulo T.
proof: None
nothing: True

html: Corollary 16.10. Assuming that:
- G an infinite group
- T h ( G ) is ℵ 0-categorical (in L groups)
Then G has finite exponent (there exists n ∈ ℕ such that ∀ ⁡ g ∈ G, g n = 1).
proof: None
cloze1: True

html: Theorem 17.3 (Fundamental Theorem of Stability (light)). The following are equivalent:
- (i)
T is stable.
- (ii)
No L-formula has the order property with respect to T.
- (iii)
For any M ⊨ T, every p ∈ S n ( M ) is definable.
- (iv)
Non-forking is an independence relation.
proof: None
nothing: True