SP20:Lecture 9 Diagonalization

From CS2800 wiki

We gave several examples of proofs that set were Countable, and started an example showing that The power set of the naturals is uncountable.


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 countable sets

ℕ ∪ {-1}

You might imagine the adding an element to a set makes it bigger. While this is true for finite sets, it is not true in general:

[math]│\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \{-1\}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Proof:
Let [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\href{/cs2800/wiki/index.php/%E2%88%AA}{∪}\{-1\} [/math] be given by [math]f(n) := n-1 [/math].


I claim that [math]f [/math] is a bijection.

To see that [math]f [/math] is injective, choose arbitrary [math]x_1, x_2 [/math] in and assume [math]f(x_1) = f(x_2) [/math]. Then [math]x_1-1 = x_2-1 [/math] so [math]x_1 = x_2 [/math] as required.

To see that [math]f [/math] is surjective, choose an arbitrary [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Let [math]x = y+1 [/math]. Since [math]y \geq -1 [/math] we have [math]x \geq 0 [/math] so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]. Moreover, [math]f(x) = x-1 = y [/math] as required.

Even naturals

You might expect that the set of even natural numbers is smaller than the set of all natural numbers. But in fact, funny things happen with infinite sets:

Let [math]X := \href{/cs2800/wiki/index.php/Set_comprehension}{\{2n} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\} [/math] be the set of even natural numbers. Then [math]│X│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │ℕ│ [/math].
Proof: cardinality of evens
Let [math]f : X \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] be given by [math]f(2n) := n [/math]. [math]f [/math] is clearly a well-defined function, because every element of the domain is of the form [math]2n [/math] for exactly one [math]n [/math]. It is also clearly a bijection (details left as an exercise). Thus the evens and the naturals have the same cardinality.

Integers

You might think that adding an infinite number of numbers to the set of natural numbers might make it bigger. But in fact, this is not (necessarily) so. The integers have the same cardinality as the natural numbers:


[math]│\href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Proof: cardinality of the integers
The following image clearly defines a bijection:

Z-is-countable.svg

Details are left as an exercise.

ℕ ⨯ ℕ

You might imagine that the set of pairs of natural numbers is larger than the set of natural numbers, but in fact they can still be matched one-to-one:


[math]│\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Proof: │ℕ ⨯ ℕ│ = │ℕ│
Note: Although this proof creates a bijection by enumerating the elements on the diagonal, this technique is 'not' called diagonalization (which is used to prove that sets are uncountable). This often leads to confusion.


We wish to construct a bijection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math].


We can draw a table containing all pairs of natural numbers:

0 1 2 [math]\cdots [/math]
0 (0,0) (0,1) (0,2) [math]\cdots [/math]
1 (1,0) (1,1) (1,2) [math]\cdots [/math]
2 (2,0) (2,1) (2,2) [math]\cdots [/math]
[math]\vdots [/math] [math]\ddots [/math]


Now, giving a function [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] is the same as giving a method for iterating through this table (identifying the 0th element, the 1th element, etc.). [math]f [/math] will be a bijection if we enumerate each pair exactly once.

To do so, we will start in the upper left hand corner, and then enumerate each pair along each diagonal, starting in the lower left, and ending in the upper right. For example, the first few pairs would be:

n f(n)
0 (0,0)
1 (1,0)
2 (0,1)
3 (2,0)
4 (1,1)
5 (0,2)
6 (3,0)
7 (2,1)
8 (1,2)
9 (0,3)
10 (4,0)
[math]\cdots [/math] [math]\cdots [/math]


This pattern clearly hits each pair once, and doesn't hit any pair more than once, so it defines a bijection.


Note: I would consider this a complete and correct proof. It clearly defines a function, and explains why it is bijective. Some students have worried about the lack of clarity of the function.

To the address the former concern, we could write down a formula for this function. However, it is 'not' necessary to write down a formula for every function; indeed many functions do not have formulae at all. Rather, we must check that the function definition is unambiguous. A good way to reason about this informally is to ask "how would I go about computing f(73)?" If there is enough description to answer this question (and it will only give one answer!), the function is probably well defined.

If we wanted to provide more specificity on the bijectivity of the function, we could note that the function first lists every pair that sums to 0, then all pairs that sum to 1, and then all pairs that sum to 2, and so on. So a pair (a,b) will be on the (a+b)th diagonal (and will be the bth element of that diagonal).

Examples of uncountable sets

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.