Last week I up­graded my desk­top mon­i­tors. I re­tired my trusty Ap­ple Cin­ema Dis­plays in fa­vor of two 4K Dell mon­i­tors. As a ty­pog­ra­pher, the up­grade from black & white to grayscale fonts in the ’90s was pretty good. But 4K is much better.

High-res­o­lu­tion dis­plays like these have al­ready taken over phones and tablets. It’s nice to see that they’re spread­ing into lap­tops and desk­tops too.

Fonts look fantastic.

Well, that’s not en­tirely true. Good fonts look fan­tas­tic. Bad fonts look worse, be­cause they can no longer hide be­hind the in­dis­tinct edges of coarser pix­els. But if you work with type—as a reader, writer, pro­gram­mer, or de­signer (which I guess cov­ers just about every­one)—then up­grad­ing to 4K is com­pletely worthwhile.

But what is “4K”? In the false ad­ver­tis­ing op­ti­mistic math of the dis­play in­dus­try, 4K is the com­mon name for a screen that’s 3840 pix­els wide by 2160 pix­els high. (Be­cause 3840 is, I guess, 4000-ish.) It has twice the res­o­lu­tion in each di­rec­tion as a stan­dard HDTV screen, which is 1920 pix­els wide by 1080 high.

When 4K screens first ap­peared, it wasn’t un­com­mon for peo­ple to de­scribe them as hav­ing “twice as many” pix­els. But that’s wrong. If you dou­ble the pixel res­o­lu­tion hor­i­zon­tally and ver­ti­cally, it’s like cut­ting each pixel in half in two di­rec­tions. So a 4K screen has four times as many pix­els as an HDTV. (Skep­tics are in­vited to mul­ti­ply the num­bers above and see that this is so.)

To the sur­prise of no one, the dis­play in­dus­try plans to keep di­vid­ing pix­els. Far­ther on the hori­zon is the 7680 × 4320 screen, known as 8K. Of course, at desk­top sizes, one rapidly ap­proaches di­min­ish­ing re­turns, be­cause the hu­man eye has its own res­o­lu­tion limit. The jump to 4K is a very no­tice­able im­prove­ment. The jump to 8K will be less so. At some point, man­u­fac­tur­ers will stop di­vid­ing pixels.

But what if they didn’t? What if they di­vided the pix­els on the screen an in­fi­nite num­ber of times? How many pix­els would the re­sult­ing screen have?

a) As many pix­els as pos­i­tive in­te­gers.
b) Fewer.
c) More.

As a fan of math, I like think­ing about ques­tions like this. (If you don’t, you can bail out now. In sum: buy a 4K mon­i­tor, and you’re welcome.)

The first thing that might give you pause is the im­pli­ca­tion in op­tion (c) that we can have a quan­tity of pix­els that’s greater than the num­ber of pos­i­tive in­te­gers. Aren’t the in­te­gers in­fi­nite? And isn’t in­fin­ity, like, as far as you can go?

Turns out the an­swer is no. For this re­sult, we can thank the Ger­man math­e­mati­cian Georg Can­tor. When Can­tor started his work in the 1860s, in­fi­nite num­bers had been used in math­e­mat­ics for hun­dreds of years. But there was al­ways a bit of mys­tery and hand­wav­ing about what they really were. Can­tor cleared away the fog.

One ques­tion Can­tor stud­ied is whether all in­fi­nite sets are the same size, or if some are big­ger. But how do you com­pare in­fi­nite sets? If we had fi­nite sets, we’d know how to com­pare them: just count the el­e­ments. Whichever set has more el­e­ments is big­ger. But with in­fi­nite sets, count­ing takes too long.

So what do we do? We can’t count in­fi­nite sets di­rectly. But sup­pose fur­ther that we couldn’t count fi­nite sets di­rectly. In that case, how could we rep­re­sent, say, the quan­tity five? We could raise our hand and say “this many fin­gers”. In so do­ing, we’d be defin­ing a quan­tity by re­fer­ring to the num­ber of el­e­ments in an ex­ist­ing set—namely, the set of fin­gers on our hand.

This quan­tity of el­e­ments in a set is also called the car­di­nal­ity of the set. How is car­di­nal­ity use­ful? If we have a set with a cer­tain car­di­nal­ity, we can use it to mea­sure other sets by match­ing up the el­e­ments of one set to the el­e­ments of the other. If the two sets have a one-to-one cor­re­spon­dence be­tween el­e­ments, then they must have the same cardinality.

For in­stance, sup­pose we want to mea­sure the car­di­nal­ity of the set of toes on our foot. We no­tice that we can touch each fin­ger on our hand to each toe on our foot. Thus we can con­clude that fin­gers and toes have the same cardinality.

That’s a rudi­men­tary ex­am­ple. What if I gave you two bags of ob­jects and asked whether they con­tained the same num­ber of ob­jects? Again, with­out count­ing. You could take an item out of both bags un­til you ex­hausted the sup­ply of one bag. If the other bag was si­mul­ta­ne­ously empty, then you’d know they had the same car­di­nal­ity. This would work re­gard­less of how many items were in the bag.

Which brings us to Can­tor’s in­sight: even though you can’t count in­fi­nite sets di­rectly, you can com­pare them by car­di­nal­ity. If two in­fi­nite sets are the same size, then you’ll be able to put them into a one-to-one cor­re­spon­dence. Or, if you can prove that no such cor­re­spon­dence ex­ists, then one of the in­fi­nite sets must be big­ger. “Find­ing a one-to-one cor­re­spon­dence” is a lot of typ­ing, so this tech­nique is more com­pactly known as bi­jec­tion.

Bi­jec­tion is a sim­ple idea. But it’s an im­por­tant tool be­cause it helps keep us out of the coun­ter­in­tu­itive weeds when work­ing with in­fi­nite sets. For in­stance, we can now fig­ure this out: are there more pos­i­tive in­te­gers {1, 2, 3, ...} or even in­te­gers {2, 4, 6, ...}? The naive an­swer would be that there must be more pos­i­tive in­te­gers, be­cause the set of pos­i­tive in­te­gers in­cludes both the even and odd integers.

But this is wrong. Us­ing bi­jec­tion, we see that we can put the pos­i­tive in­te­gers and even in­te­gers into a one-to-one cor­re­spon­dence like so:

1, 2, 3, 4, ...
2, 4, 6, 8, ...

No mat­ter how far we go, we can al­ways find the el­e­ment in one set that cor­re­sponds to the el­e­ment in the other. That’s the bi­jec­tion. Thus, the car­di­nal­ity of these two in­fi­nite sets is the same. There are just as many pos­i­tive in­te­gers as even in­te­gers. It sounds a lit­tle weird at first, but we just proved it.

To show that two in­fi­nite sets are the same size, you have to find a bi­jec­tion. But to show that one in­fi­nite set is big­ger than the other, you have to prove some­thing more dif­fi­cult: that no bi­jec­tion can exist.

But Can­tor proved this was pos­si­ble too. One of his meth­ods, the di­ag­o­nal­iza­tion ar­gu­ment, is sin­gu­larly lovely, and goes like this.

Can­tor started by con­sid­er­ing an in­fi­nite string of bi­nary dig­its like so:

10010101001011101010 ...

Then he thought about the set of all such strings:

10010101001010101010 ...
01001010100101001001 ...
10010011110001001000 ...
...

Then he asked: how many of these strings ex­ist? Clearly, it’s an in­fi­nite num­ber. And it looks like we might be able to find a bi­jec­tion with the pos­i­tive in­te­gers by just list­ing them all out in some sys­tem­atic way:

1: 10010101001010101010 ...
2: 01001010100101001001 ...
3: 10010011110001001000 ...
4: ...

If that bi­jec­tion works, then the set of in­fi­nite bi­nary strings has the same car­di­nal­ity as the pos­i­tive integers.

But here comes Can­tor’s jiu-jitsu move. He points out that if you take the nth digit from each string and flip it (from 0 to 1 or 1 to 0), you’ll end up with a new string:

1: 10010101001010101010 ...
2: 01001010100101001001 ...
3: 10010011110001001000 ...
4: ...

001 ...

Ob­vi­ously, this new string is it­self an in­fi­nite bi­nary string. So it be­longs to our set. But it’s not in the bi­jec­tion. How do we know this? Be­cause of how we con­structed it: the new string dif­fers from every string al­ready in the bi­jec­tion by at least one digit.

In other words, given any at­tempt to match up these in­fi­nite bi­nary strings with the pos­i­tive in­te­gers, you can al­ways con­struct an­other string that’s not in the bi­jec­tion. There­fore, there can be no bi­jec­tion be­tween the pos­i­tive in­te­gers and these in­fi­nite bi­nary strings. Though both sets are in­fi­nite, the set of in­fi­nite bi­nary strings is really, truly bigger.

To be more pre­cise, the car­di­nal­ity of the set of in­fi­nite bi­nary strings is greater than the car­di­nal­ity of the set of pos­i­tive in­te­gers. These two in­fi­nite car­di­nal­i­ties sur­face of­ten enough that they have their own names. Sets that share the car­di­nal­ity of the pos­i­tive in­te­gers are called count­ably in­fi­nite; sets that share the car­di­nal­ity of the in­fi­nite bi­nary strings are called un­count­ably infinite.

Re­call that our screen is con­structed by di­vid­ing the pix­els in half an in­fi­nite num­ber of times. We can now see that the word “in­fi­nite” in that sen­tence refers to a count­ably in­fi­nite num­ber of pixel di­vi­sions. Why? Be­cause we can cre­ate a bi­jec­tion be­tween the pos­i­tive in­te­gers and the pixel divisions.

Sup­pose we start with a screen that’s one gi­ant pixel:

In step 1, we cut the pixel in half horizontally:

In step 2, we cut it in half vertically:

In step 3, we cut each new pixel horizontally:

In step 4, we cut them vertically:

And so on. You can see that each round of cut­ting will cor­re­spond to a pos­i­tive in­te­ger, cre­at­ing a bi­jec­tion with a count­ably in­fi­nite set.

So how many pix­els re­main at the end? It should be clear that we have in­fi­nite pix­els. More­over, hav­ing made count­ably in­fi­nite rounds of cuts, the in­tu­itive an­swer might be that we also have a count­ably in­fi­nite num­ber of pixels.

Or do we? Is it pos­si­ble that we have more pix­els—an un­count­ably in­fi­nite set of pix­els? As be­fore, we can fig­ure this out by ask­ing whether we can cre­ate a bi­jec­tion be­tweeen our pix­els and some un­count­ably in­fi­nite set.

We have such a set. We al­ready es­tab­lished that Can­tor’s in­fi­nite bi­nary strings were un­count­ably infinite:

10010101001010101010 ...
01001010100101001001 ...
10010011110001001000 ...
...

So can we cre­ate a bi­jec­tion be­tween these strings and the pix­els? I pro­pose we can. Re­call that we con­structed our panel by mak­ing al­ter­nat­ing hor­i­zon­tal and ver­ti­cal cuts. We can match up any of these bi­nary strings to a cer­tain pixel on the screen by us­ing the dig­its in the string to “steer” us.

In step 1, we made a hor­i­zon­tal cut. So if the first digit in our string is 0, we’ll choose the top half of the pixel. If 1, we’ll choose the bot­tom half.

In step 2, we made a ver­ti­cal cut. So if our sec­ond digit is 0, we’ll choose the left half of the pixel. If 1, we’ll choose the right half.

Now we just re­peat this process: let­ting al­ter­nat­ing num­bers in the string in­di­cate top vs. bot­tom, then left vs. right. Af­ter step 4:

As we con­tinue, the cells will get smaller, and the bi­nary strings will get longer. Even­tu­ally—mean­ing, at the end of this count­ably in­fi­nite process—we’ll have a one-to-one cor­re­spon­dence be­tween every pixel and every in­fi­nite bi­nary string. In other words, we will have de­fined a bi­jec­tion. And since the in­fi­nite bi­nary strings are un­count­ably in­fi­nite, so are the pix­els. There­fore, we have more pix­els than pos­i­tive integers.

The first re­lease of this ar­ti­cle ended here. In an im­pres­sively ef­fi­cient dis­play of Cun­ning­ham’s Law, sev­eral read­ers wrote to say that my rea­son­ing was faulty. The in­fi­nite-pixel screen con­tains only a count­ably in­fi­nite num­ber of pixels.

I’ll con­cede that this is so.

To see why, let’s first find the flaw in my pre­vi­ous demon­stra­tion. I claimed that my pixel-cut­ting tech­nique would let us as­so­ciate any in­fi­nite bi­nary string with a pixel.

A cou­ple read­ers tried to find a con­tra­dic­tion us­ing Can­tor’s di­ag­o­nal­iza­tion ar­gu­ment, say­ing that there should be a way to con­struct a new in­fi­nite bi­nary string that doesn’t map to a par­tic­u­lar pixel. But there’s no way to do this.

Why? Be­cause the prob­lem with my pro­posed bi­jec­tion is not that it fails to map every in­fi­nite bi­nary string, but that it fails to map any of them.

Even though each of our bi­nary strings is in­fi­nite in length, it rep­re­sents an ex­act num­ber—a spe­cific point on the screen. This shouldn’t alarm you. For in­stance, re­call from sev­enth-grade math that the ex­act frac­tion one-third can be found on the num­ber line be­tween 0 and 1. But the dec­i­mal ex­pan­sion of this frac­tion is the in­fi­nite dec­i­mal 0.333... As we add dig­its to the dec­i­mal—0.3, 0.33, 0.333, 0.3333—we get ever closer to one-third. And though one-third is cer­tainly the limit of this se­ries of dec­i­mals, one-third it­self never ap­pears within the se­ries. In a sense, the limit is in­for­ma­tion that’s “out­side” this se­ries of approximations.

Like­wise, the pix­els in my con­struc­tion rep­re­sent ap­prox­i­ma­tions of in­fi­nite bi­nary strings, which are the lim­its of these ap­prox­i­ma­tions. But just as there’s no way to fol­low 0.333... un­til you reach ex­actly one-third, there’s no way to carve a pixel un­til you get to the ex­act point rep­re­sented by a cer­tain in­fi­nite bi­nary string. So the premise be­hind my pro­posed bi­jec­tion was faulty. I tried to fudge that which could not be fudged.

Hav­ing adopted the idea that every pixel is an ap­prox­i­ma­tion, we can use the con­struc­tion to re­count the pix­els. This time, let’s la­bel our orig­i­nal pixel with the digit 1:

Then we’ll ap­pend a bi­nary digit each time we split the cur­rent pix­els, the same way as before:

Skip­ping to step 4:

In so do­ing, we can as­so­ciate every pixel at every level of the con­struc­tion with a unique in­te­ger. (You can in­ter­pret the num­bers above as bi­nary or dec­i­mal—same re­sult.) Of course, the to­tal num­ber of pix­els is still in­fi­nite, since the dou­bling goes on for­ever. But any in­fi­nite sub­set of the pos­i­tive in­te­gers can be put into bi­jec­tion with the pos­i­tive in­te­gers (like the ex­am­ple of even in­te­gers vs. pos­i­tive in­te­gers ear­lier). So there are only as many pix­els as integers.

What about those in­fi­nite bi­nary strings? We now see that there are more of those (be­cause they’re un­count­ably in­fi­nite) than pix­els in our screen (be­cause those are count­ably in­fi­nite). But is there a way to re­late these two kinds of in­fi­nite car­di­nal­ity within this pixel con­struc­tion? I say yes. (OK, I’ve been wrong before.)

Can­tor’s The­o­rem—he dis­cov­ered sev­eral the­o­rems, but this is the epony­mous one—says that for any set of items, the set of sub­sets of items is al­ways big­ger (i.e., has greater car­di­nal­ity). With a small set, this is easy to see. The three-el­e­ment set {x, y, z} has eight sub­sets: {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} it­self, and {}, the empty set. This set of sub­sets is also known as a power set.

In gen­eral, how big is a power set? When we cre­ate any sub­set, we’re es­sen­tially mak­ing a se­ries of de­ci­sions whether to in­clude each el­e­ment. So for the set {x, y, z}, we have three el­e­ments, and hence three de­ci­sions to make. And be­cause each de­ci­sion can have two out­comes (in­clude vs. ex­clude), the num­ber of pos­si­ble sub­sets is 2 × 2 × 2 = 8. Thus, for a fi­nite set, the size of the power set is 2 raised to a power equal to the num­ber of el­e­ments in the set.

The neat part of Can­tor’s The­o­rem is that it also ap­plies to in­fi­nite sets. Con­sider the power set of pos­i­tive in­te­gers—mean­ing, all pos­si­ble sub­sets of the pos­i­tive in­te­gers. This power set is it­self an in­fi­nite set, but by Can­tor’s The­o­rem, also has greater car­di­nal­ity than the pos­i­tive integers.

This idea of a big­ger in­fi­nite set is still weird and ab­stract. So let’s try bring­ing it back to our in­fi­nite-pixel screen.

First, let’s ask how could we no­tate those sub­sets. Since every sub­set is a se­ries of in­clude–ex­clude de­ci­sions, we could adopt a nu­mer­i­cal scheme—say, “1” for in­clude and “0” for ex­clude. Then we’d just need to write one digit for every pos­i­tive in­te­ger, maybe like so:

10010101001011101010 ...

Then the full power set for the pos­i­tive in­te­gers would look some­thing like this:

10010101001010101010 ...
01001010100101001001 ...
10010011110001001000 ...
...

That should look fa­mil­iar—we’ve come full cir­cle, back to Can­tor’s set of in­fi­nite bi­nary strings. Re­call that Can­tor’s di­ag­o­nal­iza­tion ar­gu­ment showed that this set had greater car­di­nal­ity than the in­te­gers. Can­tor’s The­o­rem says the same thing, but through the idea of the power set.

When we see a row of ze­roes and ones, it sug­gests a stream of bits—a bit be­ing the small­est unit of dig­i­tal in­for­ma­tion. Hav­ing no­ticed that a power set can be writ­ten as a set of bit strings, it is pos­si­ble to rechar­ac­ter­ize the power set in terms of information?

Why not? Let’s see what hap­pens if we treat the power set as a mea­sure of the in­for­ma­tion ca­pac­ity of a set. We saw how a three-el­e­ment set {x, y, z} could be used to ex­press eight dif­fer­ent sub­sets. That’s like say­ing that three bits in a com­puter can ex­press eight num­bers (and in­deed they can). This equiv­a­lence will be true for any fi­nite set. By Can­tor’s The­o­rem, it should re­main true for in­fi­nite sets.

Let’s test it out. We now have a screen of count­ably in­fi­nite pix­els. But pix­els are the per­fect items for our ex­am­ple, since their rea­son for ex­is­tence is to dis­play in­for­ma­tion. To make things sim­ple, we’ll as­sume that our screen is in­stalled in a vin­tage Mac Plus In­fi­nite, so all the pix­els can be ei­ther white (on) or black (off).

Now turn the com­puter on. What can we say about the screen im­age? It’s a bitmap, which we can in­tu­itively un­der­stand as way of stor­ing and dis­play­ing in­for­ma­tion. The bitmap is de­fined as a set of pix­els turned white, which is a sub­set of the whole screen. Of course, any pixel in the screen can be white or black, so as we use the com­puter, and the bitmap changes, we’re see­ing dif­fer­ent sub­sets turned white.

So the fi­nal ques­tion: how many bitmaps are pos­si­ble on our in­fi­nite-pixel screen? Or equiv­a­lently: what is the in­for­ma­tion ca­pac­ity of this screen?

Since any par­tic­u­lar bitmap is rep­re­sented by a sub­set of screen pix­els, then the set of all pos­si­ble bitmaps is the set of all pos­si­ble pixel sub­sets—oth­er­wise known as the power set. Fur­ther­more, we have count­ably in­fi­nite pix­els in the screen to be­gin with. And the power set of a count­ably in­fi­nite set—as Can­tor showed in sev­eral ways—is un­count­ably infinite.

There­fore, though it turned out our screen could only hold a count­ably in­fi­nite num­ber of pix­els, it can still dis­play an un­count­ably in­fi­nite num­ber of bitmaps.

If you need to make a slide pre­sen­ta­tion of Can­tor’s in­fi­nite bi­nary strings, this is the screen to get, be­cause it can dis­play all of them.

Oth­er­wise, how­ever, my ad­vice re­mains the same—just up­grade to 4K. It’s got plenty of pix­els. Really.

—Matthew But­t­er­ick
15–18 March 2015