Week Fourteen Lecture Notes

Countable and uncountable

A set $S$ is countably infinite if there is a bijection between $S$ and the natural numbers. We can show this in two ways:

Directly construct a bijection.
Construct one-to-one functions in both directions and invoke the Cantor-Schroeder-Bernstein theorem.

A set is countable if it's either finite or countably infinite.

Intuitively:

countable set: each individual object in the set has a finite representation
uncountable set: many individual objects in the set have only infinite representations

Example

finite decimal: 3.225
repeating decimal: $7.5\overline{358}$
repeating decimal in programming-style notation: 7.5{358}

Irrational numbers have a decimal representations that goes on forever, without a repeating pattern.

Other examples of countable sets include

the integers
any subset of the integers
pairs of integers and thus the rational numbers
any finite product of countable sets (e.g. k-tuples of natural numbers)
any countable union of countable sets (to name an element, provide its set's index and then its index inside the set)

See details and proofs in textbook. We'll just do one example.

$M^*$ is countable (construct bijection)

Suppose that M is the set of all 26 uppercase letters. Recall that $M^*$ is the set of all finite-length strings made from characters in M, including the empty string ($\epsilon$).

Claim: $M^*$ is countably infinite (and thus countable).

We can put all strings from $M^*$ into an order, indexed by the integers:

First order the strings by length.
Within each length, put the strings in dictionary order.

With a bit of work, you could figure out where each length group starts and exactly how to compute the position of any input string.

strings in order — Finite-length strings of uppercase letters can be put in a list ordered by length.

So this gives us a bijection between $M^*$ and $\mathbb{N}$.

M* is countable (two one-to-one functions)

We could also construct one-to-one functions in both directions.

Part 1: make a one-to-one function f from $\mathbb{N}$ to $M^*$.

One choice is to let f map each natural number n into a string of n A's. For example $f(0) = \epsilon$, $f(2) = \texttt{AA}$, and $f(8) = \texttt{AAAAAAAA}$.

This function is very far from being a bijection, but it's definitely one-to-one.

Part 2: make a one-to-one function g from $M^*$ to $\mathbb{N}$.

To construct g, we're going to map each letter into a 2-digit code.

A	B	C	...	I	...	U	...	Z
65	66	67	...	73	...	85	...	90

If s is a string of letters, we'll make g(s) by concatenating the letter codes. E.g. g("UIUC")=85738567. Because the codes are all exactly two digits, we can easily decode one of these output numbers to get the input string that generated it. So g is one-to-one.

We need a special value for $g(\epsilon)$. One possible choice is $g(\epsilon) = 0$.

Summarizing

$f:\mathbb{N}$ to $M^*$ is one-to-one, so $|\mathbb{N}| \le |M^*|$.
$g:M^*$ to $\mathbb{N}$ is one-to-one, so $|M^*| \le |\mathbb{N}|$.

So by the Cantor-Schroeder-Bernstein Theorem, $|M^*| = |\mathbb{N}|$. So $M^*$ is countably infinite.

Diagonalization

Now let's prove that there are uncountable sets.

Claim: the set of all infinite binary sequences (aka infinite bit vectors) is uncountable.

We'll use a trick called "diagonalization" due to Georg Cantor.

Proof: suppose not. That is suppose that the set of infinite binary sequences is countable. That means that we can put all infinite binary sequences into a list indexed by the natural numbers: $S_0, S_1, S_2, \ldots$.

	$b_0$	$b_1$	$b_2$	$b_3$	$b_4$	$b_5$	$b_6$	$b_7$	$b_8$	$b_9$	$\ldots$
$S_0$	1	1	0	1	1	0	1	1	1	1	$\ldots$
$S_1$	1	1	0	0	1	0	1	1	0	0	$\ldots$
$S_2$	0	0	0	0	1	0	0	1	0	0	$\ldots$
$S_3$	0	1	1	1	1	0	1	0	0	0	$\ldots$
$S_4$	0	0	0	0	1	1	1	0	1	1	$\ldots$
$S_5$	1	1	1	0	1	0	1	0	0	1	$\ldots$
$\ldots$	$\ldots$

Now, let's make a new infinite bit vector X from the values on the diagonal of this chart. That is $X(k) = S_k(k)$.

	$b_0$	$b_1$	$b_2$	$b_3$	$b_4$	$b_5$	$b_6$	$b_7$	$b_8$	$b_9$	$\ldots$
$S_0$	1	1	0	1	1	0	1	1	1	1	$\ldots$
$S_1$	1	1	0	0	1	0	1	1	0	0	$\ldots$
$S_2$	0	0	0	0	1	0	0	1	0	0	$\ldots$
$S_3$	0	1	1	1	1	0	1	0	0	0	$\ldots$
$S_4$	0	0	0	0	1	1	1	0	1	1	$\ldots$
$S_5$	1	1	1	0	1	0	1	0	0	1	$\ldots$
$\ldots$	$\ldots$

Now let's define a vector Y that has exactly the opposite bit values as X. That is $Y_k = 1$ if and only if $X_k$ = 0.

Suppose we pick any vector $S_k$ on the list. Then Y and $S_k$ have different values at position k. That means that Y can't be any of the vectors in our list $S_0, S_1, S_2, \ldots$.

So we have a contradiction, because our list was supposed to have contained all the binary sequences. Therefore, we must have been wrong in our assumption the set was countable.

More uncountable sets

Ways to interpret a bit vector

A function from $\mathbb{N}$ to $\{0,1\}$.
A subset of the natural numbers.

Bit vector representation of a set containing 0, 1, 5, 6, and 9, but not 2, 3, 4, 7, 8, 10, 11.

number	0	1	2	3	4	5	6	7	8	9	10	11	...
in set?	1	1	0	0	0	1	1	0	0	1	0	0	...

$\mathbb{P}(\mathbb{N})$ is uncountable.
If $A$ is infinite and $B$ contains at least two elements, then the set of all functions between sets $A$ and $B$ is uncountable.

We can modify diagonalization to show that the real interval $[0,1]$ is uncountable. Short story: write the fractional parts as decimals. To make the vector Y, change diagonal digits to 5, except change 5 to 4.

$\mathbb{R}$ is uncountable.
Sets constructed using significant subsets of the reals are uncoutable.
The set of complex numbers is uncountable.
The set of graphs with real number labels on the nodes.

Beware: these sets are countable

$\{\pi, e, \sqrt{2}\}$
$\{\pi, 2\pi, 3\pi, 4\pi, \ldots\}$

Diagonalization can be done using any set to index the list. So

$\mathbb{P}(A)$ is larger than A, for any set A (finite or infinite).
$\mathbb{P}(\mathbb{P}(A))$ is larger than $\mathbb{P}(A)$.
and so forth

Recap comparison

$\mathbb{P}(\mathbb{N})$ is uncountable. However, suppose we define a set A to be the set of all finite subsets of $\mathbb{N})$. Then A is countable for the same reason that $M^*$ (finite length strings) is countable.