Model Theory + Logic

Created by Lukas Juhrich

#Mathematics

Atomic model: types are principal

…iff the complete type of any tuple is principal.

T5.3.3 ∃ctbl. atomic model

• -T complete, satisfiable
• w/ ctbl. many n-types ∀n
• ⇒ ∃ctbl. atomic model

L5.3.4 atomic model Uqness

A, B atomic (+same Th, cbtl.) ⇒ isomorphic

T5.2.7 A ctbl UP Πᵢ Aᵢ/𝒰 is ℵ₁-sat

(as long as the sig τ countable, as this provides that any 1-type looks like p={φ₁,φ₂,…})

C5.2.6

|τ|<ω, T sat ⇒ ∃ℵ₁-sat, 2^ℵ₀-sized model

P6.0.1 Atomic ctbl: Aut transitive on elements of same type

T5.3.2 Omitting ω nonpr. types

T5.3.1 + T has a ctbl. model omitting {p₁,p₂,…}

T5.2.2 Uqness

A, B Saturated (+same Th, same #) ⇒ isomorphic

L5.2.3 ∃ElExt realizing all 1-types

Proof idea(2): Show that finite subsets of „all 1-types are satisfied“ are satisfiable, then compactness.

T5.2.5 κ⁺-sat ElExt are reasonably small

Let κ≥|τ| infinite. Then
every ≤2^κ structure has a 2^κ-sized κ⁺-sat extension 

∃+ formulas

• No neg
• No ∀-quant

i.e., disjuncts of ∃x₁…xₙ (ψ₁ wedge … wedge ψₖ)

algebraic over B / acl_A(B)

a in A algebraic over B if it lies in some finite set defined by a unary τ\cup {B} Formula.

acl_A(B) := {a algebraic over B}

A has algebraicity if some finite B in A has nontrivial closure

converse: has no algebraicity = every finite subset is already algebraic in that sense (acl useless).

Algebraicity for ω-cat

Let M ω-cat, B in A finite. Then

acl_A(B) = {elements in finite orbits of Aut(A)_(B)}

Motivating example: roots = orbits under root permutation (clearly orbit finite)

T5.3.1 Omitting a nonpr. type

τ ctbl, T sat, p non-principal n-type.

Then T has a ctbl. model omitting p.

κ-saturated: Many 1-types realized

Age, Hom

• Age(C) = class of finite substructures(/iso)
• C homogeneous iff every iso of finite substructures extends to an Aut.

∀∃-formula

looks like ∀∀∀∀∀∀∃∃∃∃∃∃∃∃∃∃ψ

T6.0.3 (Ryll-Nardzewski) TFAE to ω-cat

Let B ctbly infinite, τ ctbl. Then TFAE:

T7.1.2 Hom-preservation

ψ ≡_T (sth ∃+) iff preserved under Homs

L6.2.2 B ω-cat has QE ⇔ B homogeneous

T5.2.4 ∃ SatMod

Every A has a κ-saturated EE (κ≥ω)

Amalg.Class

𝒞  is an Amalg. class iff

• ≤ω-many iso types
• Closed under taking the Amalgam (A,B₁,B₂)
• Closed under taking substructures

Age(C homog.) is an AmCl

T6.1.3 C Homog: strong amalg ⇔ no algebraicity

Frequent: ω-cat

principal n-type

p principal if implicationally generated by one formula: p = <φ> = {ψ| φ⇒ψ}

n-Types

Sets Σ…

1. of n-ary formulas ψ
2. satisfiable for some x in some model A

…of a model A(/B)

• n-Types of A: all φ which are possible in Th(A) (realized or not)
• of A_B: all φ possible in Th(A/B)
• Sₙ^A(B): complete n-Types of A_B

T7.1.8 (Chang-Łoś-Suszko)

T is ∀∃-axiomatizable iff Mod(T) closed under unions of chains

QE

T has QE iff for every φ, we have

T⊨∀xᵢ: φ(xᵢ)⇔ψ(xᵢ)

Where ψ quantifier-free

Behavior wrt B

If B grows…

• T_B can reference more constants
• A becomes „less homogeneous“, i.e.
• we can distinguish more things, and
• get more types

Free/Strong Amalgam

• free if no new relations added
• strong if nothing new glued together

T4.3.1 Fraisse

|τ|≤ω relational,𝒞  am.class. Then ∃homog. C such that Age(C)=𝒞.

Sₙ(T)

n-types Σ such that either φ or neg φ in Σ

Prototypical example: tp(x)={φ|A⊨φ(x)}

Topology w/ basis [φ]={Σ cont. φ}

T7.2.1 TFAE Model Completeness

• T model complete (every embedding is elementary)
• every φ is existential (mod T)
• Witnesses pull back through embeddings: For every A into B in Mod(T), every a in Aⁿ and φ existential, B⊨φ(e(a)) ⇒ A⊨φ(a)
• every ∃ is universal (mod T)
• every φ ıs universal (mod T)

L5.1.1 Comp + TotDisc

TODO show this

P7.2.2 T Model complete ⇒ ∀∃-axiomatizable

QE theories are model complete

κ-categoricity

A theory is κ-cat if it has models of all sizes ≤κ.

A model is κ-cat if its theory is.

These two things are interdefinable:

• A lattice (L, ∧, ∨)
• The underlying poset (L, ≤)

C6.0.4 Aut(A)=Aut(B) iff interdefinable

• A, B ω-cat
• same domain

Then Aut(A)=Aut(B) iff interdefinabe

L6.3.2: Interpreting preserves ω-cat

If

• A is ω-cat and
• B –(interprets)→ A  (w/FMP)

then B is ω-cat.

L5.0.1/2: Satis-criteria for Σ

Σ satisfiable iff finitely satisfiable (compactness).

Now, tfae for fixed model A:

1. Σ is an n-type of A
2. Σ is finitely realized in A
3. A has an ElExt realizing Σ

L7.6.2/3

T has QE iff

• Every ∃x.φ ≡ quantifier-free
• all models B₁, B₂ w/ common substructure A and a in Aⁿ, ψ(y,xᵢ) quant.free , B₁⊨∃y. ψ(y,a)⇒ B₂⊨ ∃y. ψ(y,a)

Interdefinable (same Domain)

A, B interdefinable iff every f/ every R is FO-definable in B

Stronger: “Biinterpretable”

iff ∃Isomorphism up to homotopy

Interpretation A-(I,d)→B

Interpretation (degree d) of B in A = partial surjection I: Aᵈ → B s.t.

I⁻¹R((a¹ᵢ)ᵢ, …, (aᵈᵢ)ᵢ) iff R(I(a¹ᵢ), …, I(aᵈᵢ))

is FO-definable for any atomically defined R.

B interpretable in A w/FMP (finitely many parameters) iff B interpretable in A + c₁,…,cₙ

Ex. of R⁻¹(I)

canonical:

• φ(x,y): x=y is always possible → yields relation =_I which is the kernel of I
• φ(x) : T must pull back to the domain, hence there must be a domain formula T_I(a¹,…,aᵈ)

Henkin Theory

Motto: Has Witnesses c for ∃x.φ(x)

A τ+ρ-theory T is Henkin if for every φ we have (∃x.φ(x)⇒φ(c)) in T for some c in ρ.

(c = witness for ∃x.φ(x), Henkin = witness exists)

Model companion

A model complete companion

P6.3.8 BiInt preserves „having Ess∞Sig“

Let B, C BiInt. Then B has Ess∞Sig iff C has Ess∞Sig.

Companion (eq.rel.)

T, T' companions iff T∀ = T'∀

T, T' companions iff their models inter-embed.

I◦J is interpretation

We can compose

A –(J, e)–→ B –(I, d)–→ C
⊢––(I◦J, de)––➚

and see that it satisfies the properties.

I₁ ~ I₂ (Homotopy)

A –(I₁,d₁)–→ B
A –(I₂,d₂)–→ B

are called homotopic if

„do (a₁¹, …, a₁ᵈ¹) and (a₂¹, …, a₂ᵈ²) interpret the same element?“

(arity d₁+d₂) is FO-Dble

Finitely complete (=maximally consistent)

P5.4.8 T extends to MaxHenkin T*

Define ρᵢ₊₁:= ρᵢ + {cᵩ|φ a τ+ρᵢ-formula}

Then define Tᵢ₊₁ := Tᵢ + {∃x.φ(x)⇒φ(cᵩ)}

Then Zorn-ify the consistent ⋃ᵢTᵢ to _maximally_ consistent T*

Deductive Axioms

Equality axioms (E1-E3) + equality of functions (E4) and relations (E5)

…(TAUT) is clear

D6.3.7 Ess. ∞ Signature

C has ess.∞.sig iff every relation interdefinable with it has an infinite signature

(i.e. finite „reduction“ is not possible!)

Preorder-equivalence: “Mutually interpretable”

T7.5.3 ftae ∃model companion

• T has a model companion
• all models of the Kaiser(T) are T-ec
• the class of T-ec structures has a fo axiomatization

Test

P6.3.6 A, B Biinterpretable ⇒ Aut(A)≅Aut(B)

L5.4.7 (∃ Model for T MaxHenkin)

Idea: T is so large, the consts are already a model!

Set: A = {constants in ρ}/(deduced equalities)

Structure: R([c₁],…,[cₙ]) := R(c₁,…,cₙ), f([cᵢ]) = the constant corresponding to ∃x.x=f(cᵢ)

Properties: A⊨φ iff φ in T

L5.2.8/9

Proof: Putting neg φ in Q3 gives the base. then apply „contrapositive“ tautology w/ MP

𝒪⁽ⁿ⁾:=ℕⁿ→ℕ

P6.3.4: SD closed under π, ∩, ∪

T6.3.2: X D ⇔ X, Xᶜ SD

(Theorem of the complement)

(μg)(x₁,…,xₙ)

Let g:ℕⁿ⁺¹→ℕ partial. Then

(μg)(xᵢ) = min {g(xᵢ,-) def. and =0}

Clone

≈Kartes. operad: Polys Xⁿ→X abg. unter…

• Projektionen πi
• Komposition

(μt≤z)X(xᵢ,t)

If X is primrec, then f(xᵢ,z) := (μt≤z)X(xᵢ,t) is as well.

Encoding function

∃ α: ℕ^(∞) →ℕ s.t. αⁿ in 𝒫ⁿ w/ post-inverses (βⁿ₁,…,βⁿₙ) each in 𝒫

T6.3.5 TFAE

Rec.Enum./(Semi-)Decidable sets

• X decidable (recursive) if 𝟙X in ℛ
• X sub ℕⁿ recursively enumerable (semiD) if X=π(Y), Y sub ℕⁿ⁺¹

PartRec

Like 𝒫, but with partial functions and closed under μ

TM

ℛ:=total PartRec

L6.1.11 Gödel Encoding

TODO Encoding, UTM, TM←→Rec correspondence, Halting

• λx. c
• λx,y. x+y
• λx,y. x∸y
• λx,y. x≠y
• λx,y. x<y
• λx. 2ˣ
• fibonacci duples δ(n) = (Fₙ,Fₙ₊₁)
• λx,y. x%y
• P(n):= n prime?
• ⇒ λn. π(n) := nth prime
• (finite) Sums of 𝒫-functions

LOOP-Programs

PrimRec: 𝒫 (⊂ 𝒪)

sub-clone w/ nil, suc and primrec ρ(g,h)

• clone
• λ.0 in 𝒫
• λx.x+1 in 𝒫
• ρ(g,h): g(xᵢ), h(xᵢ,y,f) give ρ(g,h)=f via
  • f(-,0):=g(-)
  • f(-,n+1):=g(-,f(n),n)

𝒫-sets {X | 𝟙X in 𝒫} sub ℕⁿ are BoolAlg

f dom g: g(xᵢ) ≤ f(‖xᵢ‖) a.e.

Ackermann ξ(n,x)

Case distinction by 𝟙-PoU

• ℬₙ := {stuff dom by ξₙ-iterates ξₙᵏ}
• ℬ = cupₙ  ℬₙ

T6.1.22 ξ not in 𝒫

• Assume λx.ξₓ(2x) in 𝒫
• Then ∃n,k s.t. ξₓ(2x)≤ξᵏₙ(x) a.e.
• But for large enough x, ξₙ₊₁(x+k) is both a strict LB (LHS) and an UB (RHS)

𝒫 subs ℬ

…b/c ξₓ(2x) grows too fast

• ∀n, k we have ξₙ₊₁(x+k)<ξₓ(2x) a.e.
• All f in 𝒫 are dominated by ξ however

PA₀

PA

For all φ(v₀,(vᵢ)), add

∀vᵢ. (φ(-,vᵢ) inductive ⇒ φ(-,vᵢ) true)

TODO PA, Σ₁, Incompleteness

Σ₁-formulas

contains

• QFree formulas

closed under

• ∃x
• ∧
• ∨
• ∀x<t.