ZF C_{0} ≠ ZF C_{α_{0}} ≠ ZF C_{ℵ_{1}} ≠ ZF C_{st}

NATE ACKERMAN

Date: March 6, 2002.

So, the topic of todays talk is non-standard models of set theory. In particular we will try and prove ZF C_{0} ⊊ ZF C_{ℵ_{0}} ⊊ ZF C_{ℵ_{1}} ⊊ ZF C_{st}. [comment on choice and how we only use it for the Downwardd Lowenhiem Skolem Theorem, but we could get around this using a result from Paris. However I have time to read through this one (i.e. ∀T ⊃ ZF has a DO model)] or at least as much of it as we can before we run out of time. Now, before we begin we will need to define some basic concepts.

Definition 0.1. If \underline{M} = ⟨M, E⟩ is a structure for L_{ZF}

(i): an element a ∈ M is \underline{standard (for M)} if ¬∃⟨a_{i}⟩_{i∈ω} s.t. (∀i)a_{i} ∈ M ∧

a_{i+1}Ea_{i}(a_{0} = a) (ii): \underline{M is standard} if all of its elements are standard (non-standard o.w.). (iii): sp(M) = \{a ∈ M|a is standard\} is the \underline{standard part of M}

Definition 0.2. we say \underline{M}⊧ ZF is in reduced form if sp(\underline{M}) is a transitive ∈- structure. (i.e. a ∈ sp(M) ⇒ a ⊆ sp(M))

Now, there is a well known theorem by Mostrowski (that I won’t prove).

Theorem 0.3 (Mostowski’s Collapsing Lemma). If \underline{M} = ⟨M, E⟩ models [a ≠ b ↔ (∃c) s.t. (cEA)∧ ≠ (cEb) or vise versa ] then \underline{M} is standard iff \underline{M} is isomorphic to a transitive ∈-structure \underline{M′} uniquely determined by \underline{M}.

So, by the Mostowski Collapsing Lemma, we can assume w/o loss of generality that all models of ZF C are in reduced form.

Definition 0.4. Now, we say a formula ϕ(x) \underline{defines an ordinal in M} if M ⊧ ∃αϕ(α). If in addition α s.t. M ⊧ ϕ(α) is standard, M is called ϕ(x)-standard.

Further, if ϕ(x) defines an ordinal in every model of ZF, then \underline{ZF_{ϕ}} is the collection of sentences true in all ϕ-standard models of ZF (and ZF_{st} is the same for all standard models of ZF. And let ϕ-SM be the 1st order sentence that says ∃ a ϕ-standard model of set theory (and similarly for SM). ”MOD” says ∃ a model of set theory.

Definition 0.5. We say \underline{N} is an end extension of \underline{M} (\underline{N} ⊆_{e} \underline{M}) if (∀a ∈ M)(∀b ∈ N) if (b ∈ a)^{N} then b ∈ M (draw picture).

It can be shown that if φ is Σ_{1}, M ⊧ φ(a_{1}, ⋯ a_{n}) ⇒ N ⊧ φ(a_{1} ⋯ a_{n}).

We can now prove the first of our inequalities.

Theorem 0.6. MOD ∈ ZF C_{ℵ_{0}} − ZF C_{0}. (If ZF C_{0} is consistent)

Proof. As ZF C_{0} is consistent, there is some number theoretic formula s.t. con(ZF C_{0}) leftrightarrow MOD. And further, MOD ∉ ZF C_{0} (by Godel).

Now let \underline{M} be ℵ_{0}-standard. So, the natural numbers of \underline{M} are just the real natural numbers, and because \underline{M} ⊧ ZF C, M ⊧ con(ZF C_{0}). So M ⊧ MOD. And therefore, because M was an arbitrary ℵ_{0}-standard model, MOD∈ ZF C_{ℵ_{0}} − ZF C_{0}.

Now that we have some feel for non-standard models, we can try a harder theorem.

Theorem 0.7. (i): Every ℵ_{1}-standard model of ZF C in reduced form contains an element of its domain which is an ℵ_{0}-standard model of ZF C_{0}

ZF C_{0} ≠ ZF C_{α0} ≠ ZF C_{ℵ1} ≠ ZF C_{st} 3

(ii): If ∃ an ℵ_{0}-standard model of ZF C then ZF C_{ℵ_{0}} ⊊ ZF C_{ℵ_{1}} (iii): If ZF C + ℵ_{0}-SM is consistent then ZF C + ℵ_{0}-SM ⊬ ℵ_{1}-SM.

Proof. (i): Now, by downward Lowenheim Skolem we know ZF C ⊢ ℵ_{0}-SM ↔ ”∃ a countable ℵ_{0}-standard model of ZF C” (This is the reason we use ZF C and not ZF. As i mentioned this can be gotten around.)

Now a countable model can be coded by a set of natural numbers. Specifically, if dom(M) = ω, then ∈^{M}⊆ ω ×ω and completely determines the model.

So we can define Mod ⊆ P (ω) s.t. a ∈ Mod ⇔”a is a code for a countable model of ZF C”.

Now, because we know by Mostowski that the satisfaction predicate is arithmetic (which I wont prove here) and that Mod is hyperarithmatic.

Further we get ”M is ℵ_{0}-standard countable model of ZF C” ⇔ ”∃ isomorphism from ⟨ω, ∈⟩ onto ⟨F in_{M}, E|_{F in_{M}} ⟩ where F in_{M} = {a ∈ M|M ⊧ ”a is a finite ordinal”}.

and if M is coded as a set of natural numbers, this isomorphism can also be coded by a set of natural numbers.

So, we can define a hyperarithmatic set Mod^{∗} ∈ P (ω) × P (ω) s.t.

⟨a, b⟩ ∈ Mod^{∗} ⇔ a, b ⊆ ω, a is the code of a countable model of ZF C and b codes an isomorphism from ω to ω of this model.

And so, ZF C ⊢ ℵ_{0}-SM ↔ (∃a ⊆ ω)(∃b ⊆ ω)(⟨a, b⟩ ∈ Mod^{∗}) which is Σ_{1}^{1}.

Now, we will complete the proof of this part of the theorem by showing that ℵ_{1}-standard models are absolute for Σ_{1}^{1} formulas (i.e. φ ⊢ Σ_{1}^{1} then φ is true ⇔ (φ is true)^{N} if N is a ℵ_{1}-standard model).

And so, if ∃Nℵ_{1}-standard model, N is ℵ_{0} -standard and so ℵ_{0}-SM is true and hence true in N.

\underline{Claim} if N is ℵ_{1}-standard, φ is Σ_{1}^{1}, then [φ is true ⇔ (φ is true)^{N}] Assume N is in reduced form. ⇐ let φ ↔ (∃x_{1} ⊆ ω)(∃x_{2} ⊆ ω) ⋯ (∃x_{n} ⊆ ω)ϕ(x_{1}, x_{2} ⋯ x_{n}) where ϕ has only number quantifiers. Now, (∃a_{i} ⊆ ω)^{N} s.t. N ⊧ ϕ(a_{1}, ⋯ a_{n}) but as N is ℵ_{0}-standard this means the a_{i}’s are standard and so ϕ(a_{1}, ⋯ a_{n}) is true in the real universe. And therefore φ is also.

⇒ By a result of Mostowski (again), we know that to every Σ_{1}^{1}-statement φ there corresponds an arithmatical predicate F_{φ} which codes a liniar ordering on ω such that ZF C ⊢ φ ↔ ”F_{φ} is not a well ordering”

Now suppose φ is true but N ⊧ ¬φ. So, F_{φ} does not code a well ordering of ω but ω^{ω} ⊧ ”F_{φ} codes a well ordering of ω”.

So, N ⊧”there is an isomorphism between the ordering coded by F_{φ} and some countable ordinal.”

Now, since N is ℵ_{1}-standard in reduced form, every countable ordinal in N is a real countable ordinal. And also, because F_{φ} is arithmetic, it is absolute for ℵ_{0}-standard models. Therefore there really does exists an isomorphism between the ordering coded by F_{φ} and a countable ordering. But this contradicts the assumption that φ is true.

(ii): If ∃ℵ_{0}-standard model, but no ℵ_{1}-standard model we are trivially done. So, assume ∃ℵ_{1}-standard model. Now, using the coding in part (i) we can define a hyperarithmatic predicate ϕ(x, y) such that

ϕ(a, n) ↔ ”a ⊆ ω is the code of a countable ℵ_{0}-standard model M and n is the godel number a f sentence φ of L_{ZF} s.t. M ⊧ φ”

(because satisfaction is hyperarithmatic )

So ⌜θ⌝ ∈ ZF C_{ℵ_{0}} ↔ (∀a ⊆ ω)a ∈ Mod → ϕ(a, ⌜θ⌝) which is clearly a Π_{1}^{1}- sentence.

Now assume ZF C_{ℵ_{0}} = ZF C_{ℵ_{1}} to get a contradiction. From the above and Godel’s theorems, there is a Π_{1}^{1}-predicate P f_{ZF C_{ℵ_{1}}} (x) which says ”the sentence with Godel number x is provable from the sentences of ZF C_{ℵ_{1}}

And so, by the fixed point theorem we know ∃ψ a formula of L_{ZF C} s.t. ZF C_{ℵ_{1}} ⊢ ψ ↔≠ P f_{ZF C_{ℵ_{1}}} (⌜ψ⌝)

Now, since we are assuming ∃ a ℵ_{1}-standard model (N) if θ is Π_{1}^{1} then θ holds iff ⌜θ⌝ ∈ ZF C_{ℵ_{1}}

Hence ⌜ψ⌝ ∈ ZF C_{ℵ_{1}} iff ¬P f_{ZF C_{ℵ_{1}}} (⌜ψ⌝) ∈ ZF C_{ℵ_{1}} iff ¬P f_{ZF C_{ℵ_{1}}} (⌜ψ⌝) iff ⌜ψ⌝ ∉ ZF C_{ℵ_{1}} ⇒⇐

and so ZF C_{ℵ_{0}} ≠ ZF C_{ℵ_{1}}.

(iii): As we proved in (i) any ℵ_{1}-standard model of ZF C is a model of ZF C+ℵ_{0}- SM and so ZF C ⊢ ℵ_{1}-SM → ”ZF C + ℵ_{0}-SM is consistent” So, if ZF C + ℵ_{0}-SM⊢ ℵ_{1}-SM it follows ZF C + ℵ_{0}-SM⊢ ”ZF C + ℵ_{0}-SM is consistent” and so ZF C + ℵ_{0}-SM is inconsistent by Godel.

It is also worth noting that Suzuki was able to show that ZF C_{ℵ_{1}} is a strictly Π_{2}^{1} set, and hence can’t equal the Π_{1}^{1} set ZF C_{ℵ_{0}}.