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.