Uncountability: Intro (Math 1)

[summary: 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 [infinity infinite]. There is a meaningful and well-defined way to compare the sizes of different infinite collections of things, and some infinite collections are larger than others.]

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 [infinity infinite]. There is a meaningful and well-defined way to compare the sizes of different infinite collections of things %%note: Specifically, mathematical systems which use the Axiom of Choice, see the technical page for details.%%. To demonstrate this, we'll use a 2d grid.

[toc:]

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 [fraction 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 %%note: You 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. %%note:That 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!