Uncountability: Intro (Math 1)
Collections of things which are the same size as or smaller than the collection of all natural numbers are called countable, while larger collections (like the set of all real numbers) are called uncountable.
All uncountable collections (and some countable collections) are infinite. There is a meaningful and well-defined way to compare the sizes of different infinite collections of things noteSpecifically, mathematical systems which use the Axiom of Choice, see the technical page for details.. To demonstrate this, we’ll use a 2d grid.
Real and Rational numbers
Real numbers are numbers with a decimal expansion, for example 1, 2, 3.5, \(\pi\) = 3.14159265… Every real number has an infinite decimal expansion, for example 1 = 1.0000000000…, 2 = 2.0000000000…, 3.5 = 3.5000000000… Recall that the rational numbers are fractions of integers, for example \(1 = \frac11\), \(\frac32\), \(\frac{100}{101}\), \(\frac{22}{7}\). The positive integers are the integers greater than zero (i.e. 1, 2, 3, 4, ..).
There is a theorem in math that states that the rational numbers are countable noteYou can see the theorem here., that is, that the set of rational numbers is the same size as the set of positive integers, and another theorem which states that the real numbers are uncountable, that is, that the set of real numbers is strictly bigger. By “same size” and “strictly bigger”, we mean that it is possible to match every rational number with some positive integer in a way so that there are no rational numbers, nor positive integers, left unmatched, but that any matching you make between real numbers and positive integers leaves some real numbers not matched with anything.
Rational grid
If you imagine laying the rational numbers out on a two-dimensional grid, so that the number \(p / q\) falls at \((p, q)\), then we may match the positive integers with the rational numbers by walking in a spiral pattern out from zero, skipping over numbers that we have already counted (or that are undefined, such as zero divided by any number). The beginning of this sequence is \(\frac01\), \(\frac11\), \(\frac12\), \(\frac{-1}{2}\), \(\frac{-1}{1}\), … Graphically, this is:
This shows that the rational numbers are countable.
Reals are uncountable
The real numbers, however, cannot be matched with the positive integers. I show this by contradiction. noteThat is to say, I show that if there is such a matching, then we can conclude nonsensical statements (and if making a new assumption allows us to conclude nonsense, then the assumption itself must be nonsense.
Suppose we have such a matching. We can construct a new real number that differs in its \(n^\text{th}\) decimal digit from the real number matched with \(n\).
For example, if we were given a matching that matched 1 with 1.8, 2 with 1.26, 3 with 5.758, 4 with 1, and 5 with \(\pi\), then our new number could be 0.11111, which differs from 1.8 in the first decimal place (the 0.1 place), 1.26 in the second decimal place (the 0.01 place), and so on. It is clear that this number cannot be matched with any number under the matching we are given, because, if it were matched with \(n\), then it would differ from itself in the \(n^\text{th}\) decimal digit, which is nonsense. Thus, there is no matching between the real numbers and the positive integers.
See also
If you enjoyed this explanation, consider exploring some of Arbital’s other featured content!
Arbital is made by people like you, if you think you can explain a mathematical concept then consider contributing to arbital!
Parents:
- Uncountability
Some infinities are bigger than others. Uncountable infinities are larger than countable infinities.
Cantor’s argument also works in the finite case and this may serve to demonstrate the idea.
Consider 4-digit binary numbers like 1001. We can use Cantor’s argument to show that there are more than four such binary numbers. Imagine you had a list of four such numbers, say 1001, 1010, 1110 and 0011. Then I can construct a number that can’t possibly be in your list since it differs from the first number in the first digit, from the second in the second etc. In this case the number is 0100.
This is a cool page, but I think it (esp. the last paragraph) goes too fast for many math 1 readers, even if it mostly uses things that math 1 people would be able to use. Maybe recategorizing it as math 2 would be best, or expanding things out and being a bit more handholdy, or putting tricky bits as optional hidden text?