FA18:Lecture 9 countability

From CS2800 wiki

We will continue our discussion of cardinality, defining countable and uncountable sets. We will see proofs by diagonalization.

At the tail end of lecture, we started a new topic, introducing some motivating examples of relations. These notes will be folded into the next lecture's notes.


Countability

Definition: Countable
A set [math]X [/math] is countable if [math]|X| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}| [/math].

Equivalently, [math]X [/math] is countable of [math]|\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |X| [/math].

Equivalently, [math]X [/math] is countable if there exists a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} X [/math].

This last definition gives an intuitive definition of countability: if we have a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} X [/math], then we can talk about could write [math]x_0 := f(0) [/math], [math]x_1 := f(1) [/math], etc., so that we can write [math]X [/math] in the form [math]X = \{x_0,x_1,x_2,\dots\} [/math].

The fact that [math]f [/math] is surjective means that every element of [math]X [/math] is [math]x_i [/math] for some [math]i [/math].

So the informal definition of countability is that [math]X [/math] is countable if its elements can be put in a (potentially infinite) sequence.


Examples of uncountable sets

Last lecture, we showed that [math]\href{/cs2800/wiki/index.php/Example:Cardinality_of_%E2%84%95_%E2%88%AA_-1}{ℕ ∪ \{-1\}} [/math], [math]\href{/cs2800/wiki/index.php/Example:Cardinality_of_the_integers}{ℤ} [/math], and [math]\href{/cs2800/wiki/index.php/Example:Cardinality_of_%E2%84%95_%E2%A8%AF_%E2%84%95}{ℕ ⨯ ℕ} [/math] were all countable. At this point, you might suspect that all sets are countable. However, this is not the case.

Diagonalization

A common technique to prove that a set is uncountable is called diagonalization.

The most famous examples of diagonalization are the proofs that the power set of the naturals is uncountable and the set of reals is uncountable.

To use diagonalization to prove that a set [math]X [/math] is uncountable, you typically do a proof by contradiction: assume that [math]X [/math] 'is' countable, so that there is a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%5Cto}{\to} X [/math], and then find a contradiction by constructing a diabolical object [math]x_D \href{/cs2800/wiki/index.php/%E2%88%88}{∈} X [/math] that is not in the image of [math]f [/math]. This contradicts the surjectivity of [math]f [/math], completing the proof.

To construct [math]x_D [/math], you typically imagine an (infinite) table describing [math]f [/math]: the [math]i [/math] row describes [math]f(i) [/math]. In the table, you represent each element of [math]X [/math] as an infinite sequence of values; so that the table has a column for each natural number. The exact structure of the table depends on the set [math]X [/math].

You then find [math]x_D [/math] by changing every value on the diagonal: you ensure that [math]x_D [/math] differs from [math]f(i) [/math] in the [math]i [/math]th column. Since for all [math]k [/math], [math]x_D ≠ f(k) [/math], [math]x_D [/math] cannot be in the image of [math]f [/math], so [math]f [/math] cannot be surjective.

The set of subsets of the natural numbers

[math]\href{/cs2800/wiki/index.php/2}{2}^{\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}} [/math] is uncountable.
Proof:
We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that [math]\href{/cs2800/wiki/index.php/2}{2}^\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] is countable. Then there exists a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/2}{2}^{\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}} [/math].


We can imagine drawing [math]f [/math] as a table. For example, the first few outputs of [math]f [/math] might look like this:


i f(i)
0 [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]
1 [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math]
2 the set of even numbers
3 the set of odd numbers
4 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math]
[math]\vdots [/math] [math]\vdots [/math]


To put the sets [math]f(i) [/math] into a common format, we might expand each set as a sequence of yes/no questions, with the [math]j [/math]th column of [math]f(i) [/math] indicating whether [math]j \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i) [/math]:

i f(i) [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]\cdots [/math]
0 [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] (yes) yes yes yes yes [math]\cdots [/math]
1 [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] no (no) no no no [math]\cdots [/math]
2 the set of even numbers yes no (yes) no yes [math]\cdots [/math]
3 the set of odd numbers no yes no (yes) no [math]\cdots [/math]
4 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math] yes no no no (no) [math]\cdots [/math]
[math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\ddots [/math]


Now, we construct a new diabolical set [math]S_D [/math] by changing each element on the diagonal. In this example, we have a "yes" in the 0th column of row 0 (meaning [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(0) [/math], so in our diabolical set we put a "no" in column 0 (by ensuring [math]0 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} S_D [/math]. Similarly, we have a "no" in row 1, column 1 (so [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(1) [/math]), so we put a "yes" in column 1 of [math]S_D [/math] (by placing [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} S_D [/math]). Continuing in this fashion, we have

[math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]\cdots [/math]
[math]S_D [/math] no yes no no yes [math]\cdots [/math]


In general, we include [math]i \href{/cs2800/wiki/index.php/%E2%88%88}{∈} S_D [/math] if and only if [math]i \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(i) [/math]. We can write this succinctly by defining [math]S_D \href{/cs2800/wiki/index.php/Definition}{:=} \{i \href{/cs2800/wiki/index.php/%5Cmid}{\mid} i \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(i)\} [/math]. Note that although we used a specific example to figure out how to construct [math]S_D [/math], this construction will work for an arbitrary [math]f [/math].


Now, [math]S_D [/math] cannot be in the image of [math]f [/math], because for any [math]k [/math], [math]S_D [/math] differs from [math]f(k) [/math] in the [math]k [/math]th column. If [math]k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(k) [/math] then [math]k \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} S_D [/math], and if [math]k \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(k) [/math] then [math]k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} S_D [/math]. in either case, [math]S_D \href{/cs2800/wiki/index.php/Equality_(sets)}{≠} f(k) [/math]. Thus [math]f [/math] cannot be surjective, a contradiction.

The set of real numbers

Proof:
In fact, we will show that the interval [math]I = [0,1) [/math] of real numbers between 0 and 1 is uncountable. Since [math]I \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math], we can conclude that [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] is uncountable.


We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that [math]I [/math] is countable. Then there exists a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} I [/math].

We can imagine drawing [math]f [/math] as a table. For example, the first few outputs of [math]f [/math] might look like this:


i f(i)
0 [math]1/2 [/math]
1 [math]0 [/math]
2 [math]π-3 [/math]
3 [math]0.8989898989\cdots [/math]
4 [math]1/2 [/math]
[math]\vdots [/math] [math]\vdots [/math]


We can put the real numbers [math]f(i) [/math] into a common format by listing out their digits:

i f(i) tenths hundredths thousandths [math]\cdots [/math] [math]\cdots [/math] [math]\cdots [/math]
0 1/2 (5) 0 0 0 0 [math]\cdots [/math]
1 0 0 (0) 0 0 0 [math]\cdots [/math]
2 [math]π-3 [/math] 1 4 (1) 5 9 [math]\cdots [/math]
3 [math]0.8989\cdots [/math] 8 9 8 (9) 8 [math]\cdots [/math]
4 1/2 5 0 0 0 (0) [math]\cdots [/math]
[math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\vdots [/math] [math]\ddots [/math]


We construct a new diabolical number [math]x_D [/math] by changing each digit on the diagonal. We can add 5 to each digit (wrapping around if necessary) to set the corresponding digit of [math]x_D [/math]. In example table above, we would have [math]x_D = 0.05645\cdots [/math].

Now, [math]x_D [/math] cannot be in the image of [math]f [/math], because for any [math]k [/math], [math]x_D [/math] differs from [math]f(k) [/math] in the [math]k [/math]th digit. This contradicts the fact that [math]f [/math] is surjective, completing the proof.

Relations

At the tail end of lecture, we started a new topic, introducing some motivating examples of relations. These notes will be folded into the next lecture's notes.