A solutions manual for Set Theory by Thomas Jech
3. Cardinal Numbers
3.1. \(\quad\)(i) A subset of a finite set is finite.
\(\quad\)(ii) The union of a finite set of finite sets is finite.
\(\quad\)(iii) The power set of a finite set is finite.
\(\quad\)(iv) The image of a finite set (under a mapping) is finite.
Proof. \(\quad\)(i) Let \(X\) be a finite set and \(Y\subset X\). Suppose that \(Y\) is infinite. \(Y\) is T-infinite, thus there is \(S\subset P(Y)\) such that \(S\) has no \(\subset\)-maximal element. But by definition, \(P(Y)\subset P(X)\), and so \(S\subset P(X)\), a contradiction.
\(\quad\)(ii) Let \(p\) be a finite number; for each \(i<p\), let \(S_{i}\) be a finite set and let \(f_{i}\) be a function of \(S_i\) onto some finite ordinal \(n_i\). Let \(S=\bigcup_{i<p}S_i\) and let \(f\) be the function of \(S\) given by \(x\mapsto\sum_{i<k}n_i+f_k(x)\) where \(k\) is the least number such that \(x\in S_k\). \(f\) is a one-to-one function of \(S\) into \(\sum_{i<p}n_i\) that is bounded. Therefore, \(S\) is finite.
\(\quad\)(iii) Let \(X\) be a finite set. \(|P(X)|=2^{|X|}<\aleph_0\).
\(\quad\)(iv) If \(f\) is a function of a finite set \(X\), then there is a one-to-one function \(g\) of \(X\) onto some \(n<\omega\), and so there is a one-to-one function of \(f(X)\) into \(n\) given by \(y\mapsto\bigcap{(g_{-1}\circ f_{-1})(\{y\})}\).\(\quad\square\)
3.2. \(\quad\)(i) A subset of a countable set is at most countable.
\(\quad\)(ii) The union of a finite set of countable sets is countable.
\(\quad\)(iii) The image of a countable set (under a mapping) is at most countable.
Proof. \(\quad\)(i) Let \(X\) be a countable set and \(Y\subset X\). There is a one-to-one function \(f\) of \(X\) onto \(\omega\). Let \(id_Y\) be the function of \(Y\) into \(X\) given by \(x\mapsto x\). \(f\cdot id_Y\) is a function of \(Y\) into \(\omega\), thus \(|Y|\le\aleph_0\). Therefore, by definition of \(\aleph_0\), \(Y\) is at most countable.
\(\quad\)(ii) Let \(n\) be a finite number, and let \(S=\bigcup_{i<n}S_i\) be a union of a finite family of countable sets, and let \(f_{i}\) be a function of \(S_i\) onto \(\omega\) for each \(i<n\). If we let \(f:S\to\omega\) be the function given by \(x\mapsto 2^i 3^{f_i(x)}\) where \(i\) is the least number \(x\in S_i\), then \(f\) is a one-to-one function of \(S\) into \(\omega\). Thus \(S\) is countable.
\(\quad\)(iii) If \(f\) is a function of a countable set \(X\), then there is a one-to-one function \(g\) of \(X\) onto \(\omega\), and so there is a one-to-one function of \(f(X)\) into \(\omega\) given by \(y\mapsto \bigcap{(g_{-1}\circ f_{-1})(\{y\})}\).\(\quad\square\)
3.3. \(\mathbb{N}\times\mathbb{N}\) is countable.
\(\quad\)[\(f (m, n) = 2^m (2n + 1) - 1\).]
Proof. \(\quad\)Let \(f\) be the function of \(\mathbb{N}\times\mathbb{N}\) into \(\mathbb{N}\) given by \((m,n)\mapsto 2^m (2n + 1) - 1\). Let \(x\in\omega\) and \(m=\) sup \(\{a\in\omega:2^a\) divides \(x + 1\}\). \((x+1)/{2^m}\) is odd, thus there is \(n\in\omega\) such that \(2n + 1=(x+1)/{2^m}\), and so \(f\) is a function onto \(\mathbb{N}\). Suppose that \(2^{m_1} (2{n_1} + 1)=2^{m_2}(2{n_2} + 1)\). Since \(2\) is not a prime factor of \(2{x} + 1\) for all \(x\in\mathbb{N}\), \(m_1=m_2\) and \(n_1=n_2\), thus \(f\) is a one-to-one function onto \(\mathbb{N}\). Therefore, \(\mathbb{N}\times\mathbb{N}\) is countable.\(\quad\square\)
3.4. \(\quad\)(i) The set of all finite sequences in \(\mathbb{N}\) is countable.
\(\quad\)(ii) The set of all finite subsets of a countable set is countable.
Proof. \(\quad\)(i) Let \(f\) be the function of all finite sequences in \(\mathbb{N}\) into \(\mathbb{N}\) given by, for some \(k\in \mathbb{N}\), \(\langle s_i\in\mathbb{N}:i<k\rangle\mapsto \prod_{i<k}p_{i+1}^{s_i+1}-1\) where \(p_i\) is the \(i\)-th prime number. Clearly, \(f\) is a one-to-one function onto \(\mathbb{N}\).
\(\quad\)(ii) Let \(X\) be a countable set and let \(Y\) be a set of all finite subsets of \(X\). There is a one-to-one function \(f\) of \(X\) onto \(\mathbb{N}\), thus for each \(S\in Y\), there is a unique increasing finite sequence \(\langle f(x): x\in S\rangle\), and so there is a one-to-one function of \(Y\) into all finite sequences in \(\mathbb{N}\); \(Y\le\aleph_0\) and \(\aleph_0=|X|=\{S\in Y:S\text{ is singleton}\}\subset Y\); thus \(\aleph_0\le Y\). Therefore, \(Y=\aleph_0\).\(\quad\square\)
3.5. Show that \(\Gamma(\alpha\times\alpha)\le\omega^\alpha\).
Proof. \(\quad\)We show this by induction of \(\alpha\). \(\Gamma(0\times 0)\le\omega^0\). \(\Gamma( \alpha\times\alpha)\le\omega^\alpha\) \(\Leftrightarrow\) \(\Gamma((\alpha+1)\times(\alpha+1))\) \(=\) \(\Gamma(\alpha\times\alpha)+ \alpha\cdot 2 + 1\) \(\le\) \(\omega^\alpha+\omega^\alpha\cdot 2+\omega^\alpha\) \(=\) \(\omega^{\alpha}\cdot 4\le\omega^{\alpha+1}\). For a limit ordinal \(\gamma>0\), by definition \(\Gamma(\gamma\times\gamma)=\text{sup }\{ \Gamma(\alpha\times\alpha):\alpha<\gamma\}\le\omega^\gamma\).\(\quad\square\)
3.6. There is a well-ordering of the class of all finite sequences of ordinals such that for each \(\alpha\), the set of all finite sequences in \(\omega_\alpha\) is an initial segment and its order-type is \(\omega_\alpha\).
Proof. \(\quad\)We define: \[
\begin{aligned}
\langle\alpha_0,\ldots&\rangle\prec\langle\beta_0,\ldots\rangle
\leftrightarrow\\
&\text{there is }k\text{ such that }\\
&\qquad\alpha_k<\beta_k\text{ and }\alpha_i=\beta_i
\text{ for all }i<k,\\
\langle\alpha_i:i<m&\rangle<\langle\beta_i:i<n\rangle\leftrightarrow\\
&\text{either }\sum_{i<m}\alpha_i+m <
\sum_{i<n}\beta_i+n\\
&\text{or }\sum_{i<m}\alpha_i+m=\sum_{i<n}\beta_i+n\\
&\qquad\text{ and }
\langle\alpha_i:i<m\rangle\prec\langle\beta_i:i<n\rangle.\\
\end{aligned}
\] \(\quad\)Let \(X\) be the class of all finite sequences of ordinals. The relation \(<\) defined above is a linear ordering of \(X\). Moreover, if \(S\subset X\) is nonempty, then \(S\) has the least element. If we let \(\Gamma(\alpha)=\) the order-type of the set \(\{\beta\in X:\beta<\alpha\}\) for \(\alpha\in X\), then \(\Gamma\) is a one-to-one mapping of \(X\) onto \(Ord\). Note that for a finite sequence \(\alpha\) in \(\omega\), \(\Gamma(\alpha)\in\omega\), and so \(\langle\omega\rangle\) is the least element \(\alpha\) of \(X\) such that \(\alpha\) is not a finite sequence in \(\omega\); thus \(\Gamma(\langle\omega\rangle)=\omega\).
\(\quad\)Let \(\gamma(\alpha)=\Gamma(\langle\alpha\rangle)\). Note that \(\gamma(\alpha)\) is an increasing function of \(\alpha\) and also that since each infinite cardinal is indecomposable, by definition of \((X,<)\), \(\gamma(\omega_\alpha)\) is the set of all finite sequences in \(\omega_\alpha\). Let \(\eta(\alpha)=\) the order-type of the set of all finite sequences in \(\alpha\). \(\gamma(\alpha)\le\eta(\alpha)\) and \(\gamma(\omega_\alpha) =\eta(\omega_\alpha)\) for each \(\alpha\). We show that \(\gamma(\omega_\alpha)=\omega_\alpha\) by induction of \(\alpha\). This is true for \(\alpha=0\). Thus let \(\alpha\) be the least ordinal such that \(\gamma(\omega_\alpha)\ne\omega_\alpha\). Since \(\gamma\) is increasing, \(\gamma(\omega_\alpha)\ge\omega_\alpha\); thus \(\gamma(\omega_\alpha)>\omega_\alpha\), and so there is a sequence \(\beta\) such that \(\Gamma(\beta)=\omega_\alpha\) and \(\beta<\langle\omega_\alpha\rangle\). Then there is an ordinal \(\delta\) such that \(\beta<\langle\delta\rangle<\langle\omega_\alpha\rangle\); thus \(\Gamma(\beta)=\omega_\alpha<\gamma(\delta)\le\eta(\delta)\), and so \(\aleph_\alpha\le|\eta(\delta)|\) \(=\) \(|\eta(|\delta|)| \le\eta(|\delta|)\). But since \(\delta<\omega_\alpha\), by the minimality of \(\alpha\), \(\eta(|\delta|)=|\delta|<\aleph_\alpha\), a contradiction. Finally, by definition of \(\gamma\), for each nonzero limit ordinal \(\alpha\), \(\gamma(\omega_\alpha)= \text{sup }\{\gamma(\omega_\xi):\xi<\alpha\}=\omega_\alpha\).\(\quad\square\)
\(\quad\)We say that a set \(B\) is a projection of a set \(A\) if there is a mapping of \(A\) onto \(B\). Note that \(B\) is a projection of \(A\) if and only if there is a partition \(P\) of \(A\) such that \(|P| = |B|\). If \(|A|\ge |B| > 0\), then \(B\) is a projection of \(A\). Conversely, using the Axiom of Choice, one shows that if \(B\) is a projection of \(A\), then \(|A|\ge |B|\). This, however, cannot be proved without the Axiom of Choice.
3.7. If \(B\) is a projection of \(\omega_\alpha\), then \(|B|\le\aleph_\alpha\).
Proof. \(\quad\)Let \(f\) be a function of \(\omega_\alpha\) onto \(B\). There is a one-to-one function of \(B\) into \(\omega_\alpha\) given by \(b\mapsto\bigcap f_{-1}(\{b\})\).\(\quad\square\)
3.8. The set of all finite subsets of \(\omega_\alpha\) has cardinality \(\aleph_\alpha\).
\(\quad\)[The set is a projection of the set of finite sequences.]
Proof. \(\quad\)Let \(X\) be the set of all finite sequences in \(\omega_\alpha\) and let \(Y\) be the set of all finite subsets of \(\omega_\alpha\). There is a function of \(X\) onto \(Y\) given by \(\langle\alpha_0,\ldots\alpha_n\rangle\mapsto\{\alpha_0,\ldots\alpha_n\}\). Thus \(\aleph_\alpha = |X|\ge|Y|\). But there is a one-to-one mapping of \(S\subset Y\) such that each \(x\in S\) is singleton onto a set of cardinality \(\aleph_\alpha\). Thus \(Y\ge\aleph_\alpha\). Therefore, \(|Y|=\aleph_\alpha\).\(\quad\square\)
3.9. If \(B\) is a projection of \(A\), then \(|P (B)|\le |P (A)|\).
\(\quad\)[Consider \(g(X) = f_{-1}(X)\), where \(f\) maps \(A\) onto \(B\).]
Proof. \(\quad\)Since there is a unique \(f_{-1}(S)\subset A\) for each \(S\subset B\), the one-to-one function of \(P(B)\) into \(P(A)\) given by \(S\mapsto f_{-1}(S)\) exits.\(\quad\square\)
3.10. \(\omega_{\alpha+1}\) is a projection of \(P(\omega_\alpha)\).
\(\quad\)[Use \(|\omega_\alpha\times\omega_\alpha| =\omega_\alpha\) and project \(P(\omega_\alpha\times\omega_\alpha)\): If \(R\subset\omega_\alpha \times\omega_\alpha\) is a well-ordering, let \(f(R)\) be its order-type.]
Proof. \(\quad\)Since \(\omega_{\alpha+1}\) is a set of possible well-orderings of subsets of \(X\) such that \(|X| = \aleph_\alpha\), there is \(R\in P(\omega_\alpha\times\omega_\alpha)\) such that \(f(R)=\beta\) for each \(\beta\in\omega_{\alpha+1}\). Let \(g(R)=f(R)\) if \(R\) is a well-ordering; otherwise \(g(R)=0\). There is the mapping of \(P(\omega_\alpha\times\omega_\alpha)\) onto \(\omega_{\alpha+1}\) given by \(R\mapsto g(R)\).\(\quad\square\)
3.11. \(\aleph_{\alpha+1}<2^{2^{\aleph_\alpha}}\).
\(\quad\)[Use Exercises 3.10 and 3.9.]
Proof. \(\quad\)By exercises 3.10 and 3.9, \(\aleph_{\alpha+1}\le{2^{\aleph_\alpha}}\), and by Cantor’s theorem, \(\aleph_{\alpha+1}<2^{2^{\aleph_\alpha}}\).\(\quad\square\)
3.12. If \(\aleph_\alpha\) is an uncountable limit cardinal, then cf \(\omega_\alpha\) = cf \(\alpha\); \(\omega_\alpha\) is the limit of a cofinal sequence \(\langle\omega_\xi :\xi <\text{cf }\alpha\rangle\) of cardinals.
Proof. \(\quad\)cf \(\omega_\alpha=\) cf cf \(\alpha=\) cf \(\alpha\).\(\quad\square\)
3.13 (ZF). Show that \(\omega_2\) is not a countable union of countable sets.
\(\quad\)[Assume that \(\omega_2=\bigcup_{n<\omega}S_n\) with \(S_n\) countable and let \(\alpha_n\) be the order-type of \(S_n\). Then \(\alpha=\text{sup}_n\alpha_n\le\omega_1\) and there is a mapping of \(\omega\times\alpha\) onto \(\omega_2\).]
Proof. \(\quad\)We can assume that \(S_n\) is disjoint for each \(n\le\omega\). Then we have the one-to-one function of \(\omega\times\alpha\) onto \(\omega_2\) given by \((n,\beta)\mapsto\) the \(\beta\)-th element of \(S_n\) if \(\beta\in\alpha_n\); otherwise \((n,\beta)\mapsto 0\). Thus \(\aleph_2=|\omega_2|\le|\omega\times\alpha|\le\aleph_0\cdot \aleph_1=\aleph_1\), a contradiction.\(\quad\square\)
\(\quad\)A set \(S\) is Dedekind-finite (D-finite) if there is no one-to-one mapping of \(S\) onto a proper subset of \(S\). Every finite set is D-finite. Using the Axiom of Choice, one proves that every infinite set is D-infinite, and so D-finiteness is the same as finiteness. Without the Axiom of Choice, however, one cannot prove that every D-finite set is finite.
\(\quad\)The set \(\mathbb{N}\) of all natural numbers is D-infinite and hence every \(S\) such that \(|S|\ge\aleph_0\), is D-infinite.
3.14. \(S\) is D-infinite if and only if S has a countable subset.
\(\quad\)[If \(S\) is D-infinite, let \(f:S\to X\subset S\) be one-to-one. Let \(x_0\in S-X\) and \(x_{n+1}=f(x_n)\). Then \(S\supset\{x_n:n<\omega\}\).]
Proof. \(\quad\)If \(S\) is D-infinite, then since \(f\) is one-to-one, \(x_m\neq x_n\) for all \(m\) and \(n\) such that \(0\le m < n<\omega\). Thus there is a countable set \(X=\{x_n:n<\omega\}\subsetneq S\).
\(\quad\)Conversely, if \(S\) has a countable subset \(X=\{x_n:n<\omega\}\), then there is the one-to-one mapping of \(S\) onto \(S\smallsetminus\{x_0\}\) given by \(x\mapsto x\) if \(x\notin X\); otherwise \(x_n\mapsto x_{n+1}\).\(\quad\square\)
3.15. \(\quad\)(i) If \(A\) and \(B\) are D-finite, then \(A\cup B\) and \(A\times B\) are D-finite.
\(\quad\)(ii) The set of all finite one-to-one sequences in a D-finite set is D-finite.
\(\quad\)(iii) The union of a disjoint D-finite family of D-finite sets is D-finite.
Proof. \(\quad\)(i) Suppose that \(X\subset A\cup B\) is countable. Since a subset of a countable set is at most countable, \(X\cap A\) and \(X\cap B\) are at most countable. Since \(X=(X\cap A)\cup(X\cap B)\) and the union of a finite set of finite sets is finite, \(X\cap A\) or \(X\cap B\) are countable. Thus \(A\) or \(B\) are D-infinite, a contradiction. Suppose that \(X=\{(x_i, y_i):i<\omega\}\) \(\subset A\times B\) is countable. Consider \(C=\{x \in A:(x, y)\in X\) for some \(y\}\) and \(D=\{y \in A:(x, y)\in X\) for some \(x\}\). Since \(\aleph_0=|X|\le |C|\times|D|\) and \(|C|\le|X|=\aleph_0\) and \(|D|\le|X|=\aleph_0\), \(C\) or \(D\) are countable. But \(C\subset A\) and \(D\subset B\), a contradiction.
\(\quad\)(ii) Let \(A\) be a D-finite set and let \(X=\{X_i: i<\omega\}\) be a subset of all finite one-to-one sequences in \(A\). Suppose that \(X\) is countable. Consider the cardinality of \(S=\bigcup_{i<\omega}\text{ran}(X_i)\). Since \(X_i\) is a finite one-to-one sequence for all \(i<\omega\), \(|S|\le|\omega|\cdot|\omega|=\aleph_0\). If \(|S|=n\) for some \(n<\omega\), then \(X_i \in \bigcup\{S^1, S^2,\ldots S^n\}\) for all \(i<\omega\), thus \(X\subset \bigcup\{S^1, S^2,\ldots S^n\}\). By (i), and induction of \(n\), the union of a finite family of D-finite sets is D-finite, and a finite product of D-finite sets is D-finite, thus \(\bigcup\{S, S^2,\ldots S^n\}\) is D-finite. But \(X\subset \bigcup\{S, S^2,\ldots S^n\}\), a contradiction. Thus \(S\) is countable. But \(S\subset A\), also a contradiction.
\(\quad\)(iii) For some D-finite \(I\), let \(X=\bigcup_{i\in I}X_i\) be a union of a disjoint D-finite family of D-finite sets. Suppose that \(S=\{\alpha_n:n<\omega\}\subset X\) is countable. Consider the cardinality of \(T=\{i\in I:i\) such that \(\alpha\in X_i\) for some \(\alpha\in S\}\). Since \(X_i\) is disjoint for each \(i\in I\), \(|T|\le|S|=\aleph_0\). Now suppose that \(|T|=n<\omega\). Then \(S\) is a union of a finite family of D-finite set, thus finite; a contradiction. So \(T\) is countable. But \(T\subset I\), also a contradiction.\(\quad\square\)
\(\quad\)On the other hand, one cannot prove without the Axiom of Choice that a projection, power set, or the set of all finite subsets of a D-finite set is D-finite, or that the union of a D-finite family of D-finite sets is D-finite.
3.16. If \(A\) is an infinite set, then \(PP(A)\) is D-infinite.
\(\quad\)[Consider the set \(\{\{X\subset A:|X|=n\}:n<\omega\}\).]
Proof. \(\quad\) The set \(\{\{X\subset A:|X|=n\}:n<\omega\}\subset PP(A)\) is countable.\(\quad\square\)