Screen with an infinite number of pixels

Last week I updated my monitors. I threw out the Apple Cinema Display and in their place took 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 dekstopov. Fonts look wonderful.

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


But what is "4K"? With a light hand of marketers, this is a screen of 3840 by 2160 pixels (3840 is almost 4000). On each side, the resolution is twice as large as 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 like you cut each pixel both vertically and horizontally. That is, on a 4K screen 4 times more pixels than HDTV.

And, characteristically, no one is going to stop at this, 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 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: 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 their number infinite? Infinity - this is "plenty"? Yes?


Georg Cantor looks at you as beginning mathematicians

Not really. When the German mathematician Georg Cantor began his activities in the 1860s, infinity has been used in mathematics for quite some time. But with them there were always some vagueness and understatement. Cantor explained everything.

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

OK, we cannot count the infinite multitude 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 "here are so many fingers." That is, we compare the number of known set - the number of fingers. The number of elements of a set is also called its capacity. If we have a set of a certain power, we can compare it with other sets, comparing the elements of one set with the elements of another. If the two sets have a one-to-one correspondence of all the elements, their sets are equal.

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

And if we have two bags of objects and we need to compare, do they contain the same number of them, without counting them? We can take out one piece from each bag until they run out 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 Cantor thought so: although we cannot count the infinities, we can compare their powers. If they coincide, then we can make a one-to-one correspondence (bijection) from the 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 more - all positive or only even. One could simply answer that there are more positive ones, because the set of positive ones includes both even and odd ones.

But it is not. A bijection shows that we can put into correspondence sets of positive numbers and even numbers:

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

And no matter how far we go - there is always an element in one set that corresponds to an element in another. Therefore, the power of these sets is the same. It sounds strange, but it is.

Big infinity

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

Cantor started with an infinitely long binary string:

10010101001011101010 ...

Then he thought about the set of all such lines:

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

And he 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: 10010101001010101010 ...
2: 01001010100101001001 ...
3: 10010011110001001000 ...
four:…

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

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

1: 1 0010101001010101010 ...
2: 0 1 001010100101001001 ...
3: 10 0 10011110001001000 ...
four:…

001 ...

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

In other words, in any way to match the set of infinite binary strings with the set of positive integers, you can always construct such a line that is not included in the bijection. That is, a bijection is impossible. Therefore, although both sets are infinite, the power 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 capacity as a set of infinite binary strings is called uncountable.

Back to the screen with an infinite number of pixels

Remember that pixels are divided on the screen 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:



Step 2 - Vertical



On 3, we divide everything horizontally



4 - vertical



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? An infinite number. Moreover, since we have made a countable infinite number of cuts, we must 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 lines.

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

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

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

0...

1...

In the second step, we made a vertical cut. Then, if our second number is 0, we select the left half of the pixel. If 1 is 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 cells will decrease, and binary lines will increase. And we get 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, then the number of pixels is uncountable.

Cunningham Act: the best way to get an answer online is to publish the wrong

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

Find a gap in the reasoning. I stated that the pixel cutting technology would allow each pixel to be assigned to each infinite binary string. Several readers tried to find a contradiction with the help of diagonalization, saying that you can think of a way to make a line that does not correspond to a pixel. But it is not.

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

Although each line is infinite, it corresponds to the exact number - a certain point on the screen. This should not confuse you. For example, remember that the number 1/3 is on the segment between 0 and 1. But the decimal notation of this number is infinite 0.3333 (3). The more digits we add, the closer to 1/3. And while 1/3 is the limit of this series of numbers after the decimal point, it will never be recorded exactly. In a sense, the limit is “beyond” a 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 add 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.

By adopting the idea that each pixel is an approximation, we can use our design to recalculate pixels. Let's enumerate the initial pixel 1.

1

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

10

11

100 101

110 111

Jump to step 4:

10000	10001	10100	10101
11000	11001	11100	11101

Thus, you can assign a unique integer (whether binary or decimal) to each pixel. The total number of pixels is infinite, but any infinite subset of positive integers can be found a bijection with many positive integers. Therefore, there will be no more pixels than integers.

Bonus

What about endless binary strings? It turns out that there are more of them (since their set is uncountable) than the pixels on the screen (since their set is countable). Can we put these two infinities in any correspondence? I think so.

Cantor's theorem says that for any set of objects, the set of their subsets is always greater (that is, it has more 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 a set, or boolean.

How big is a boolean? Creating a subset, we essentially 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 (to accept and not to 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 extent of the number of elements of 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, will also have more power than a set of positive integers.

This idea, with the fact that one is more than another, still seems strange and abstract. Let's go back to our screen with an infinite number of pixels. Let's see how we can denote these subsets. Each subset is a set of solutions to include / not include, therefore we can designate 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 complete boolean for positive integers will look something like this:

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

Familiar. We returned to the Cantor set of infinite binary strings. Recall that the diagonalization showed that this set has more power than whole numbers. Cantor's theorem says the same thing, but only in relation to the boolean.

Too many bits

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

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

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

Turn on the computer. There will be a bitmap on the screen. 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 the 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, boolean. And the 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 number of pixels, it will be able to display an uncountable infinite number of images. If you need a presentation of a set of infinite binary lines - then take such a screen, because it will be able to display them all.

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

Reader Exercise

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