$ \newcommand{\func}{\operatorname} \newcommand{\lcm}{\func{lcm}} \newcommand{\hl}[1]{\textbf{#1}} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\f}[1]{\left\lf #1 \right\rf} \newcommand{\bb}[1]{\left( #1 \right)} \newcommand{\Sb}[1]{\left\lbrack #1 \right\rbrack} \renewcommand{\ss}[1]{\left\lbrace #1 \right\rbrace} \renewcommand{\mod}[1]{\left\lvert #1 \rightrvert} \newcommand{\R}{\boldsymbol{R}} \newcommand{\C}{\boldsymbol{C}} \newcommand{\Z}{\boldsymbol{Z}} \newcommand{\Q}{\boldsymbol{Q}} \renewcommand{\P}{\mathbb{P}} \newcommand{\Po}{\mathcal{P}} \newcommand{\F}{\mathcal{F}} \newcommand{\Zz}{\Z_{\geq 0}} \renewcommand{\c}[1]{\left\langle #1 \right\rangle} \renewcommand{\mod}[1]{\left\lvert #1 \right\rvert} \newcommand{\norm}[1]{\left\lVert #1 \right\rVert} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\eqbreak}{\phantom{{} = {}}} \newcommand{\impliesbreak}{\phantom{{} \implies {}}} \newcommand{\iffbreak}{\phantom{{} \iff {}}} \newcommand{\del}{\partial} \renewcommand{\d}[1]{\, \mathrm{d} #1} \newcommand{\dydt}{\frac{\d{y}}{\d{t}}} \newcommand{\dydx}{\frac{\d{y}}{\d{x}}} \newcommand{\pd}[2]{\frac{\del #1}{\del #2}} \newcommand{\pp}[3]{\frac{\del^2 #1}{\del #2 \del #3}} \newcommand{\dd}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}} \newcommand{\Inn}{\func{Inn}} \newcommand{\Aut}{\func{Aut}} \newcommand{\diag}{\func{diag}} \newcommand{\id}{\func{id}} \newcommand{\GL}{\func{GL}} \newcommand{\SL}{\func{SL}} \newcommand{\End}{\func{End}} \newcommand{\Hom}{\func{Hom}} \newcommand{\Tr}{\func{Tr}} \newcommand{\rank}{\func{rank}} \newcommand{\ORD}{\mathbf{ORD}} \newcommand{\OD}{\mathbf{OD}} \newcommand{\HOD}{\mathbf{HOD}} \newcommand{\ZF}{\mathsf{ZF}} \newcommand{\ZFC}{\mathsf{ZFC}} \newcommand{\ZC}{\mathsf{ZC}} \renewcommand{\AC}{\mathsf{AC}} \newcommand{\DC}{\mathsf{DC}} \newcommand{\CC}{\mathsf{CC}} \newcommand{\CH}{\mathsf{CH}} \newcommand{\SH}{\mathsf{SH}} \newcommand{\KH}{\mathsf{KH}} \newcommand{\GCH}{\mathsf{GCH}} \newcommand{\PA}{\mathsf{PA}} \newcommand{\BST}{\mathsf{BST}} \newcommand{\MA}{\mathsf{MA}} \newcommand{\Con}{\func{Con}} \newcommand{\ON}{\mathbf{ON}} \newcommand{\dom}{\func{dom}} \newcommand{\ran}{\func{ran}} \newcommand{\pred}{\func{pred}} \newcommand{\mos}{\func{mos}} \newcommand{\WF}{\mathbf{WF}} \newcommand{\type}{\func{type}} \newcommand{\V}{\mathbf{V}} \renewcommand{\L}{\mathcal{L}} \newcommand{\cl}{\func{cl}} \newcommand{\trcl}{\func{tc}} \newcommand{\TC}{\func{TC}} \newcommand{\A}{\mathfrak{A}} \newcommand{\B}{\mathfrak{B}} \newcommand{\add}{\func{add}} \newcommand{\cov}{\func{cov}} \newcommand{\non}{\func{non}} \newcommand{\cf}{\func{cf}} \newcommand{\forces}{\Vdash} \newcommand{\one}{\mathbbm{1}} \newcommand{\restrictedto}{\mathord{\upharpoonright}} \newcommand{\Fn}{\func{Fn}} \newcommand{\Col}{\func{Col}} \newcommand{\bigtriangle}{\triangle} \newcommand{\U}{\mathcal{U}} \newcommand{\W}{\mathcal{W}} \newcommand{\N}{\mathcal{N}} \newcommand{\Seq}{\mathit{Seq}} \newcommand{\lh}{\func{lh}} \newcommand{\Ult}{\func{Ult}} \newcommand{\In}{\func{In}} \newcommand{\otp}{\func{otp}} \newcommand{\symdiff}{\, \triangle \,} \newcommand{\crit}{\func{crit}} \newcommand{\sat}{\func{sat}} \renewcommand{\int}{\func{int}} \newcommand{\length}{\func{length}} \newcommand{\Lim}{\func{Lim}} \newcommand{\Succ}{\func{Succ}} \newcommand{\G}{\mathcal{G}} \newcommand{\T}{\mathcal{T}} \newcommand{\ext}{\func{ext}} \newcommand{\height}{\func{height}} \renewcommand{\diamond}{\diamondsuit} \newcommand{\D}{\mathcal{D}} \newcommand{\NS}{\mathrm{NS}} $
Exercise 1.1.
Solution. $\impliedby$ is clear. For $\implies$, suppose $(a,b) = \lbrace \lbrace a\rbrace,\lbrace a,b\rbrace\rbrace = \lbrace \lbrace c\rbrace,\lbrace c,d\rbrace\rbrace = (c,d)$. Then $\lbrace a\rbrace \in \lbrace \lbrace c\rbrace,\lbrace c,d\rbrace\rbrace$, so $\lbrace a\rbrace = \lbrace c\rbrace$ or $\lbrace a\rbrace = \lbrace c,d\rbrace$. We consider two cases.- If $c = d$, then either way we have $\lbrace a\rbrace = \lbrace c\rbrace$, so we have $a = c$. We see that in this case, $\lbrace \lbrace a\rbrace,\lbrace a,b\rbrace\rbrace = \lbrace \lbrace c\rbrace\rbrace$. Then $\lbrace a,b\rbrace = \lbrace c\rbrace = \lbrace a\rbrace$, so $\lbrace a,b\rbrace \subseteq \lbrace a\rbrace \implies b = a$. Hence $a = b = c = d$.
- If $c \neq d$, then we must have $\lbrace a\rbrace = \lbrace c\rbrace$ and $\lbrace c\rbrace \neq \lbrace c,d\rbrace$. This also implies that $\lbrace a,b\rbrace = \lbrace c,d\rbrace$. Since $a = c$, ($b = c$ or $b = d$) and $c \neq d$, we must have $b = d$.
$\square$
Exercise 1.2.
Solution. If such an $X$ exists, then $X \in P(X) \subseteq X$, contradicting Axiom of Regularity (see Page 63 of the textbook).$\square$
Exercise 1.3.
Solution. Let $Y := \lbrace x \in X : x \subseteq X\rbrace$. Since $X$ is inductive, $\emptyset \in X$ and $\emptyset \subseteq X$ trivially, so $\emptyset \in Y$. Now suppose $x \in Y \subseteq X$. Note that since $X$ is inductive, $x \cup \lbrace x\rbrace \in X$. Then $x \subseteq X$, and since $x \in X$ we have $\lbrace x\rbrace \in X$. Thus, $x \cup \lbrace x\rbrace \subseteq X$ and hence $x \cup \lbrace x\rbrace \in Y$. So $Y$ is indeed inductive.Since $\boldsymbol{N}$ is the smallest inductive set, it follows that $\boldsymbol{N} = \lbrace x \in \boldsymbol{N} : x \subseteq \boldsymbol{N}\rbrace$, i.e. $\boldsymbol{N}$ is transitive.
$\square$
Exercise 1.4.
Solution. Let $Y := \lbrace x \in X : x \text{ is transitive}\rbrace$. Clearly $\emptyset$ is transitive, so $\emptyset \in Y$. Now suppose $x \in X$ and $x$ is transitive. We wish to show that $x \cup \lbrace x\rbrace$ is transitive, which would complete the proof.Let $y \in x \cup \lbrace x\rbrace$. If $y \in x$, then $y \subseteq x \subseteq x \cup \lbrace x\rbrace$. Otherwise, $y \in \lbrace x\rbrace$ so $y = x$. Then clearly $x \subseteq x \cup \lbrace x\rbrace$. Thus $x \cup \lbrace x\rbrace$ is transitive.
$\square$
Exercise 1.5.
Solution. Clearly $\emptyset$ is transitive and $\emptyset \notin \emptyset$ as $\emptyset$ has no elements. Now suppose $x \in X$. In the proof of Exercise 1.4 we have already seen that $x \cup \lbrace x\rbrace$ is transitive. It remains to show that $x \cup \lbrace x\rbrace \notin x \cup \lbrace x\rbrace$.Suppose not, so $x \cup \lbrace x\rbrace \in x \cup \lbrace x\rbrace$. We consider two cases. If $x \cup \lbrace x\rbrace \in x$, then since $x$ is transitive, $x \cup \lbrace x\rbrace \subseteq x$. In particular, $x \in x$, a contradiction. Otherwise, we have $x \cup \lbrace x\rbrace \in \lbrace x\rbrace$, i.e. $x \cup \lbrace x\rbrace = x$. But this also implies that $x \in x$, a contradiction.
$\square$
Exercise 1.6.
Solution. Clearly $\emptyset$ is transitive and since it has no non-empty subset, the second requirement holds trivially. Now suppose $x$ is transitive and every non-empty $z \subseteq x$ has an $\in$-minimal element. In the proof of Exercise 1.4 we have already seen that $x \cup \lbrace x\rbrace$ is transitive.Let $z \subseteq x \cup \lbrace x\rbrace$ be non-empty. We consider two cases. If $z \subseteq x$, then by induction hypothesis on $x$ we have that $z$ has an $\in$-minimal element. Otherwise, we have $z = z' \cup \lbrace x\rbrace$ for some $z' \subseteq x$. Let $t \in z'$ be $\in$-minimal in $z'$. If $t$ is $\in$-minimal in $z$, then we're done. Otherwise, we must have $x \in t$. Since $t \in x$ and $x$ is transitive, we have that $x \in x$. This means that $t$ is not $\in$-minimal in $z'$, a contradiction.
$\square$
Exercise 1.7.
Solution. Let $n \in X$. Then $X \cap n \subseteq n$, and by Exercise 1.6 we have that $X \cap n$ has a $\in$-minimal element. Let $m \in X \cap n$ be such a $\in$-minimal element. We shall show that $m$ is the $\in$-minimal element in $X$.Suppose not, so there exists a $m' \in X$ such that $m' \in m$. By Exercise 1.3, we have that $m = \lbrace p \in \boldsymbol{N} : p \in m\rbrace$. Since $m \in n$, by the same Exercise we have $p \in n$. Thus, $m' \in X \cap n$, so $m$ is not $\in$-minimal in $X \cap n$, a contradiction.
$\square$
Exercise 1.8.
Solution. $\emptyset$ is in the set by definition, and if $x$ is in the set then $x \cup \lbrace x\rbrace$ is in the set by definition (precisely because $x$ is in the set).$\square$
Exercise 1.9.
Solution. This follows from that $\boldsymbol{N}$ is inductive and Exercise 1.8.$\square$
Exercise 1.10.
Solution. Let $A := \lbrace n \in \boldsymbol{N} : n \text{ is T-finite}\rbrace$. Clearly $0 = \emptyset \in A$ as it is vacuously T-finite. Suppose $n$ is T-finite. We shall show that $n + 1$ has $n$ as its $\subseteq$-maximal element, and is hence T-finite. Let $m \in n + 1 = n \cup \lbrace n\rbrace$. If $m \in \lbrace n\rbrace$, then $m = n$ so $m \subseteq n \cup \lbrace n\rbrace$ immediately. If $m \in n$, then let $m' \in n$ be its $\subseteq$-maximal element. Since $n$ is transitive by Exercise 1.4, we have $m \subseteq m' \subseteq n \subseteq n + 1$. Thus $n + 1$ is T-finite. By induction (Exercise 1.9), $A = \boldsymbol{N}$ so every $n \in \boldsymbol{N}$ is T-finite.$\square$
Exercise 1.11.
Solution. Suppose $\boldsymbol{N}$ is T-finite. Let $n \in \boldsymbol{N}$ be $\subseteq$-maximal. Then $n \cup \lbrace n\rbrace \in \boldsymbol{N}$ and therefore $n \cup \lbrace n\rbrace \subseteq n$. Hence $n \in n$, contradicting Exercise 1.4.$\square$
Exercise 1.12.
Lemma 1.12.A. Let $X$ be a finite set and suppose $X$ has $n + 1$ elements for some $n \in \boldsymbol{N}$. Then, for any $x_0 \in X$, we have $X - \lbrace x_0\rbrace$ has $n$ elements.
Proof. Let $f : X \to n + 1$ be a bijection, and fix $x_0 \in X$. Let $x' = f^{-1}(n)$. Define $g : X \to X$ by:
$$ \begin{align*}
g(x) =
\begin{cases}
x_0, &\text{if $x = x'$} \\
x', &\text{if $x = x_0$} \\
x, &\text{otherwise}
\end{cases}
\end{align*}$$ Then $f \circ g : X \to n + 1$ is a bijection such that $(f \circ g)(x_0) = n$. Then $(f \circ g)\restrictedto X - \lbrace x_0\rbrace : X - \lbrace x_0\rbrace \to n$ is a bijection, as desired.
$\blacksquare$
Solution. Let $A = \lbrace n \in \boldsymbol{N} : \text{If $X$ has $n$ elements then $X$ is T-finite}\rbrace$. Clearly $0 \in A$ as the empty set is vacuously T-finite. Suppose sets with $n$ elements are T-finite. Let $X$ be a set with $n + 1$ element, and suppose $X$ is not T-finite. Let $x_0 \in X$, so $X \setminus \lbrace x_0\rbrace$ has $n$ elements by Lemma 1.12.A. Then by induction hypothesis, $X \setminus \lbrace x_0\rbrace$ is T-finite, so let $x \in X \setminus \lbrace x_0\rbrace$ be an element $\subseteq$-maximal in $X \setminus \lbrace x_0\rbrace$. Since it is not $\subseteq$-maximal in $X$, we must have $x \subsetneq x_0$. But $x_0$ is not $\subseteq$-maximal either, so $x_0 \subsetneq x'$ for some $x' \in X \setminus \lbrace x_0\rbrace$. Then $x \subsetneq x'$, so $x$ is not $\subseteq$-maximal in $X \setminus \lbrace x_0\rbrace$, a contradiction.
$\square$
Exercise 1.13.
Lemma 1.13.A. Let $X$ be a finite set and suppose $X$ has $n$ elements for some $n \in \boldsymbol{N}$. Then, for any $x_0 \notin X$, we have $X \cup x_0$ has $n + 1$ elements.
Proof. Let $f : X \to n$ be a bijection, and fix a set $x_0$. Define $g : X \to n + 1$ by:
$$ \begin{align*}
g(x) =
\begin{cases}
n, &\text{if $x = x_0$} \\
f(x), &\text{otherwise}
\end{cases}
\end{align*}$$ It's easy to see that $g$ is indeed a bijection as desired.
$\blacksquare$
Solution. Let $S$ be infinite and let $X$ be the set in the hint. Let $u \in X$. Since $u$ is finite and $X$ is infinite, $u \neq X$. Thus, there exists some $x \in X \setminus u$. By Lemma 1.13.A, $u \cup \lbrace x\rbrace$ has $n + 1$ and is in particular finite, so $u \cup \lbrace x\rbrace$. Then $u \subsetneq u \cup \lbrace x\rbrace$.
$\square$
Exercise 1.14.
Solution. The hint basically solves the problem. If $\varphi(x,p)$ is a property with parameter $p$, then for any $p$ we may define $F := \lbrace (x,x) : \varphi(x,p)\rbrace$ instead.$\square$
Exercise 1.15.
Solution. Axiom of Union: If $X$ is a set, and $Y$ is a set such that $\bigcup X \subseteq Y$, then:$$ \begin{align*}
\bigcup X = \lbrace x \in Y : (\forall u \in x)(\exists v \in X) \, u \in v\rbrace
\end{align*}$$ Axiom of Power Set: If $X$ is a set, and $Y$ is a set such that $P(X) \subseteq Y$, then:
$$ \begin{align*}
P(X) = \lbrace x \in Y : (\forall u \in x) \, u \in X\rbrace
\end{align*}$$ Axiom schema of Replacement: Let $F$ be a function, and fix a set $X$. Let $Y$ be such that $F(X) \subseteq Y$. Then:
$$ \begin{align*}
F(X) = \lbrace x \in Y : (\exists u \in X) \, x = F(u)\rbrace
\end{align*}$$ Note that if we denote $\varphi(u,x)$ as the formula "$x = F(u)$" then $\varphi$ is a property, so we may indeed apply Axiom Schema of Separation.
$\square$