Set theory - chapter 1: Axioms of Set Theory

1.1

⇐ Trivial

⇒ Let $(a, b) = (c, d)$ . We shall use the axiom of extensionality to prove $a = c$ and $b = d$ . Suppose one of the pair contains the same elements, for instance $a = b$ . Then ${{c}, {c, d}}$ is equal to ${{a}}$ and so has one element. Hence ${c} = {c, d}$ and the same argument gives $c = d$ . Finally ${{a}} = {{c}}$ and $a = b = c = d$ . Otherwise, both sets have two elements. The elements of same cardinality are equal : ${a} = {c}$ and ${a, b} = {c, d}$ . The first equality gives $a = c$ . Using this in the second equal, we get $b = d$ .

1.2

Suppose that $℘ (X) \subseteq X$ . Since $X \in ℘ (X)$ we get $X \in X$ which contradicts the axiom of regularity : $S = {X}$ has no ∈-minimal element. Alternative proof (using result of chapter 3) : $∣ ℘ (X) ∣ \leq ∣ X ∣$ contradicts Cantor's theorem.

1.3

Let $X$ be inductive and $Y = \{x \in X| x \subseteq X\}$ . We shall show that $Y$ is inductive :

$\emptyset \in X$ and $\emptyset \subseteq X$ so $\emptyset \in Y$
Let $y \in Y$ then $y \in X$ and $y \subseteq X$ . Because $X$ is inductive, $y \cup {y} \in X$ . Moreover, $y \subseteq X$ and ${y} \subseteq X$ , hence $y \cup {y} \subseteq X$ . Consequently, $y \cup {y} \in Y$ .

If $n \in ℕ$ then for all inductive set $X$ , $n \in X$ . By the previous result, $Y_{X} = \{x \in X| x \subseteq X\}$ is inductive thus $n \in Y_{X}$ and $n \subseteq X$ . Hence, $n \subseteq ⋂ \{X| X is inductive\} = ℕ$ and $ℕ$ is transitive.

Now let $n \in ℕ$ and $Z_{n} = \{m \in ℕ| m < n\}$ . Clearly, $Z_{n} \subseteq n$ by definition of <. Conversely, $ℕ$ is transitive, $n \subseteq ℕ$ so $n \subseteq Z_{n}$ . Finally $n = Z_{n} = \{m \in ℕ| m < n\}$ .

1.4

Let $X$ be inductive and $Y = \{x \in X| x transitive\}$ . $\emptyset \in X$ and $\emptyset$ is transitive so $\emptyset \in Y$ . Let $y \in Y$ . Since X is inductive, $y \cup {y} \in X$ . If $z \in y \cup {y}$ the either $z \in y$ or $z = y$ . In the former case, $z \subseteq y$ by transitivity of $y$ so $z \subseteq y \cup {y}$ . In the latter case, $z = y \subseteq y \cup {y}$ . Hence we showed that $y \cup {y}$ is transitive and $y \cup {y} \in Y$ . Finally, $Y$ is inductive.

Let $n \in ℕ$ and $X$ be inductive. Then $n \in Y_{X} = \{x \in X| x transitive\}$ . Hence $n$ is transitive.

1.5

Let $X$ be inductive and $Y = \{x \in X| x transitive and x \notin x\}$ . We shall show that $Y$ is inductive :

$\emptyset \in Y$
If $y \in Y$ then as in 1.4 $y \cup {y}$ is transitive. Suppose $y \cup {y} \in y \cup {y}$ . Then $y \cup {y} \in y$ or $y \cup {y} = y$ . Because $y$ is transitive, the first case implies $y \cup {y} \subseteq y$ . In any case, we get $y \in y$ which is a contradiction. Hence $y \cup {y} \in Y$ .

Now let $n \in ℕ$ and $X$ be inductive. Then $n \in Y_{X}$ so $n \notin n$ . But $n \in n + 1 = n \cup {n}$ so $n \neq n + 1$ .

1.6

Let $X$ be inductive and $Y = {x \in X ∣ x is transitive and every nonempty z \subseteq x has an ∈-minimal element}$ . We shall show that $Y$ is inductive :

$\emptyset \in Y$
As in 1.4, if $y \in Y$ is transitive, then so is $y \cup {y} \in X$ . Let $z$ be a nonempty subset of $y \cup {y}$ . Suppose $z \ {y}$ is nonempty and let $e$ one of its ∈-minimal elements. Then $e$ is also ∈-minimal in $z$ for otherwise $y \in e \in y$ which contradicts the axiom of regularity. If $z \ {y} = \emptyset$ then obviously $z = {y}$ has an ∈-minimal element. Finally $y \cup {y} \in Y$ .

1.7

Let $X \subseteq ℕ$ be a nonempty set and $n \in X$ . If $n \cap X = \emptyset$ then $n$ is clearly a ∈-minimal element of $X$ and we are done.

Suppose that $n \cap X$ is nonempty. $ℕ$ is inductive and its elements are transitive by 1.4. The set of all $m \in ℕ$ such that every nonempty subset of $m$ has an ∈-minimal element is inductive, so is $ℕ$ itself. Hence the subset $n \cap X$ of $n$ has an ∈-minimal element $e$ . There is no $x \in X$ such that $x \in e$ , otherwise it would belong to $n \cap X$ by transitivity of $n$ . Finally $e$ is ∈-minimal in $X$ .

1.8

Let $X$ be inductive and $Y = \{x \in X| x = \emptyset \lor (\exists y x = y \cup {y})\}$ . We shall show that $Y$ is inductive :

$\emptyset \in Y$
If $y \in Y$ then $y \cup {y} \in X$ and consequently $y \cup {y} \in Y$

Hence $ℕ \subseteq Y$ and for all $n \neq 0$ there is $y$ such that $n = y \cup {y}$ . We have $y \in n \in ℕ$ so $y \in ℕ$ . Finally $n = y + 1$ .

1.9 (Induction)

Suppose $ℕ \neq A$ and let $x$ be ∈-minimal in $ℕ \ A$ (such an element exists by 1.7). $0 \in A$ so $x = y + 1$ for some $y \in ℕ$ . But $y \in A$ for otherwise $x$ would not be∈-minimal in $ℕ \ A$ . Thus $x = y + 1 \in A$ . A contradiction.

1.10

Let $A = \{n \in ℕ| n is T-finite\}$ . We shall show that $A = ℕ$ by induction (1.9) i.e. every set is T-finite.

$0 \in A$ . If $X$ is an non-empty subset of $℘ (\emptyset) = {\emptyset}$ , then $X = {\emptyset}$ and $\emptyset$ is ⊂-maximal in $X$ .
Let $n \in A$ and $X \subseteq ℘ (n + 1)$ a non-empty set. Let $e$ be a maximal element of the non-empty set $\{x \ {n}| x \in X\} \subseteq ℘ (n)$ . If $e$ is maximal in $℘ (n + 1)$ then we are done. Otherwise, let show that $f = e \cup {n}$ is maximal in $℘ (n + 1)$ . If $g \supseteq f$ then $g \ {n} \supseteq f \ {n} = e$ hence $g \ {n} = e$ by maximality of $e$ in $℘ (n)$ . Thus $g = e \cup {n} = f$ .

1.11

For all $n \in ℕ$ , $n + 1 = n \cup {n} ⋥ n$ shows that $n$ not maximal. Hence $ℕ \subseteq ℘ (ℕ)$ has no ⊂-maximal element i.e. $ℕ$ is T-infinite.

1.12

Let $f : S \to n$ be 1-1 onto. Let $X \subseteq ℘ (S)$ a non-empty set. Then $Y = \{f (x)| x \in X\} \subseteq ℘ (n)$ is non-empty and there exists a maximal $e \in Y$ . But $\forall x, y \in X (x \subseteq y \Leftrightarrow f (x) \subseteq f (y))$ . Hence $f_{- 1} (e)$ is ⊂-maximal in $X$ and $S$ is T-finite.

1.13

Let $S$ be infinite and $X = \{u \subseteq S| u is finite\}$ . $X$ is non-empty since $\emptyset \in X$ . Suppose $X$ has an ⊂-maximal element $e$ . Then $S \ e \neq \emptyset$ and there exists $x \in S \ e$ . Then $y = e \cup {x} ⊋ e$ . A contradiction. Then $S$ is T-infinite.

1.14

Let $X, p$ be two sets and $φ (u, p)$ be a formula. Let $F = \{(x, x)| φ (x, p)\}$ . By replacement, $F (X)$ is set. $\forall x (x \in F (X)) \Leftrightarrow (x \in X \land φ (x, p))$ and the separation axiom holds for $φ, X, p$ .

1.15

For (1.8), let $X, Y$ such that $\forall (x \in X) \forall (u \in x) u \in Y$ let $Z = \{u \in Y| (\exists x \in X u \in x)\}$ . Then $Z = ⋃ X$ .
For (1.9) consider $Z = \{u \in Y| u \subseteq X\}$ .
For (1.10) consider $Z = \{u \in Y| (\exists x \in X φ (x, u, p))\}$ .

This page is W3C-compliant - Author: Frédéric WANG