# 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:

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.

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!

Parents:

• Uncountability

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

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

• Can­tor’s ar­gu­ment also works in the finite case and this may serve to demon­strate the idea.

Con­sider 4-digit bi­nary num­bers like 1001. We can use Can­tor’s ar­gu­ment to show that there are more than four such bi­nary num­bers. Imag­ine you had a list of four such num­bers, say 1001, 1010, 1110 and 0011. Then I can con­struct a num­ber that can’t pos­si­bly be in your list since it differs from the first num­ber in the first digit, from the sec­ond in the sec­ond etc. In this case the num­ber is 0100.

• This is a cool page, but I think it (esp. the last para­graph) goes too fast for many math 1 read­ers, even if it mostly uses things that math 1 peo­ple would be able to use. Maybe re­cat­e­go­riz­ing it as math 2 would be best, or ex­pand­ing things out and be­ing a bit more hand­holdy, or putting tricky bits as op­tional hid­den text?