• Quick access
  • Homepage (fr)
  • International
  • François's Blog
  • Frédéric's Blog
  • Maths (fr)
  • Computer Science (fr)
  • Programming (fr)
  • Our games (fr)
  • Video games (fr)
• Special pages
  • Log in (fr)
  • Forum
  • Authors (fr)
  • Site Map (fr)
• Parent directories
  • International
  • Set Theory
  • Set theory - Chapter 3: Cardinal Numbers
• Current directory
  • Set theory - Chapter 1: Axioms of Set theory
  • Set theory - Chapter 2: Ordinal Numbers
  • Set theory - Chapter 3: Cardinal Numbers
  • Set theory - Chapter 6: The Axiom of Regularity
  • Set theory - Chapter 14: Forcing

Set theory - Chapter 3: Cardinal Numbers

3.1

First, we notice that the ordering ${\le }_{\mathrm{Ord}}$ is the same as ${\le }_{\mathrm{Card}}$ for natural numbers. Let $n,m$ be two natural numbers. We can suppose $n{\le }_{\mathrm{Ord}}m$. Then $n\subseteq m$ and the identity is 1-1 from $n$ to $m$, i.e. $n{\le }_{\mathrm{Card}}m$.

1. Let $X$ be a finite set of cardinality $n$ and $f:X\to n$ 1-1 onto. Let $Y\subseteq X$. The identity of $Y$ is 1-1 so we have $\mid Y\mid \le \mid X\mid =n$. Let $p$ be the least natural number such that $\mid Y\mid \le p$. We shall show that $\mid Y\mid =p$. If $p=0$, then $Y=\varnothing$ and we are done. Otherwise, we can write $p=q+1$and there exists a 1-1 $g$ from $Y$ to $p$ that is not surjective. We can suppose $q\notin \mathrm{ran}\left(g\right)$. Then $g:Y\to q$ is 1-1 and $\mid Y\mid \le q<p$. A contradiction. Finally $Y$ is finite.
2. Let $S=\bigcup _{i<p}{S}_i$ and $f_i:S_i\to n_i$ 1-1 (onto). Let $f:\mid \begin{array}{c}S\to \sum _{i<p}{n}_i\\ x\mapsto (\sum _{j<k_i}{n}_j+f_i\left(x\right))\end{array}$ where for each $i$, $k_i$ is the least natural number such that $x\in S_{k_i}$. Clearly, $f$ is well-defined and 1-1 so $\mid S\mid \le \sum _{i<p}{n}_i$. As in (i), we conclude that $S$ is finite.
3. Let $S$ be finite and $f:S\to n$ 1-1 onto. Let $g:\mid \begin{array}{c}\wp \left(S\right)\to 2^n\\ X\mapsto \sum _{x\in X}{2}^{f\left(x\right)}\end{array}$. By unicity of the binary decomposition of a natural (easy to show by induction) and because $f$ is one-to-one, see that $g$ is also one-to-one. Hence $\wp \left(S\right)$ is finite.
4. Let $S$ be finite and $f:S\to n$ 1-1 onto and consider a mapping $F:S\to T$. Then $g:\mid \begin{array}{c}F\left(S\right)\to n\\ x\mapsto min\left\{i<\omega |(F\left(f^{-1}\left(i\right)\right)=x)\right\}\end{array}$ is 1-1 so $F\left(S\right)$ is finite.

3.2

1. Let be an enumeration of $S$ (i.e. $f:n\mapsto a_n$ is 1-1 onto from $\mathbb{N}$ to $S$) and $X\subseteq S$ . If $X$ is finite, then we are done. Define by induction for each $n<\omega$ $x_n{=a}_p$ where $p$ is the least natural such that $a_p\notin \left\{x_i|i<n\right.i$and $a_p\in X$ . Such an $a_p$ always exists for otherwise $X\subseteq \left\{x_i|i<n\right.i$ would be finite by 3.1 (i). Then $n\mapsto x_n$ is 1-1 from ${\aleph }_0$ to $X$ and $x\mapsto f^{-1}\left(x\right)$ is 1-1 from $X$ to ${\aleph }_0$ . By Cantor-Berstein, $X$ is countable.
2. Let $S=\bigcup _{i<n}{S}_i$ with $f_i:S_i\to {\aleph }_0$1-1 onto. We suppose $n\ge 1$ for otherwise $S=\varnothing$. Then ${f_0}^{-1}$ is 1-1 from ${\aleph }_0$ to $S$. Define $g:\mid \begin{array}{c}S\to {\aleph }_0\\ x\mapsto 2^i{3}^{f_i\left(x\right)}\end{array}$ where $i<n$ is the least element such that $x\in S_j$. By Cantor-Bernstein, $\mid S\mid ={\aleph }_0$.
3. Let $f:S\to {\aleph }_0$ 1-1 and $F:S\to F\left(S\right)$. Define $g:\mid \begin{array}{c}F\left(S\right)\to {\aleph }_0\\ x\mapsto g\left(x\right)\end{array}$ where $g\left(x\right)$ is the least $i$ such that $F\left(f^{-1}\left(i\right)\right)=x$. Then $g$ is 1-1. By (i), $g\left(F\left(S\right)\right)\subseteq {\aleph }_0$ is at most countable. So $F\left(S\right)$ too.

3.3

$$f:\mid \begin{array}{c}\mathbb{N}\times \mathbb{N}\to \mathbb{N}\\ \left(n,m\right)\mapsto 2^m\left(2n+1\right)-1\end{array}$$

Let $x\in \mathbb{N}$ and p be the greatest natural such that $2^p$ divides $x+1$. Then $\raisebox{1ex}{$x+1$}\!\left/ \!\raisebox{-1ex}{$2^p$}\right.$ is odd and can be written $2q+1$ for some natural $q$. Thus $f$ is onto. If $f(n_1,m_1)=f(n_2,m_2)$ then $2^{n_1}(2m_1+1)=2^{n_2}(2m_2+1)$. Hence $n_1=n_2$ since $(2m_i+1)$ is odd. Then $m_1=\frac{2m_2+1-1}{2}=m_2$. Therefore $f$ is also onto. Finally $\mathbb{N}\times \mathbb{N}$ is countable.

3.4

1. Let $g:<a_i:i<n>\mapsto 2^n\prod _{i<n}{p_i}^{a_i}-1$ where $p_i$ is the $i+1$th prime number. Then $g$ is 1-1 onto.
2. Let $S=\left\{a_i|i<{\aleph }_0\right\}$ a countable set. Let $g:X\mapsto \prod _{i<n}{p_i}^{{\chi }_X\left(a_i\right)}-1$ where ${\chi }_X$ is the characteristic function of X. Then $g$ is 1-1 onto.

3.5

For $n<\omega$, $\Gamma \left(n\times n\right)<\omega \le {\omega }^n$. $\Gamma \left(\omega \times \omega \right)=\omega \le {\omega }^{\omega }$. Let $\alpha \ge \omega$ such that $\Gamma \left(\alpha \times \alpha \right)\le {\omega }^{\alpha }$.Then the order type of $\left(\alpha +1\right)\times \left(\alpha +1\right)$ given by the canonical ordering is:

1. First, the initial segment $\alpha \times \alpha$ given by $\left(0,\alpha \right)$
2. The elements $\left(\zeta ,\alpha \right)$ for $\zeta <\alpha$
3. The elements $\left(\alpha ,\zeta \right)$ for $\zeta <\alpha$
4. and finally $\left(\alpha ,\alpha \right)$.

Consequently, $\Gamma \left(\left(\alpha +1\right)\times \left(\alpha +1\right)\right)=\Gamma \left(\alpha \times \alpha \right)+\alpha 2+1\le {\omega }^{\alpha }+\alpha 3\le {\omega }^{\alpha }+{\omega }^{\alpha }3\le {\omega }^{\alpha }4\le {\omega }^{\alpha }\omega ={\omega }^{\alpha +1}$

If $\lambda >\omega$ is a limit ordinal such that $\Gamma \left(\alpha \times \alpha \right)\le {\omega }^{\alpha }$ for all $\alpha <\lambda$ then since $\alpha \mapsto \Gamma \left(\alpha \times \alpha \right)$ and $\alpha \mapsto {\omega }^{\alpha }$ are continuous then $\Gamma \left(\lambda \times \lambda \right)\le {\omega }^{\lambda }$.

3.6

...

3.7

Let $f:{\omega }_{\alpha }\to B$ an onto mapping. Then $g:\mid \begin{array}{c}B\to {\omega }_{\alpha }\\ x\mapsto min\left(f^{-1}\left(x\right)\right)\end{array}$ is 1-1 and $\mid B\mid \le \mid {\omega }_{\alpha }\mid ={\aleph }_{\alpha }$.

3.8

Let $X={\left[{\omega }_{\alpha }\right]}^{<\omega }$ and $Y=\bigcup _{n<\omega }{{\omega }_{\alpha }}^n$. The onto mapping $f:\mid \begin{array}{c}Y\to X\\ \left(x_1,x_2,x_3,...,x_n\right)\mapsto \left\{x_1,x_2,x_3,...,x_n\right\}\end{array}$ shows that $X$ is a projection of $Y$. But

$$\mid Y\mid =\mid \bigcup _{n<\omega }{{\omega }_{\alpha }}^n\mid =\sum _{n<\omega }\mid {{\omega }_{\alpha }}^n\mid =\sum _{n<\omega }{\aleph }_{\alpha }={\aleph }_{\alpha }{\aleph }_0={\aleph }_{\alpha }$$

Hence by 3.7, $\mid X\mid \le {\aleph }_{\alpha }$. Now $h:\mid \begin{array}{c}{\omega }_{\alpha }\to X\\ x\mapsto \left\{x\right\}\end{array}$ is 1-1 so $\mid X\mid ={\aleph }_{\alpha }$.

3.9

Let $B$ be a projection of $A$ and $f:A\to B$ onto. Let $g:\mid \begin{array}{c}\wp \left(B\right)\to \wp \left(A\right)\\ X\mapsto f^{-1}\left(X\right)\end{array}$. Suppose that $g\left(X_1\right)=g\left(X_2\right)$ then for all $x\in X_1$there is $y\in f^{-1}\left(X_1\right)=f^{-1}\left(X_2\right)$ such that $f\left(y\right)=x$. Hence $x\in X_2$ and $X_1\subseteq X_2$. By symmetry, $X_1=X_2$ and so $g$ is 1-1. Thus $\mid \wp \left(B\right)\mid \le \mid \wp \left(A\right)\mid$.

3.10

Let $f:\wp \left({\omega }_{\alpha }\times {\omega }_{\alpha }\right)\to {\omega }_{\alpha +1}$ such that for all $R\in \wp \left({\omega }_{\alpha }\times {\omega }_{\alpha }\right)$, $f\left(R\right)$ is the order-type of $R$ if this one is a well-ordering of ${\omega }_{\alpha }$ and any $x\in {\omega }_{\alpha +1}$ otherwise. In the former case, $f\left(R\right)=\beta$ for an ordinal $\beta$ such that $\mid \beta \mid \le \mid {\omega }_{\alpha }\mid$. Hence $f\left(R\right)=\beta <{\omega }_{\alpha +1}$ and $f$ is well-defined.

Each $\beta \in {\omega }_{\alpha }$is an ordinal and its well-ordering $R$ satisfies $f\left(R\right)=\beta$. If $\beta \in {\omega }_{\alpha +1}$ and $\beta \ge {\omega }_{\alpha }$, then $\mid \beta \mid =\mid {\omega }_{\alpha }\mid$. Let $g$ be a one-to-one mapping from ${\omega }_{\alpha }$ onto $\beta$ and define the relation ≼ on ${\omega }_{\alpha }$ by $x\preccurlyeq y$ iff $g\left(x\right)\in g\left(y\right)$. Then by construction we have $f(\preccurlyeq )=\beta$. Finally $f$ is onto.

Since $\mid {\omega }_{\alpha }\times {\omega }_{\alpha }\mid ={\aleph }_{\alpha }={\omega }_{\alpha }$ we conclude that ${\omega }_{\alpha +1}$ is a projection of $\wp \left({\omega }_{\alpha }\right)$.

3.11

By Cantor's theorem, $\mid {\omega }_{\alpha +1}\mid <\mid \wp \left({\omega }_{\alpha +1}\right)\mid$. Using 3.10 and 3.9 we get $\mid \wp \left({\omega }_{\alpha +1}\right)\mid \le \mid \wp \left(\wp \left({\omega }_{\alpha }\right)\right)\mid$. Finally, ${\aleph }_{\alpha +1}<2^{2^{{\aleph }_{\alpha }}}$.

3.12

Let ${\aleph }_{\alpha }$ an uncountable limit cardinal. Then $\alpha \ge 1$ is limit. Let $<{\alpha }_{\zeta }:\zeta <\mathrm{cf}\left(\alpha \right)>$a cofinal sequence in $\alpha$. If $\kappa <{\aleph }_{\alpha }$, there is $\beta <\alpha$ such that $\kappa ={\aleph }_{\beta }$. Let $\zeta <\mathrm{cf}\left(\alpha \right)$ such that ${\alpha }_{\zeta }>\beta$. Then ${\aleph }_{{\alpha }_{\zeta }}>{\aleph }_{\beta }=\kappa$. So we have $\underset{\zeta <\mathrm{cf}\left(\alpha \right)}{sup}{\aleph }_{{\alpha }_{\zeta }}={\aleph }_{\alpha }$. By Lemma 3.7(ii) the sequence $<{{\aleph }_{\alpha }}_{\zeta }:\zeta <\mathrm{cf}\left(\alpha \right)>$shows that $\mathrm{cf}\left(\mathrm{cf}\left(\alpha \right)\right)=\mathrm{cf}\left({\aleph }_{\alpha }\right)$. Finally $\mathrm{cf}\left(\alpha \right)=\mathrm{cf}\left({\omega }_{\alpha }\right)$.

3.13

Suppose that ${\omega }_2=\bigcup _{n<\omega }{S}_n$with $\mid S_n\mid ={\aleph }_0$ and let ${\alpha }_n$ be the order-type of $S_n$. We may assume that the sets $S_n$ are disjoint. Then $\forall n<\omega ,{\alpha }_n<{\omega }_1$and $\alpha =sup{\alpha }_n\le {\omega }_1$. Define $f:\mid \begin{array}{c}\omega \times \alpha \to {\omega }_2\\ \left(n,\zeta \right)\mapsto f\left(n,\zeta \right)\end{array}$ where $f\left(n,\zeta \right)$ is the $\zeta$th element of $S_n$ if $\zeta <{\alpha }_n$ and any element of ${\omega }_2$ otherwise. Then $f$ is onto and we can build a 1-1 map from ${\omega }_2$ to $\omega \times \alpha$ (without AC since $\omega \times \alpha$ is well-ordered). Consequently ${\aleph }_2=\mid {\omega }_2\mid \le \mid \omega \times \alpha \mid \le {\aleph }_0{\aleph }_1={\aleph }_1$. A contradiction.

3.14

Let $S$ be D-infinite and $f:S\to X⊊S$ a 1-1 onto map. Let $x_0\in S\backslash X$and define for all $n<\omega$ $x_{n+1}=f\left(x_n\right)$. $x_0\notin X$ while for every $n>0,x_n\in X$. Hence $x_0$ is distinct of all $x_n,n>0$. We show by induction on $n$ that for all $0<m<n$, $x_m\ne x_n$ . This is true for $n=1$ by the previous remark. Suppose it is true for some $n\ge 1$. Then for all $0<m<n+1$, $x_m\ne x_{n+1}$ or otherwise $x_{m-1}=x_n$ (since $f$ is 1-1) contradicts either the induction hypothese or the inital remark on $x_0$. Hence $n\mapsto x_n$ is 1-1 and $S$ contains the countable subset $X=\left\{x_n:n<\omega \right\}$.

Conversely, if $X=$$\left\{x_n:n<\omega \right\}$ is a countable subset of $S$. Then $f:\mid \begin{array}{c}S\to S\backslash \left\{x_0\right\}\\ x\mapsto \{\begin{array}{c}x\text{ if }x\notin X\\ x_{n+1}\text{ if }x=x_n\end{array}\end{array}$ shows that S is D-infinite.

3.15

We use the equivalent definition of D-finiteness obtained in 3.14. For each proof we suppose that final set is D-infinite and shows that one of the initial set is not D-finite.

1. • Let $X\subseteq A\cup B$ a countable set. Then by 3.2 (ii), $X\cap A$ and $X\cap B$ are at most countable. If one of them is finite, then so is $X=\left(X\cap A\right)\cup \left(X\cap B\right)$by 3.1 (i). Thus one of them is a countable subset of $A$ or $B$.
   • Let $\left\{\left(a_n,b_n\right)|n<\omega \right\}=X$ a countable subset of $A\times B$. Let ${\alpha }_0=a_0$ and for $n>0,{\alpha }_n=a_k$ where $k$ is the least index such that $a_k\notin \left\{{\alpha }_i|i<n\right\}$(if such an index exists). The sequence${\left({\beta }_n\right)}_{n<\omega }$ is defined similarly. At least one of these sequences is completly defined, otherwise let $n,m$ the least indices such that ${\alpha }_n$ and ${\beta }_m$ are not defined, then $X$ is a subset of the finite set $\left\{{\alpha }_i|i<n\right\}\times \left\{{\beta }_i|i<m\right\}$ . Suppose for instance that $\left\{{\alpha }_n|n<\omega \right\}$ is well defined, then it is a countable subset of $A$.
2. Let $A$ a set and $\{{\left(u_k^i\right)}_{k<n_i},i<\omega \}$ a countable set of 1-1 finite sequence of elements of $A$. Let $x_0=u_0^0$ and for all $n>0,x_n=u_k^i$ where $i$ is the least index such that $\mathrm{ran}{u}^i$ is not included in $\left\{x_j:j<n\right\}$and $k$ the least index such that $u_k^i\notin \left\{x_j:j<n\right\}$. This sequence is well defined, otherwise if $n$ is the least index such that $x_n$ can not be defined, then $\left\{u_k^i,i<\omega ,k<n_i\right\}\subseteq X=\left\{x_j:j<n\right\}$and $\langle {\left(u_k^i\right)}_{k<n_i},i<\omega \rangle$ is included in the finite set (by 3.4 i) ${\left[X\right]}^{<\omega }$. Finally, $\left\{x_n|n<\omega \right\}$ is a countable subset of $A$.
3. Let ${\left(X_i\right)}_{i\in I}$ a dijoint family of D-finite sets and suppose that their union is D-infinite. Let $X=\left\{x_n|n<\omega \right\}$ a countable subset of $\bigcup _{i\in I}{X}_i$. For each $n<\omega$ let $m$ the least natural such that $x_m\in \bigcup _{i\in \left\{i_k|k<n\right\}}{X}_i$ . Such an $m$ always exists for otherwise $X\subseteq \bigcup _{i\in \left\{i_k|k<n\right\}}{X}_i$ while this union is D-finite by (i). Then, define $i_n$ the unique index such that $x_m\in X_i$. Finally, we get a countable set $\left\{i_n|n<\omega \right\}\subseteq I$.

3.16

Let $A$ an infinite set and for all $n<\omega ,X_n=\left\{X\subseteq A|\mid X\mid =n\right\}$ . Each $X_n$ is non-empty : $A$ is infinite so we can choose $n$ elements of $A$ to build an element of $X_n$. Moreover the $X_n$ are clearly pairwise distinct. Hence $\left\{X_n|n<\omega \right\}$is a countable subset of $\wp \left(\wp \left(A\right)\right)$. Finally, $\wp \left(\wp \left(A\right)\right)$ is D-infinite.

This page is W3C-compliant - Author: Frédéric WANG