Infinite Pixel Screen

Last week I updated my monitors. Threw Apple Cinema Display and took in their place 4K monitors from Dell. As a printer, I liked the previous upgrade from black and white to grayscale monitors in the 90s. But 4K is even better. High resolution displays have already arrived on smartphones and tablets. It's nice that they appear in laptops and dextops. Fonts look wonderful.

Although - good fonts look wonderful. The bad ones look worse - they no longer hide behind the poorly distinguishable edges of rough pixels. If you work with text - read, write, program, draw (and this covers almost all professions), then an upgrade to 4K is worth it.



But what is 4K? With the easy hand of marketers, this is a 3840-by-2160-pixel screen (3840 is almost 4,000). On each side, the resolution is two times higher than that of HDTV, that is, 1920x1080.

At first, people said that 4K screens had “twice as many pixels.” In fact, if you double the number of pixels linearly, it’s the same as cutting each pixel both vertically and horizontally. That is, on a 4K screen there are 4 times more pixels than HDTV.

And, which is typical, no one is going to stop there, on the horizon there are already 7680 x 4320 displays, known as 8K. On the other hand, the resolution perceived by the human eye has limits. The transition to 4K is noticeable. At 8K - less noticeable. At some point, you will need to stop dividing the pixels.

But what if they don't stop? What if they divide the pixels endlessly? How many pixels will there be on the screen?

a) by the number of positive integers
b) less
c) more

If you are not interested in mathematics, then the result of the article is this: buy a 4K monitor. Do not mention it.

Compare infinity

To begin with, you may be surprised at point c), which refers to a number greater than the number of positive integers. Isn't there an infinite number of them? Is infinity “after all”? Yes?


Georg Cantor looks at you as an aspiring mathematician

. Actually, no. When the German mathematician Georg Cantor began his activities in the 1860s, infinities have been used in mathematics for quite some time. But there were always some ambiguities and misunderstandings with them. Cantor explained everything.

One of the questions he studied is whether all infinite sets have the same size? But how to compare infinite sets? If we had finite sets, we could recount them. Who has more elements, he won.

OK, we cannot count the infinite set directly. But imagine that we cannot recalculate a finite set directly. How can we imagine, for example, the number five? You can show your hand and say "that's so many fingers." That is, we correlate the number to a known set - the number of fingers. The number of elements in a set is also called its power. If we have a set of a certain power, we can compare it with other sets by comparing the elements of one set with the elements of another. If two sets have a unique correspondence between all elements, their sets are equal.

For example, we want to know the power of many toes. We can touch each finger on the toe. Therefore, we conclude that the powers of the sets of fingers on the arm and foot are equal.

And if we have two bags of objects and we need to compare, do they contain the same number of objects without recounting them? We can take one piece out of each bag until they end in one of the bags. If at this moment they end in another, their powers are equal. And this method does not depend on the number of things.

So Kantor thought so: although we cannot count infinities, we can compare their powers. If they coincide, then we can make up a one-to-one correspondence (bijection) from two sets. Or, we can prove that there is no such correspondence - then the power of one of the sets is greater.

Bijection is a simple, but also useful tool for work. For example, we can find out the answer to the question of which integers are greater - all positive or only even. One could simply answer that there are more positive ones, because a lot of positive ones include both even and odd ones.

But this is not so. The bijection shows that we can match the sets of positive numbers and even numbers:

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

And it doesn’t matter how far we go - there will always be an element in one set corresponding to the element in a different. Therefore, the power of these sets is the same. It sounds strange, but it is.

Great infinity

To show that the power of one set is greater than the other, it is necessary to prove that there is no bijection for them. And Cantor showed that this is possible. His proof uses diagonalization and is as follows.

Cantor began with an infinitely long binary string:

10010101001011101010 ...

Then he thought about the set of all such lines:

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

and asked: how many of them exist? Obviously an infinite number. And we can find a bijection with positive integers by simply listing all these lines in some way:

1: 1001010100101010101010 ...
2: 0100101010000101001001 ...
3: 10010011110001001000 ...
4: ...

If such a bijection is possible, then the set of infinite binary strings has the same power as the set of positive integers.

And then Kantor suddenly remarks that if we select the nth digit in the nth line and compose a new infinite number from them, while replacing 0 with 1, and 1 with 0, we get a new line:

1: 1 0010101001010101010 ...
2: 0 1 001010100101001001 ...
3: 10 0 10011110001001000 ...
4: ...

001 ...

The resulting string will also be infinite and binary. So she will belong to our multitude. But she will not be in the bijection. Why? Because we built it that way: a new line differs from any line from our list by at least 1 character.

In other words, with any way to match many infinite binary strings with many positive integers, you can always construct a line that is not included in the bijection. That is, bijection is impossible. Therefore, although both sets are infinite, the cardinality of the set of infinite binary strings is greater.

These two different powers are quite common, so they have their own names. The power of the set of positive integers is called countable. A set with the same power as a set of infinite binary strings is called uncountable.

Back to the screen with an infinite number of pixels

Remember that on our screen the pixels are divided an infinite number of times? Now we know that our “infinity” refers to countable infinity. Why? Because we can create a bijection between positive integers and pixel division.

If we start with a giant pixel:



In step 1, divide it in half horizontally:



In step 2 - vertically



By 3, divide everything horizontally



4 - vertically



Etc.

Each section corresponds to a positive integer, so we get a bijection with a countable infinite set.

And how many pixels do we get? Infinite number. Moreover, since we made a countable infinite number of cuts, we need to get a countable infinite number of pixels. Or not?

Could it be that we suddenly get an uncountable infinite number of pixels? Let's try to make a bijection between the number of pixels and some uncountable infinite set. For example, the same set of infinite binary strings.

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

Recall that we did our screen by cutting the pixel vertically or horizontally. Each of the binary strings can be mapped to a specific pixel on the screen using the numbers from the string.

In the first step, we made a horizontal section. If the first digit in the line is 0, we select the top of the pixel. If 1 is the bottom.

0...

1...

In the second step, we made a vertical section. Then, if our second number is 0, we select the left half of the pixel. If 1 - right.

00...

01...

Now we just repeat this process - the numbers will indicate top or bottom, then left or right. After step 4:

0000...	0001...	0100...	0101...
1000...	1001...	1100...	1101...

Further, the cells will decrease, and the binary strings will increase. And we get a one-to-one correspondence of each pixel to each infinite binary string. That is, we get a bijection. And, since the number of infinite binary strings is uncountable, the number of pixels is uncountable.

Cunningham Law: The best way to get an answer online is to post the wrong

After the first publication of the article, I received letters stating a gap in the discussion. And in the end it turned out that a screen with an infinite number of pixels contains a countable set of them.

We find a gap in the discussion. I stated that pixel cutting technology will allow you to assign a pixel to each infinite binary line. Several readers have tried to find a contradiction using diagonalization, saying that you can think of a way to make a line that does not correspond to a pixel. But this is not so.

Because the problem with my bijection is not that she cannot attach every infinite binary string, but that she cannot attach any of them.

Although each line is infinite, it corresponds to an exact number - a specific point on the screen. This should not bother you. For example, recall that the number 1/3 is between 0 and 1. But the decimal notation for this number is infinite 0.3333 (3). The more numbers we add, the closer to 1/3. And although 1/3 is the limit of this series of decimal digits, it will certainly never be written down. In a sense, the limit is “outside” the series of approximations.

So the pixels in my design represent approximations of infinite binary strings, being their limits. But since there is no way to build 0.3333 (3) to exactly 1/3, there is no way to find a pixel until you reach a certain point represented by a specific infinite binary string. Therefore, my assumption about the bijection was false.

Having accepted the idea that each pixel is an approximation, we can use our design to recalculate pixels. Let's number the starting pixel 1.

1

Now add a binary digit every time we divide the pixel - in the same way as before:

10

11

100101

110111

Jump to step 4:

10000	10001	10100	10101
11000	11001	11100	11101

Thus, you can match each pixel with a unique integer (it doesn't matter, binary or decimal). The total number of pixels is infinite, but to any infinite subset of positive integers you can find a bijection with many positive integers. Therefore, there will be no more pixels than integers.

Bonus

What about infinite binary strings? It turns out that there are more of them (since there are many uncountable ones) than there are pixels on the screen (since there are many countable ones). Can we match these two infinities? I think so.

Cantor's theorem says that for any set of objects, the set of their subsets is always greater (i.e., has a large power). This is easy to see with a small set. The set of three elements {x, y, z} has eight subsets: {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y , z} and {} (empty). This set of subsets is also known as the degree of the set, or Boolean.

How big is the boulean? Creating a subset, we, in fact, make several decisions about whether or not to include each element. That is, in the set {x, y, z} there are three elements, and three solutions. And since each decision has two options (accept and not accept), then the number of possible subsets is 2 * 2 * 2 = 8. That is, for a finite set, the size of the boolean will be 2 to the power of the number of elements in the set.

The trick of Cantor's Theorem is that it also works for infinite sets. Consider a Boolean of positive integers - that is, all possible subsets of positive integers. A Boolean itself will be an infinite set, but, according to Cantor’s Theorem, it will also have a greater power than a set of positive integers.

The idea that one set is bigger than the other still seems strange and abstract. Back to our screen with an infinite number of pixels. Let's see how we can designate these subsets. Each subset is a set of decisions to include / not include, so we can denote inclusion by “1”, and not inclusion by “0”. Then we just need to write one digit for each of the positive integers:

10010101001011101010 ...

So, a full Boolean for positive integers will look something like this:

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

It’s familiar. We are back to the Cantor set of infinite binary strings. Recall that diagonalization showed that this set has more power than integers. Cantor's theorem says the same thing, but only with respect to Boolean.

Too many bits

A sequence of zeros and ones reminds us of a stream of bits. If a bulean can be written as a sequence of bits, is it possible to somehow describe it in information terms?

Well then. Consider a boulean as a measure of the information capacity of a set. We saw that a set of three elements {x, y, z} can be used to create eight different subsets. It’s the same as three bits in a computer can express eight numbers. Such equivalence will be preserved for any finite set. And by Cantor’s Theorem - for the infinite too.

Check it out. We have a screen from a countable infinity of pixels. Pixels suit us, because they are needed just to display information. Let them take only two colors - white (on) and black (off).

Turn on the computer. The screen will display a bitmap. It is defined as a set of white pixels - which will be a subset of the whole screen. Of course, when using a computer, the image changes, and we get different subsets of pixels.

So: how many bitmaps can be displayed on a screen with an infinite number of pixels? That is, what is the information capacity of such a screen?

Since any selected image is represented by a subset of pixels, the set of all possible images is the set of all possible subsets of pixels, that is, a boulean. A boolean of a countable set is an uncountable set.

It turns out that, despite the fact that our screen can only contain a countable infinite set of pixels, it can display an uncountable infinite set of images. If you need a presentation of many endless binary strings, then take such a screen, because it will be able to display them all.

Well, otherwise, just update the display to 4K. He will have a lot of pixels.

Reader Exercise

If we build our screen from an infinite number of pixels of a given size that make up an infinite grid - will there be more pixels on this screen than on our original, less, or the same?