Discrete Math · Undergraduate
Countable and Uncountable Sets: Sizes of Infinity
Quick answer
Two sets have the same size, or cardinality, when a bijection pairs their elements exactly. A set is countable if it is finite or can be listed as a first, second, third element and so on, matching the natural numbers. The even numbers, the integers and even the rational numbers are countable. The real numbers are not: Cantor's diagonal argument builds a number missing from any proposed list. So some infinite sets are strictly larger than others.
What you'll learn
- Define equal cardinality with bijections
- Show that the integers and the rationals are countable
- Prove the real numbers are uncountable with the diagonal argument
- Use countability to compare infinite sets
Counting by pairing
Two finite sets have the same size when their elements can be paired off with none left over. For infinite sets, take that as the definition: and have the same cardinality when there is a bijection between them.
A set is countable if it is finite or has the same cardinality as . Equivalently, its elements can be listed as a sequence that reaches each one after finitely many steps.
Infinite sets behave strangely under this rule. The map pairs the natural numbers with the even numbers, so the evens, a part of , are as numerous as all of .
Why the rationals can be listed
Write the positive fractions in a grid, across and down. Listing one row at a time would never finish the first row. Instead, walk the diagonals, where is constant: ; then ; then ; and so on, skipping values seen before, such as . Each diagonal is finite, so every fraction is reached after finitely many steps. The rationals are countable.
Worked examples
Common mistakes
Practice problems
-
Give a bijection from to the odd natural numbers.
Answer
Full solution
It is one-to-one, and every odd number comes from .
-
Is the set of all finite strings of s and s countable?
Answer
Yes
Full solution
List them by length: there are finitely many of each length, of length .
-
Is the set of all infinite sequences of s and s countable?
Answer
No
Full solution
Given any list, flip the -th entry of the -th sequence. The new sequence is not on the list.
-
Explain why the union of two countable sets is countable.
Answer
Interleave the two lists: , skipping repeats.
Full solution
Each element appears at a finite position in the merged list.
-
Are the irrational numbers countable?
Answer
No
Full solution
is the union of the rationals and the irrationals. If both were countable, so would be .
-
Using the formula in Example 3, find the position of .
Answer
Full solution
.
-
Show that and have the same cardinality.
Answer
is a bijection.
Full solution
It is one-to-one, and each comes from .
-
A student says the rationals must be uncountable because between any two there is another. What is wrong?
Answer
Density is about order, not size; the diagonal listing reaches every rational.
Full solution
The listing ignores the order on the number line. It only needs each fraction to appear at some finite position.
Frequently asked questions
What does it mean for a set to be countable?
It is finite, or there is a bijection between it and the natural numbers, so its elements can be listed in a sequence that eventually reaches each one.
Are there as many even numbers as natural numbers?
Yes. The map n ↦ 2n pairs them exactly, even though the evens are a proper subset.
Why are the rational numbers countable?
Arrange the fractions p/q in a grid and walk through it along diagonals, skipping repeats. Every fraction is reached after finitely many steps.
What is Cantor's diagonal argument?
Given any list of real numbers in (0, 1), build a number whose n-th digit differs from the n-th digit of the n-th number. It differs from every number on the list, so no list contains all reals.
Are some infinities bigger than others?
Yes. The reals are uncountable, so there is no bijection with the naturals. Cantor also showed every set is smaller than the set of its subsets.