Definition. A set $X$ is called countable (or denumerable) if $card(X)\le card(\mathbb N)$. In particular, all finite sets are countable. If $X$ is countable but not finite, then $X$ is countably infinite.

Proposition. a. If $X$ and $Y$ are countable, so is $X\times Y$.

b. If $A$ is countable and $X_\alpha$ is countable for every $\alpha\in A$, then $\cup_{\alpha\in A}X_\alpha$ is countable.

c. If $X$ is countably infinite, then $card(X)=card(\mathbb N)$.

Proof. a. If suffices to prove that $\mathbb N^2$ is countable. Define a bijection from $\mathbb N$ to $\mathbb N^2$ by listing, for $n$ successively equal to 2, 3, 4, …, those elements $(j, k)\in\mathbb N^2$ such that $j+k=n$ in order of increasing $j$, thus:

(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1), …

b. For each $\alpha\in A$ $\exists$ a surjective $f_\alpha: \mathbb N\to X_\alpha$, and then the map $f: \mathbb N\times A\to\cup_{\alpha\in A}X_\alpha$ defined by $f(n, \alpha)=f_\alpha(n)$ is surjective.

c. $X$ is an infinite subset of $\mathbb N$. Lef $f(1)$ be the smallest element of $X$, and define $f(n)$ inductively to be the smallest element of $X\setminus\{f(1), ..., f(n-1)\}$. Then $f$ is a bijection from $\mathbb N$ to $X$. $\Box$

Corollary. $\mathbb Z$ and $\mathbb Q$ are countable.

Proof. $\mathbb Z$ is the union of the countable sets $\mathbb N$, $\{-n: n\in\mathbb N\}$, and $\{0\}$, and one can define a surjection $f: \mathbb Z^2\to\mathbb Q$ by $f(m, n)=m/n$ if $n\not=0$ and $f(m, 0)=0$. $\Box$

Definition. A set $X$ is said to have the cardinality of the continuum if $card(X)=card(\mathbb R)$. We use letter $latex\mathfrak c$ as an abbreviation for $card(\mathbb R)$:

$card(X)=\mathfrak c$ iff $card(X)=card(\mathbb R)$

Proposition. $card(\mathcal P(\mathbb N))=\mathfrak c$.

Proof. If $A\subset \mathbb N$, define $f(A)\in\mathbb R$ to be $\sum_{n\in A}2^{-n}$ if $\mathbb N\setminus A$ is infinite and $1+\sum_{n\in A}2^{-n}$ if $\mathbb N\setminus A$ is finite. Then $f: \mathcal P(\mathbb N)\to\mathbb R$ is injective. On the other hand, define $g: \mathcal P(\mathbb Z)\to\mathbb R$ by $g(A)=log(\sum_{n\in A}2^{-n})$ if $A$ is bounded below and $g(A)=0$ otherwise. Then $g$ is surjective since every positive real number has a base-2 decimal expansion. Since $card(P(\mathbb Z))=card(\mathcal P(\mathbb N))$, the result follows from the Schroder-Bernstein Theorem. $\Box$

Corollary. If $card(X)\ge\mathfrak c$, then $X$ is uncountable.

Proposition. a. If $card(X)\le\mathfrak c$ and $card(Y)\le\mathfrak c$, then $card(X\times Y)\le\mathfrak c$.

b. If $card(A)\le\mathfrak c$ and $card(X_\alpha)\le\mathfrak c$ for all $\alpha\in A$, then $card(\cup_{\alpha\in A}X_\alpha)\le\mathfrak c$.

Proof. It suffices to take $X=latex Y=\mathcal P(\mathbb N)$. Define $\phi, \psi: \mathbb N\to\mathbb N$ by $\phi(n)=2n$ and $\psi(n)=2n-1$. Then $f: \mathcal P(\mathbb N)^2\to\mathcal P(\mathbb N)$ defined by $f(A, B)=\psi(A)\cup\phi(B)$ is bijective.  $\Box$

” Gratitude makes sense of our past, brings peace for today, and creates a vision for tomorrow.” ~ Melody Beattie

To be continued tomorrow 🙂

References

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 8-9.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.