The correct answer to the infinite-pixel screen puzzle

Some time ago I came across an article by Matthew Butterick titled “The infinite-pixel screen.” The article describes the trend of doubling monitor resolutions and uses it as a pretext to pose a mathematical puzzle about a screen whose resolution was doubled infinitely many times; the question is whether such a screen would have a countable number of pixels.

The infinite-pixel screen article

The initial answer given in the article is that the screen would have uncountably many pixels, however, the article was later updated to state that the original reasoning is flawed and the correct answer is that the cardinality would actually be countable. The updated explanation did not convince me and I was not the only one with doubts as Will Mitchell argues on his blog that the first answer was the correct one.

Will Mitchell’s article

Both articles appeal to reader’s intuition and come to different conclusions. To get to the bottom of this we need to be more rigorous with the problem statement and solution. In the next sections I will restate the original problems and both reasonings. I am not going to introduce the notion of a countable set; readers are assumed to be familiar with it and the diagonal argument. If you haven't already, you can read the original article for a quick introduction.

Problem statement

To simplify the formalization, I am going to drop the second dimension and work with the [0, 1) line interval, i.e., {𝑥 ∈ ℝ | 0 ≤ 𝑥 < 1}. This simplification doesn’t fundamentally change the problem but helps to unclutter the notation. You can verify that the whole argument easily adapts to 2D or any other dimension for that matter.

Let [0, 1) represent our entire screen estate. Our starting point is a single pixel screen, that is, the set of pixels S₀ is defined as {[0, 1)}. With each successive step we are halving each pixel so after the first step the set of pixels S₁ will be {[0, ½), [½, 1)}, and after the second step we will get S₂ = {[0, ¼), [¼, ½), [½, ¾), [¾, 1)}. Below is a visual represenation of the first three steps.

S₀ = |———————————————————————————————————————————————————————————————|
     0                                                               1

S₁ = |———————————————————————————————|———————————————————————————————|
     0                               ½                               1

S₂ = |———————————————|———————————————|———————————————|———————————————|
     0               ¼               ½               ¾               1

S₃ = |———————|———————|———————|———————|———————|———————|———————|———————|
     0       ⅛       ¼       ⅜       ½       ⅝       ¾       ⅞       1

It is not hard to see that the general formula for Sₙ is {[k/2ⁿ, (k+1)/2ⁿ) | k ∈ {0, 1, ..., 2ⁿ-1}}.

Given the definition above, what is the cardinality of the set Sₙ as n goes to infinity?

The first argument from intuition

Let’s notice that at each step Sₙ covers our entire screen estate. If we focus on a single point 𝑥 then we can find a sequence of intervals Iₙ such that Iₙ ∈ Sₙ, Iₙ₊₁ ⊆ Iₙ, and 𝑥 ∈ Iₙ. For example, if 𝑥 = ⅓ then this sequence would be [0, 1), [0, ½), [¼, ½), [¼, ⅜), etc. If we consider the limit of all such sequences we get every real number in the [0, 1) interval (we also get 1 but let’s ignore that). From that we conclude that the limit has as many points as [0, 1) so uncountably many.

If you are wondering how that relates to the infinite strings of 0s and 1s, consider the binary expansion of ⅓ which is 0.010101... and notice that the digits (or rather bits) after the decimal point (binary point?) dictate the necessary sequence: first is 0 so we get the lower half of the whole interval, second is 1 so we get the upper half of the previous interval and so on.

The second argument from intuition

This time we are going to take approach of assigning a number to each pixel, specifically the lower end of its interval. This way we get a new sequence of sets: T₀ = {0}, T₁ = {0, ½}, T₂ = {0, ¼, ½, ¾}, ..., Tₙ = {k/2ⁿ | k ∈ {0, 1, ..., 2ⁿ-1}}. For each n, there is an obvious bijection between Sₙ and Tₙ so we may deal with these sequences interchangably with regards to cardinality.

Let’s consider the set U = {k/2ⁿ | n ∈ ℕ, k ∈ ℕ, k < 2ⁿ-1}, that is, the set of all proper fractions with a power of two in the denominator. Notice that Tₙ ⊆ U for all n and that this property does not hold for any proper subset of U. From this we conclude that U is the limit of our sequence. But U is a subset of rational numbers and there are countably many of them so this set is also countable.

To relate this to the finite strings of 0s and 1s, we again consider the binary representation of the elements in these sets. If a number can be written with finitely many bits after the binary point then it can be represented as a fraction with a power of 2 denominator. So the set Tₙ can be thought of as containing all strings of length n, while U is the set of all finite strings. Notice that ⅓ is not in U because its binary representation is repeating and therefore not finite.

So what is the limit?

Do you see the mistake? If not then perhaps recalling the definition of a limit that you probably learned in high school may help:

When the limit of the sequence exists, the real number L is the limit of this sequence if and only if for every real number ε > 0, there exists a natural number N such that for all n > N, we have |aₙ − L| < ε.

Taken from the Wikipedia article on Limit

“Well, that's not very helpful,” you may say, “this only defines a limit of a sequence of real numbers and we are dealing with sets.” That's actually the core issue of the puzzle – the article does not specify what it means by a set limit.

It turns out that the answer differs depending on the limit generatlization we choose. For example, if we consider the set-theoretic limit we get the countable set U from the second argument. On the other hand if we consider the Kuratowski limit of the same sequence we will get the full [0,1] interval.

The difference between these approaches boils down to whether we consider the sets in our sequence of screens as devoid of structure or whether we exploit the fact that they contain real numbers with the usual topology. Ultimately the question is underspecified and depending on which assumptions we choose the correct limit may be either of the argued ones or even both of them.