Uncountability: Intuitive Intro

Col­lec­tions which have less than or the same num­ber of items 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 and some in­finite col­lec­tions are larger than oth­ers noteAt least, within math­e­mat­i­cal sys­tems which in­clude the Ax­iom of Choice, see the tech­ni­cal page for de­tails.. To demon­strate this, we’ll ex­plore a graph­i­cal demon­stra­tion with tiles and paths.

Tiles and paths

A colored sidewalk, the top row red, the bottom row blue

Con­sider, as shown above, a side­walk that goes on for­ever in one di­rec­tion, which is made up of equal-sized square tiles. The side­walk is two squares across. Con­sider a per­son who walks for­ever on it, obey­ing the fol­low­ing rule: Each step the per­son takes must be to one of the two tiles im­me­di­ately in front of that per­son; no go­ing back­wards, no skip­ping tiles, no go­ing side­ways, no stand­ing in place for­ever. The fol­low­ing is the be­gin­ning of one pos­si­ble path: A zig-zagging path that begins on blue.

Now let’s ask two ques­tions:

  1. How many tiles are there?

  2. How many pos­si­ble paths are there?

In both cases, you could just say that there are in­finitely many, and that would be cor­rect. But now let’s con­sider a third ques­tion:

  1. Is the num­ber of tiles the same as the num­ber of pos­si­ble paths?

It turns out that there is a mean­ingful and well-defined way to com­pare the sizes of differ­ent in­finite col­lec­tions of things, and some in­finite col­lec­tions are larger than oth­ers. In par­tic­u­lar, some in­finite col­lec­tions are countable (like the set of all nat­u­ral num­bers), while oth­ers are un­countable (like the set of all real num­bers). As we will see, it can be shown that the num­ber of tiles on our in­finite side­walk is countable, but that the num­ber of pos­si­ble paths one could take, fol­low­ing the rules above, is un­countable. So there are in fact more pos­si­ble paths than there are tiles.

Let’s dig into ex­actly what this means and why it’s true.

Pairing off

We say that two col­lec­tions of things are the “same size” if you can match the items to­gether com­pletely: you can pair each of the things in the first col­lec­tion with ex­actly one of the things in the sec­ond col­lec­tion, in such a way that there is noth­ing left un­paired. For ex­am­ple, given two sets of three things each, we may pair them. Here is an ex­am­ple of such a pairing:

Example pairing showing that 3 = 3: Three things on each side, all matched up: a cow (http://www.faqs.org/photo-dict/phrase/348/cow.html) matched to a racecar (http://www.zcars.com.au/wrc/), an airplane (http://www.penziononyx.cz/) matched to a watermelon (http://www.free-extras.com/tags/1/watermelon.htm),the earth (http://www.treehugger.com/2010/04/18-week/) matched to a computer (http://www.sb.fsu.edu/~xray/Xrf/anaconda.html)

You might think it ob­vi­ous, then, that the num­ber of paths our per­son can walk is big­ger than the num­ber of tiles. We can match each tile with the path that starts on a tile the same color as it, and changes to the other color af­ter it hits this tile. For ex­am­ple, we would match the third red tile with the path An example of a path

It is im­por­tant to note, how­ever, that it is not suffi­cient that we find some match­ing that leaves things left over. We must show that ev­ery match­ing leaves things left over. For ex­am­ple, an in­finite side­walk that is one tile across has just as many tiles as an in­finite side­walk that is two tiles across, as we can see from the pic­ture be­low by match­ing the 1R on top with the 1R on bot­tom, the 1B on top with the 1B on bot­tom, the 2R on top with the 2R on bot­tom, and so on.

A two-tile-wide sidewalk, with each column having a B tile and an R tile A one-tile-wide sidewalk, alternating B and R tiles

In fact, if we were only to re­quire that some match­ing leave ex­tra tiles, then the num­ber of tiles in a side­walk that is one tile wide would not be equal to it­self, for we could match the first tile with 1B (in the bot­tom pic­ture above), the sec­ond tile with 2B, and so on, and we would leave over half the tiles!

In fact, even if we had a field of tiles that is in­finite in ev­ery di­rec­tion, we would still have no more tiles than if we had only a side­walk that is one tile across. The fol­low­ing match­ing shows this:

A one-tile-wide sidewalk, with each tile numbered starting at 1 A field of tiles

An un­pairable path

You might won­der, given that there are so many differ­ent ways to match up in­finitely many things, how we can know that there is no match­ing that catches ev­ery­thing. I will now prove that, no mat­ter how you try to match paths (ways of walk­ing) and tiles, you will miss some paths. Since we have already seen that the num­ber of tiles in a side­walk two tiles wide is the same as the num­ber of tiles in a side­walk one tile wide, I will show that any match­ing be­tween paths and tiles in a side­walk one tile wide misses some paths. I will do this by cre­at­ing a path that does not match the path we have cho­sen for any tile noteThis type of proof is known as a proof by con­tra­dic­tion..

Sup­pose we are given a match­ing be­tween tiles and paths. Since we have num­bered the tiles in a side­walk one tile wide (\(\fbox{1}\fbox{2}\fbox{3}\fbox{4}\fbox{5}\fbox{6}\fbox{7}\fbox{8}\overline{\underline{\vphantom{1234567890}\cdots}}\)), we also have a num­ber­ing of the paths in our match­ing. Con­sider a new path that differs from the \(n^\text{th}\) path in our match­ing on the \(n^\text{th}\) tile, that is, the \(n^\text{th}\) step that you take. For ex­am­ple, if our first eight paths are

8 paths: 1: BRBRBRBR, 2: BBBBBBBB, 3: RRRRRRRR, 4: BRRRRRBB, 5: RBBRBRRB, 6: RBRRBBRR, 7: BRRRRRRB, 8: BRRBBBBB

then our new path is

The path RRBBRRBR

Clearly, this path is not any of the ones in the match­ing, be­cause it differs from ev­ery sin­gle path at some point (in par­tic­u­lar, it differs from the \(n^\text{th}\) path on the \(n^\text{th}\) tile, the \(n^\text{th}\) step you take, which is high­lighted in yel­low).

Be­cause we can re­peat this ex­er­cise no mat­ter what match­ing we’re given, that means any pos­si­ble match­ing will always leave out at least one path. Thus, the num­ber of paths a per­son can take must be strictly larger than the num­ber of tiles in the side­walk.

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!

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.