We used the cardinality definitions to define countability; we gave several examples of countable and uncountable sets.

Countability

Definition: Countable

Equivalently, [math]X [/math] is countable of .

Equivalently, [math]X [/math] is countable if there exists a surjection .

This last definition gives an intuitive definition of countability: if we have a surjection , 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.

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:

Claim (see proof):

Proof:

Let be given by .

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 is surjective, choose an arbitrary . Let . Since we have so . Moreover, 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:

Claim (see proof):

Let be the set of even natural numbers. Then .

Proof: cardinality of evens

Let be given by . is clearly a well-defined function, because every element of the domain is of the form for exactly one . 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:

Claim (see proof):

Proof: cardinality of the integers

The following image clearly defines a bijection:

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:

Claim (see proof):

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 .

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 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 , and then find a contradiction by constructing a diabolical object 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

Claim (see proof):

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 [math]f [/math] as a table. For example, the first few outputs of [math]f [/math] might look like this:

i	f(i)
0
1
2	the set of even numbers
3	the set of odd numbers
4
[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 :

i	f(i)						[math]\cdots [/math]
0		(yes)	yes	yes	yes	yes	[math]\cdots [/math]
1		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		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 , 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 [math]S_D [/math] (by placing ). Continuing in this fashion, we have

						[math]\cdots [/math]
[math]S_D [/math]	no	yes	no	no	yes	[math]\cdots [/math]

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 [math]S_D [/math], this construction will work for an arbitrary [math]f [/math].

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

Claim (see proof):

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 [math]I [/math] is countable. Then there exists a surjection .

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, 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.

SP18:Lecture 9 Countability

Contents

Countability

Countable sets

ℕ ∪ {-1}

Even naturals

Integers

ℕ ⨯ ℕ

Examples of uncountable sets

Diagonalization

The set of subsets of the natural numbers

The set of real numbers