**Definition.** A set is called countable (or denumerable) if . In particular, all finite sets are countable. If is countable but not finite, then is countably infinite.

**Proposition.** a. If and are countable, so is .

b. If is countable and is countable for every , then is countable.

c. If is countably infinite, then .

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

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

b. For each $\exists$ a surjective , and then the map defined by is surjective.

c. is an infinite subset of $\mathbb N$. Lef be the smallest element of , and define inductively to be the smallest element of . Then is a bijection from to .

**Corollary. ** and are countable.

Proof. is the union of the countable sets , , and , and one can define a surjection by if and .

**Definition.** A set is said to have the cardinality of the continuum if . We use letter $latex\mathfrak c$ as an abbreviation for :

iff

**Proposition.** .

Proof. If , define to be if is infinite and if is finite. Then is injective. On the other hand, define by if is bounded below and otherwise. Then is surjective since every positive real number has a base-2 decimal expansion. Since , the result follows from the Schroder-Bernstein Theorem.

**Corollary.** If , then is uncountable.

**Proposition. **a. If and , then .

b. If and for all , then .

Proof. It suffices to take . Define by and . Then defined by 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.