Proposition The denumerable union of disjoint (in our book, pairwise disjoint) countable nonempty sets are denumerable. (Why add the condition of nonemptiness?)

Proof. Let $S_1$ , $S_2$ , ... be all the given sets. Then we know that each $S_j$ is in the form

$\begin{align} S_j=\{s_{j1},s_{j2},\cdots s_{j,n}\}\,\,\,\,\, or\,\,\,\,\, S_j=\{s_{j1}, s_{j2}\cdots \}\notag \end{align}$

Then the mapping $s_{jk}\mapsto \langle j,k\rangle$ , where $k$ is in the "domain" of $S_j$ , is bijective. Hence its image must be a subset of $\mathbb{N}\times\mathbb{N}$ . Moreover, $\{s_{11},s_{21}, s_{31}\cdots\}$ forms a denumerable set. Hence a previous example yields that $\coprod S_j$ is denumerable.

口

Proposition The denumerable union of countable sets is countable.

Proof. Let $S_1$ , $S_2$ , ... be all given sets. Set

$\begin{align} T_1&=S_1\notag\\ T_{j+1}&=S_{j+1}\setminus T_j \qquad\qquad \textit{for }j\in\mathbb{N}\notag \end{align}$

Then $\{T_j\}_{j=1}^\infty$ is pairwise disjoint. So

$\begin{align} S=\bigcup_{j=1}^\infty S_j = \coprod_{j=1}^\infty T_j\notag \end{align}$

is a denumerable union of disjoint countable sets. It'll be countable. (When is it non-denumerable? Can it even be empty?)

口

    Hence

Proposition   The countable union of countable sets is countable.

Here is a criterion for countability, which might or might not be useful.

Proposition   A set $S$ is countable if and only if $S\preceq \mathbb{N}$ .

Proof. If $S$ is denumerable, then $S\approx \mathbb{N}$ and hence $S\preceq \mathbb{N}$ . If $S$ if finite, then $S\preceq\mathbb{N}$ because $I_n\preceq \mathbb{N}$ . Conversly, Let $f$ be one-to-one from $S$ into $\mathbb{N}$ . Let $T=Im(f)$ . Then

(a) If $T$ contains no maximum, then $\mathbb{N}\preceq T$ (why?). Since $T\subset \mathbb{N}$ , we obtain that $\mathbb{N}\approx T$ . Since $f$ is onto $T$ , it follows that $S\approx T$ .

(b) If $T$ contains a maximum, say $n_0\in\mathbb{N}$ . Then $T\subset I_{n_0}$ . Hence $T$ is equinumerous to some $I_m$ (why? This might be proved by induction.). Similarly, the assertion is proved by $S\approx T\approx I_m$ .

口

Next, we consider sets with power of continuum. ("The set $A$ has power of continuum" means that $A\approx \mathbb{R}$ )

Proposition $\mathbb{R}^n:= \mathbb{R}\times\mathbb{R}\times\cdots\times\mathbb{R}$ for $n$ times, has the power of continuum.

Proof. Denote

$\begin{align} \mathfrak{m}=\{n\,\,:\,\,\mathbb{R}^n\,\,\textit{has the power of continuum} \}\notag \end{align}$

It's shown that $1,2\in\mathfrak{m}$ . Suppose that $k\in\mathfrak{m}$ . Let $f:\mathbb{R}\to\mathbb{R}^k$ and $G:\mathbb{R}\to\mathbb{R}\times \mathbb{R}$ be bijections. Write

$\begin{align} f(x)&=(f_1 (x), f_2 (x)\cdots f_k (x))\notag\\ g(x)&=(g_1 (x), g_2 (x))\notag \end{align}$

Then define $h:\mathbb{R}\to\mathbb{R}^{k+1}$ as

$\begin{align} h(x)=(f_1\circ g_1 (x), f_2 \circ g_1 (x)\cdots f_k \circ g_1 (x), g_2 (x)),\notag \end{align}$

$h(x)$ is then one-to-one and onto.

口

What is the connection between the natural number set $\mathbb{N}$ and the real number set $\mathbb{R}$ in the sense of cardinality (the "number" of elements in a set)?? In fact, a thoroughly obvervation would tell us the following proposition.

Proposition $[0,1)\approx \wp (\mathbb{N})$ and $\wp (\mathbb{N})\approx \{f\,|\,f:\mathbb{N}\to\{0,1\}\}$

Proof. Define the mapping $f$ by $0.a_1 a_2\cdots\mapsto\{j\,|\,a_j=1\}$ , and the mapping $g$ by $B\subset\mathbb{N}\mapsto 0.b_1 b_2 b_3\cdots$ in binary where $b_{2j}=1$ if and only if $j\in B$ while all other decimal digits are 0. Hence $f$ and $g$ play roles as injections in both directions. Schr $\ddot{o}$ der Bernstein (Be careful for the spelling!) Theorem says that $[0,1)\approx \wp (\mathbb{N})$ .

The other assertion is similar. Take $\varphi$ as the mapping who maps a subset $B$ of $\mathbb{N}$ to the function $f:\mathbb{N}\to\{0,1\}$ such that $f(n)=1$ if and only if $n\in B$ . Another mapping $\tau$ is chosen to map a function $f:\mathbb{N}\to\{0,1\}$ to the subset $B=\{j\in\mathbb{N}\,:\,f(j)=1\}$ . They both are injection (Verify it!). Therefore Schr $\ddot{o}$ der Bernstein leads us to the conclusion.

口

Through the same argument, we derive the following proposition.

Proposition $\wp (\mathbb{A})\approx \{f\,|\,f:\mathbb{A}\to\{0,1\}\}$ for any set $\mathbb{A}$ .

Proof. Define the mapping $\varphi$ who maps a subset $A$ of $\mathbb{A}$ to the function $f:\mathbb{A}\to\{0,1\}$ such that $f(a)=1$ if and only if $a\in A$ . Another mapping $\tau$ is chosen to map a function $f:\mathbb{A}\to\{0,1\}$ to the subset $A=\{a\in\mathbb{A}\,:\,f(a)=1\}$ . They both are injection and then we prove the equinumerosity.

As an important remark, I have to mention which sets we have compared about their sizes. Indeed, we have the following types of discussion.

(i)    $\mathbb{N}\approx \mathbb{Z}\approx \mathbb{Q}\prec \mathbb{R}\approx\mathbb{C}$ .

(ii)    $\mathbb{R}\approx [0,1]\approx [0,1)\approx (0,1)\approx \mathbb{R}^+ \approx [0,\infty)$

(iii)    $\wp (\mathbb{N})\approx\mathbb{R} \approx \{f\,|\,f:\mathbb{N}\to \{0,1\}\}$

(iv)    $\mathbb{N}\approx \mathbb{N}\times\mathbb{N}\approx\mathbb{N}\times\mathbb{N}\times\mathbb{N}\approx\cdots\approx\mathbb{N}\times\mathbb{N}\times\cdots\mathbb{N}\prec_{(\ast)}\mathbb{N}\times\mathbb{N}\times\cdots$ .

(v)    $\mathbb{R}\approx \mathbb{R}\times\mathbb{R}\approx\mathbb{R}\times\mathbb{R}\times\mathbb{R}\approx\cdots\approx\mathbb{R}\times\mathbb{R}\times\cdots\mathbb{R}\approx_{(\ast\ast)}\mathbb{R}\times\mathbb{R}\times\cdots$ .

Note I have to emphasize the meaning of the notation $\mathbb{A}\times\mathbb{A}\times\cdots$ for a given set $\mathbb{A}$ . Recall that we use Order Pairs as elements in the product sets of given sets, namely

$\begin{align} \prod_{j=1}^n A_j = A_1\times A_2 \times\cdots\times A_n = \{(a_1, a_2,\cdots a_n)\,:\,a_j\in A_j \},\notag \end{align}$

and an interesting notion for an order pair is that, we might view it as a function ! By this I mean, after we define

$\begin{align} (a_1,a_2,\cdots a_n)=\{ \langle 1,a_1\rangle, \langle 2,a_2\rangle\cdots \langle n,a_n\rangle \}\notag \end{align}$

the concept about an order pair is illustrated.

The notation $\mathbb{A}\times\mathbb{A}\times\cdots$ seems to express all "infinite order pairs". Comparing with above, if $(a_1, \cdots , a_n)$ stands for a finite sequence, it is natural to convent that $(a_1,a_2,\cdots)$ means an infinite sequence, i.e.

$\begin{align} (a_1,a_2,\cdots)=\{\langle 1,a_1\rangle , \langle 2,a_2\rangle\cdots \}\notag \end{align}$

Directly thinking, we finally define $\mathbb{A}\times \mathbb{A}\times \cdots = \{a\,\,|\,\, a:\mathbb{N}\to\mathbb{A}\}$ . In particular, if we choose $\mathbb{A}=\mathbb{N}$ , then $\mathbb{N}\times\mathbb{N}\times\cdots = \{a\,\,|\,\, a:\mathbb{N}\to\mathbb{A}\}$ , all sequences in $\mathbb{N}$ .

口

Next, what are worth thinking for a while are the equinumerosity $(\ast)$ and the "dominance" $(\ast\ast)$ . Indeed, imitating Cantor's diagonal method for real numbers, we can show that $\mathbb{N}\times\mathbb{N}\cdots$ is uncountable. However, we still have no idea about whether it has power of continuum.

So we postpone the proof and then show the later assertion $(\ast\ast)$ first.

Proposition $\mathbb{R}\times\mathbb{R}\times\cdots \approx \mathbb{R}$

Proof. We ought to define an injection $\varphi :[0,1)\times [0,1)\times \cdots \to [0,1)$ throughout decimal expressions. For $r= (r_1, r_2, r_3, \cdots)\in\mathbb{R}\times\mathbb{R}\times\cdots$ , write

$\begin{align} r_1 &= 0.r_{11} r_{12} r_{13} r_{14}\cdots\notag\\ r_2 &= 0.r_{21} r_{22} r_{23} r_{24}\cdots\notag\\ r_3 &= 0.r_{31} r_{32} r_{33} r_{34}\cdots\notag\\ r_4 &= 0.r_{41} r_{42} r_{43} r_{44}\cdots\notag\\ &\vdots\notag \end{align}$

Then we define $\varphi (r) = 0.r_{11} r_{21} r_{22} r_{12} r_{13} r_{23} r_{33} r_{32} r_{31} r_{41} r_{42} r_{43} r_{44} r_{34}\cdots$ . We know $\varphi$ is injective (Show!), and we can easily find a converse injection. Hence Schr $\ddot{o}$ der Bernstein Theorem concludes the equinumerosity.

口

Proposition $\mathbb{N}\times\mathbb{N}\times\cdots \approx \mathbb{R}$

Proof. Since

$\begin{align} \mathbb{R}\approx \{0,1\}\times\{0,1\}\times\cdots \preceq \mathbb{N}\times\mathbb{N}\times\cdots \preceq \mathbb{R}\times\mathbb{R}\times\cdots\approx \mathbb{R},\notag \end{align}$

immediately we have $\mathbb{N}\times\mathbb{N}\times\cdots \approx \mathbb{R}$ .

口

At last, I shall show two essential properties for sets with large cardinality.

Definition $\mathbb{T}$ is defined as all functions from $\mathbb{R}$ to $\mathbb{R}$ . $\mathbb{T}_c$ is defined as all functions from $\mathbb{R}$ continuously to $\mathbb{R}$ .

In all my articles, $\mathbb{T}$ is defined as all functions from $\mathbb{R}$ to $\mathbb{R}$ ; $\mathbb{T}_2$ is defined as all functions from $\mathbb{R}$ to $\{0,1\}$ .

Proposition $\mathbb{R}\prec \mathbb{T}$ .

Proof. Assume $\mathbb{R}\approx \mathbb{T}$ (Why $\mathbb{R}\preceq \mathbb{T}$ ??). Let $F:\mathbb{R}\to\mathbb{T}$ be such a bijection. Define a function $g:\mathbb{R}\to \mathbb{R}$ such that for $c\in \mathbb{R}$ ,

$\begin{align} g(c)= \begin{cases} 0, &\text{if $(F(c))(c)=1 $; } \\ 1, &\text{otherwise.} \end{cases} \end{align}$

(This is the "diagonal argument" on continuum.) We know that $g\in\mathbb{T} =F(\mathbb{R})$ . For $x\in \mathbb{R}$ , since $g(x)\ne (F(x))(x)$ , we have that $g\ne F(x)$ . This means $g\notin F(\mathbb{R})$ , a contradiction.

口

Problem Is $\mathbb{R}\prec \mathbb{T}_c$ or $\mathbb{R}\approx \mathbb{T}_c$ ?? [改自台灣某知名大學碩士班入學考題]

Proposition (Cantor) For every set $A$ , $A\prec \wp (A)$ , or equivalently, $A\prec \{f\,|\, f:A\to \{0,1\}\}$ .

Proof. We prove the later type. Denote $\ddot{\mathbb{A}}=\{f\,|\, f:\mathbb{A}\to\{0,1\}\}$ . Assume $\mathbb{A}\approx \ddot{\mathbb{A}}$ (Why $\mathbb{A}\preceq \ddot{\mathbb{A}}$ ??). Let $F:\mathbb{A}\to\ddot{\mathbb{A}}$ be such a bijection. Define a function $g:\mathbb{A}\to \{0,1\}$ such that for $c\in \mathbb{A}$ ,

$\begin{align} g(c)= \begin{cases} 0, &\text{if $(F(c))(c)=1 $; } \\ 1, &\text{otherwise.} \end{cases} \end{align}$

We know that $g\in\ddot{\mathbb{A}} =F(\mathbb{A})$ . For $x\in \mathbb{A}$ , since $g(x)\ne (F(x))(x)$ , we have that $g\ne F(x)$ . This means $g\notin F(\mathbb{A})$ , a contradiction.

口

(i)	$\mathbb{N}\approx \mathbb{Z}\approx \mathbb{Q}\prec \mathbb{R}\approx\mathbb{C}$ .
(ii)	$\mathbb{R}\approx [0,1]\approx [0,1)\approx (0,1)\approx \mathbb{R}^+ \approx [0,\infty)$
(iii)	$\wp (\mathbb{N})\approx\mathbb{R} \approx \{f\,\|\,f:\mathbb{N}\to \{0,1\}\}$
(iv)	$\mathbb{N}\approx \mathbb{N}\times\mathbb{N}\approx\mathbb{N}\times\mathbb{N}\times\mathbb{N}\approx\cdots\approx\mathbb{N}\times\mathbb{N}\times\cdots\mathbb{N}\prec_{(\ast)}\mathbb{N}\times\mathbb{N}\times\cdots$ .
(v)	$\mathbb{R}\approx \mathbb{R}\times\mathbb{R}\approx\mathbb{R}\times\mathbb{R}\times\mathbb{R}\approx\cdots\approx\mathbb{R}\times\mathbb{R}\times\cdots\mathbb{R}\approx_{(\ast\ast)}\mathbb{R}\times\mathbb{R}\times\cdots$ .