How Many Pixels Are In An Infinite Resolution Screen?
Earlier this week, I came across an article on Butterick's Practical Typography that was about 4K monitors. Or, so I thought when I started reading it. I had glossed over the title, so about halfway down I was hit by some sudden Cantor. Discrete Math!
A lot of people would have a lot of different reactions to that, but I was pleasantly surprised. The question posed was this: If you keep doubling the resolution of a computor monitor, how many pixels will the infinitely divided screen have?
Butterick comes to the conclusion that it is uncountably infinite. In an update, readers had written to him that it is actually countably infinite. He admits that this is so, and explains the error of his ways. There's just one problem...
Butterick was right all along!
The Flaw, or Lack Thereof
In his original argument, Butterick attempts to draw a bijection between the pixels on an infinite resolution screen and the set of infinite binary strings. In the correction, he says that this bijection failed to actually map any pixels. I think the bijection is sound, though. Let me see if I can get the actual mapping down.
Mapping Pixels to Binary Strings
Each pixel is somewhere on the screen. Let's assume it's a square screen, and assign coordinates to the corners. Top left is (0,0) and bottom right is (1,1). Anywhere in between can clearly be addressed by a coordinate pair.
Note that we only care that each pixel can be a coordinate pair, not that all coordinate pairs will necessarily be used. That's the next section.
Given a pixel, we map it to a binary string by dividing the space like Butterick did. For each digit, we divide the space in half, alternating horizontal and vertical. If the digit is on the left or top, we set the digit to 0. Bottom or right gets a 1. If it is precisely on the line, we'll give it a 0 and keep going. We continue this process indefinitely, thus constructing the string that perfectly matches the pixel.
Every pixel is somewhere in the space, and so every pixel will map to a binary string. Further, the pixels are infinitely small, and so the binary string will be of infinite length.
Mapping Binary Strings to Pixels
Can each infinite binary string map to a pixel? I believe so. When we split the resolution of the monitor, we cut each pixel into four parts. When taken in pairs, we can use binary strings to map which of the resulting pixels we are talking about. 00 means top-left, 01 means top-right, 10 means bottom-left, and 11 means bottom-right.
Because of the manner of splitting, after an infinite process of these pairs, we will have followed the splits to the exact pixel. Further, each binary string represents a unique sequence, and so each string will map to a unique pixel.So, not only does every pixel map to an infinite binary string, but every infinite binary string maps to one of our infinitely-small pixels. Bijection accomplished; there are uncountably many pixels.
There's another way of thinking about this which might help you believe that the mapping works. Suppose that we had split the screen in ten pieces in each dimension instead of two. We'd be left with 100 times the pixel each time. From there, consider the coordinate location of each pixel.
After one split, you'd have pixels at locations like (0.1,0.3) or (0.7,0.8). You'd never have anything smaller than the tenths digit showing up in your pairs.
After another split, you'd have pairs like (0.17,0.34) or (0.79,0.81). Again, nothing smaller than the hundredths digit. But do you see the pattern?
After N splits, you can represent any pair with up to N decimal digits. After an infinite series of splits, you'd have infinite digits to work with. And with infinite digits, you can represent any real number between 0 and 1.
There are uncountably infinite real numbers between 0 and 1, and so there must be an uncountably infinite number of pixels.
The Not-So-Flawed Correction
I'm not entirely sure the reasoning of the people who wrote in to correct Butterick, but I can at least comment on the logic of the correction he posted. It wasn't so much flawed as just counting something different.
In the correction, he counts pixels by assigning them to positive integers. By doing so, he claims that since you can map all of the pixels to integers, there must be countably many of them. That's true, and this is all well and good, but it doesn't say anything about the ininite resolution screen.
You see, the set of all of the pixels of all finitely-sized screens in all the world, no matter what their resolution, is countably infinite. But these are finite resolutions, not our “infinity screen.” It's a subtle disctinction, but an important distinction.
That's All I've Got...For Now
I hope this does something to clear up the issue (and I hope Internet Folks will tweet me if I'm wrong). Problems like this are really fun to think about. I'm done for now, but I think there is another followup post coming soon. Infinity is a weird thing. Be wary of it.