main.tex

\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumitem}

\include{MathMacrosJDH}

\theoremstyle{definition}
\newtheorem{innercustomthm}{Exercise}
\newenvironment{customthm}[1]
  {\renewcommand\theinnercustomthm{#1}\innercustomthm}
  {\endinnercustomthm}

\title{
\vspace{-2cm}
  \author{Wojciech Aleksander Wołoszyn}
  Solutions for
  T. Jech's Set Theory \\
}

\begin{document}
\maketitle

\begin{customthm}{I.1.1}
    Assume that $(a,b)=(c,d)$ or, in other words, $\set{\set{a},\set{a,b}} = \set{\set{c},\set{c,d}}$. By the axiom of extensionality, we have that $\set{a} \in \set{\set{c},\set{c,d}}$ and $\set{a,b} \in \set{\set{c},\set{c,d}}$. By the axiom of pairing, we have that $\set{a} = \set{c}$ or $\set{a} = \set{c,d}$ and $\set{a,b} = \set{c}$ or $\set{a,b} = \set{c,d}$. Suppose, $\set{a} = \set{c,d}$, then, by pairing and extensionality, $a=c=d$. So $\set{\set{a},\set{a,b}} = \set{\set{c},\set{c,d}}$ becomes $\set{\set{a},\set{a,b}} = \set{\set{a}}$, and, again by pairing and extensionality, $a=b$. And we have that $a=b=c=d$. Suppose $\set{a} = \set{c}$ and $\set{a} \neq \set{c,d}$. Then, by extensionality and pairing, $a=c \neq d$. If $\set{a,b} = \set{c}$, then $a=b=c$, which would imply $a=b=c=d$, contradiction. So $\set{a,b} = \set{c,d}$ and $a \neq b$. By the axioms of pairing and extensionality, we have that $a=c$ and $b=d$. Other direction is immediate.
\end{customthm}

\begin{customthm}{I.1.2}
    Suppose we have that $P(X) \subset X$. Then, there must be a surjection $f \colon X \to P(X)$. But the set $\set{x \colon x \not\in f(x)}$ is not in $P(X)$.
\end{customthm}

\begin{customthm}{I.1.3}\label{ex:set-of-elements-of-inductive-set-is-inductive}
    Let $Y=\set{x \in X \colon x \subset X}$. We show that $Y$ is inductive. First, it is obvious that $\emptyset \in Y$. Let $y \in Y$. Since $Y \subset X$, it follows that $y \in X$. But $X$ is inductive, so $y \cup \set{y} \in X$. Furthermore, $\set{y} \subset X$. By the definition of $Y$, it is also the case that $y \subset X$. So $y \cup \set{y} \subset X$. Thus, $y \cup \set{y} \in Y$.
    
    Let $N$ be the smallest inductive set $N = \bigcap \set{X \colon X \text{ is inductive}}$. Set $Y = \set{x \in N \colon x \subset N}$. By the definition of $Y$, $Y \subset N$. But $N$ is minimal, so we have that $N \subset Y$. Hence, $Y=N$. And $N$ is transitive, because $y \in N$, implies $y \subset N$.
    
    We show by induction that $n = \set{m \in N \colon m < n}$. Since $N$ is inductive, we have that $\emptyset \in N$. Assume that $n = \set{m \in N \colon m < n}$. Now, $n+1 = n \cup \set{n} = \set{m \in N \colon m < n} \cup \set{n} = \set{m \in N \colon m < n \text{ or } m=n} = \set{m \in N \colon m < n + 1}$.
\end{customthm}

\begin{customthm}{I.1.4}\label{ex:set-of-transitive-elements-of-inductive-set-is-inductive}
    Let $Y = \set{x \in X \colon x \text{ is transitive}}$. First, since $X$ is inductive, $\emptyset \in X$. The empty set is transitive, so $\emptyset \in Y$. Let $y \in Y$. We know that $Y \subset X$, so $y \in X$. And we know that $y$ is transitive, so $y \subset X$. Hence $y \cup \set{y} \in X$. It remains to show that $y \cup \set{y}$ is transitive. Let $\gamma \in y \cup \set{y}$. Then $\gamma$ is either equal to $y$ or an element of $y$. If $\gamma = y$, then, in particular, $\gamma \subset y$. If $\gamma \in y$, then $\gamma \subset y$, because $y$ is transitive. And so, $\gamma \subset y \cup \set{y}$.
    
    Set $Y = \set{x \in N \colon x \text{ is transitive}}$. By the definition of $Y$, $Y \subset N$. But since $Y$ is inductive and $N$ is a minimal inductive set, we also have that $N \subset Y$. Hence, $N=Y$ and every element $n$ of $N$ is transitive.
\end{customthm}

\begin{customthm}{I.1.5}\label{ex:set-of-transitive-elements-with-x-not-in-x-of-inductive-set-is-inductive}
    Let $Y = \set{x \in X \colon x \text{ is transitive and } x \not\in x}$. First, since $X$ is inductive, $\emptyset \in X$. The empty set is transitive and has no element (particularly $\emptyset \not\in \emptyset)$), so $\emptyset \in Y$. Let $y \in Y$. From exercise~\ref{ex:set-of-transitive-elements-of-inductive-set-is-inductive}, the set $y \cup \set{y}$ is transitive. It is enough to show that $y \cup \set{y} \not\in y \cup \set{y}$. If the opposite were the case then either $y \cup \set{y}$ would be equal to $y$ or an element of $y$. If $y \cup \set{y} = y$, then $\set{y} \subset y$, hence $y \in y$, which is a contradiction. If $y \cup \set{y} \in y$, then, again $y \in y$.
    
    Set $Y = \set{x \in N \colon x \text{ is transitive and } x \not\in x}$. By the definition of $Y$, $Y \subset N$. But since $Y$ is inductive and $N$ is a minimal inductive set, we also have that $N \subset Y$. Hence, $N=Y$ and every element $n$ of $N$ is such that $n \not\in n$. In other words, $n \neq n+1$ for each $n \in N$.
\end{customthm}

\begin{customthm}{I.1.6}
    Let $Y = \set{x \in X \colon x \text{ is transitive and every nonempty } z \subset x \text{ has an $\in$-minimal element}}$. First, since $X$ is inductive, $\emptyset \in X$. The empty set is transitive and has no nonempty elements, so it is in $Y$. From exercise~\ref{ex:set-of-transitive-elements-of-inductive-set-is-inductive}, the set $y \cup \set{y} \in X$ is transitive. Let $z \subset y \cup \set{y}$ be nonempty. If $t \in z$, then $t \in y \cup \set{y}$. So either $t \in y$ or $t=y$, so $t \subset y$. So $t$ is either an $\in$-minimal or has $\in$-minimal element. But since $t \in z$, $z$ has $\in$-minimal element. And so, $y \cup \set{y} \in Y$.
\end{customthm}

\begin{customthm}{I.1.7}\label{ex:every-nonempty-subset-of-N-is-inductive}
    Let $X$ be a nonempty subset of $N$ and let $n \in X$. If $n \cap X$ is nonempty, then there is a minimal element $m \in n \cap X \subset n$, because $n$ has a minimal element. If $n \cap X$ is empty, then $n$ is the minimal element. If it weren't then there would be an element $m \in X$ such that $m \in n$. But $n \cap X$ is empty, so this is impossible.
\end{customthm}

\begin{customthm}{I.1.8}
    Let $Y = \set{x \in X \colon x = \emptyset \text{ or } x = y \cup \set{y} \text{ for some y}}$. First, the empty set is in $Y$. Let $\gamma \in Y$ be nonempty. There is some $y$ such that $\gamma = y \cup \set{y}$. Note that $\gamma \cup \set{\gamma}$ is also of this form and $\gamma \in Y$, so $\gamma \cup \set{\gamma} \in Y$. 
\end{customthm}

\begin{customthm}{I.1.9}
    $A$ is a subset of $N$, so $A \subset N$. Since $\emptyset \in A$ and $n \in A \implies n+1 = n \cup \set{n} \in A$, $A$ is inductive. By definition, $N$ is the minimal inductive set so $N \subset A$. Hence, $A=N$.
\end{customthm}

\begin{customthm}{I.1.10}
    We proceed by induction. Element $0 = \emptyset \in N$ has no nonempty elements, so it's trivially $T$-finite. Suppose $n$ is $T$-finite. And let $X \subset P(n+1)$ be nonempty. Note that $X$ is either equal to $Y$ or to $Y \cup \set{n}$, for some subset $Y$ of $P(n)$. By the induction hypothesis, $Y$ has a $\subset$-maximal element $y$. If $X = Y$, $y$ is the maximal element of $X$. If $X = Y \cup \set{n}$, $y \cup \set{n}$ is the maximal element of $X$.
\end{customthm}

\begin{customthm}{I.1.11}
    It is enough to observe that $n \in N$ is a proper subset of $n+1 \in N$.
\end{customthm}

\begin{customthm}{I.1.12}
    Let $S$ be a finite set. And take any nonempty $X \subset P(S)$. We need to show that there is a $\subset$-maximal element in $X$. By the definition of finiteness, there is a bijection $f: S \to n$ for some $n \in N$. So there is an $x \in X$ such that $f(x)$ is a $\subset$-maximal element of $f(X)$. We claim that $x$ must be a $\subset$-maximal element in $X$. Otherwise there would be some $y \in X$ such that $x \subset y$, but $f(x) \not\subset f(y)$, which is absurd.
\end{customthm}

\begin{customthm}{I.1.13}
    Let $S$ be infinite and set $X = \set{u \subset S \colon u \text{ is finite}}$. Note that $\emptyset \in X$, so $X$ is nonempty. Suppose $X$ has a $\subset$-maximal element $x$. Take $s \in S$ such that $s \not\in x$ (there must be such element as $S$ is infinite and $x$ is finite). But then $x \cup \set{s}$ is also finite, hence is in $X$. This is a contradiction with $x$ being the $\subset$-maximal element in $X$.
\end{customthm}

\begin{customthm}{I.1.14}
    Let $\varphi(x)$ be a formula and let $X$ be arbitrary. Take $F = \set{(x,x) \colon \varphi(x)}$. By the Replacement Schema, $F(X) = \set{x \in X \colon \varphi(x)}$ for every $X$. Hence, the Separation Axioms follow from Replacement Schema.
\end{customthm}

\begin{customthm}{I.1.15}
\leavevmode
    \begin{enumerate}
        \item We have that $\forall X \exists Y (\forall x \in X) (\forall u \in X) u \in Y$. Set an $X$ and take $\varphi(u) = (\exists z \in X) u \in z$. By the Separation Schema and the above weaker version of the Union, there is a set $Y' = \set{u \in Y \colon \varphi(u)} = \set{u \in Y \colon (\exists z \in X) u \in z}$. But then, $u \in Y' \iff \exists z (z \in X \land u \in z)$. Hence $Y' = \bigcup X$.
        \item We have that $\forall X \exists Y \forall u (u \subset X \implies u \in Y)$. Set an $X$ and take $\varphi(u) = u \subset X$. By the Separation Schema and the above weaker version of the Power Set, there is a set $Y' = \set{u \in Y \colon \varphi(u)} = \set{u \in Y \colon u \subset X}$. But then, $u \in Y' \iff u \subset X$. Hence $Y' = P(X)$.
        \item Let $F$ be a class function. We have that $\forall X \exists Y F(X) \subset Y$. Set an $X$ and take $varphi(u) = \exists x \in X F(x,u)$. By the Separation Schema and the above weaker version of the Replacement, there is a set $Y' = \set{u \in Y \colon \varphi(u)} = \set{u \in Y \colon \exists x \in X F(x,u)} = F(X)$.
    \end{enumerate}
\end{customthm}

\begin{customthm}{I.2.1}
    Let $P,Q,R$ be partial orderings. Order $P$ is isomorphic to itself via the identity function. If $P$ is isomorphic to $Q$ via $f$, then $Q$ is isomorphic to $P$ via $f^{-1}$. Finally, if $P$ is isomorphic to $Q$ via $f$ and $Q$ is isomorphic to $R$ via $g$, then $P$ is isomorphic to $R$ via $g \circ f$.
\end{customthm}

\begin{customthm}{I.2.2}
    Let $\alpha$ be a limit ordinal. Suppose there is a $\beta < \alpha$ such that $\beta+1 \geq \alpha$. Hence, $\beta + 1 = \alpha$. But that would mean that $\alpha$ is a successor cardinal, contradiction.
    
    Let $\alpha$ be such that for every $\beta < \alpha$, $\beta + 1 < \alpha$. Then $\alpha$ must be a limit cardinal. If it weren't then there would be some $\beta_0 < \alpha$ such that $\alpha = \beta_0 + 1$, contradiction.
\end{customthm}

\begin{customthm}{I.2.3}
    Let $X$ be inductive. First, $\emptyset \in X \cap \Ord$ -- for $\Ord$ by definition. for $X$ because it is inductive. Let $x \in X \cap \Ord$, then $x \cup \set{x} \in X \cap \Ord$ -- it is a basic fact that for $\Ord$ and it follows from inductivity for $X$. Hence, $X \cap \Ord$ is inductive.
    
    By exercise~\ref{ex:set-of-elements-of-inductive-set-is-inductive}, $N$ -- the smallest inductive set -- is transitive. It is easy to see that $N$ is linearly ordered. And what is more, by exercise~\ref{ex:every-nonempty-subset-of-N-is-inductive}, every nonempty subset of $N$ has an $\in$-minimal element. Hence, $N$ is an ordinal number. Also, note that for any $n<N$, $n+1<N$, so it is a limit ordinal. Furthermore, it is the smallest limit ordinal other than the empty set: every $n \in N$ is such that $(n-1) + 1 \not\in n$.
\end{customthm}

\begin{customthm}{I.2.4}
    The first implication (i$\to$ii) follows, because $N$ is inductive and infinite.
    
    For the second (ii$\to$iii), assume that $X$ is infinite and consider the set $Y = \set{x \subset X \colon x \text{ is finite}}$. For each $x \in Y$, let $f(x)$ be a number of elements in $x$. Note that $f \colon Y \to \omega$ is a function. Let us prove this function is a surjection. Suppose $n \in Y$. There must be at least one $x \in f^{-1}(n)$. Otherwise, $X$ wouldn't be infinite. Hence, $f(Y) = \omega$ is a set.
    
    The last implication (iii$\to$i), observe that $\omega$ is an inductive set. Indeed, $\emptyset \in \omega$ and whenever $\alpha \in \omega$, then $\alpha+1 \in \omega$.
\end{customthm}

\begin{customthm}{I.2.5}
    A nonempty subset $\set{a_0,a_1,\ldots}$ of $W$, constructed from such a sequence, would not have a $\in$-minimal element.
\end{customthm}

\begin{customthm}{I.2.6}
    Let $\alpha$ be an ordinal. Take $\alpha_0 = \alpha$ and $\alpha_{n+1} = \alpha_n + 1$. Define the ordinal $\beta = \bigcup \alpha_n = \sup \set{\alpha_n} = \lim \alpha_n$. We shall prove that $\beta$ is a limit ordinal and since $\alpha$ was chosen arbitrarily, there are arbitrarily large limit ordinals. It suffices to show that whenever $\gamma \in \beta$, then $\gamma + 1 \in \beta$. Let $\gamma \in \beta$. There is an $\alpha_n$ such that $\gamma < \alpha_n$ (otherwise $\gamma \geq \beta$). But then $\gamma + 1 < \alpha_n + 1 = \alpha_n < \beta$. This ends the proof.
\end{customthm}

\begin{customthm}{I.2.7}

\end{customthm}

\begin{customthm}{I.2.8}
    By induction: \\ i) $\gamma = 0$, easy; successor: $\alpha \cdot (\beta + \gamma + 1) = \alpha \cdot (\beta + \gamma) + \alpha \cdot 1 = \alpha \cdot \beta + \alpha \cdot \gamma + \alpha \cdot 1 = \alpha \cdot \beta + \alpha (\gamma + 1)$; limit: $\alpha \cdot (\beta + \gamma) = \alpha \cdot (\beta + \lim \gamma_n) = \lim \alpha \cdot (\beta + \gamma_n) = \lim \alpha \cdot \beta + \alpha \cdot \gamma_n = \alpha \cdot \beta + \alpha \cdot (\lim \gamma_n) = \alpha \cdot \beta + \alpha \cdot \gamma$. \\
    ii) $\gamma = 0$, easy; successor: $\alpha^{\beta + \gamma + 1} = \alpha^{\beta + \gamma} \cdot \alpha^1 = \alpha^\beta \cdot \alpha^\gamma \cdot \alpha^1 = \alpha^\beta \cdot \alpha^{\gamma + 1}$; limit: $\alpha^{\beta + \gamma} = \alpha^{\beta + \lim \gamma_n} = \lim \alpha^{\beta + \gamma_n} = \lim \alpha^\beta \cdot \alpha^{\gamma_n} = \alpha^\beta \cdot \alpha^{\lim \gamma_n} = \alpha^\beta \cdot \alpha^{\gamma}$. \\
    iii) $\gamma = 0$, easy; successor: $(\alpha^\beta)^{\gamma+1} = (\alpha^\beta)^\gamma \cdot (\alpha^\beta)^1 = \alpha^{\beta \cdot \gamma} + (\alpha^\beta \cdot 1) = \alpha^{\beta \cdot (\gamma +1)}$; limit: $(\alpha^\beta)^{\gamma} = (\alpha^\beta)^{\lim \gamma_n} = \lim (\alpha^\beta)^{\gamma_n} = \lim \alpha^{\beta \cdot \gamma_n} = \alpha^{\beta \cdot (\lim \gamma_n)} = \alpha^{\beta \cdot\gamma}$.
\end{customthm}

\begin{customthm}{I.2.9} \leavevmode \\
    i) $(\omega+1) \cdot 2 = \omega + 1 + \omega + 1 = \omega + \omega + 1 = \omega \cdot 2 + 1$ \\
    ii) $(\omega \cdot 2)^2 = (\omega \cdot 2) \cdot (\omega \cdot 2) = (\omega \cdot \omega \cdot 2) = \omega^2 \cdot 2$
\end{customthm}

\begin{customthm}{I.2.10} \leavevmode \\
    i) Let $\alpha<\beta$. It is hard not to see that $\alpha + 0 < \beta + 0$. Suppose $\alpha + \gamma < \beta + \gamma$. Observe that $(\alpha + \gamma) + 1 < (\beta + \gamma) +1$ and, if $\gamma$ is a limit ordinal, suppose the hypothesis holds for $\gamma' < \gamma$, $\alpha + \gamma = \lim \alpha + \gamma_n \leq \lim \beta + \gamma_n = \beta + \gamma$. \\
    ii) Likewise, $\alpha \cdot 0 \leq \beta \cdot 0$ and $\alpha \cdot 1 \leq \beta \cdot 1$ Suppose $\alpha \cdot \gamma < \beta \cdot \gamma$. Observe $\alpha \cdot (\gamma + 1) = \alpha \cdot \gamma + \alpha \cdot 1 < \beta \cdot \gamma + \beta = \beta (\gamma + 1)$. For limits, $\alpha \cdot \gamma = \lim \alpha \cdot \gamma_n \leq \lim \beta \cdot \gamma_n = \beta \cdot \gamma$ \\
    iii) Finally, $\alpha^0 < \beta^0$. Suppose $\alpha^\gamma < \beta^\gamma$. Observe $\alpha^{\gamma+1} = \alpha^\gamma \cdot \alpha \leq \beta^\gamma \cdot \beta = \beta^{\gamma+1}$. For limits, $\alpha^\gamma = \lim \alpha^{\gamma_n} \leq \lim \beta^{\gamma_n} = \beta^\gamma$.
\end{customthm}

\begin{customthm}{I.2.11}
    
\end{customthm}

\begin{customthm}{I.2.12}
    Let $\alpha_0 = \omega$, $\alpha_{n+1} = \omega^{\alpha_n}$ and $\epsilon_0 = \lim \alpha_n$. Observe that $\omega^{\epsilon_0} = \omega^{\lim \alpha_n} = \lim \omega^{\alpha_n} = \lim \alpha_{n+1} = \epsilon_0$.
    
    Note that the above sequence $\alpha_n$ is increasing. Suppose there is $\epsilon < \epsilon_0$ such that $\omega^\epsilon = \epsilon$. It is obvious that such $\epsilon$ must be infinite. Take the smallest $n \in \omega$ such that $\alpha_{n+1} > \epsilon$. Observe that $\omega^{\alpha_n} = \alpha_{n+1} > \epsilon = \omega^\epsilon$. But then, $\alpha_n > \epsilon$, contradiction.
\end{customthm}

\begin{customthm}{I.2.13}
    
\end{customthm}

\begin{customthm}{I.2.14}
    If that were true, then $X = \set{a_n \colon n \in N } \subset P$ would be a nonempty set with no $E$-minimal element.
\end{customthm}

\begin{customthm}{I.2.15}
    
\end{customthm}

\begin{customthm}{I.2.16}
    
\end{customthm}

\begin{customthm}{I.3.1}
    i) Suppose $X$ is finite and $Y \subset X$ is infinite. Thus, $Y$ is $T$-infinite, i.e., there is a nonempty $Z \subset P(Y)$ with no $\subset$-maximal element. But $P(Y) \subset P(X)$ and $X$ is finite (hence $T$-finite), so $Z$ must have a maximal element---contradiction. \\
    ii) Let $\bigcup X_i$ be a finite union of finite sets. With each $X_i$, there is an associated bijection $f_i \colon X_i \to n_i$ for some natural number $n_i$. We define a function $f \colon \bigcup X_i \to \sum n_i$ by $f(x) = f_k(x) + \sum_{i<k} n_i$, where $k$ is minimal natural number such that $x \in X_k$. Clearly, $f$ is one-to-one. Note that $f$ is not necessarily a bijection ($X_i$ may overlap). \\
    iii) Let $X$ be finite and have $n$ elements. Then $P(X)$ equinumerous with $2^X$, so has $2^n$ elements. \\
    iv) Let $X$ be finite and let $f \colon X \to f(X)$ be a mapping. Since $X$ is finite, there is a bijection $g \colon X \to n$ for some natural number $n$. Consider an instance of $f^{-1}$. Then $h(x) = g \circ f^{-1}$ is in one to one correspondence with $n$ (though, again, not necessarily bijective correspondence, unless $f$ was one-to-one itself).
\end{customthm}

\begin{customthm}{I.3.2}
    i) Let $X$ be countable and let $Y \subset X$. Since $X$ is countable, there is a bijection $f \colon X \to \omega$. But note that $f$ composed with the identity function $\mathrm{id} \colon Y \to X$ is in one-to-one correspondence with $\omega$. \\
    ii) Let $\bigcup X_i$ be a finite union of countable sets. With each $X_i$, there is an associated bijection $f_i \colon X_i \to \omega \times \set{i}$. Take $f(x) \colon \bigcup X \to \omega \times \omega$ to be $f(x) = (f_i(x),i)$ with $i$ minimal. The desired function is $g \colon \bigcup X \to \omega$ defined by $g(x) = \Gamma \circ f(x)$, where $\Gamma$ is a bijection between $\omega \times \omega$ and $\omega$. Indeed, this proves that the finite union of countable sets is at least countable. And from i) we know that is is also at most countable. \\
    iii) Let $X$ be countable and let $f \colon X \to f(X)$ be a mapping. Since $X$ is countable, there is a bijection $g \colon X \to \omega$. Consider an instance of $f^{-1}$. Then $h(x) = g \circ f^{-1}$ is in one to one correspondence with $\omega$.
\end{customthm}

\begin{customthm}{I.3.3}
    It is enough to prove that $f \colon N \times N \to \omega$, $f(m,n) = 2^m(2n+1)-1$ is one-to-one. Note that $2^a(2b+1)-1 = 2^c(2d+1) - 1$ implies $2^a(2b+1) = 2^c(2d+1)$ implies $a=c, b=d$.
\end{customthm}

\begin{customthm}{I.3.4}
    i) There are $\omega^n$ sequences of length $n$ in $N$. We use the axiom of choice to say that for each $n$ there is an injection $f_n \colon \text{sequences of length }n \to N$. But then, the function $f(x) = (f_n(x),n)$, where $n$ is the length of finite sequence $x$ is an injection. So the cardinality of all finite length sequences is at most countable. It is also at least countable because the number of all sequences of size $1$ is already countable. \\
    ii) 
\end{customthm}

\begin{customthm}{I.3.5}
    We prove it by induction on $\alpha$. First, $\Gamma(0 \times 0) = 0 \leq \omega^0 = 1$. Now, $\alpha \times \alpha$ is isomorphic to $\alpha \cdot \alpha$, so $\Gamma((\alpha+1) \times (\alpha+1)) = \text{order type of } (\alpha+1) \cdot (\alpha+1) = \text{order type of } \alpha^2 + \alpha \cdot 2 + 1 = \Gamma(\alpha \times \alpha) + \alpha \cdot 2 + 1 \leq \omega^\alpha + \alpha \cdot 2 + 1 \leq \omega^{\alpha+1}$.
\end{customthm}

\begin{customthm}{I.3.7}
    Let $B$ be a projection of $\omega_\alpha$, i.e., there is a surjection $f \colon \omega_\alpha \to B$. It suffices to show that there is an injection $g \colon B \to \omega_\alpha$. Let $g(x) = s(f^{-1}(x))$ where $s$ is a selector function.
\end{customthm}

\begin{customthm}{I.3.8}
    We know that the set of all finite sequences in $\omega^\alpha$ is of order-type $\omega_\alpha$ and hence its cardinality is $\aleph_\alpha$. It suffices to show that there is a surjection $f: [\omega_\alpha]^{<\omega}  \to \omega_\alpha^{<\omega}$. Then, by the axiom of choice we can construct an injection $g(x) = s(f^{-1}(x))$. It is enough to take $f$ to map any set in $[\omega_\alpha]^{<\omega}$ to an increasing sequence of its elements in $\omega_\alpha^{<\omega}$.
\end{customthm}

\begin{customthm}{I.3.9}
    Let $B$ be a projection of $A$. That is, let there be a surjection $f \colon A \to B$. Define $g \colon P(B) \to P(A)$ as $g(X) = f^{-1}(X)$. We need to show that $g$ is one-to-one. Suppose $g(X) = g(Y)$, then $f^{-1}(X) = f^{-1}(Y)$ and $X=Y$, done.
\end{customthm}

\begin{customthm}{I.3.10}
    
\end{customthm}

\begin{customthm}{I.3.11}
    Since $\omega_{\alpha+1}$ is a projection of $P(\alpha)$, we know that $\aleph_{\alpha+1} \leq 2^{\aleph_\alpha}$. But by the Cantor's theorem, $2^{\aleph_\alpha} < 2^{2^{\aleph_\alpha}}$. So $\aleph_{\alpha+1} < 2^{2^{\aleph_\alpha}}$.
\end{customthm}

\begin{customthm}{I.3.12}
    Note that $\omega_\zeta$, $\zeta < \cof \alpha$, is a non-decreasing $\cof \alpha$ sequence of ordinals in $\omega_\alpha$ and $\lim \omega_\zeta = \omega_\alpha$, so $\cof \cof \alpha = \cof \alpha = \cof \omega_\alpha$.
\end{customthm}

\begin{customthm}{I.3.13}
    We work in $\ZF$. Suppose $\omega_2 = \bigcup_{n < \omega} S_n$ and each $S_n$ is countable and let $\alpha_n$ be the order-type of $S_n$. Then, for each $n$, there is a unique isomorphism $f_n \colon \alpha_n \to S_n$. Let us denote $\sup \alpha_n$ by $\alpha$. We define a function $f \colon \omega \times \alpha \to \omega_2$ by:
    \begin{equation*}
        f(n, \kappa) = \begin{cases} f_n(\kappa) & \mbox{if } \kappa \in \alpha_n \\ 0 & \mbox{otherwise.} \end{cases}
    \end{equation*}
    Let $\gamma \in \omega_2$, then there is a minimal $n$ with $\gamma \in S_n$ and $f_n^{-1}(\gamma) \in \alpha_n$, so there is a unique inverse (the one taking $n$ to be minimal, this uses the fact that $\omega \times \omega_2$ is well-ordered under $\ZF$) $f^-1(n,\gamma) = (n,f_n^{-1}(\gamma)$. Thus, $f$ is a surjection and $\aleph_2 \leq |\omega \times \alpha| \leq \aleph_0 \cdot \aleph_1 = \aleph_1$, contradiction.
\end{customthm}

\begin{customthm}{I.3.14}
    Let $S$ be $D$--infinite. So there is a one-to-one mapping $f \colon S \to X$, where $X$ is a subset of $S$. Choose $x_0 \in S \setminus X$ and define $x_{n+1} = f(x_n) \in X$. But then, the set $\set{x_n \mid n < \omega}$ is a countable subset of $S$.
    
    For the other direction, let $X \subset S$ be countable, say, $X=\set{x_n \mid n < \omega}$. Then, define $f \colon S \to X$ by:
    \begin{equation*}
        f(s) = \begin{cases} x_{n+1} & \mbox{if } s = x_n \\ s & \mbox{otherwise.} \end{cases}
    \end{equation*}
\end{customthm}

\begin{customthm}{I.3.15}
    i) Let $A,B$ be $D$--finite sets, then $A$ and $B$ have no countable subsets. Suppose the set $A \cup B$ is $D$--infinite, and so has a countable subset $X$. But then, $X = X \cap (A \cup B) = (X \cap A) \cup (X \cap B)$. Sets $(X \cap A)$ and $(X \cap B)$ cannot be countable, hence are finite. Sum of two finite sets is finite, so $X$ is finite, hence $D$--finite.
    
    Suppose $X \subset A \times B$ is $D$--infinite and $A,B$ are $D$--finite. Then, $|X| \leq |\set{a \mid (a,b) \in A}| \times |\set{b \mid (a,b) \in B}|$. But $|\set{a \mid (a,b) \in A}|$ and $|\set{b \mid (a,b) \in B}|$, as subsets of $D$--finite sets, cannot be countable and are finite. Hence, $|X|$ is also finite, contradiction.
    \\
    ii)
    iii)
\end{customthm}

\begin{customthm}{I.3.16}
    
\end{customthm}

\begin{customthm}{I.4.1}
    For the cardinality, of the set of real continuous functions, it is enough to observe that every such a function is determined by its values at rational points, i.e., let $p_n/q_n \to x$, then $f(x) = \lim f(p_n/q_n)$. So the cardinality is $\continuum^\omega = \continuum$.
    
    For all the real functions, it is obviously $\continuum^\continuum$ (every real point can be mapper to any real point).
\end{customthm}

\begin{customthm}{I.4.2}
    It is enough to prove that for two sequences $x,y \in \omega^\omega$ that are chosen arbitrarily and are distinct, the linear orderings $x_0 + \Z + x_1 + \Z + \ldots$ and $y_0 + \Z + y_1 + \Z + \ldots$ are different.
    
    Let us first look at $x_0 + \Z$ and $y_0 + \Z$. If $x_0 \neq y_0$, say $x_0>y_0$, then these orders cannot be isomorphic---there is nowhere we can send $x_0$ to without breaking the ordering. And the same argument holds for $x_0 + \Z + \ldots + x_k + \Z$ and $y_0 + \Z + \ldots + y_k + \Z$ for any $k$. Finally, for $x_0 + \Z + x_1 + \Z + \ldots$ and $y_0 + \Z + y_1 + \Z + \ldots$, we look at the minimal $k$ such that $x_k$ and $y_k$ are different and repeat the argument.
\end{customthm}

\begin{customthm}{I.4.3}
    Any polynomial has at most finitely many roots and there are countably many polynomials with integer coefficients. So there are at most $\omega^{<\omega} = \aleph_0$ algebraic reals. And of course linear polynomials with integer coefficient have different algebraic roots and form a countable set, so there are exactly countably many algebraic reals.
\end{customthm}

\begin{customthm}{I.4.4}
    It suffices to prove it for $\R \times \R$, because it has the same cardinality as $\R$. Let $S$ be a countable subset of $\R \times \R$. Now, for each real $r$, the line $(\set{r} \times \R) \setminus S$ has at least one point (otherwise $S$ would be the whole line and hence of cardinality continuum). So the whole set $(\set{r} \times \R) \setminus S$ must have cardinality $1 \cdot |\R| = \continuum$.
\end{customthm}

\begin{customthm}{I.4.5}
    i) The set of irrational numbers is equal to $\R \setminus \Q$.
    \\
    ii) The set of transcendental numbers is equal to $\R\setminus \mathbb{A}$
    \\
    By above and previous exercise, both sets are of cardinality continuum.
\end{customthm}

\begin{customthm}{I.4.6}
    There are at least $\continuum$ many open sets of reals as each interval $(x, \infty)$ is distinct, open, and there are $\continuum$ many of them. On the other hand, each open set is a countable sum of rational intervals and there are at most $\omega^\omega = \continuum$ possible combinations of those.
\end{customthm}

\begin{customthm}{I.4.7}
    Cantor set is non-empty, because it is in one-to-one correspondence with $0$-$1$ $\omega$--sequences and hence has cardinality $\continuum$. It is closed, because it is an intersection of closed sets. What is left is to prove that the Cantor set has no isolated points. Let $x$ be an arbitrary point in the Cantor set and let us pick $\epsilon > 0$. It suffices to find $y \neq x$ such that $|x-y|<\epsilon$. Recall that the Cantor set $C$ is an intersection of $2^n$ intervals $C_n$ each of length $3^{-n}$. Pick $n$ large enough so that $3^{-n}<\epsilon$. Let $[a,b]$ be one of those intervals that comprise $C_n$. Since $x \in C$, $x \in C_{n+1}$ and there is a subinterval $[a_0,b_0] \subset [a,b]$. But, by the construction of $C_{n+1}$, there is another interval $[a_1,b_1] \subset [a,b]$, which has an empty intersection with $[a_0,b_0]$. It is clear from the construction of the Cantor set that it has a nonempty intersection with the interval $[a_0,b_0]$. Hence, there is a $y \neq x$ in the Cantor set such that $|x-y| \leq 3^{-n} < \epsilon$.
\end{customthm}

\begin{customthm}{I.4.8}\label{ex:perfect-set-intersected-with-interval-cardinality-continuum}
    Let $P$ be perfect and $P \cap (a,b) \neq \emptyset$. Pick an $x \in P \cap (a,b)$. Since, $P$ is perfect, there must be a sequence of elements not equal to $x$ both in $(a,x)$ and in $(x,b)$. So $P \cap (a,x) \neq \emptyset \neq P \cap (x,b)$. Now, pick $x_0 \in (a,x)$ and $x_1 \in (b,x)$. This process can be repeated and after $\omega$ many steps with have picked $\continuum$ many distinct points in $P \cap (a,b)$.
\end{customthm}

\begin{customthm}{I.4.9}\label{ex:P_1-and-P_2-perfect-and-not-subset-of-each-other-then-their-difference-is-of-cardinality-continuum}
    Let $P_2 \not \subset P_1$ be perfect sets. There is a point $x \in P_2 \setminus P_1$. There must be a sufficiently small interval $(a,b)$ containing $x$ such that $(a,b) \cap P_1 = \emptyset$ (if it weren't the case we could construct a sequence of $P_1$ elements approaching $x$ and then $x \in P_1$). By the exercise above, this ends the proof.
\end{customthm}

\begin{customthm}{I.4.10}
    Let $P$ be perfect. Take any $p \in P$ and any neighborhood $(a,b)$ of $p$. Then, by exercise~\ref{ex:perfect-set-intersected-with-interval-cardinality-continuum} this neighborhood contains uncountably many elements of $P$.
\end{customthm}

\begin{customthm}{I.4.11}
    Let $P$ be perfect, $P \subset F$, where $F$ is closed and let $F^*$ be the set of all condensation points of $F$. By exercise above, the set of condensation points $P^*$ of $P$ is equal to $P$. But then, it must be the case that $P^* \subset F^*$, and so $P \subset F^*$.
\end{customthm}

\begin{customthm}{I.4.12}
    Let $F$ be an uncountable closed set and let $P$ be the perfect set constructed in the proof of Cantor-Bendixson theorem. Take any $a \in F^*$. Each neighborhood of $a$ must have an element from $P$, because $F \setminus P$ is countable and $a$ is a condensation point. But that means $a$ is a limit of elements of $P$, hence $a \in P$. So $F^* \subset P$. This, combined with the exercise above, gives us that $F^*=P$.
\end{customthm}

\begin{customthm}{I.4.13}
    By the exercise above and Cantor-Bendixson theorem, we have that $F = F^* \cup (F \setminus F^*)$, where $F^*$ is a perfect set and $F \setminus F^*$ is at most countable. Suppose there is another set $P$ such that $F = P \cup (F \setminus P)$ such that $P$ is perfect and $F \setminus P$ is countable.
    
    Suppose $P \subset F^*$, then $F = P \cup (F \setminus F^*)$, so $P = F^*$. We proceed similarly if $F^* \subset P$. Suppose $P \not\subset F^*$. But then $\emptyset = F^* \setminus P \cup ((F \setminus F^*) \setminus (F \setminus P)) \supset F^* \setminus P$ and, by exercise~\ref{ex:P_1-and-P_2-perfect-and-not-subset-of-each-other-then-their-difference-is-of-cardinality-continuum}, $F^* \setminus P$ has cardinality continuum. This is a contradiction!
\end{customthm}

\begin{customthm}{I.4.14}
    Suppose $\Q$ is the intersection of countable collection of open sets $U_n$. Since $\Q$ is dense, $U_n$ must also be dense. Let us enumerate $\Q$ by $q_n$. Consider sets $V_n = \R \setminus \set{q_n}$. Then the family of sets consisting of all $U_n$ and $V_n$ is a collection of open dense sets. By the Baire Category Theorem, the intersection of these sets is dense. But $\cap V_n = \emptyset$, so it is definitely not---contradiction.
\end{customthm}

\begin{customthm}{I.4.15}
    Suppose $B$ is a Borel set and $f \colon X \to Y$ is a continuous function. We need to prove that $f^{-1}(B)$ is also Borel. It is enough to prove that $\set{f^{-1}(B) \mid B \text{ Borel}}$ forms a $\sigma$-algebra and contains all open sets:
    \\
    i) it contains all open sets in $f^{-1}(Y)$, because $f$ is continuous.
    \\
    ii) set $\set{f^{-1}(B) \mid B \text{ Borel}}$ forms a $\sigma$-algebra, because $f^(Y)$ is its element, $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$, and $f^{-1}(Y/A) = X/f^{-1}(A)$.
\end{customthm}

\begin{customthm}{I.4.16}
    Set is $G_\delta$ if it is a countable intersection of open sets. An open set is a set such that given $x$ in that set and $\delta > 0$, whenever $|x-y| < \delta$, $y$ is an element of that set. Note that $f$ is continuous at $x$ just in case for all $n$, there is a $\delta_n$ such that for $x_1,x_2 \in B(x,\delta_n)$, we have that $|f(x_1)-f(x_2)|<1/n$. We need to prove that, for each $n$, the set
    \begin{equation*}
        C_n = \set{x \mid \exists \delta_n(x) \forall x_1,x_2 \in B(x, \delta) \implies |f(x_1) - f(x_2)| < 1/n}
    \end{equation*}
    is open. Take $x \in C_n$ and $\epsilon<\delta_n(x)/2$ (small enough to suffice, I think). Then any $y$ such that $|x-y|<\delta_n(x)/2$ is such that $y \in C_n$ (take $\delta_n(y)<\delta_n(x)/2$ or whatever). Hence, $C_n$ is open. To end the proof, note that $C = \cap C_n$ is the set of points of continuity of $f$.
\end{customthm}

\begin{customthm}{I.4.17}
    i) Define a map that takes $(x,y) \mapsto x_0, y_0, x_1, y_1, \ldots$, $x,y \in \mathcal{N}$. We prove that this map, say $F$, is a homeomorphism. It is clear that it is bijective. Let us now prove that $F$ is continuous. Take any finite sequence $s$ and look at the basis $O(s) = \set{f \in \mathcal{N} \mid s \subset f}$. This set will be taken by $F^{-1}$ to a set of the form $O(s^0) \times O(s^1)$, where $s^0 = s_0, s_2, s_4,\ldots$ and $s^1 = s_1, s_3, \ldots$. And this set is clearly open. Hence, $F$ is continuous. Now, we prove that $F$ is an open map, i.e., $F$ maps open sets to open sets. But, $F(O(s^1) \times O(s^2)) = O(s)$, where $s = s^1_0, s^2_0, s^1_1, \ldots$, which is open. \\
    ii) Let us define a map $F \colon \mathcal{N}^\omega \to \mathcal{N} \times \mathcal{N}$ such that $F(x) = y$ if and only if $y(n,m) = x_n(m)$. This is clearly a bijection. Take $O(s) \times O(t)$ and look at $F^{-1}(O(s) \times O(t))$. This is equal to some set $\prod_{i \in \omega} X_i$, where each $X_i$ is a subset if a copy of $\mathcal{N}$. Note that all but finitely many $X_i$ are equal to $\mathcal{N}$ and each $X_i$ is of the form $\bigcup_{i \in \omega} O(w^i)$ for some sequence of finite sequences $w_i$. Conversely, take a set $U$ that is in the basis of $\mathcal{N}^\omega$. Then $U$ is of the form $\prod_{i \in \omega} U_i$, where each $U_i$ is open in $\mathcal{N}$ and all but finitely many $U_i$ are a copy of $\mathcal{N}$. Again, the image of $U$ will be equal to some open $V \subset \mathcal{N} \times \mathcal{N}$. Indeed, it is true that for any finite sequence $s, t$ such that there are $f,g \in V$ extending $s$ and $t$ respectively, it holds that there is a finite extensions of $s,t$, say $s',t'$ such that $[s'], [t'] \in V$.
\end{customthm}

\begin{customthm}{I.4.18}
    Let $s \in T_F$, then there is some $f \in F$ such that $s \subset f$. But then $s^\frown f(length(s)+1) \subset f$, so $s$ cannot be maximal.
    
    Take a map $F \mapsto T_F$. We have just proved that $T_F$ has no maximal node, so the map is indeed between closed sets of the Baire space and sequential sequences without maximal nodes. Suppose trees $F$ and $G$ are getting mapped to the same $T$. Hence, $T_F = T_G$. Then, we have that $[T_F]=F$ and $[T_G]=G$ are equal, so $F$=$G$ and we know that our map is injective. Now, take any sequential tree without maximal nodes $T$ and note that $[T]$ is closed. So there is an $F$ that is getting mapped to $T$ via our map. Hence, the map is surjective.
\end{customthm}

\begin{customthm}{I.4.19}
    Let $P$ be a perfect Polish space. And let $F \colon P \to P'$ be a homeomorphism to a separable complete metric space. We need to find a closed copy of the Cantor set within $P'$. Let $S$ be a set of all finite sequences of $0$'s and $1$'s. Let us inductively define closed sets $I_s$:
    \begin{itemize}
        \item[(i)] $I_s \cap P'$ is perfect;
        \item[(ii)] $diam(I_s) \leq 1/length(s)$;
        \item[(iii)] $I_{s^\frown 0} \subset I_s$, $I_{s^\frown 1} \subset I_s$, and the intersection $I_{s^\frown 0} \cap I_{s^\frown 1}$ is empty.
    \end{itemize}
    And by completeness, it follows that for each $f \in \set{0,1}^\omega$, the set $P' \cap \bigcap_{n<\omega} I_{f_{|n}}$ has exactly one element.
    
    Now, define $F' \colon \set{0,1}^\omega \to P'$ as $F'(f) = x \in P' \cap \bigcap_{n<\omega} I_{f_{|n}}$. By the definition, $F'$ is an injection. Take any $x \in P' \cap \bigcap_{n<\omega} I_{f_{|n}}$ together with it's neighbourhood $U$. Observe that $F'^{-1}(U)$ is mapped to a set $O(s)$ in the base of the topology of the Cantor space, for some finite sequence of $0$'s and $1$'s $s$. On the other hand, take any base $O(s)$ in the Cantor space and it will be mapped by $F$ to the set of the form $U \cap \bigcup \set{P' \cap \bigcup_{n<\omega} I_{f_{|n}} \mid f \in \set{0,1}^\omega}$, where $U$ is open in $P'$. And this set is open in $P' \cap \bigcup \set{ \bigcap_{n<\omega} I_{f_{|n}} \mid f \in \set{0,1}^\omega}$. Hence, $F'$ is a homeomorphism between the Cantor space and a closed subset of $P'$. This ends the proof.
\end{customthm}

\begin{customthm}{I.4.20}
    Let $x_n$ be a dense subset of a Polish space $X$ and define $f(x) = (d(x,x_n) \mid n \in N)$. Note that we can assume $0 \leq d \leq 1$ as we can always normalize the metric via map $d \mapsto 1/(1+d)$.
    
    Suppose $f(x)=f(y)$. Let $\epsilon > 0$ and take $n$ such that $d(x,x_n) < \epsilon/2$. Then, $d(x,y) \leq d(x,x_n) + d(y,x_n = 2d(x,x_n) < \epsilon)$. But this works for any $\epsilon > 0$, so $d(x,y)=0$, hence $x=y$. So $f$ is injective.
    
    Take any $\zeta_m \to x$, then 
    $f(\zeta_m) = (d(\zeta_m,x_n) \mid n \in N) = ( \lim d(\zeta_m, x_n) \mid n \in N) = f(x)$. So $f$ is continuous.
    
    Take $f(\zeta_m) \to f(x)$. Then, $d(\zeta_m,x_n) \to d(x,x_n)$ for every $n$. But then for any $\epsilon > 0$, there is an $n$ such that for sufficiently large $m$, we have that $d(\zeta_m,x) < d(\zeta_n, x_n) + d(x_n,x) < \epsilon/2 + \epsilon/2 = \epsilon$. Hence, $\zeta_m \to x$ and $f$ is an open mapping.
    
    We now prove that the image of $f$ is a $G_\delta$ subset of the Hilbert's cube. Observe that Hilbert's cube is a Polish space and that the image of $f$ is also a Polish space. Take the base $B_n$ of the Hilbert's cube. For any open neighborhood of $f(x)$ and $\epsilon>0$, there is a base $B_n$ contained in that neighborhood such that $\text{diam}(f(X) \cap B_N) < \epsilon$ (with respect to the induced complete metric). Define a $G_\delta$ set $Y$ as follows.
    \begin{equation*}
        Y = \bigcap_{m<\omega} \bigcup_{n<\omega} \set{B_n \mid \text{diam}(f(X) \cap B_n) < 1/m}.
    \end{equation*}
    Observe that $f(X) \subset Y$. Take $y \in Y$. For every $m$, there is an $n(m)$ such that $y \in B_{n(m)}$ with $\text{diam}(f(X) \cap B_{n(m)} < 1/m$. So $f(X)$ is dense in $Y$ and there is a Cauchy sequence $y_m \in f(X)$ converging to $y$. Hence, $y \in f(X)$ and the image of $f$ is $G_\delta$.
\end{customthm}



\end{document}