Uncountability: Intro (Math 1)

Col­lec­tions of things which are the same size as or smaller than the col­lec­tion of all nat­u­ral num­bers are called countable, while larger col­lec­tions (like the set of all real num­bers) are called un­countable.

All un­countable col­lec­tions (and some countable col­lec­tions) are in­finite. There is a mean­ingful and well-defined way to com­pare the sizes of differ­ent in­finite col­lec­tions of things noteSpeci­fi­cally, math­e­mat­i­cal sys­tems which use the Ax­iom of Choice, see the tech­ni­cal page for de­tails.. To demon­strate this, we’ll use a 2d grid.

Real and Ra­tional numbers

Real num­bers are num­bers with a dec­i­mal ex­pan­sion, for ex­am­ple 1, 2, 3.5, \(\pi\) = 3.14159265… Every real num­ber has an in­finite dec­i­mal ex­pan­sion, for ex­am­ple 1 = 1.0000000000…, 2 = 2.0000000000…, 3.5 = 3.5000000000… Re­call that the ra­tio­nal num­bers are frac­tions of in­te­gers, for ex­am­ple \(1 = \frac11\), \(\frac32\), \(\frac{100}{101}\), \(\frac{22}{7}\). The pos­i­tive in­te­gers are the in­te­gers greater than zero (i.e. 1, 2, 3, 4, ..).

There is a the­o­rem in math that states that the ra­tio­nal num­bers are countable noteYou can see the the­o­rem here., that is, that the set of ra­tio­nal num­bers is the same size as the set of pos­i­tive in­te­gers, and an­other the­o­rem which states that the real num­bers are un­countable, that is, that the set of real num­bers is strictly big­ger. By “same size” and “strictly big­ger”, we mean that it is pos­si­ble to match ev­ery ra­tio­nal num­ber with some pos­i­tive in­te­ger in a way so that there are no ra­tio­nal num­bers, nor pos­i­tive in­te­gers, left un­matched, but that any match­ing you make be­tween real num­bers and pos­i­tive in­te­gers leaves some real num­bers not matched with any­thing.

Ra­tional grid

If you imag­ine lay­ing the ra­tio­nal num­bers out on a two-di­men­sional grid, so that the num­ber \(p / q\) falls at \((p, q)\), then we may match the pos­i­tive in­te­gers with the ra­tio­nal num­bers by walk­ing in a spiral pat­tern out from zero, skip­ping over num­bers that we have already counted (or that are un­defined, such as zero di­vided by any num­ber). The be­gin­ning of this se­quence is \(\frac01\), \(\frac11\), \(\frac12\), \(\frac{-1}{2}\), \(\frac{-1}{1}\), … Graph­i­cally, this is:

A counting of the rational numbers

This shows that the ra­tio­nal num­bers are countable.

Reals are uncountable

The real num­bers, how­ever, can­not be matched with the pos­i­tive in­te­gers. I show this by con­tra­dic­tion. noteThat is to say, I show that if there is such a match­ing, then we can con­clude non­sen­si­cal state­ments (and if mak­ing a new as­sump­tion al­lows us to con­clude non­sense, then the as­sump­tion it­self must be non­sense.

Sup­pose we have such a match­ing. We can con­struct a new real num­ber that differs in its \(n^\text{th}\) dec­i­mal digit from the real num­ber matched with \(n\).

For ex­am­ple, if we were given a match­ing that matched 1 with 1.8, 2 with 1.26, 3 with 5.758, 4 with 1, and 5 with \(\pi\), then our new num­ber could be 0.11111, which differs from 1.8 in the first dec­i­mal place (the 0.1 place), 1.26 in the sec­ond dec­i­mal place (the 0.01 place), and so on. It is clear that this num­ber can­not be matched with any num­ber un­der the match­ing we are given, be­cause, if it were matched with \(n\), then it would differ from it­self in the \(n^\text{th}\) dec­i­mal digit, which is non­sense. Thus, there is no match­ing be­tween the real num­bers and the pos­i­tive in­te­gers.

See also

If you en­joyed this ex­pla­na­tion, con­sider ex­plor­ing some of Ar­bital’s other fea­tured con­tent!

Ar­bital is made by peo­ple like you, if you think you can ex­plain a math­e­mat­i­cal con­cept then con­sider con­tribut­ing to ar­bital!


  • Uncountability

    Some in­fini­ties are big­ger than oth­ers. Un­countable in­fini­ties are larger than countable in­fini­ties.