MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Problem Set 10 — The Relative Independence of the Regularity Axiom

In this homework, we will show that the regularity axiom does not follow from the other axioms of set theory. Let ZFC^{−} be Zermelo-Fraenkel set theory with choice but without the regularity axiom. In other words, ZFC^{−} consists of the following axioms and axiom schemas:

1. Extensionality.  ∀A ∀B [∀x (x ∈ A ⟺ x ∈ B) ⇒ A = B].
2. Empty Set.  ∃B ∀x (x ∉ B).
3. Union.  ∀A ∃B ∀x [x ∈ B ⟺ ∃b (x ∈ b ∧ b ∈ A)].
4. Power Set.  ∀A ∃B ∀x (x ∈ B ⟺ x ⊆ A).
5. Infinity.  ∃A [∅ ∈ A ∧ ∀a (a ∈ A ⇒ a ∪ {a} ∈ A)].
6. Replacement Schema. ∀t_{1} … ∀t_{k} ∀A [\begin{matrix}∀x ∀y_{1} ∀y_{2} (ϕ(x, y_{1}) ∧ ϕ(x, y_{2}) ⇒ y_{1} = y_{2}) \\ ⇒ ∃B ∀y (y ∈ B ⟺ ∃x (x ∈ A ∧ ϕ(x, y)))]. \end{matrix}
7. Choice.  ∀A [\begin{matrix}∀x (x ∈ A ⇒ x ≠ ∅) ∧ ∀x ∀y (x ∈ A ∧ y ∈ A ∧ x ≠ y ⇒ x ∩ y = ∅) \\ ⇒ ∃C ∀x (x ∈ A ⇒ ∃w (C ∩ x = \{w\}))]. \end{matrix}

We have omitted the pairing axiom and the subset axiom schema from this list, because we have proved in Problems 7.8 and 7.9 that they are consequences of the replacement axiom schema.

The goal of this homework is to prove:

Theorem 1. If ZFC^{−} is consistent, then the regularity axiom does not follow from the axioms of ZFC^{−}.

Theorem 1 is half of an independence result. The other half states that ZFC^{−}, if consistent, does not imply the negation of the regularity axiom. We will show this latter statement in class. Thus, ZFC^{−} neither implies the regularity axiom nor its negation, and we say that the regularity axiom is independent of ZFC^{−}.

This kind of independence result is called a relative independence result, because we assume all along that ZFC^{−} is consistent. If ZFC^{−} were, in fact, inconsistent, then it would imply everything, including the regularity axiom. Since it is not known whether ZFC^{−} is really consistent (although most people hope so), the hypothesis cannot be dropped from Theorem 1.

We will now prove Theorem 1. The outline of the proof is as follows: suppose ZFC^{−} is consistent. Then there exists some universe 𝒰 of sets in which the ZFC^{−}-axioms hold. We will use 𝒰 to construct a different universe 𝒰′, and we will show that all the ZFC^{−}-axioms hold in 𝒰′, but the regularity axiom does not. Thus it follows that the ZFC^{−}-axioms do not imply the regularity axiom.

Definition. We say that a formula R(x, y) is a bijection from the universe 𝒰 onto itself if it satisfies the following conditions:

∀x ∀y ∀y′ (R(x, y) ∧ R(x, y′) ⇒ y = y′);
∀x ∀x′ ∀y (R(x, y) ∧ R(x′, y) ⇒ x = x′);
∀x ∃y R(x, y)
∀y ∃x R(x, y)

In other words, R is a function class that is one-to-one and onto the entire universe of sets. We will use a more convenient notation and write F (x) for the unique set y such that R(x, y). Of course, we also write F^{−1}(y) for the unique set x such that F (x) = y.

Problem 1 Verify that the formula

F (x) = \{ \begin{matrix}1 & if x = 0 \\ 0 & if x = 1 \\ x & if x ≠ 0 and x ≠ 1 \end{matrix}

defines a function class that is a bijection from the universe onto itself. Give two other examples of such bijections. ♣

Now let us fix some bijection F of the universe onto itself. We define the universe 𝒰′ as follows:

The sets of 𝒰′ are the same as the sets of 𝒰 . In particular, two sets are considered equal in 𝒰′ iff they are equal in 𝒰 . The element relation on 𝒰′, which we denote by ∈′, is defined by

x ∈′ y ⟺ x ∈ F (y).  (1)

Thus, x is considered to be an element of y in the universe 𝒰′ iff x is an element of F (y) in the universe 𝒰 .

Problem 2 Show that for any set x, one has x ∉′ F^{−1}(∅). Also show that, if F is the bijection from Problem , then ∅ ∈′ ∅. ♣

Now, if E(x_{0}, …, x_{k−1}) is any formula, then we write E′(x_{0}, …, x_{k−1}) for the formula obtained from it by changing ∈ to ∈′ throughout. We shall show that the universe 𝒰′ satisfies all the axioms of ZFC^{−}. This amounts to showing that whenever A is an axiom of ZFC^{−}, then A′ holds in 𝒰 .

Empty Set Axiom: To show that the empty set axiom holds in 𝒰′, we must show that

∃B ∀x (x ∉′ B).  (2)

Which set will work for B? In Problem , we have seen an example of ∅ ∈′ ∅, so that B = ∅ does not in general satisfy (2). However, from the first part of Problem , we know that for all sets x, x ∉′ F^{−1}(∅), and thus (2) is satisfied with B = F^{−1}(∅). Thus, F^{−1}(∅) is the “empty set” of 𝒰′, and we denote it by ∅′.

Extensionality Axiom:

Problem 3 Prove that 𝒰′ satisfies the extensionality axiom, i.e., prove that

∀A ∀B [∀x (x ∈′ A ⟺ x ∈′ B) ⇒ A = B]. ♣

Union Axiom: Let A be any set. We must show that there exists a set B such that x ∈′ B if and only if ∃b (x ∈′ b ∧ b ∈′ A).

Problem 4 Let c = ⋃_{b∈F (A)} F (b), and let B = F^{−1}(c). Prove that x ∈′ B iff x ∈ c iff ∃b (x ∈′ b ∧ b ∈′ A). Conclude that 𝒰′ satisfies the union axiom. ♣

Power Set Axiom: We first need to figure out what it means to be a subset in 𝒰′. By definition, x is a subset of A in 𝒰′, in symbols x ⊆′ A, if ∀z (z ∈′ x ⇒ z ∈′ A). The latter formula is equivalent to ∀z (z ∈ F (x) ⇒ z ∈ F (A)), that is, it is equivalent to F (x) ⊆ F (A).

Problem 5 Let c = {x | F (x) ⊆ F (A)}. Prove that c is a set. Let B = F^{−1}(c), and prove that

x ∈′ B ⟺ x ⊆′ A.

Conclude that the power set axiom holds in 𝒰′. ♣

Problem 6 The binary union, binary intersection, and singleton operations in 𝒰′ are defined as follows:

\begin{aligned}x ∪′ y & = & F^{−1}(F (x) ∪ F (y)), \\ x ∩′ y & = & F^{−1}(F (x) ∩ F (y)), \\ \{x\}′ & = & F^{−1}(\{x\}). \end{aligned}

Verify that these are indeed unions, intersections, and singletons in 𝒰′, i.e., show that

\begin{aligned}z ∈′ x ∪′ y & ⟺ & z ∈′ x ∨ z ∈′ y \\ z ∈′ x ∩′ y & ⟺ & z ∈′ x ∧ z ∈′ y \\ z ∈′ \{x\}′ & ⟺ & z = x. \end{aligned} ♣

Infinity Axiom: We define by recursion a map f with domain ω: f(0) = ∅′, and f(n^{+}) = f(n) ∪′ {f(n)}′. Let η be the range of f, and let A = F^{−1}(η).

Problem 7 Prove that the set A satisfies the infinity axiom in 𝒰′, i.e.,

∅′ ∈′ A and ∀a (a ∈′ A ⇒ a ∪′ {a}′ ∈′ A). ♣

Replacement Schema: Let A be a set and ϕ(x, y) be a formula such that ϕ′(x, y) defines a function class. Let c be the set of images of F (A) under this functional relation. Then

∀y (y ∈ c ⟺ ∃x (x ∈ F (A) ∧ ϕ′(x, y)).

If we let B = F^{−1}(c), then

∀y (y ∈′ B ⟺ ∃x (x ∈′ A ∧ ϕ′(x, y)).

Thus, the replacement schema holds.

Axiom of Choice: Suppose A is a set for which the hypothesis of the axioms of choice holds in 𝒰′, i.e.,

∀x (x ∈′ A ⇒ x ≠ ∅′) and ∀x ∀y (x ∈′ A ∧ y ∈′ A ∧ x ≠ y ⇒ x ∩′ y = ∅′)

hold. Let A_{1} be the set {F (x) | x ∈ F (A)}.

Problem 8 Prove that

∀x (x ∈ A_{1} ⇒ x ≠ ∅) and ∀x ∀y (x ∈ A_{1} ∧ y ∈ A_{1} ∧ x ≠ y ⇒ x ∩ y = ∅). ♣

In other words, A_{1} satisfies the hypothesis of the axiom of choice in 𝒰 . Since the axiom of choice holds in 𝒰 , there exists a set C_{1} such that

∀x (x ∈ A_{1} ⇒ ∃w (C_{1} ∩ x = {w})).

Since the last statement holds for all x, it also holds for F (x), so we get

∀x (F (x) ∈ A_{1} ⇒ ∃w (C_{1} ∩ F (x) = {w})).

Problem 9 Let C be the set F^{−1}(C_{1}). Prove that C_{1} ∩ F (x) = {w} iff C ∩′ x = {w}′. Also, prove that F (x) ∈ A_{1} iff x ∈′ A. ♣

So we have

∀x (x ∈′ A ⇒ ∃w (C ∩′ x = {w}′)),

which is the conclusion of the axiom of choice for 𝒰′. So 𝒰′ satisfies the axiom of choice.

Problem 10 Let 𝒰′ be the universe constructed as above from the bijection from Problem . Prove that 𝒰′ does not satisfy the regularity axiom. Hint: Recall that regularity implies that no set is a member of itself. Use Problem . ♣

Proof of Theorem 1: Suppose that ZFC^{−} is consistent. Take some universe 𝒰 of set theory in which the axioms of ZFC^{−} hold. Let 𝒰′ be constructed as in the previous problem. Then 𝒰′ satisfies all the axioms of ZFC^{−}, but not the regularity axiom. It follows that the axioms of ZFC^{−} do not imply the regularity axiom. □