Finite, countable, and uncountable sets

If there exists a 1-1 mapping of $A$ onto $B$, we say that $A$ and $B$ can be put in 1-1 correspondence, or that $A$ and $B$ have the same cardinal number, or that $A$ and $B$ are equivalent, and denote it by $A\sim B$.

For any positive integer $n$, let ${\mathbb{N}}_n$ be the set whose elements are the integers $1,2,\dots ,n$; Let $\mathbb{N}$ be the set consisting of all positive integers. For any $A$, we say:

• $A$ is finite if $A\sim {\mathbb{N}}_n$ for some $n$.
• $A$ is infinite if $A$ is not finite.
• $A$ is countable if $A\sim \mathbb{N}$.
• $A$ is uncountable if $A$ is neither finite nor countable.
• $A$ is at most countable if $A$ is finite or countable.

Info

A finite set cannot be equivalent to one of its subsets. This is, however, possible for infinite sets.

---

Countable sets

Stripping down a countable set

Theorem 1(Theorem).

If $A\subseteq B$ and $B$ is countable, then $A$ is either countable or finite.

If a set can be arranged into a single list, then deleting some elements from this list results in another (shorter, and potentially terminating) list. This means that countable sets are the smallest type of infinite set. Anything smaller is either still countable or finite.

Combining countable sets

Theorem 2(Theorem).

Let $\{E_n\},n=1,2,3,\dots$, be a countable collection of sets. Then

$$S=\bigcup _{n=1}^{\infty }{E}_n$$

is countable.
A lil note

Theorem 3(Theorem).

Let $A$ be a countable set, and let $B_n$ be the set of all $n$-tuples $(a_1,a_2,\dots a_n)$ where $a_k\in A,1\le k\le n$, and the elements $a_1,\dots ,a_n$ need not be distinct. Then, $B_n$ is countable.

Theorem 4(Colollary).

The set $\mathbb{Q}$ is countable.

---

Uncountable sets

Theorem 5(Theorem).

Let $A$ be the set of all sequences whose elements are the digits 0 and 1. This set $A$ is uncountable.

Proof
Let $E$ be a countable subset of $A$, and let $E$ consist of the sequences $s_1,s_2,s_3,\dots$ . Construct a sequence $s$ as follows: If the $n$th digit in $s_n$ is 1, we let the $n$th digit ok $s$ be 0, and vice versa. Then, the sequence differs from every member of $E$ in at least one place, hence $s\notin E$. But clearly $s\in A$, so $E$ is a proper subset of $A$.
We have shown that every countable subset of $A$ is a proper subset of $A$. It follows that $A$ is uncountable. ❏

Why does't this work for $\mathbb{Q}$?

The number we construct from the diagonalization procedure has an infinite number of decimals, i.e, it is irrational.

This theorem also implies that the set of all real numbers is uncountable, since all real numbers have a binary representation. However, do also note the proof that follows.

Theorem 6(Theorem).

The set $\mathbb{R}$ is uncountable.

Proof
Assume there does exist a 1-1 correspondence $f:\mathbb{N}\to \mathbb{R}$. This means that we should be able to write $\mathbb{R}=\{x_1,x_2,\dots \}$.
Now, consider a closed interval $I_1$ that does not contain $x_1$. Next, let $I_2$ be a closed interval, contained in $I_1$, which does not contain $x_2$. In general, given an interval $I_n$, construct an interval $I_{n+1}$ to satisfy

• $I_{n+1}\subseteq I_n$ and
• $x_{n+1}\notin I_{n+1}$

Now consider the intersection ${\bigcap }_{n=1}^{\infty }{I}_n$. For every real number $x_k$, $x_k\notin I_k$, and it follows that

$$x_k\notin \bigcap _{n=1}^{\infty }{I}_n$$

Now, we assumed every real number eventually appears in the list $x_1,x_2,\dots$, which leads to the conclusion that ${\bigcup }_{n=1}^{\infty }{I}_n=\varnothing$. However, the nested interval property asserts that ${\bigcup }_{n=1}^{\infty }{I}_n\ne \varnothing$. This contradiction means that such an enumeration of $\mathbb{R}$ is impossible. ❏

Why doesn't this work for $\mathbb{Q}$?

The nested interval property does not hold for $\mathbb{Q}$. Consider $I_n$ to be rational bounds for $\sqrt{2}$, for example (like what Rudin does in 1.1). Then, ${\bigcap }_{n=1}^{\infty }{I}_n=\varnothing$ since $\sqrt{2}\notin \mathbb{Q}$.

This combined with our proof that the union of two countable sets is countable, and that $\mathbb{Q}$ is countable, implies that $\mathbb{I}$, the set of all irrational numbers, is not countable since $\mathbb{R}=\mathbb{Q}\cup \mathbb{I}$.

Theorem 7(Theorem).

In $\mathbb{R}$, there cannot exist an uncountable collection of disjoint open intervals.

Proof
Let $A$ be a collection of disjoint open intervals. The key is to try to show $A\sim \mathbb{Q}$ instead of $A\sim \mathbb{N}$. From the density of the rationals, we know that we can associate a unique rational number with each interval in $A$. So, the cardinality of $A$ must be less than or equal to $\mathbb{Q}$, which implies $A$ cannot be uncountable. ❏