Set theory - Chapter 1: Axioms of Set Theory

Suppose $(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, the two 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$. Conversely, it is clear that if $a=c$ and $b=d$ we have $(a,b)=(c,d)$.

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

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

1. (1)

   $\emptyset\in X$ and $\emptyset\subseteq X$ so $\emptyset\in Y$

2. (2)

   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\mathbb{N}$ 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\bigcap\{X:X\text{ is inductive}\}=\mathbb{N}$ and $\mathbb{N}$ is transitive.

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

Let $X$ be inductive and $Y=\{x\in X:x\text{ is 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\}$ then 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\subseteq y\cup\{y\}$ too. Hence $y\cup\{y\}$ is transitive and $y\cup\{y\}\in Y$. Finally, $Y$ is inductive.

Let $n\in\mathbb{N}$ and $X$ be inductive. Then $n\in Y_{X}=\{x\in X:x\text{ is transitive}\}$. Hence $n$ is transitive.

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

1. (1)

   $\emptyset\in Y$

2. (2)

   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\mathbb{N}$ 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$.

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

1. (1)

   $\emptyset\in Y$

2. (2)

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

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

Suppose that $n\cap X$ is nonempty. $\mathbb{N}$ is inductive and its elements are transitive by exercise 1.4. The set of all $m\in\mathbb{N}$ such that every nonempty subset of $m$ has an $\in$-minimal element is inductive, so this set is $\mathbb{N}$ itself. Hence the subset $n\cap X$ of $n$ has an $\in$-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 $\in$-minimal in $X$.

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

1. (1)

   $\emptyset\in Y$

2. (2)

   If $y\in Y$ then $y\cap\{y\}\in X$ and consequently $y\cap\{y\}\in Y$.

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

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

Let $A=\{n\in\mathbb{N}:n\text{ is }T-\text{finite}\}$. We shall show that $A=\mathbb{N}$ by induction (exercise 1.9) i.e. every set is $T$-finite.

1. (1)

   $0\in A$. If $X$ is an non-empty subset of $\operatorname{\mathcal{P}}(\emptyset)=\{\emptyset\}$, then $X=\{\emptyset\}$ and $\emptyset$ is $\subseteq$-maximal in $X$.

2. (2)

   Let $n\in A$ and $X\subseteq\operatorname{\mathcal{P}}(n+1)$ a non-empty set. Let $e$ be a maximal element of the non-empty set $\{x\setminus\{n\}:x\in X\}\subseteq\operatorname{\mathcal{P}}(n)$. If $e$ is maximal in $\operatorname{\mathcal{P}}(n+1)$ then we are done. Otherwise, let’s show that $f=e\cup\{n\}$ is maximal in $\operatorname{\mathcal{P}}(n+1)$. If $g\supseteq f$ then $g\setminus\{n\}\supseteq f\setminus\{n\}=e$ hence $g\setminus\{n\}=e$ by maximality of $e$ in $\operatorname{\mathcal{P}}(n)$. Thus $g=e\cap\{n\}=f$.

For all $n\in\mathbb{N}$, $n+1=n\cup\{n\}\subsetneq n$ shows that $n$ is not maximal. Hence $\mathbb{N}\subseteq\operatorname{\mathcal{P}}(n)$ has no $\subseteq$- maximal element i.e. $\mathbb{N}$ is $T$-infinite.

Let $f:S\rightarrow n$ be 1-1 onto. Let $X\subseteq\operatorname{\mathcal{P}}(S)$ a nonempty set. Then $Y=\{f(x):x\in X\}$ is nonempty and there exists a maximal element $e\in Y$. But $\forall x,y\in X,(x\subseteq y\iff f(x)\subseteq f(y))$. Hence $f_{{-1}}(e)$ is $\subseteq$-maximal in $X$ and $S$ is $T$-finite.

Let $S$ be infinite and $X=\{u\subseteq S:y\text{ is finite}\}$. $X$ is nonempty since $\emptyset\in X$. Suppose $X$ has an $\subseteq$-maximal element $e$. Then $S\setminus e\neq\emptyset$ and there exists $x\in S\setminus e$. Then $y=e\cup\{x\}\supsetneq e$. A contradiction. Finally, $S$ is $T$-infinite.

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

1. (1)

   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=\bigcup X$.

2. (2)

   For (1.9) consider $Z=\{u\in Y:u\subseteq X\}$.

3. (3)

   For (1.10) consider $Z=\{u\in Y:\exists x\in X,\varphi(x,u,p)$.