# FA18:Lecture 9 countability

($1)$2 | $3 ($4) | $5 ($6)

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 is countable if .

Equivalently, is countable of .

This last definition gives an intuitive definition of countability: if we have a surjection , then we can talk about could write , , etc., so that we can write in the form .

The fact that is surjective means that every element of is for some .

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

# Examples of uncountable sets

Last lecture, we showed that , , and 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 is uncountable, you typically do a proof by contradiction: assume that 'is' countable, so that there is a surjection , and then find a contradiction by constructing a diabolical object that is not in the image of . This contradicts the surjectivity of , completing the proof.

To construct , you typically imagine an (infinite) table describing : the row describes . In the table, you represent each element of 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 .

You then find by changing every value on the diagonal: you ensure that differs from in the th column. Since for all , , cannot be in the image of , so cannot be surjective.

## The set of subsets of the natural numbers

is uncountable.
Proof:
We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that is countable. Then there exists a surjection .

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

i f(i)
0
1
2 the set of even numbers
3 the set of odd numbers
4

To put the sets into a common format, we might expand each set as a sequence of yes/no questions, with the th column of indicating whether :

i f(i)
0 (yes) yes yes yes yes
1 no (no) no no no
2 the set of even numbers yes no (yes) no yes
3 the set of odd numbers no yes no (yes) no
4 yes no no no (no)

Now, we construct a new diabolical set by changing each element on the diagonal. In this example, we have a "yes" in the 0th column of row 0 (meaning , so in our diabolical set we put a "no" in column 0 (by ensuring . Similarly, we have a "no" in row 1, column 1 (so ), so we put a "yes" in column 1 of (by placing ). Continuing in this fashion, we have

no yes no no yes

In general, we include if and only if . We can write this succinctly by defining . Note that although we used a specific example to figure out how to construct , this construction will work for an arbitrary .

Now, cannot be in the image of , because for any , differs from in the th column. If then , and if then . in either case, . Thus cannot be surjective, a contradiction.

## The set of real numbers

The set of real numbers is uncountable.
Proof:
In fact, we will show that the interval of real numbers between 0 and 1 is uncountable. Since , we can conclude that is uncountable.

We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that is countable. Then there exists a surjection .

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

i f(i)
0
1
2
3
4

We can put the real numbers into a common format by listing out their digits:

i f(i) tenths hundredths thousandths
0 1/2 (5) 0 0 0 0
1 0 0 (0) 0 0 0
2 1 4 (1) 5 9
3 8 9 8 (9) 8
4 1/2 5 0 0 0 (0)

We construct a new diabolical number by changing each digit on the diagonal. We can add 5 to each digit (wrapping around if necessary) to set the corresponding digit of . In example table above, we would have .

Now, cannot be in the image of , because for any , differs from in the th digit. This contradicts the fact that 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.