Two Models of ¬∃tcl(x)

Martin Goldstern

September 1998

Let tcl(x) = {x} ∪ x ∪ ⋃ x ∪ ⋯ be the transitive closure of x. The usual proof that tcl(x) exists invokes the replacement axiom.

To show that some form of replacement is necessary, we give a model of ZC (i.e., ZFC except for the replacement axiom), in which there is a set which has no transitive closure.

(Note that the “usual” model of ZC, the sets of rank < α, satisfy ∀x ∃tcl(x).)

First model: Let κ = sup{κ_{n} : n ∈ ω}, where κ_{0} ≥ ℵ_{0} and 2^{κ_{n}} ≤ κ_{n+1} for all n. Define H(κ) as

H(κ) := {x : ∀n ≥ 0 |⋃^{n} x| < κ}

where ⋃^{0} x = x, ⋃^{n+1} x = ⋃(⋃^{n} x).

It is easy to see that H(κ) satisfies ZC. Let a := {κ_{0}, {κ_{1}}, {{κ_{2}}}, {{{κ_{3}}}}. Then a ∈ H(κ), but H(κ) ⊧ “there is no transitive set containing a.”

Second model: [suggested by Bernhard Bodenstorfer] For convenience we will work in the theory ZF C \ {Foundation} + ∃A = {a_{n} : n ∈ ℤ} ∀n : a_{n+1} = {a_{n}}, all a_{n} distinct. (The argument can be translated into ZFC.)

Let A = {a_{n} : n ∈ ℤ} be as above. For every ordinal α we define sets R_{α} (the “pure” sets) and M_{α}:

– R_{0} = ∅, M_{0} = A.

– R_{α+1} = 𝔓(R_{α}) = {x : x ⊆ M_{α}, x ∩ (M_{α} \ R_{α}) = ∅}

– M_{α+1} = {x : x ⊆ M_{α}, x ∩ (M_{α} \ R_{α}) is finite}

– M_{δ} = ⋃_{α<δ} M_{α}, R_{δ} = ⋃_{α<δ} R_{α} for δ a limit ordinal

Check that for any limit ordinal δ > ω we have M_{δ} ⊧ ZC, and M_{δ} ⊧ “a_{0} has no transitive closure”.

For example, to check the separation axiom, let B ∈ M_{α+1}. We show that every C ⊆ B is in M_{α+1}:

Let B_{0} = B∩R_{α}, B_{1} = B\B_{0}. So B_{1} is finite. Let C_{0} = C∩B_{0}, C_{1} = C∩B_{1}. Now C ⊆ R_{α} and C_{1} is a finite subset of M_{α} \ R_{α}, so C ∈ M_{α+1}.

Each model M_{α} will satisfy the axiom of foundation. This can be proved by induction. (Note that A ∉ M_{α}, for all α)