Two finite sets have the same size when their elements can be matched up one for one. Nothing in that sentence mentions counting, so it can be asked of infinite sets too — and the answer is not what intuition expects. The whole numbers, the even numbers and the fractions can all be matched up with each other, so in this sense they are the same size. The real numbers cannot be matched with any of them, and that gap is the first genuinely surprising fact in the course.

A hotel with a room for every whole number is full, and one more guest arrives. Move the guest in room one to room two, room two to room three, and so on: everybody still has a room and room one is now free. An infinite set can be matched with a proper part of itself, which no finite set can do, and that is the signal that a different notion of size is at work.

A set is countable when its elements can be written in a list with no gaps and no repeats — which is exactly a bijection from the naturals. The question is never how many there are, but whether such a list can be made at all.

Two sets have the same cardinality when there is a bijection between them. A set is countably infinite when it has the same cardinality as $\mathbb{N}$, countable when it is finite or countably infinite, and uncountable otherwise. Listing the elements of a set as $a_1,a_2,a_3,\dots$ with nothing missed and nothing repeated is the same thing as giving that bijection.

• $\mathbb{Z}$ is countable: list it as $0,1,-1,2,-2,\dots$, which reaches every integer exactly once.
• $\mathbb{Q}$ is countable: arrange the fractions in a grid by numerator and denominator and read it along the diagonals, skipping repeats.
• A countable union of countable sets is countable, and $$ is countable when and are.

The proof answers a challenge. Suppose someone hands you a list claiming to contain every number between zero and one. Build a number that is not on it, by making it differ from the first listed number in the first decimal place, from the second in the second, and so on. It cannot equal the nth entry, because they already disagree at the nth digit, so it is missing from the list — and the list was arbitrary. This takes on trust that each real number has a decimal expansion, which this course does not prove.

Take any attempted list of the numbers between zero and one.

Write each listed number as a decimal expansion, digit by digit.

Build a new number by choosing its nth digit to differ from the nth digit of the nth entry. Using only 5 and 6 avoids the trailing-nines ambiguity.

The new number lies in the interval, and differs from the nth entry at the nth digit, so it is not the nth entry — for every n.

The list misses b. Since the list was arbitrary, no list can contain them all.

Size here is not a count. Two sets have the same size when a bijection matches them, and countable means one of them can be the naturals.

The argument does not examine a particular list. It takes any list and builds a number the list cannot contain.

• Two sets have the same size when a bijection matches them, and an infinite set may match a proper part of itself.
• $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{N}\times\mathbb{N}$ and every subset of a countable set are countable.
• $\mathbb{R}$, every interval and the irrationals are uncountable.
• The diagonal argument defeats an arbitrary list rather than a badly chosen one.

Great work! You now know how to:

• Say what it means for two sets to have the same cardinality
• Show that $\mathbb{Z}$ and $\mathbb{Q}$ are countable by producing a list
• Run the diagonal argument and say why it defeats every list at once
• Keep density and cardinality apart