Title: Part II / Logic and Set Theory
Tags: Set::Theory First-order::Predicate::Logic Well::Ordering::and::Ordinals Propositional::Logic Posets::and::Zorn's::Lemma Cardinal::Arithmetic

Q: Definition. The language of Propositional Logic consists of [...]
A: a set P of primitive propositions and the set \(L=L(P)\) of propositions(or compound propositions) as follows:
(i)\(P \subset L\)
(ii) \(\bot \in L\)
(iii)if \(p,q \in L\) then \((p \implies q) \in L\)

Q: Definition. A valuation on L is [...]
A: a function \(v : L \to \{0,1 \}\) s.t.
(i) \(v(\bot) = 0\)
(ii) \(v(p \implies q) = \begin{cases} 0 & \text{ if }v(p) = 1, v(q) = 0 \\ 1 & \text{otherwise}\end{cases}\)

Q: Proposition. (i) If \( v \) and \( v' \) are valuations with \( v|_P = v'|_P \), then \( v = v' \).
(ii) For any function \( w: P \to \{0,1\} \), there exist a valuation \( v \) on \( L \) such that \( v|_P = w \).
A: (i) Let \( L' = \{ p \in L : v(p) = v'(p) \} \). By assumption, \( L_1 \subset L' \). If \( p, q \in L' \), then \( v(p \Rightarrow q) = v'(p \Rightarrow q) \) by definition. It follows that \( L_n \subset L' \) implies \( L_{n+1} \subset L' \) for every \( n \in \mathbb{N} \). By induction, \( L_n \subset L' \) for all \( n \in \mathbb{N} \), and thus \( v = v' \).
(ii) Set \( v(p) = w(p) \) for every \( p \in P \), and set \( v(\bot) = 0 \). This defines \( v \) on \( L_1 \). Having defined \( v \) on \( L_n \) for some \( n \in \mathbb{N} \), for \( p \in L_{n+1} \setminus L_n \), write \( p = (q \Rightarrow r) \) for unique \( q, r \in L_n \), and define \[ v(p) = \begin{cases} 0 & \text{if } v(q) = 1, v(r) = 0, \\ 1 & \text{otherwise}. \end{cases} \] This defines \( v \) on \( L_{n+1} \). Thus, we obtain a valuation \( v \) on \( L \) with \( v|_P = w \).

Q: Definition. Let \(t \in L\). We say t is a tautology if [...]
A: \(v(t) = 1\) for all valuations.

Notation. At this point we enrich our language by introducing the symbols T('true' or 'top'), and \(\wedge\)('and'), \(\vee\)('or') and \(\neg\)('not').
\[T = (\bot \implies \bot)\]\[\neg p = (p \implies \bot)\]
\[p \vee q = (\neg p \implies q)\]
\[p \wedge q = \neg(p \implies \neg q)\]

Q: Definition. Let \(S \subset L, t \in L\). Say S entails t(or semantically entails t)if [...]We write this as \(S \vDash t\). We say S proves t(or syntactically entails t) if [...] We write \(S \vdash t\).
A: for any valuation v, \[v(s) = 1 \;\; \forall s \in S \implies v(t) = 1\]; there's a proof of t from S.

Q: Definition. For \(t \in L\), valuation v, say t is true in v (or v is a model of t) if [...]
A: \(v(t) = 1\).

Q: In propositional logic which propositions do we adopt as axioms?
A: \[p \implies(q \implies p) (p,q \in L)\]\[(p \implies (q \implies r)) \implies ((p \implies q) \implies (p \implies r)) (p,q,r \in L)\]\[\neg \neg p \implies p(p \in L)\]

Q: Proposition. Deduction Theorem. Let \(S \subset L, p,q \in L\). Then \(S \vdash (p \implies q)\) iff \(S \cup \{p\} \vdash q\)
A: Assume \(S \vdash (p \implies q)\). Write down a proof of \(p \implies q\) from S and add the following lines to obtain a proof of q from \(S \cup \{p\}\):\[p \; \; \text{(premiss)}\]\[q \; \; \text{(MP)}\]Now lets assume \(S \cup \{p\} \vdash q\). Let \(t_1 , \dots , t_n = q\) be a proof of q from \(S \cup \{p\}\). We prove that \(S \vdash (p \implies t_i)\) by induction on i: putting \(i = n\) gives \(S \vdash (p \implies q)\)
Case 1: \(t_i\) is an axiom of \(t_i \in S\). Then \[t_i \implies (p \implies t_i) \; \; (A1)\]\[t_i \;\; (\text{premiss or axiom})\]\[p \implies t_i \;\; (MP)\]is a proof of \(p \implies t_i\) from S.
Case 2: \(t_i = p\). In this \(S \vdash (p \implies p)\) since \(\vdash(p \implies p)\)
Case 3: \(\exists j,k < i, t_k = (t_j \implies t_i)\)
By induction we can write down proofs of \((p \implies t_j)\) and \((p \implies (t_j \implies t_i))\) from S. We add the lines: \[(p \implies (t_j \implies t_i)) \implies ((p \implies t_j) \implies (p \implies t_i)) \; \; (A2)\]\[(p \implies t_j) \implies (p \implies t_i) \;\; (MP)\]\[p \implies t_i \; \; (MP)\]to obtain a proof of \(p \implies t_i\) from S.

Q: Proposition. Soundness Theorem. Let \(S \subset L, t \in L\). Then \(s \vdash t\) implies \(s \vDash t\).
A: Let \(t_1 , \dots , t_n = t\) be a proof t from S. Let v be a model of S. Need \(v(t) = 1\). We prove \(v(t_i) = 1\) by induction on i.
If \(t_i\) is a premiss then \(v(t_i) = 1\). Since v is a model of S.
If \(t_i\) is an axiom then \(v(t_i) = 1\) as all axioms are tautologies
If \(\exists j,k < i\) s.t. \(t_k = (t_j \implies t_i)\) then by induction \(v(t_j) = v(t_j \implies t_i) = 1 \) hence \(v(t_i) = 1\)

Q: Definition. Let \(S \subset L \). Say S is inconsistent if \([...]\), otherwise S is consistent.
A: S \vdash \bot

Q: Theorem. Model Existence Lemma. Let \(S \subset L\). Then if S is consistent, S has a model.
A: Only consider case when set P of primitive propositions countable.
Note that \(L_1 = P \cup \{\bot\}\) is countable and hence by induction \(L_n\) is countable thus \(L = \cup_{n \in \mathbb{N}} L_n\) countable.
Enumerate L as \(t_1 , t_2 , t_3 , \dots\)
If \(T \subset L\) is consistent and \(t \in L\) then one of \(T \cup \{t\}\) or \(T \cup \{\neg t\}\) is consistent. Indeed, if not, then \(T \cup \{t\} \vdash \bot\) and \(T \cup \{\neg t\} \vdash \bot\).
Then by the deduction theorem \(T \vdash \neg t, T \vdash(\neg t \implies \bot)\) and hence \(T \vdash \bot\) by MP.
Now start with the consistent set S. Let \(S_0 = S\), define \(S_n\) by induction: assume \(S_{n-1}\) is defined and is consistent. Then let \(S_n\) be either \(S_{n-1} \cup \{t_n\}\) or \(S_{n-1} \cup \{\neg t_n\}\) so that \(S_n\) is consistent. Finally, let \(\overline{S} = \bigcup_{n \ge 0} S_n\).
Note that \(S \subset \overline{S}\) and \(\forall t \in L\) either \(t \in \overline{S} \) or \(\neg t \in \overline{S}\). \(\overline{S}\) is consistent: if \(\overline{S} \vdash \bot\) then as proofs are finite \(\exists n\) s.t. \(S_n \vdash \bot\). Contradiction.
S is deductively closed, i.e. if \(t \in L\) and \(\overline{S} \vdash t\) then \(t \in \overline{S}\). Indeed, if \(t \not \in \overline{S}\) then \(\neg t \in \overline{S}\). So we have a proof: first write down a proof of t from S, and add the lines \(\neg t(premiss), \bot (MP)\) so \(\overline{S} \vdash \bot\).
Now define \(v : L \to \{0,1\}\) by \(v(t) = \begin{cases}1 & \overline{S} \vdash t \\ 0 & \text{otherwise}\end{cases}\)
Note that v is a model of \(\overline{S}\) and hence of S, once we show that v is a valuation.
Firstly, \(v(\bot) = 0\) since \(\overline{S}\) is consistent. We now check \(v(p \implies q)\) for abitrary \(p,q \in L\)
Case 1: \(v(p ) = 1, v(q) = 0\), ie \(p \in \overline{S}, q \not \in \overline{S}\). Need \(v(p \implies q) = 0\). If not then write down a proof of \(p \implies q\) from \(\overline{S}\) and add p as a premiss, q by MP so \(\overline{S} \vdash q\) and \(q \in \overline{S}\) since it is deductively closed.
Case 2: \(v(q) = 1\), need \(v(p \implies q) = 1\)
We have \(q \implies (p \implies q)\) by A1 so by adding q we have \( p\implies q\)
Case 3: \(v(p) = 0\), need \(v(p \implies q) = 1\) ie \(\overline{S} \vdash (p \implies q)\) or equivalently \(\overline{S} \cup \{p\} \vdash q\) by deduction theorem. We therefore have \(p, \neg p\) are premisses, \(\bot\) by MP, \(\bot \implies((q \implies \bot) \implies \bot)\) by A1, \(\neg \neg q\) by MP and using A3 we have q.

Q: Corollary. Adequancy Theorem. Let \(S \subset L, t \in L\). If \(S \vDash t\) then \(S \vdash t\).
A: Since \(S \vDash t\), we have \(S \cup \{\neg t\}\vDash \bot\). By theorem 4, \(S \cup \{\neg t\} \vdash \bot\) and have \(S \vdash \neg \neg t\) by the Deduction theorem. Add the lines \[\neg \neg t \implies t\]\[t\]to get \(S \vdash t\).

Q: Theorem. Completeness Theorem. Let \(S \subset L, t \in L\). Then \(S \vDash t\) iff \(S \vdash t\)
A: Using the Soundness theorem and Adequancy theorem.

Q: Corollary. Compactness Theorem. Let \(S \subset L\) and \(t \in L\). If \(S \vDash t\) then exists finite subset  S' of S s.t. \(S' \vDash t\)
A: Trivial if \(\vDash\) replaced with \(\vdash\) as proofs are finite.

Q: Corollary. Let \(S \subset L\). If every finite subset of S has a model then S has a model.
A: If S doesn't have a model, then \(S \vDash \bot\). By Corollary 7 exists finite subset S' of S s.t. \(S' \vDash \bot\). Contradiction

Q: Corollary. Decidability Theorem. Let \(S \subset L \) be a finite set and \(t \in L\). Then there's an algorithm that can determine in finite time whether \(S \vdash t\)
A: Proof  is trivial if \(\vdash\) is replaced with \(\vDash\). Just a truth table for \(S \cup \{t\}\) of all \(2^n\) possible values of the primitive propositions that occur in \(S \cup \{t\}\), where n is the number of such propositions.

Q: Definition. A well-ordering of a set X is [...]
A: a linear order < on X s.t. every subset of X has a least element: \[(\forall S \subset X)(S \neq \emptyset \implies (\exists x \in S)(\forall y \in S)(x \le y))\]

Q: Definition. Let X,Y be linearly ordered sets. Say \(X,Y\) are order-isomorphic if [...]
A: \(\exists\) bijection \(f: X \to Y\) that is order-preserving: \(x < y \implies f(x) < f(y)\).
Back Extra: Such an f is an order isomorphism. Note that the inverse is also an order-isomorphism.

Q: Definition. A subset I of a linearly ordered set X is an initial segment of X if \[[...]\]
A: \forall x,y \in X, (x \in I \wedge y < x) \implies y \in I

Q: Lemma. Let X,Y be well-ordered sets, I be an initial segement of Y and \(f: X \to I\) be an order-isomorphism. Then for every \(x \in X\) we have \[f(x) = \min (Y \setminus \{f(y) | y < x\})\]
A: Fix \(x \in X\) and let \(A = Y \setminus \{f(y) | y < x\}\). Note that \(A \neq \emptyset\) as \(f(x) \in A\). Let \(a = \min A\). Then \(a \le f(x)\), so \(a \in I\). Hence \(a = f(z)\) for some \(z \in X\). We need to show that \(z = x\). Since \(f(z) = a \le f(x)\) we have \(z \le x\) as f is order preserving. If \(z < x\), then \(f(z) \not \in A\), ie \(a \not \in A\). Contradiction.

Q: Proposition. Induction. Let X be a well-ordered set and \(S \subset X\) s.t. \(\forall x \in X,\) if \(y \in S\) for all \(y < x\), then \(x \in S\). Then \(S = X\)
A: If not then let \(x = \min (X \setminus S)\). Then for \(y<x.\) we have \( y \in S\). By assumption on S, we have \(x \in S\).

Q: Proposition. Let \(X,Y\) be well-ordered sets that are order isomorphic. Then there is a unique order isomorphism from X to Y.
A: Assume \(f,g: X \to Y\) are order isomorphisms. We prove \((\forall x)(f(x) = g(x)) \) by induction.
Fix \(x \in X\). Assume \((\forall y < x)(f(y) = g(y))\)(induction hypothesis)
By Lemma 1, \(f(x) =\min A, A = Y \setminus \{f(y) | y < x\}\)
\(g(x) = \min B, B = Y \setminus\{g(y) | y < x\}\)
By induction hypothesis, \(A = B\), so \(f(x) = g(x)\).
By proposition 2, \(f = g\)/=.

Q: Theorem. Definition by recursion. Let X be a w.o. set and Y be an arbitrary set. Then for any function \(G: P(X \times Y) \to Y\) there exists a unique \(f : X \to Y\) s.t. \(\forall x \in X\) \(f(x) = G(f|_{I_x})\).
A: Say h is an attempt if h is a function \(I \to Y\) where the domain of h, denoted \(\text{dom h}\) is an i.s. I of X and \(\forall x \in \text{ dom h}, h(x) = G(H|_{I_x})\)
The theorem says that there is a unique attempt whose domain is X
We first show that if h,h' are attempts then \(h(x) = h'(x) \forall x \in \text{dom h} \cap \text{ dom h'}\) by induction.
Fix \(x \in \text{dom h} \cap \text{ dom h'}\), assume \(h(y) = h'(y) \forall y < x\)
We have \(h(x) = G(h|_{I_x}) = G(h'|_{I_x}) = h'(x)\)
To complete the proof for existence, we let \(f = \bigcup\{ h| h \text{ is an attempt} \}\)
For any \(x \in X\), if there's an attempt h defined at x, then \(h(x)\) is independent of h by above. So f is a function.
The domain of f is \(\bigcup\{\text{dom h | h an attempt}\}\) which is an i.s. of X
Given \(x \in \text{dom }f,\)there's an attempt h defined at x and \(f(x) = h(x)\)
It follows that \(f(y) = h(y) \forall y < x\). Hence \(f(x) = g(x) = G(h |_{I_x}) = G(f|_{I_x})\). Thus f is an attempt
If \(\text{dom f} \neq X\), then \(\text{dom }f = I_x\) for some \(x \in X\). So there does not exist an attempt defined at x. But \(f \cup \{(x, G(f))\}\) is an attempt defined at x. Contradiction. \(\square\)

Q: Proposition. Subset Collapse. Let Y be a w.o. set and \(X \subset Y\). Then there exists a unique i.s. of Y which is o.i. to X.
A: Uniqueness. Assume f is an order-isomorphism from X to an i.s. of Y. By Lemma 1, \[f(x) = \min \{Y \setminus \{f(y) | y <x \}\} \; \; \forall x \in X\]By induction f is uniquely determined.
Existence. WLOG \(Y \neq \emptyset\). Fix \(y_0 \in X\). Define \(f: X \to Y\) by recursion:\[f(x) = \begin{cases}\min\{Y \setminus\{f(y) | y < x\}\} & \text{if }Y\setminus\{f(y) | y <x \} \neq \emptyset \\ y_0 & \text{ otherwise}\end{cases}\]We first prove that the otherwise clause doesn't arise.
We do this by proving that \(f(x) \le x\) for all \(x \in X\) by induction.
Fix \(x \in X\) and assume \(f(y) \le y\) for all \(y < x\). Then \(x \in Y \setminus\{f(y) | y < x\}\) and have \(f(x) \le x\)
Fix \(y<x\) in X. \(f(x) \in Y \setminus \{f(z) | z < x\} \subset Y \setminus \{f(z) | z < y\}\)
Hence \(f(y) \le f(x)\) and so \(f(y) < f(x)\). So f is order-preserving
Let \(a \in Y \setminus \text{im} f\)
We show that \(f(x) < a \; \; \forall x \in X\). It'll then follow that \(\text{im}f\) is an i.s. of Y and we're done
By induction: Fix \(x \in X\), assume that \(f(y) < a \; \; \forall y < x\)
\(a \in Y \setminus\{f(y) | y < x\}\), so \(f(x) \le a\), and thus \(f(x) < a\)

Q: Theorem. Let X,Y be w.o. sets. Then either \(X \le Y\) or \(Y \le X\) where \(X \le Y \implies \)X is order-isomorphic to an initial segment of Y
A: Assume \(Y \not \le X\). In particular \(Y \neq \emptyset\), So can fix \(y_0 \in Y\)
Define \(f:X \to Y\) by recursion: \[f(x) = \begin{cases}\min\{Y \setminus\{f(y) | y < x\}\} & \text{if }Y\setminus\{f(y) | y <x \} \neq \emptyset \\ y_0 & \text{ otherwise}\end{cases}\]Assume the otherwise clause arises. Then there's a least x where it occurs. So \[f(I_x) = \{f(y) | y < x\} = Y\]And \(\forall y < x, f(y) = \min (Y \setminus \{f(z) | z < y\})\)
As in Proposition 5 we show that \(f|_{I_x}\) is order-preserving. So Y is order-isomorphic to an i.s. of X. Contradiction.
As in Proposition 5 we show f is order-preserving and \(\text{im }f\) is an i.s. of Y. Hence \(X \le Y\)

Q: Proposition. Let X,Y be well ordered sets. If \(X \le Y\) and \(Y \le X\) then X is order isomorphic to Y.
A: Let \(f: X \to Y\) and \(g: Y \to X\) be order isomorphisms to initial segments of Y and X respectively. Then \(g \circ f : X \to X\) is an order isomorphism to an i.s. of X. By Proposition 5 and Proposition 3 \(g \circ f = Id_X\). Similarly \(f\circ g = Id_Y\). \(\square\)

Q: Proposition. Let \(\{X_i | i \in I\}\) be a nested set of well ordered sets. Then \(\exists\) well ordered set \(X\) s.t. \(X_i \le X\) for all \(i \in I\)
A: Let \(X = \bigcup_{i \in I} X_i\)
For \(x,y \in X\), we let \(x < y\) iff \(\exists i \in I \) s.t. \(x,y \in X_i\) and \(x <_i y\) where \(<_i\) is the well ordering of \(X_i\)
Since the \(X_i\) are nested, it follows that \(<\) on X is a well-defined linear order s.t. each \(X_i\) is an initial segment of X.
Let \(S \subset X, S \neq \emptyset\). Then \(\exists i \in I\) s.t. \(X_i \cap S \neq \emptyset\)
Since \(X_i\) is a well ordered set, \(X_i \cap S\) has a least element say x. Since \(X_i\) is an initial segment of \(X,\) x is a least element of S.

Q: Definition. An ordinal is [...] The order-type of a well-ordered set X is [...]
A: a well-ordered set with two ordinals regarded the same if they are order-isomorphic to each other.; the unique ordinal to which its order-isomorphic.
Back Extra: For \(\alpha,\beta\) ordinals and \(X,Y\) well-ordered sets of those order types we write \(\alpha \le \beta\) to mean \(X \le Y .\)Similarly for \(\alpha < \beta\).

Q: Proposition. Let \(\alpha\) be an ordinal. Then the ordinals strictly less than \(\alpha\) form a well-ordered set of order-type \(\alpha\)
A: Let X be a w.o. set whose order type is \(\alpha\)
Let \(X' = \{Y \subset X | Y \text{ is a proper i.s. of } X\}\)
X' is linearly ordered by \(<\) by proposition 5, theorem 6 and proposition 7.
The map \(X \to X', x \mapsto I_x\) is an order-isomorphism. Hence \(X'\) is well-ordered by \(<\) and so is \(\{\text{order type}(Y) | Y \in X'\}\)
which consists exactly of ordinals \(< \alpha\)

Q: Theorem. Let S be a non empty set of ordinals. Then S has a least element
A: Let \(\alpha \in S\). If \(\alpha\) is not a least element, then \(S \cap I_{\alpha} \neq \emptyset\).
By proposition 9, \(S \cap I_{\alpha}\) has a least element \(\beta\). Since \(I_{\alpha}\) is an i.s. of ordinals, it follows that \(\beta\) is a least element of S.

Q: Theorem. Burali-Forti paradox. The ordinals do not form a set.
A: Assume that X is a set consisting of all ordinals.
By Theorem 10, X is well-ordered by \('<'\)
Let \(\alpha \) be the order type of \(X\). So \(\alpha \in X\), and \(I_{\alpha}\) is a proper i.s. of X of order-type \(\alpha\), and have \(I_{\alpha} \) is o.i. to X. Contradiction.

Q: Theorem. There exists an uncountable ordinal.
A: Idea: If there is an uncountable ordinal, then there is a least one, say \(\alpha\). Then \( I_{\alpha} \) is the set of countable ordinals, i.e., the set of order-types of well-orderings of subsets of \(\mathbb{N}\).
Proof: Define
\[A = \{(M,R) \in \mathbb{P}\mathbb{N} \times \mathbb{P}(\mathbb{N} \times \mathbb{N}) : R \text{ is a well-ordering of } X \}\]
as the set of well-orderings of subsets of \(\mathbb{N}\). Then define
\[B = \{\text{order-type}(X) : X \in A\}\]
which consists of all countable ordinals.
Set \(\omega_1 = \sup B\). If \(\omega_1\) is countable, then so is \(\omega_1^+\), implying \(\omega_1^+ \in B\). This leads to \(\omega_1^+ \leq \omega_1\), a contradiction.

Q: Theorem. Hartog's Lemma.\[\text{ For every set } X,\text{ there is an ordinal }\gamma\text{ which does not inject into } X\]
A: This generalizes Theorem 12. We define the set \(B\) of order-types of well-orderings of subsets of \(X\). Define
\[\gamma = (\sup B)^+.\]
If there exists an injection from \(\gamma\) to \(X\), then \(\gamma\) induces a well-ordering on a subset of \(X\) with order-type \(\gamma\). This implies \(\gamma \in B\), so
\[\gamma \leq \sup B < \gamma,\]
which is a contradiction.

Q: Proposition. \(\beta \le \gamma\) implies \(\alpha + \beta \le \alpha + \gamma\)
A: Proof by induction on \(\gamma\).
Base case: \(\gamma = 0\). If \(\beta \leq \gamma\), then \(\beta = 0\), so
\[\alpha + \beta = \alpha + \gamma = \alpha.\]
Successor case: \(\gamma = \delta^+\). If \(\beta \leq \gamma\), then either \(\beta = \gamma\) or \(\beta \leq \delta\). By induction,
\[\alpha + \beta \leq \alpha + \delta < (\alpha + \delta)^+ = \alpha + \beta.\]
Limit ordinal case: If \(\gamma\) is a nonzero limit ordinal and \(\beta \leq \gamma\), then \(\beta < \delta\) for some \(\delta < \gamma\). By induction,
\[\alpha + \beta \leq \alpha + \delta \leq \alpha + \gamma.\]

Q: Lemma. Let \( S \) be a non-empty set of ordinals. Then
\[\alpha + \sup S = \sup \{\alpha + \beta : \beta \in S\}\]
for any ordinal \( \alpha \).
A: Put \( T = \{\alpha + \beta : \beta \in S\} \).
For \( \beta \in S \), we have \( \beta \leq \sup S \), and hence \( \alpha + \beta \leq \alpha + \sup S \) by Proposition 14.
It follows that \( \sup T \leq \alpha + \sup S \).
To show the reverse inequality, first assume that \( S \) has a greatest element \( \gamma \).
Then \( \gamma = \sup S \), and \( \alpha + \gamma \) is also the greatest element of \( T \) by Proposition 14.
It follows that \( \sup T = \alpha + \gamma = \alpha + \sup S \).
Now assume that \( S \) has no greatest element. Then \( \lambda = \sup S \) is a non-zero limit ordinal.
Indeed, \( \lambda \notin S \) as \( S \) has no greatest element, and so \( S \subset I_{\lambda} \),
which implies that \( \lambda = \sup S \leq \sup I_{\lambda} \), so \( I_{\lambda} \) has no greatest element.
Next, given \( \gamma < \lambda \), there exists \( \beta \in S \) with \( \gamma < \beta \).
Hence \( \alpha + \gamma \leq \alpha + \beta \leq \sup T \). It follows that
\[\alpha + \sup S = \alpha + \lambda = \sup \{\alpha + \gamma : \gamma < \lambda\} \leq \sup T.\]

Q: Proposition. \( \alpha + (\beta + \gamma) = (\alpha + \beta) + \gamma \).
A: We proceed by induction on \( \gamma \) with \( \alpha, \beta \) fixed. As usual, there are three cases.
\( \gamma = 0 \):
\[\alpha + (\beta + 0) = \alpha + \beta = (\alpha + \beta) + 0.\]
\( \gamma = \delta^+ \) is a successor: Then by induction, we get
\[\alpha + (\beta + \gamma) = \alpha + (\beta + \delta)^+ = \left[ \alpha + (\beta + \delta) \right]^+ = \left[ (\alpha + \beta) + \delta \right]^+ = (\alpha + \beta) + \gamma.\]
\( \gamma \) is a non-zero limit: Then using Lemma 15 and induction, we get
\[\alpha + (\beta + \gamma) = \alpha + \sup \{\beta + \delta : \delta < \gamma\}\]
\[= \sup \{\alpha + (\beta + \delta) : \delta < \gamma\}\]
\[= \sup \{(\alpha + \beta) + \delta : \delta < \gamma\} = (\alpha + \beta) + \gamma.\]
\(\square\)

Q: Proposition. The synthetic and inductive definitions of ordinal addition coincide.
A: Let us temporarily write \(\alpha \dot{+} \beta\) for the synthetic definition while keeping \(\alpha + \beta\) for the inductive definition of addition. We prove \(\alpha + \beta = \alpha \dot{+} \beta\) by induction on \(\beta\) with \(\alpha\) fixed.
\(\beta = 0\):
\[\alpha + 0 = \alpha = \text{order-type}(\alpha \sqcup 0) = \alpha \dot{+} 0.\]
\(\beta = \delta^+\) is a successor: by induction, we have
\[\alpha + \beta = (\alpha + \delta)^+ = (\alpha \dot{+} \delta)^+.\]
The latter is the order-type of \((\alpha \sqcup \delta) \sqcup 1\) which is order-isomorphic to \(\alpha \sqcup (\delta \sqcup 1)\).
Thus,
\[\alpha + \beta = \alpha \dot{+} \delta^+ = \alpha \dot{+} \beta.\]
\(\beta\) is a non-zero limit: By induction we have
\[\alpha + \beta = \sup \{\alpha + \delta : \delta < \beta\} = \sup \{\alpha \dot{+} \delta : \delta < \beta\}.\]
For \(\delta < \beta\), \(\alpha \dot{+} \delta\) is the order-type of \(\alpha \sqcup \delta\), and the supremum of the nested set \(\{\alpha \sqcup \delta : \delta < \beta\}\) of well-ordered sets is
\[\bigcup_{\delta < \beta} (\alpha \sqcup \delta) = \alpha \sqcup \beta\]
which has order-type \(\alpha \dot{+} \beta\). This completes the proof that \(\alpha + \beta = \alpha \dot{+} \beta\) in this case. \(\square\)

Q: Definition. A partial order on a set X is [...] A poset is a set with a partial order.
A: a relation \(\le\) on X that is reflexive, antisymmetric and transitive.
Back Extra: We write \(x<y\) if \(x \le y\) and \(x \neq y\)

Q: Definition. A Hasse diagram of a poset X is [...]
A: a drawing of X in which we join x to y with an upward edge if y covers x, ie, \(x<y\) and \(\not \exists z \quad x < z < y\)

Q: Definition. A subset S of a poset X is a chain if [...] A subset S is an antichain if [...]
A: S is linearly ordered by the partial order of X.; no two distinct elements of S are related.

Q: Definition. Let X be a poset, \(S \subset X, x \in X\). Say x is an upper bound for S if [...] Say x is a least upper bound or a supremum of S if [...]
A: \(y \le x\) for all \(y \in S\).; x is an upper bound for S and \(x \le y\) for all upper bounds y for S.

Q: Definition. A poset X is complete if [...]
A: every subset of X has a supremum.
Back Extra: X has a greatest element and a least element.

Q: Definition. A map \(f:X \to Y\) between posets is said to be order preserving if \[[...]\]
A: x \le y \implies f(x) \le f(y)

Q: Theorem. Knasten-Tarski fixed point theorem. Let X be a complete poset and \(f:X \to X\) be order-preserving. Then f has a fixed point.
A: Let \(S = \{x \in X | x \le f(x)\}\) and \(z = \sup S\).
We show that \(f(z) = z\)
For \(x \in S,\) we have \(x \le z\). Then \(x \le f(x) \le f(z)\) as f is order preserving.
Thus \(f(z)\) is an upper bound for S, and so \(z \le f(z)\). It follows that \(f(z) \le f(f(z))\) and so \(f(z) \in S\) and \(f(z) \le z\).

Q: Corollary. Schröder-Bernstein Theorem. Suppose that \(A,B\) are sets such that there are injections \(f:A\to B\)and \(g:B\to A\). Then there is a bijection \(h: A \to B\)
A: We seek partitions \(A=P\cup Q\) and \(B=R\cup S\)such that \(f(P)=R\) and \(g(S)=Q\). If we then define \(h:A\to B\) by  \[h(x)= \begin{cases} f(x) & x\in P \\ g^{-1}(x) & x\in Q \end{cases} \] then \(h\) is a bijection. To see that such a partition exists, let \(X=P(A)\) and define \(H:X\to X\) by \(H(P)=A\setminus g(B\setminus f(P))\). Then \(H\) is order-preserving and \(X\) is a complete poset. Hence, by Tarski's fixed-point theorem, \(H\) has a fixed point \(P\). Setting \(Q=A\setminus P\), \(R=f(P)\), and \(S=B\setminus R\), we get the desired partitions.

Q: Theorem. Every vector space \( V \) has a basis.
A: We seek a maximal (with respect to inclusion) linearly independent set \(B\). Any such set is a basis, i.e., span \(V\) otherwise for any \(x \in V \setminus \text{span}B\) the set \(B \cup \{x\}\) is linearly independent contradicting the maximality of \(B\).
Let \(X = \{A \subset V : A \text{ is linearly independent}\}\) partially ordered by inclusion. Let \(C = \{A_i : i \in I\}\) be a chain in \(X\). We show that \(A = \bigcup_{i \in I} A_i\) is linearly independent. Then \(A\) is an upper bound for \(C\). So assume that \(\sum_{j=1}^n \lambda_j x_j = 0\) is a linear relation on \(A\). For each \(j = 1,\ldots,n\) we have \(x_j \in A_{i_j}\) for some \(i_j \in I\). Since \(C\) is a chain, there is a \(k\), \(1 \leq k \leq n\), such that \(A_{i_j} \subset A_{i_k}\) for each \(j = 1,\ldots,n\). Since \(A_{i_k}\) is linearly independent, it follows that \(\lambda_j = 0\) for all \(j\), and hence \(A\) is linearly independent.
We showed that every chain in \(X\) has an upper bound. By Zorn's Lemma, \(X\) has a maximal element. \(\square\)

Q: Definition. Let \( X \) be a poset. Say \( x \in X \) is a \(\textit{maximal element}\) of \( X \) if [...]
A: \( x \leq y \) implies \( x = y \) for every \( y \in X \).
Back Extra: 1. For a set \( S \), the poset \( X = \mathcal{P}(S) \) has maximal element \( S \). In fact, \( X \) has a maximum element.
2. In general, a greatest element is maximal, but the converse is false. E.g., in the poset \( \{a, b, c, d\} \) with \( a < c \), \( b < c \), \( a < d \), \( b < d \), both \( c \) and \( d \) are maximal, but there is no maximum.
3. In \( \mathbb{N} \) with \( a < b \) if \( a|b \), there are no maximal elements.

Q: Theorem. Zorn's Lemma. Let \(X\) be a (non-empty) poset in which every chain has an upper bound. Then \(X\) has a maximal element.
A: Assume that \(X\) has no maximal elements. Then for every \(x \in X\) we can fix an element \(x' \in X\) with \(x < x'\). Let us also fix, for every chain \(C\), an upper bound \(u(C)\) for \(C\) in \(X\). Let \(\gamma = \gamma(X)\) (from Hartogs' lemma) and define \(f: \gamma \to X\) by recursion as follows:
\[f(0) = u(\emptyset)\]
\[f(\alpha + 1) = f(\alpha)'\]
\[f(\lambda) = u(\{f(\alpha) : \alpha < \lambda\})\] \quad \(\lambda \neq 0\) limit.
An easy induction (on \(\beta\) with \(\alpha\) fixed) shows that \(f(\alpha) < f(\beta)\) for all \(\alpha < \beta\). It follows that \(f\) is injective contradicting the choice of \(\gamma\). \(\square\)

Q: Theorem. Model Existence. Let \(P\) be any set of primitive propositions. Let \(S \subset L = L(P)\) be consistent. Then there exists \(\overline{S} \subset L\) such that \(S \subset \overline{S}\) and for all \(t \in L\), either \(t \in \overline{S}\) or \(\neg t \in \overline{S}\).
A: We seek a maximal consistent set \(\overline{S} \supset S\). We then complete the proof as follows. Given \(t \in L\), one of \(\overline{S} \cup \{t\}\) and \(\overline{S} \cup \{\neg t\}\) is consistent since otherwise \(\overline{S} \cup \{t\} \vdash \bot\) and \(\overline{S} \cup \{\neg t\} \vdash \bot\), which implies \(\overline{S} \vdash \neg t\) and \(\overline{S} \vdash \neg \neg t\) by the Deduction Theorem, and hence \(\overline{S} \vdash \bot\) by modus ponens. It follows by maximality of \(\overline{S}\) that either \(t \in \overline{S}\) or \(\neg t \in \overline{S}\).
Let \(X = \{T \subset L : S \subset T, T \text{ is consistent}\}\) partially ordered by inclusion. Note that \(X \neq \emptyset\) since \(S \in X\). Next, let \(C = \{T_i : i \in I\}\) be a non-empty chain in \(X\). We show that \(T = \bigcup_{i \in I} T_i\) is an upper bound of \(C\). We have \(S \subset T\) (as \(C \neq \emptyset\)) and \(T_i \subset T\) for all \(i \in I\). So we just need to show that \(T \in X\), i.e., \(T\) is consistent. If \(T \vdash \bot\), then since proofs are finite, there exist \(i_1,\ldots,i_n\) in \(I\) such that \(\bigcup_{j=1}^n T_{i_j} \vdash \bot\). Since \(C\) is a chain, for some \(k = 1,\ldots,n\) we have \(\bigcup_{j=1}^n T_{i_j} = T_{i_k} \vdash \bot\) — contradiction.
By Zorn's Lemma, \(X\) has a maximal element as required. \(\square\)

Q: Theorem. Well-ordering Principle. Every set \(A\) can be well-ordered.
A: Let \(X = \{(B,R) \in \mathbb{P}A \times \mathbb{P}(A \times A) : R \text{ well-orders } B\}\). We partially order \(X\) by \((B_1,R_1) \leq (B_2,R_2)\) if and only if \(B_2\) extends \(B_1\) (i.e., \(B_1 \subset B_2\), \(R_1 = R_2 \cap (B_1 \times B_1)\) and \(B_1\) is an initial segment of \(B_2\)).
Note that \(X \neq \emptyset\) as \((\emptyset,\emptyset) \in X\). Assume that \(\{(B_i,R_i) : i \in I\}\) is a non-empty chain in \(X\), i.e., a nested set of well-ordered sets. Then \((\bigcup_{i \in I} B_i,\bigcup_{i \in I} R_i)\) is an upper bound (cf. Proposition 8 in Chapter 2).
By Zorn's Lemma, there is a maximal element \((B,R)\) in \(X\). If \(B \neq A\), then for any \(x \in A \setminus B\), the extension \((B,R)^+ = (B \cup \{x\}, R \cup \{(b,x) : b \in B\})\) contradicts the maximality of \((B,R)\). Thus, \(A = B\) and \(R\) is a well-ordering of \(A\). \(\square\)

Q: What is the Axiom of Choice?
A: The assertion that for every set \(X = \{A_i : i \in I\}\) of non-empty sets, there is a function \(f : I \to \bigcup_{i \in I} A_i\) with \(f(i) \in A_i\) for all \(i \in I\), called a choice function for X.

Q: Theorem. \(AC \iff ZL \iff WO\)
A: Already proved \(AC \implies ZL\) and \(ZL \implies WO\)
For \(WO \implies AC\), let \(X = \{A_i : i \in I\}\) be a set of non-empty sets. Let \(Y = \bigcup_{i \in I} A_i\) and fix a well-ordering of Y. Define \(f : I \to Y\) by letting \(f(i)\) be the least element of \(A_i\). Then f is a choice function of X.

Q: Definition. A [...] a sentence.
A: formula with no free variables is called

Definition. The language is specified by two disjoint sets: the set \(\Omega\) of operation symbols and the set \(\Pi\) of predicate symbols together with an arity function \(\alpha : \Omega \cup \Pi \to \mathbb{N_0}\). The language then consists of the following.
Variables. Countable set disjoint from \(\Omega,\Pi\), denote them as \(x,y,z,\dots\) or \(x_1, x_2, \dots\)
Terms. Defined inductively: every variable is a term, if \(\omega \in \Omega, n = \alpha(\omega)\) and \(t_1, \dots , t_n\) are terms, then \(\omega t_1 \dots t_n\) is also a term.
Atomic formulae. There are of two kinds:
(i) If s,t are terms then \((s=t) \) is an atomic formula
(ii) If \(\varphi \in \Pi, \alpha(\varphi) = n \) and \(t_1, t_2, \dots , t_n\) are terms then \(\varphi t_1 \dots t_n\) is an atomic formula

Formulae. Defined inductively:
(i) Atomic formulae are formulae
(ii) \(\bot\) is a formula
(iii) If p,q are formulae, then \((p \implies q)\) is a formula. As before, we introduce \(\vee, \wedge, \neg, \top, \iff\) in order to abbreviate certain formulae
(iv) If p is a formula and x is a free variable in p, then \((\forall x) p\) is a formula

Q: Definition. A structure in a language \(L = L(\Omega, \Pi)\), or L-structure, is [...]
A: a non-empty set A together with functions \[\omega_A : A^n \to A \quad (n \text{ the arity of } \omega)\]for each \(\omega \in \Omega\), and subsets \(\varphi_A \subset A^n (n\) the arity of \(\varphi\)) or equivalently, identifying a subset with its indicator function, functions \[\varphi_A : A^n \to \{0,1\} \quad (n \text{ the arity of } \varphi)\]for each \(\varphi \in \Pi\)

Definition. Let \( L \) be a first-order language and \( A \) be an \( L \)-structure. Let \( t \) be a term in \( L \) and \( p \) be a formula in \( L \) both with free variables contained in the set \(\{x_1, \ldots, x_n\}\). We define interpretations \( t_A: A^n \to A \) of \( t \) in \( A \) and \( p_A: A^n \to \{0, 1\} \) (equivalently, \( p_A \subset A^n \)) of \( p \) in \( A \) by induction on the language \( L \) as follows.
If \( t \) is \( x_i \) for some \( i = 1, \ldots, n \), then
\[t_A: A^n \to A , \quad t_A(a_1, \ldots, a_n) = a_i\]
is projection on the \( i^th \) coordinate 
If \( t \) is \( \omega t_1 \ldots t_m \) for some \( \omega \in \Omega \) with arity \( m \) and terms \( t_1, \ldots, t_m \), then
\[t_A: A^n \to A , \quad t_A(a_1, \ldots, a_n) = \omega_A((t_1)_A(a_1, \ldots, a_n), \ldots, (t_m)_A(a_1, \ldots, a_n)) .\]
If \( p \) is \((u = v)\) for terms \( u, v \), then
\[p_A = \{(a_1, \ldots, a_n) \in A^n : u_A(a_1, \ldots, a_n) = v_A(a_1, \ldots, a_n)\}.\]
\(\perp_A\) is the constant function with value 0.
If \( p \) is \((q \Rightarrow r)\), then
\[p_A = \{(a_1, \ldots, a_n) \in A^n : q_A(a_1, \ldots, a_n) = 0 \text{ or } r_A(a_1, \ldots, a_n) = 1\}.\]
If \( p \) is \( (\forall x_{n+1})q \) with \( FV(q) \subset \{x_1, \ldots, x_n, x_{n+1}\} \), then
\[p_A = \{(a_1, \ldots, a_n) \in A^n : (a_1, \ldots, a_n, a_{n+1}) \in q_A \text{ for all } a_{n+1} \in A\} \]

Q: Definition. Let \( L = L(\Omega, \Pi) \) be a first-order language and \( A \) be an \( L \)-structure. Given a formula \( p \) in the language \( L \), we say \( p \) is satisfied in \( A \) (or \( p \) holds in \( A \), or \( p \) is true in \( A \) or \( A \) is a model of \( p \)) if [...]
A: \( p_A = A^n \) or, equivalently, \( p_A : A^n \to \{0, 1\} \) is the constant function with value 1, where \( n \) is the number of free variables in \( p \).

Q: Definition. A theory in \( L \) is [...] A model for a theory \( T \) is [...]
A: a set of sentences in \( L \).; an \( L \)-structure in which each sentence in \( T \) is satisfied.

Q: Definition. Given a first-order language \(L = L(\Omega, \Pi)\), a set S of sentences in L and a sentence t in L, we say S (semantically) entails t, written \(S \vDash t\), if [...]
A: t holds in every model of S.

Q: Definition. Let \(L = L(\Omega, \Pi)\) be a first-order language, S a set of formulae in L and t a formula in L. [...] We then say S (semantically) entails t, written \(S \vDash t\), if \(S' \vDash t'\)/
A: Introduce a new constant to L for each free variable occuring in \(S \cup \{t\}\). For a formula \( u \in S \cup \{t\}\), let \(u'\) be the sentence obtained from u by replacing each free occurence of a variable with the corresponding constant and set \(S' = \{s' : s \in S\}\).

Q: Definition. A formula t in a first-order language L is a tautology if[...]
A: \(\emptyset \vDash t\), ie, t holds in every L-structure.

Q: Definition. Let p be a formula in a first-order language L. If x is a free variable in p and t is a term in L whose variables do not occur bound in p, then \(p[t/x]\) is [...]
A: the formula obtained from p by replacing each free occurence of x with t.

Definition. Axioms of syntactic entailment.
\[(A1) \quad p \implies (q \implies p)\]\[(A2)\quad (p \implies (q \implies r)) \implies ((p \implies q) \implies (p \implies r))\]\[(A3)\quad \neg \neg p \implies p\]
\[(A4) \quad(\forall x)(x = x)\]\[(A5) \quad(\forall x)(\forall y)((x = y) \implies (p \implies p[y/x]))\]
\[(A6) \quad ((\forall x)p) \implies p[t/x]\]\[(A7) \quad (\forall x)(p \implies q) \implies (p \implies (\forall x)q)\]

Q: What are the rules of deduction in first-order predicate logic.
A: MP and Gen
Generalisation: from p, we can deduce \((\forall x)p\) provided x does not occur free in any premiss used in the proof of p

Q: Definition. Let S be a set of formulae and p be a formula. A proof of p from S is [...]
A: a finite sequence \(t_1, \dots , t_n\) of formulae such that \(t_n = p\) and for every i,
(i) either \(t_i\) is an axiom, or
(ii) \(t_i\) is a premiss, or
(iii) \(t_i\) follows by modus ponens
(iv) \(t_i\) follows by Generalisation
Back Extra: We say S proves p, and write \(S \vdash p\) if there is a proof of p from S. If S is a theory, p is a sentence and S proves p, then we saw p is a theorem of S.

Q: Proposition. Deduction Theorem. Let S be a set of formulae and p,q be formulae. Then \(S \vdash (p \implies q)\) if and only if \(S \cup \{p\} \vdash q\).
A: The forward direction is easy. Now for q from \(S \cup \{p\}\)
Assume \(t_1 , \dots , t_n\) is a proof of q from \(S \cup \{p\}\) and we show that \(S \vdash (p \implies t_i)\) for all i.
Induction before the ith step: for each \(j < i\), we have \(S \vdash (p \implies t_j)\) such that if a variable x did not occur free in any premiss used in the proof of \(t_j\) from \(S \cup \{p\}\), then x does not occur free in any premiss used in the proof of \((p \implies t_j)\) from S.
Case 1: If \(t_{i}\) is an axiom or \(t_{i} \in S\), then
\[t_{i} \Rightarrow (p \Rightarrow t_{i}) \tag{A1}\]
\[t_{i} \quad \text{(axiom or premiss)}\]
\[p \Rightarrow t_{i} \quad \text{(MP)}\]
is a proof of \(p \Rightarrow t_{i}\) from \(S\).
Case 2: If \(t_{i} = p\), then \(S \vdash (p \Rightarrow t_{i})\) since \(\vdash (p \Rightarrow p)\).
Case 3: If there exist \(j,k < i\) such that \(t_{k} = (t_{j} \Rightarrow t_{i})\), then by induction hypothesis, there are proofs of \(p \Rightarrow t_{j}\) and \(p \Rightarrow (t_{j} \Rightarrow t_{i})\) from \(S\). Adding the lines
\[(p \Rightarrow (t_{j} \Rightarrow t_{i})) \Rightarrow ((p \Rightarrow t_{j}) \Rightarrow (p \Rightarrow t_{i})) \tag{A2}\]
\[(p \Rightarrow t_{j}) \Rightarrow (p \Rightarrow t_{i}) \quad \text{(MP)}\]
\[p \Rightarrow t_{i} \quad \text{(MP)}\]
we obtain a proof of \(p \Rightarrow t_{i}\) from \(S\).
Case 4: Finally, if for some \(j < i\) we have \(t_{i} = (\forall x)t_{j}\), then \(x\) occurs free in \(t_{j}\) and \(x\) does not occur free in any premiss used in the proof of \(t_{j}\) from \(S \cup \{p\}\). We now have two further cases.
Case 4a: If \(x\) occurs free in \(p\), then \(p\) was not used in the proof of \(t_{j}\) from \(S \cup \{p\}\), and so we have a proof of \(t_{j}\) from \(S\) and \(x\) does not occur free in any premiss used in this proof. We write down this proof and append the lines
\[(\forall x)t_{j} \quad \text{(Gen)}\]
\[(\forall x)t_{j} \Rightarrow (p \Rightarrow (\forall x)t_{j}) \tag{A1}\]
\[p \Rightarrow (\forall x)t_{j} \quad \text{(MP)}\]
to obtain a proof of \(p \Rightarrow t_{i}\) from \(S\).
Case 4b: If \(x\) does not occur free in \(p\), then we have the following proof from \(S\).
\[p \Rightarrow t_{j} \quad \text{(induction hypothesis)}\]
\[(\forall x)(p \Rightarrow t_{j}) \quad \text{(Gen)}\]
\[(\forall x)(p \Rightarrow t_{j}) \Rightarrow (p \Rightarrow (\forall x)t_{j}) \tag{A7}\]
\[p \Rightarrow (\forall x)t_{j} \quad \text{(MP)}\]
In all cases it is easy to check that the induction hypothesis is valid up to and including the \(i^{\text{th}}\) step.

Q: What is Gödel's Completeness Theorem for first-order logic?
A: Let S be a set of formulae and p be a formula. Then \(S \vDash p\) iff \(S \vdash p\)

Q: Theorem. Compactness Theorem. Let S be a first-order theory. If every finite subset of S has a model, then S has a model.
A: If \(S \vDash \bot\) then \(S \vdash \bot\). As proofs are finite, there's a finite \(S' \subset S\) s.t. \(S' \vdash \bot\). Then by the Soundness theorem \(S' \vDash \bot\) ie \(S'\) has no model.

Q: Corollary. Finite groups cannot be axiomatised as a first-order theory.
A: Suppose T is a theory in some language L whose models are exactly the finite groups. Then let \[S = T \cup \{\neg t_1 , \neg t_2 , \dots\}\]where \(t_n \) is as above.Note that \(\neg t_n\) says there are more than n elements in any model.  Any finite subset of S has a model, eg the cyclic group \(C_n\) for n sufficiently large. By compactness S has a model.

Q: Corollary. If a first-order theory T has arbitrarily large finite models, then it has an infinite model
A: Let \(S = T \cup \{\neg t_1 , \neg t_2, \neg t_3 , \dots \}\) where \(t_n\) is as before. By assumption, any finite subset of S has a model. By compactness, S has a model, which is an infinite model of T.

Q: Theorem. The Upward Löwenheim-Skolem Theorem. If a first-order theory S has an infinite model, then S has an uncountable model.
A: Add uncountably many new constants \(\{c_i | i \in I\}\) to the language. Consider \[S' = S \cup \{\neg (c_i = c_j) | i,j \in I, i \neq j\}\]By assumption S has an infinite model, which is a model of every finite subset of \(S'\)
By compactness \(S'\) has a model A, ie a model A of S together with an injection \(I \to A, c_i \mapsto (c_i)_A\)

Q: Corollary. The Downward Löwenheim-Skolem Thoerem. Let S be a first-order theory in a countable language. If S has a model, then it has a countable model.
A: By the Soundness Theorem, S is consistent since it has a model. Then the model constructed in the proof of the Model Existence Lemma is countable.

Q: Definition. A subset \(A \subset \mathbb{N}_0\) is definable in PA if [...]
A: there is a formula p with free variable x such that \(p_{\mathbb{N}_0}\), the interpretation of p in \(\mathbb{N}_0\) is A.

Q: What is the Axiom of extensionality(Ext)?
A: If two sets have the same members, then they are equal
\[(\forall x)(\forall y)((\forall z)(z \in x \iff z \in y) \implies (x = y))\]

Q: What is the Axiom of seperation(Sep)?
A: Can form a subset of a set. This is an axiom scheme\[(\forall t_1) \dots (\forall t_n)((\forall x)(\exists y)(\forall z)(z \in y \iff ((z \in x) \wedge p)))\]for any formula p with \(FV(p) = \{z , t_1 , \dots , t_n\}\), where \(t_1 , \dots , t_n\) should be thought of as parameters. The set y whose existence is asserted in the sentence above is unique by (Ext) and is denoted by \(\{ z \in x : p\}\). (Formally, we are adding an (n+1)-ary operation symbol)

Q: What is the Empty-set axiom(Emp)?
A: There is a set with no element \[(\exists x)(\forall y)\neg(y \in x)\]

Q: What is the Pair-set axiom(Pair)?
A: For any sets x,y, we can form \(\{x,y\}\)\[(\forall x)(\forall y)(\exists z)(\forall y)(t \in z \iff ((t=x) \vee (t = y)))\]The unique set z whose existence is assrted here is denoted by \(\{x,y\}\). We shall write \(\{x\}\) for \(\{x,x\}\)

Q: What is the Union axiom(Un)?
A: Can form the union of a set \[(\forall x)(\exists y)(\forall z)((z \in y)\iff (\exists t)((t \in x) \wedge (z \in t)))\]y is the union of the members of x

Q: What is the Power-set axiom(Pow)?
A: Can form the power set of a set \[(\forall x)(\exists y)(\forall z)(z \in y \iff z \subset x)\]where \(z \subset x\) is shorthand for \((\forall t)(t \in z \implies t \in x)\). The unique set y is denoted by \(\mathbb{P}x\)

Q: What is the Axiom of infinity(Inf)?
A: Define \(x^+ = x \cup \{x\}\).Say that x is a successor set if \[(0 \in x) \wedge (\forall y)(y \in x \implies y^+ \in x)\]The axiom of infinity states that successor sets exists \[(\exists x )(x \text{ is a successor set})\]

Q: Definition. A class is [...]
A: a collection C of elements of V such that there is a formula p with one free variable satisfying \(C = p_V\), i.e., \(x \in C\) iff \(p(x)\) holds in V(i.e. \(p_V(x) = 1\))
Back Extra: V is a class: we can take p to be the formula \((x = x)\)
The collection of sets of size one is a class: we can take p to be the formula \((\exists y)(x = \{y\})\)

Q: Definition. A class C given by a formula p with one free variable x is a set if [...] Otherwise, we say C is a proper class.
A: \((\exists y)(\forall x)(x \in y \iff p)\) holds in V.
Back Extra: V is a proper class (Russell's paradox)
The class given by the formula \((\forall y)('\text{y is a successor set}' \implies x \in y)\) is the set \(\omega.\)

Q: Definition. A function-class is [...]
A: a subset \(F \) of \(V \times V\) such that \(F = p_V\) for some formula p with two free variables x,y satisfying \[(\forall x)(\forall y)(\forall z)((p \wedge p[z/y]) \implies (y = z))\]Thus, \((x,y) \in F\) if and only if \(p(x,y)\) holds in V which we will write as \(F(x) = y\).
Back Extra: The map \(x \mapsto \{x\}\) is a function class: we can take p to be \((y = \{x\})\)

Q: What is the Axiom of Replacement(Rep)?
A: An axiom-scheme stating that the image of a set under a function-class is a set.\[(\forall t_1)\dots (\forall t_n)[(\forall x)(\forall y)(\forall z)((p \wedge p[z/y]) \implies (y=z)) \implies (\forall x)(\exists y)(\forall z)(z \in y \iff (\exists u)(u \in x \wedge p[u /x, z/y]))]\]
for any formula p with \(FV(p) = \{x,y,t_1, \dots, t_n\}\)

Q: What is the Axiom of Foundation(Fnd)?
A: Every non-empty set has an \(\in\)-minimal member\[(\forall x)(\neg(x = \emptyset)\implies (\exists y)(y \in x \wedge(\forall z)(z \in x \implies \neg(z \in y))))\]

Q: What is the Axiom of Choice(AC)?
A: \[(\forall x)((\forall y \in x) \neg(y = \emptyset) \implies (\exists f)(f : x \to \bigcup x \wedge(\forall y \in x)(f(y) \in y)))\]

Q: Definition. A set x is transitive if [...]
A: every member of a member of x is a member of x. Thus, 'x is transitive' is shorthand for \[(\forall y)((\exists z)(z \in x \wedge y\in z)\implies y \in x)\]
Back Extra: Equivalently \(\bigcup x \subset x\). This is not the same as saying that \(\in \) is a transitive relation on x.

Q: Lemma. Every set x is contained in a transitive set: \[(\forall x)(\exists y)('\text{y is transitive}' \wedge x \subset y)\]
A: You show that the map sending \(0 \mapsto x, 1 \mapsto \bigcup x, 2 \mapsto \bigcup\bigcup x\) is a function-class and then the result follows from the Axiom of Replacement.
Let 'f is an attempt' to mean \[(f \text{ is a function}) \wedge (\text{dom}f \in \omega) \wedge (x = f(0)) \wedge (\forall m)(\forall n)((m \in \text{dom}f \wedge n \in \text{dom}f \wedge n = m^+) \implies f(n) = \bigcup f(m))\]Show that any two attempts agree on the intersection of their domains, and that every member of \(\omega\) is in the domain of some attempt by forming the set \[w = \{n \in \omega : (\exists f)((f \text{ is an attempt}) \wedge (n \in \text{dom}f))\}\]Show that \(w\) is a successor set, so then it follows that \(w = \omega\)
Let p be the following formula with free variables y,z: \[(\exists f)((f \text{ is an attempt}) \wedge ((y,z) \in f))\]and this is a function-class. Then the image of \(\omega\) under this function-class is a set by Replacement. Show that the set is transitive and that \(x \subset t\) and we are done.
Since \(\{(0,x)\}\) is an attempt, it follows \(x \in w, x \subset t\)
Assume \(a \in t\), then \(a \in z\) for some \(z \in w\) and in turn \(z = f(n)\) for some attempt f with \(n \in \text{dom}f\). There is also an attempt g with \(n^+ \in \text{dom}g\). Then \(n \in \text{dom} g\) since members of \(\omega\) are transitive, and \(g(n) = f(n) = z\). It follows \(g(n^+) = \bigcup g(n) = \bigcup z\), so \(\bigcup z \in w\). Thus for any \(b \in a, b\in \bigcup z \in w\) hence \(b \in t\) as required.

Q: Theorem. Principle of \(\in-\)induction. For each formula p with free variables \(FV(p) = \{x,t_1 , \dots ,t_n\}\), the following sentence holds in ZF\[(\forall t_1)\dots(\forall t_n)((\forall x)[(\forall y \in x)p[y/x] \implies p] \implies (\forall x)p)\]
A: Fix values \( t_1, \ldots, t_n \) of the parameters and assume that \( p(x) \) holds whenever \( p(y) \) holds for all members \( y \) of \( x \), i.e., \( (\forall x)[(\forall y \in x)p[y/x] \Rightarrow p] \) holds. Assume for a contradiction that \( -(\forall x)p(x) \) holds and fix any set \( x \) such that \( p(x) \) fails.
(At this point we would like to take a minimal counterexample, i.e., an \(\epsilon\)-minimal member of \(\{y: -p(y)\}\). However, \(\{y: -p(y)\}\) may not be a set. This is where transitive closure comes in.)
By Lemma 1 we can form the set \( t = \text{TC}(\{x\}) \), and by (Sep) we can form the set \( u = \{y \in t: -p(y)\} \). Then \( x \in u \), and hence \( u \) has an \(\epsilon\)-minimal member \( z \). If \( y \in z \), then \( y \in t \) since \( t \) is transitive, and thus \( y \notin u \) since \( z \) is \(\epsilon\)-minimal in \( u \). It follows that \( p(y) \) holds for all \( y \in z \). By assumption on \( p \), we deduce \( p(z) \) contradicting the choice of \( z \).

Q: Theorem. \(\in\)-recursion theorem. Let G be a function-class defined everywhere, then there is a function-class F such that \((\forall x)(F(x) = G(F |_x))\). Moreover, F is unique.
A: We first prove uniqueness. Assume that \( F_1 \) and \( F_2 \) both satisfy the conclusions of the theorem. We show \( (\forall x)(F_1(x) = F_2(x)) \) by \(\epsilon\)-induction. Fix a set \( x \) and assume that \( (\forall y \in x)(F_1(y) = F_2(y)) \). Then \( F_1|_x = F_2|_x \), and hence \( F_1(x) = G(F_1|_x) = G(F_2|_x) = F_2(x) \).
We now turn to existence. We say that a set \( f \) is an attempt if
\[(f \text{ is a function}) \land (\text{dom } f \text{ is transitive}) \land (\forall x)(x \in \text{dom } f \Rightarrow f(x) = G(f|_x))\]
Note that if \( x \in \text{dom } f \), then \( x \subset \text{dom } f \) since \(\text{dom } f \) is transitive, and hence \( f|_x \) makes sense. Now a straightforward \(\epsilon\)-induction (as in the proof of uniqueness) shows that
\[(*) \quad (\forall f)(\forall g)(\forall x)\left([(f \text{ is an attempt}) \land (g \text{ is an attempt})] \land (x \in \text{dom } f) \land (x \in \text{dom } g)] \Rightarrow f(x) = g(x)\right)\]
Another \(\epsilon\)-induction shows that
\[(\forall x)(\exists f)((f \text{ is an attempt}) \land (x \in \text{dom } f))\]
To see this, fix a set \( x \) and assume that for all \( y \in x \) there is an attempt defined at \( y \). Note that an attempt defined at \( y \) is defined on \( \text{TC}(\{y\}) \) since the domain of an attempt is transitive, and the restriction to \( \text{TC}(\{y\}) \) of this attempt is still an attempt. Hence by (*), for each \( y \in x \) there is a unique attempt \( f_y \) defined on \( \text{TC}(\{y\}) \). Then \(\{f_y : y \in x\}\) is a set by Replacement and \( f' = \bigcup\{f_y : y \in x\} \) is an attempt whose domain contains \( x \). Finally, \( f = f' \cup \{(x, G(f'|_x))\} \) is an attempt defined at \( x \).
We now let \( q \) be the formula \((\exists f)((f \text{ is an attempt}) \land y = f(x))\). It is now straightforward to verify that \( q \) defines a function-class \( F \) with the required properties.

Q: Definition. A relation r is well-founded if [...]A relation r is local if [...]
A: every non-empty set has an r-minimal member: \[\forall(x)(\neg(x = \emptyset) \implies (\exists y)[y \in x \wedge (\forall z \in x)\neg r(z,y)])\]; the r-predecessors of a set form a set: \[(\forall x)(\exists y)(\forall z)(z \in y \iff r(z,x))\]

Q: Definition. A relation r on a set a is extensional if [...]
A: members of a are uniquely determined by their set of r-predecessors: \[(\forall x \in a)(\forall y \in a)((\forall z \in a)(zrx \iff zry) \implies x =y)\]

Q: Theorem. Mostowski's Collapsing Theorem. Let r be a well-founded extensional relation on a set a. Then there is a transitive set b and a bijection \(f: a \to b \) such that \[(\forall x \in a)(\forall y \in a)(xry \iff f(x) \in f(y))\]Moreover, the pair \((b,f)\) is unique.
A: We begin with existence. By \( r \)-recursion there is a function-class \( f \) such that
\[(\forall x \in a)(f(x) = \{f(y) : y \in a, \, y r x\})\]
Since \(\{(x, f(x)) : x \in a\}\) is a set by (Rep), we can take \( f \) to be a function. We next set \( b = \{f(x) : x \in a\} \) which is also a set by (Rep). We verify that \((b, f)\) satisfies the conclusions of the theorem.
We first show that \( b \) is transitive. Given \( z \in b \), \( z = f(x) \) for some \( x \in a \), and hence \( z = \{f(y) : y \in a, \, y \not\subset x\} \). It follows that \( w \in b \) whenever \( w \in z \).
By definition, \( f \) is surjective and \( x r y \) implies \( f(x) \in f(y) \) for all \( x, y \in a \). It remains to show that \( f \) is injective. This will also show that \( f(x) \in f(y) \) implies \( x r y \) for all \( x, y \in a \). Indeed, if \( f(x) \in f(y) \), then \( f(x) = f(z) \) for some \( z \in a \) with \( z r y \). Then by injectivity \( z = x \), and thus \( x r y \).
For \( x \in a \), say that \( f \) is injective at \( a \) if \( (\forall y \in a)(f(y) = f(x) \Rightarrow y = x) \). Then \( f \) is injective if and only if \( (\forall x \in a)(f \) is injective at \( x) \) which we show by \( r \)-induction. Fix \( x \in a \) and assume that \( f \) is injective at \( s \) for all \( s \in a \) with \( sr x \). Assume that \( f(x) = f(y) \) for some \( y \in a \). Then
\[\{f(s) : s \in a, \, s rx\} = \{f(t) : t \in a, \, t r y\}\]
Since \( f \) is injective at every \( s \in a \) with \( s r x \), it follows that
\[\{s : s \in a, \, s r x\} = \{t : t \in a, \, t r y\}\]
Since the relation \( r \) is extensional, we have \( x = y \) as required.
We complete the proof by showing uniqueness. Let \((b, f)\) and \((b', f')\) be pairs both satisfying the conclusions of the theorem. We show
\[(\forall x \in a)(f(x) = f'(x))\]
by \( r \)-induction. Fix \( x \in a \) and assume that \( f(y) = f'(y) \) for all \( y \in a \) with \( y r x \). Given \( w \in f(x) \), we have \( w \in b \) since \( b \) is transitive, and \( w = f(z) \) for some \( z \in a \) since \( f \) is surjective. Then \( f(z) \in f(x) \), and hence \( z r x \). It follows by the induction hypothesis that \( w = f(z) = f'(z) \in f'(x) \). Similarly, \( w \in f'(x) \) implies \( w \in f(x) \). Thus, by the Axiom of Extensionality, we have \( f(x) = f'(x) \). This completes the \( r \)-induction which shows that \( f = f' \), and thus \( b = b' \). □

Q: Definition. An ordinal is [...]
A: a transitive set well-ordered by \(\in\)
Back Extra: Suppose a is a set and r is a well-ordering on a. By Mostwoski, there is a transitive set b and a bijection \(f: a \to b\) such that \(xry \iff f(x) \in f(y)\)
Thus \((a,r)\) is order isomorphic to \((b, \in)\)
It follows that b is an ordinal. Moreover, by the uniqueness part of the theorem, this is the unique ordinal to which \((a,r)\) is order-isomorphic.
This unique ordinal is called the order-type of the well-ordered set a.

Proposition. Let \(\alpha, \beta \in ON\) and \(a\) be a set of ordinals.
(i) Every member of \(\alpha \) is an ordinal
(ii) \(\beta \in \alpha \iff \beta < \alpha\)
(iii) \(\beta \in \alpha\) or \(\beta = \alpha \) or \(\alpha < \beta\)
(iv)\(\alpha^+ = \alpha \cup \{\alpha\}\)
(v)\(\bigcup a\) is an ordinal and \(\bigcup a = \sup a\)
Proofs.
(i) Fix \(\gamma \in \alpha\). Then \(\gamma \subset \alpha\) since \(\alpha\) is transitive, and so \(\gamma\) is linearly ordered by \(\epsilon\). It remains to show that \(\gamma\) is transitive. Let \(\eta \in \delta\) and \(\delta \in \gamma\). Since \(\alpha\) is transitive, we have \(\delta \in \alpha\), and in turn \(\eta \in \alpha\). Since \(\epsilon\) linearly orders \(\alpha\), it is in particular a transitive relation on \(\alpha\), and thus \(\eta \in \gamma\).
(ii) Recall that for a well-ordered set \(x\), for every \(y \in x\) we denote by \(I_y\) the proper initial segment \(\{z \in x : z < y\}\) of \(x\), and moreover, every proper initial segment is of this form. It follows that if \(\beta \in \alpha\), then \(I_\beta = \{\gamma \in \alpha : \gamma \in \beta\}\) is a proper initial segment of \(\alpha\). Since \(\alpha\) is transitive, \(I_\beta = \beta\), and thus \(\beta < \alpha\). Conversely, if \(\beta < \alpha\), then \(\beta\) is order-isomorphic to \(I_\delta = \delta\) for some \(\delta \in \alpha\). By uniqueness, \(\delta = \beta\), and thus \(\beta \in \alpha\).
(iii) is immediate from parts (i) and (ii) and from Theorem 2.6. Note that if \(\alpha \neq \beta\), then \(\alpha\) and \(\beta\) are not order-isomorphic by uniqueness in Theorem 4.

(iv) Let \(\beta\) be the successor of \(\alpha\), i.e., \(\beta = \alpha \cup \{\alpha\}\). It is straightforward to check that \(\beta\) is an ordinal. Then \(\alpha\) is the maximum element of \(\beta\) (with respect to \(\epsilon\) of course), and \(\alpha\) is a proper initial segment of \(\alpha\). So \(\beta\) is indeed \(\alpha^+\) in the sense of Chapter 2.
(v) First observe the following consequences of parts (ii) and (iii). Firstly, \(\beta \subset \alpha \Leftrightarrow \beta \leq \alpha\). Secondly, one of \(\beta \subset \alpha\) and \(\alpha \subset \beta\) must hold. Thus, \(a\) is a nested set of transitive sets well-ordered by \(\epsilon\). It follows that \(\bigcup a\) is a transitive set well-ordered by \(\epsilon\), i.e., an ordinal, and it is the supremum of \(a\).

Q: Lemma. \( V_\alpha \) is transitive for all \(\alpha \in \text{ON}\).
A: We proceed by induction on \(\alpha\).
\(\alpha = 0\): \( V_0 = \emptyset \) is transitive.
\(\alpha = \beta + 1\): Assume \( V_\beta \) is transitive and let \( x \in V_\alpha \) and \( y \in x \). We need to show that \( y \in V_\alpha \). Since \( V_\alpha = \mathbb{P}V_\beta \), we have \( x \subset V_\beta \) and \( y \in V_\beta \). Since \( V_\beta \) is transitive, it follows that \( y \subset V_\beta \), and hence \( y \in \mathbb{P}V_\beta = V_\alpha \), as required.
\(\alpha \) is a non-zero limit: Assume \( V_\beta \) is transitive for all \(\beta < \alpha\). Then \( V_\alpha \) is a union of transitive sets, and thus transitive. \(\square\)

Q: Lemma. \( V_\alpha \subset V_\beta \) for all \(\alpha \leq \beta\).
A: We proceed by induction on \(\beta\). In each case, we can assume \(\alpha < \beta\). The case \(\beta = 0\) is clear.
\(\beta = \gamma + 1\): Let \(\alpha < \beta\). Then \(\alpha \leq \gamma\), and so \(V_\alpha \subset V_\gamma\) by the induction hypothesis. It follows that \(V_\alpha \in \mathbb{P}V_\gamma = V_\beta\). By Lemma 6, the set \(V_\beta\) is transitive, and thus \(V_\alpha \subset V_\beta\), as required.
\(\beta\) is a non-zero limit: If \(\alpha < \beta\), then \(V_\alpha \subset V_\beta\) by definition of \(V_\beta\).

Q: Theorem. The von Neumann hierarchy exhausts the set theoretic universe. \[(\forall x)(\exists \alpha \in ON)(x \in V_{\alpha})\]
A: We prove \((\forall x)(\exists \alpha \in \text{ON})(x \subset V_\alpha)\) by \(\epsilon\)-induction.
Fix a set \(x\), and assume that every \(y \in x\) has a rank (the induction hypothesis). Set \(\alpha = \sup\{\text{rank}(y)^+ : y \in x\}\) noting that \(\{\text{rank}(y)^+ : y \in x\}\) is a set by Replacement. For each \(y \in x\), we have \(y \subset V_{\text{rank}(y)}\), and so \(y \in V_{\text{rank}(y)^+}\). By Lemma 7 we have \(V_{\text{rank}(y)^+} \subset V_\alpha\) for all \(y \in x\), and hence \(x \subset V_\alpha\), as required. \(\square\)

Q: Corollary. \(\text{rank}(x) = \sup\{\text{rank}(y)^+ : y \in x\}\).
A: It follows from the proof of Theorem 8 that
\[\text{rank}(x) \leq \sup\{\text{rank}(y)^+ : y \in x\}.\]
For the reverse inequality, we first show that if \(x \in V_\alpha\) then \(\text{rank}(x) < \alpha\). So let us assume that \(x \in V_\alpha\). Then \(\alpha > 0\). If \(\alpha = \beta^+\), then \(x \subset V_\beta\), and hence \(\text{rank}(x) \leq \beta < \alpha\). If \(\alpha\) is a limit ordinal, then \(x \in V_\beta\) for some \(\beta < \alpha\). It follows that \(x \subset V_\beta\) since \(V_\beta\) is transitive, and thus \(\text{rank}(x) \leq \beta < \alpha\).
Now set \(\alpha = \text{rank}(x)\). Then for each \(y \in x\), we have \(y \in V_\alpha\), and hence \(\text{rank}(y) < \alpha\) by the claim above. It follows that \(\sup\{\text{rank}(y)^+ : y \in x\} \leq \alpha\).

Q: Definition. Let x be a set. In ZFC we define the cardinality \(\text{card}(x)\) of x to be [...] In ZF we first define the essential rank \(\text{ess rank}(x)\) of x to be [...]
A: the least ordinal \(\alpha\) such that \(x \equiv \alpha\).; the least ordinal \(\alpha\) such that there exists a set y with \(\text{rank}(y) = \alpha\) and \(y \equiv x\). We then define \[\text{card}(x) = \{y \in V_{\text{ess rank}(x) + 1} : y \equiv x\}\]which is a set by Seperation.

Q: Definition. Say that a set m is a cardinal if [...]
A: \(m = \text{card}(x)\) for some set x.
Back Extra: In this case we say m is the cardinality of x.

Q: Definition. Say \(\alpha \in ON\) is an initial ordinal if [...]
A: \((\forall \beta \in ON)(\beta < \alpha \implies \neg(\beta \equiv \alpha))\)

Q: Definition. Define \(\omega_{\alpha}\) for \(\alpha \in ON\) by recursion: [...]
A: \[\omega_0 = \omega\]\[\omega_{\beta^+} = \gamma(\omega_{\beta})\]\[\omega_{\lambda} = \sup \{\omega_{\beta} : \beta < \lambda\}\]

Q: Definition. Write \(m \le n\) if [...], and \(m<n\) if [...]
A: M injects into N; \(m \le n\) and \(m \neq n\).

Q: Definition. We define cardinal addition, multiplication and exponentiation as follows. [...]
A: \[m+n = \text{card}(M \sqcup N)\]\[m \cdot n = \text{card}(M \times N)\]\[m^n = \text{card}(M^N)\]
Back Extra: \(M^N = \{f \in \mathbb{P}(N \times M) : f: N \to M\}\)

Q: Proposition. The ordinals \(\omega_{\alpha}\) are exactly the infinite initial ordinals.
A: We first show that the \(\omega_{\alpha}\) are initial ordinals by induction on \(\alpha\). We only need to check the case when \(\alpha\) is a non-zero limit. In this case, assume that \(\omega_{\alpha} \equiv \gamma\) for some \(\gamma < \omega_{\alpha}\). Then \(\gamma < \omega_{\beta}\) for some \(\beta < \alpha\). Since \(\omega_{\beta} < \omega_{\alpha}\) (easy induction on \(\alpha\)), it follows that \(\omega_{\beta}\) injects into \(\gamma\) contradicting the induction hypothesis that \(\omega_{\beta}\) is an initial ordinal.
Now assume that \(\delta\) is an infinite initial ordinal. An easy induction shows that \(\alpha \leq \omega_{\alpha}\) for all \(\alpha \in \text{ON}\), and hence there is a least \(\alpha\) with \(\delta < \omega_{\alpha}\). Since \(\delta\) is infinite, \(\alpha \neq 0\), and moreover \(\alpha\) cannot be a limit otherwise \(\delta < \omega_{\beta}\) for some \(\beta < \alpha\) contradicting the minimality of \(\alpha\). Thus \(\alpha = \beta^+\) for some \(\beta\) that satisfies \(\omega_{\beta} \leq \delta < \omega_{\beta^+} = \gamma(\omega_{\beta})\). It follows that \(\delta\) injects into \(\omega_{\beta}\), and thus \(\delta = \omega_{\beta}\) as \(\delta\) is an initial ordinal.

Q: Theorem. \(\aleph_{\alpha} \cdot \aleph_{\alpha} = \aleph_{\alpha}\) for all \(\alpha \in \text{ON}\).
A: We proceed by induction on \(\alpha\). The case \(\alpha = 0\) is clear since \(\omega \times \omega \equiv \omega\). Now let \(\alpha > 0\) and assume that \(\omega_{\beta} \times \omega_{\beta} \equiv \omega_{\beta}\) for all \(\beta < \alpha\).
Well-order \(\omega_{\alpha} \times \omega_{\alpha}\) by 'going up in squares': \((x, y) < (w, z)\) if and only if
either \(\max\{x, y\} < \max\{w, z\}\)
or \(\max\{x, y\} = \max\{w, z\} = \delta\), say, and either
\[\begin{cases} y < z < \delta \\ \text{or } y < \delta = z \\ \text{or } x < w, y = z = \delta \end{cases}\]
Given \(\delta \in \omega_{\alpha} \times \omega_{\alpha}\), the proper initial segment \(I_{\delta}\) is contained in \(\beta \times \beta\) for some \(\beta < \omega_{\alpha}\). (E.g., if \(\delta = (x, y)\), then \(\beta = \max\{x, y\}^+\) will do.) Then \(\text{card}(\beta) < \text{card}(\omega_{\alpha})\) since \(\omega_{\alpha}\) is initial. So by induction hypothesis, either \(\beta\) is finite, or \(\beta \times \beta \equiv \beta\). It follows that \(\text{card}(I_{\delta}) \leq \text{card}(\beta \times \beta) < \text{card}(\omega_{\alpha})\).
The above shows that every proper initial segment of \(\omega_{\alpha} \times \omega_{\alpha}\) has order-type \(<\omega_{\alpha}\), and hence \(\omega_{\alpha} \times \omega_{\alpha}\) has order-type \(\leq \omega_{\alpha}\). It follows that \(\omega_{\alpha} \times \omega_{\alpha}\) injects into \(\omega_{\alpha}\), and so \(\aleph_{\alpha} \cdot \aleph_{\alpha} \leq \aleph_{\alpha}\).
Since \(\aleph_{\alpha} = \aleph_{\alpha} \cdot 1 \leq \aleph_{\alpha} \cdot \aleph_{\alpha}\), the result follows.

Q: Corollary. Let \(\alpha \le \beta\) be ordinals. Then \(\aleph_{\alpha} + \aleph_{\beta} = \aleph_{\alpha}\cdot \aleph_{\beta} = \aleph_{\beta}\)
A: \[\aleph_{\beta} \le \aleph_{\alpha} + \aleph_{\beta} \le \aleph_{\beta} \cdot 2 \le \aleph_{\beta} \cdot \aleph_{\beta} = \aleph_{\beta}\]

Q: Definitions. Let I be a set, and for each \(i \in I\) let \(m_i\) be a cardinal. Then \[\sum_{i \in I}m_i = [...]\]and \[\prod_{i \in I}m_i = [...]\]
A: \text{card}\left ( \bigsqcup_{i \in I} M_i\right ); \text{card}\left ( \prod_{i \in I}M_i \right )
Back Extra: where \(\sqcup_{i \in I} M_i = \cup_{i \in I} M_i \times \{i\}\) and \[\prod_{i \in I} M_i = \{f : I \to \cup_{i \in I} M_i : f(i) \in M_i \text{ for all }i \in I\}\]