Topic 5 of 8
Step 21: Proofs and discrete maths
Cardinality and countability
Step 21 · Proofs and discrete maths topics
Compare the sizes of sets by pairing their elements, see why the integers and fractions are countable, and follow Cantor's proof that the real numbers are not.
Same size by matching
Two sets have the same size, or cardinality, when there is a bijection between them: a pairing that matches every element of one with exactly one element of the other. For finite sets this is counting; for infinite sets it is the only fair test.
Example: Evens and naturals
Show that the even numbers 2, 4, 6, … and the naturals 1, 2, 3, … have the same size.
- Pair n with 2n.
- Every natural has one partner, and every even number is reached exactly once.
AnswerThe same size, though the evens are only part of the naturals
Example: Two intervals
Show that the intervals (0, 1) and (0, 2) have the same size.
- f(x) = 2x is a bijection from (0, 1) onto (0, 2).
AnswerThe same size
Countable sets
A set is countable if its elements can be listed, first, second, third and so on, with every element turning up somewhere. That means a finite set, or one in bijection with the naturals.
Example: The integers
List the integers.
- 0, 1, −1, 2, −2, 3, −3, …
- Every integer turns up at a definite place.
AnswerThey are countable
Example: The fractions
Why are the positive fractions countable?
- Arrange a/b in a grid, with row a and column b.
- Walk the diagonals: 1/1, then 1/2 and 2/1, then 1/3, 2/2 and 3/1, and so on, skipping repeats.
AnswerEvery fraction turns up, so they can be listed
| a / b | b = 1 | b = 2 | b = 3 | b = 4 |
|---|---|---|---|---|
| a = 1 | 1/1 | 1/2 | 1/3 | 1/4 |
| a = 2 | 2/1 | 2/2 | 2/3 | 2/4 |
| a = 3 | 3/1 | 3/2 | 3/3 | 3/4 |
| a = 4 | 4/1 | 4/2 | 4/3 | 4/4 |
Uncountable sets
Cantor showed that the real numbers cannot be listed. Given any list of numbers between 0 and 1, build a new number whose nth digit differs from the nth digit of the nth number. It differs from every number on the list, so the list missed it.
Example: The diagonal
A list begins 0.5131…, 0.2718…, 0.3333…, 0.1415… Build a number not on it: make each digit 4 unless the diagonal digit is 4, then use 5.
- The diagonal digits are 5, 7, 3 and 5.
- None is 4, so the new number begins 0.4444…
Answer0.4444… differs from the nth number in its nth digit
Example: Comparing sizes
Which is bigger: the rationals or the reals?
- The rationals are countable, and the reals are not.
AnswerThe reals
Try it yourself
Work each one on paper first, then open the answer to check.
Give a bijection from the naturals to the odd numbers 1, 3, 5, …
Show answer
n ↦ 2n − 1
Are the integers countable?
Show answer
Yes
Are the rational numbers countable?
Show answer
Yes
Is the interval (0, 1) countable?
Show answer
No
In a diagonal argument, the 3rd number on the list is 0.1729… Which digit must the new number avoid in 3rd place?
Show answer
2
Do the naturals and the squares 1, 4, 9, … have the same size?
Show answer
Yes: pair n with n²