# 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

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:

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:

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

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.

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:

## 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}\over­line{\un­der­line{\vphan­tom{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

then our new path is

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.

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.

• Nice! I’ve never seen an ex­am­ple like this be­fore, and it’s ac­tu­ally kind of sur­pris­ing. It seems to im­ply that 2^N is qual­i­ta­tively differ­ent than N or N^2, but I’m not sure how to phrase it. (And I won­der if there is a re­la­tion­ship be­tween that and P=NP prob­lem.)

• Thanks!

A^B is the set of func­tions from B to A. So 2^N is pow­er­set of N (a func­tion f from N to {0, 1} says, for each el­e­ment of N, whether or not that el­e­ment is in the sub­set defined by f), which is iso­mor­phic to the re­als. Per­haps this should go some­where in one or more of the ver­sions. I don’t know any con­nec­tion be­tween this and P=NP (al­though I sup­pose it could be be­hind the ex­po­nen­tial bounds on var­i­ous things).

• A sum­mary of the rele­vant car­di­nal ar­ith­metic, by the way (in the pres­ence of choice): $$\aleph_{\alpha} + \aleph_{\alpha} = \aleph_{\alpha} = \aleph_{\alpha} \aleph_{\alpha}$$$while $$2^{\aleph_{\alpha}} > \aleph_{\alpha}$$$

• Should be “two tile wide”, right?

• Which in­stance of that are you refer­ring to (there are five)?

• Can the image be­low be cropped? The ex­ces­sive whites­pace is dis­tract­ing.