Экран с бесконечным количеством пикселей

На прошлой неделе я обновил свои мониторы. Выбросил Apple Cinema Display и на их место взял 4К-мониторы от Dell. Как печатнику, мне понравился предыдущий апгрейд с чёрно-белых до grayscale-мониторов в 90-х годах. Но 4К – ещё лучше. Дисплеи высокого разрешения уже пришли на смартфоны и планшеты. Приятно, что они появляются и у ноутбуков и декстопов. Шрифты выглядят чудесно.

Хотя – хорошие шрифты выглядят чудесно. Плохие выглядят хуже – они уже не спрячутся за плохо различимыми гранями грубых пикселей. Если вы работаете с текстом – читаете, пишете, программируете, рисуете (а это охватывает чуть ли не все профессии), то апгрейд на 4К стоит того.



Но что есть «4К»? С лёгкой руки маркетологов, это экран размера 3840 на 2160 пикселей (3840 – это ну почти 4000). По каждой из сторон разрешение в два раза больше, чем у HDTV, то есть 1920х1080.

Спервоначалу люди говорили, что у 4К-экранов «в два раза больше пикселей». На самом деле, если вы удвоите количество пикселей линейно, это всё равно, что вы разрежете каждый пиксель как по вертикали и по горизонтали. То есть, на экране 4К в 4 раза больше пикселей, чем у HDTV.

И, что характерно, на этом останавливаться никто не собирается, на горизонте уже дисплеи 7680 х 4320, известные как 8К. С другой стороны, разрешение, воспринимаемое человеческим глазом, имеет границы. Переход на 4К заметен. На 8К – менее заметен. В какой-то момент нужно будет перестать делить пиксели.

Но что, если они не перестанут? Что, если они будут делить пиксели бесконечно? Сколько тогда пикселей будет на экране?

а) по количеству положительных целых чисел
б) меньше
в) больше

Если вам не интересна математика, тогда итог статьи такой: купите 4К-монитор. Не стоит благодарности.

Сравниваем бесконечности

Для начала вас может удивить пункт в), в котором говорится о числе, большем, чем количество положительных целых чисел. Разве их не бесконечное число? Бесконечность – это ведь «сколько угодно»? Да?


Георг Кантор смотрит на вас, как на начинающих математиков

На самом деле, нет. Когда немецкий математик Георг Кантор начинал свою деятельность в 1860-х, бесконечности использовались в математике уже довольно долго. Но с ними всегда были некоторые неясности и недосказанности. Кантор всё объяснил.

Один из вопросов, которые он изучал – одинаков ли размер у всех бесконечных множеств? Но как сравнить бесконечные множества? Если б у нас были конечные множества, мы бы могли их пересчитать. У кого больше элементов, тот и победил.

ОК, мы не можем пересчитать бесконечное множество напрямую. Но представим, что мы не можем пересчитать конечное множество напрямую. Как мы сможем представить, например, число пять? Можно показать руку и сказать «вот столько пальцев». То есть, мы сопоставляем количество известному множеству – количеству пальцев. Количество элементов множества также называется его мощностью. Если у нас есть множество определённой мощности, мы можем сравнивать его с другими множествами, сопоставляя элементы одного множества элементам другого. Если у двух множеств найдётся однозначное соответствие всех элементов – их множества равны.

Например, мы хотим узнать мощность множества пальцев на ноге. Мы можем прикоснуться каждым пальцем руки к пальцу на ноге. Поэтому мы заключаем, что мощности множеств пальцев на руке и ноге равны.

А если у нас есть два мешка объектов и нам надо сравнить, содержат ли они одинаковое их количество, не пересчитывая их? Мы можем вынимать по одной штуке из каждого мешка, пока они не закончатся в одном из мешков. Если в этот момент они закончатся и в другом – их мощности равны. И этот метод не зависит от количества вещей.

Вот и Кантор так подумал: хотя мы не можем пересчитать бесконечности, мы можем сравнить их мощности. Если они совпадают, тогда мы можем составить из двух множеств взаимно однозначное соответствие (биекцию). Или же, мы можем доказать, что не существует такого соответствия – тогда мощность одного из множеств больше.

Биекция – это простой, но и полезный инструмент для работы. Например, мы можем узнать ответ на вопрос, каких целых чисел больше – всех положительных или только чётных. Можно было бы просто ответить, что положительных больше, потому, что множество положительных включает как чётные, так и нечётные.

Но это не так. Биекция показывает, что мы можем поставить в соответствие множества положительных чисел и чётных:

1, 2, 3, 4,…
2, 4, 6, 8,…

И неважно, как далеко мы зайдём – всегда найдётся элемент в одном множестве, соответствующий элементу в другом. Поэтому мощность этих множеств одинаковая. Звучит странно, но это так.

Большая бесконечность

Чтобы показать, что мощность одного множества больше другого, необходимо доказать, что для них не существует биекции. И Кантор показал, что это возможно. Его доказательство использует диагонализацию и выглядит следующим образом.

Кантор начал с бесконечно длинной двоичной строки:

10010101001011101010…

Потом он подумал про множество всех таких строк:

10010101001010101010…
01001010100101001001…
10010011110001001000…
…

И спросил: а сколько их существует? Очевидно, бесконечное число. И мы можем найти биекцию с положительными целыми числами, просто перечислив все эти строки каким-нибудь способом:

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

Если такая биекция возможна, тогда множество бесконечных двоичных строк имеет ту же мощность, что и множество положительных целых.

И тут внезапно Кантор замечает, что если мы в n-ной строке выберем n-ную цифру и составим из них новое бесконечное число, при этом заменяя 0 на 1, а 1 на 0, то мы получим новую строчку:

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

001…

Полученная строка тоже будет бесконечной и двоичной. Так что она будет принадлежать к нашему множеству. Но её не будет в биекции. Почему? Потому, что мы именно так её построили: новая строка отличается от любой строки из нашего списка минимум на 1 символ.

Иначе говоря, при любом способе сопоставить множество бесконечных двоичных строк со множеством положительных целых чисел, вы всегда можете сконструировать такую строчку, которая не входит в биекцию. То есть, биекция невозможна. Поэтому, хотя оба множества бесконечные, мощность множества бесконечных двоичных строк больше.

Две этих разных мощности довольно часто встречаются, поэтому у них есть свои названия. Мощность множества положительных целых чисел называется счётной. Множество с такой же мощностью, как у множества бесконечных двоичных строк, называется несчётным.

Вернёмся к экрану с бесконечным количеством пикселей

Помните, что у нас на экране пиксели поделены бесконечное число раз? Теперь мы знаем, что наша «бесконечность» относится к счётной бесконечности. Почему? Потому, что мы можем создать биекцию между положительными целыми числами и делением пикселей.

Если мы начнём с гигантского пикселя:



На 1 шаге поделим его пополам по горизонтали:



На 2 шаге – по вертикали



На 3, делим все по горизонтали



На 4 – по вертикали



И т.д.

Каждый разрез соответствует положительному целому числу, поэтому мы получаем биекцию со счётным бесконечным множеством.

И сколько же пикселей у нас получится? Бесконечное число. Более того, раз мы сделали счётное бесконечное число разрезов, мы должны получить счётное бесконечное число пикселей. Или нет?

Может ли быть, что у нас вдруг получится несчётное бесконечное множество пикселей? Давайте попробуем сделать биекцию между количеством пикселей и каким-нибудь несчётным бесконечным множеством. Например, тем же самым множеством бесконечных двоичных строк.

10010101001010101010…
01001010100101001001…
10010011110001001000…
…

Вспомните, что мы делали наш экран, разрезая пиксель то по вертикали, то по горизонтали. Каждую из двоичных строк можно сопоставить конкретному пикселю на экране, используя цифры из строки.

На первом шаге мы сделали горизонтальный разрез. Если первая цифра в строке – 0, мы выбираем верхнюю часть пикселя. Если 1 – нижнюю.

0...

1...

На втором шаге мы сделали вертикальный разрез. Тогда, если наше второе число – 0, мы выбираем левую половину пикселя. Если 1 – правую.

00...

01...

Теперь мы просто повторим этот процесс – цифры будут обозначать верх или низ, затем лево или право. После шага 4:

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

Дальше ячейки буду уменьшаться, а двоичные строки увеличиваться. И мы получим взаимно однозначное соответствие каждого пикселя каждой бесконечной двоичной строке. То есть, мы получим биекцию. И, поскольку количество бесконечных двоичных строк несчётное, то и количество пикселей – несчётное.

Закон Каннингхэма: лучший способ получить ответ в интернете – опубликовать неверный

После первой публикации статьи я получил письма, в которых указывался пробел в рассуждениях. И в конце концов оказалось, что экран с бесконечным количеством пикселей содержит их счётное множество.

Найдём пробел в рассуждениях. Я заявил, что технология резки пикселей позволит назначить каждой бесконечной двоичной строке свой пиксель. Несколько читателей попробовали найти противоречие при помощи диагонализации, говоря, что можно придумать способ сделать такую строку, которая не соответствует пикселю. Но это не так.

Потому, что проблема моей биекции не в том, что она не может пристроить каждую бесконечную двоичную строку, а в том, что она не может пристроить ни одну из них.

Хотя каждая строка бесконечна, она соответствует точному числу – определённой точке на экране. Это не должно вас смущать. К примеру, вспомните, что число 1/3 находится на отрезке между 0 и 1. Но десятичная запись этого числа бесконечна 0,3333(3). Чем больше цифр добавляем, тем ближе к 1/3. И хотя 1/3 является пределом этой серии цифр после запятой, она точно никогда не будет записана. В каком-то смысле, предел находится «вне» серии аппроксимаций.

Так и пиксели в моей конструкции представляют аппроксимации бесконечных двоичных строк, являясь их пределами. Но так как нет способа достроить 0,3333(3) до в точности 1/3, нет способа найти пиксель, пока вы не дойдёте до определённой точки, представленной конкретной бесконечной двоичной строкой. Поэтому моё предположение насчёт биекции было ложным.

Приняв идею того, что каждый пиксель – аппроксимация, мы можем использовать нашу конструкцию для пересчёта пикселей. Давайте пронумеруем начальный пиксель 1.

1

Теперь добавим двоичную цифру каждый раз, когда будем делить пиксель – тем же способом, что и ранее:

10

11

100101

110111

Перепрыгнем на шаг 4:

10000	10001	10100	10101
11000	11001	11100	11101

Таким образом можно поставить в соответствие каждому пикселю уникальное целое число (неважно, двоичное или десятичное). Общее число пикселей – бесконечное, но любому бесконечному подмножеству положительных целых чисел можно найти биекцию с множеством положительных целых чисел. Поэтому пикселей будет не больше, чем целых чисел.

Бонус

А что насчёт бесконечных двоичных строк? Получается, что их больше (т.к. их множество несчётное), чем пикселей на экране (поскольку их множество счётное). Можем ли мы поставить в какое-нибудь соответствие эти две бесконечности? Мне кажется, да.

Теорема Кантора говорит, что для любого множества предметов, множество их подмножеств всегда больше (т.е. имеет большую мощность). Это легко видеть на примере небольшого множества. У множества из трёх элементов {x, y, z} есть восемь подмножеств: {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} и {} (пустое). Это множество подмножеств известно также как степень множества, или булеан.

Насколько велик булеан? Создавая подмножество мы, по сути, принимаем несколько решений по поводу того, включать или нет каждый элемент. То есть, в множестве {x, y, z} есть три элемента, и три решения. А т.к. у каждого решения есть два варианта (принять и не принять), то количество возможных подмножеств 2 * 2 * 2 = 8. То есть, для конечного множества размер булеана будет 2 в степени количества элементов множества.

Хитрость Теоремы Кантора в том, что она работает и для бесконечных множеств. Рассмотрим булеан положительных целых – то есть, все возможные подмножества положительных целых. Булеан сам по себе будет бесконечным множеством, но, по Теореме Кантора, тоже будет иметь большую мощность, чем множество положительных целых чисел.

Эта идея с тем, что одно множество больше другого, всё ещё кажется странной и абстрактной. Вернёмся к нашему экрану с бесконечным количеством пикселей. Давайте посмотрим, как мы можем обозначить эти подмножества. Каждое подмножество – это набор решений включить/не включать, поэтому мы можем обозначить включение через «1», а не включение – через «0». Затем нам надо просто написать одну цифру для каждого из положительных целых чисел:

10010101001011101010…

Значит, полный булеан для положительных целых будет выглядеть как-то так:

10010101001010101010…
01001010100101001001…
10010011110001001000…
…

Знакомо. Мы вернулись к канторовскому множеству бесконечных двоичных строк. Вспомните, что диагонализация показала, что у этого множества мощность больше, чем у целых чисел. Теорема Кантора говорит то же самое, но только по отношению к булеану.

Слишком много битов

Последовательность нулей и единиц напоминает нам поток битов. Если булеан можно записать в виде последовательностей битов, нельзя ли как-то описать его в информационных терминах?

Ну а что ж. Рассмотрим булеан как меру информационной ёмкости множества. Мы видели, что набор из трёх элементов {x, y, z} можно использовать для создания восьми разных подмножеств. Это всё равно, как три бита в компьютере могут выразить восемь чисел. Такая эквивалентность будет сохраняться для любого конечного множества. А по Теореме Кантора – и для бесконечных тоже.

Проверим. У нас есть экран из счётной бесконечности пикселей. Пиксели нам подходят, поскольку они нужны как раз для отображения информации. Пусть они могут принимать только два цвета – белый (вкл) и чёрный (выкл).

Включим компьютер. На экране будет битовое отображение. Оно определяется как набор белых пикселей – который будет подмножеством целого экрана. Конечно, при использовании компьютера изображение меняется, и мы получаем разные подмножества пикселей.

Итак: сколько битовых изображений можно отобразить на экране с бесконечным числом пикселей? То есть, какова информационная ёмкость такого экрана?

Поскольку любое выбранное изображение представлено подмножеством из пикселей, то множество всех возможных изображений – это множество всех возможных подмножеств из пикселей, то бишь, булеан. А булеан счётного множества является несчётным множеством.

Получается, что, несмотря на то, что наш экран может содержать лишь счётное бесконечное множество пикселей, он сможет отображать несчётное бесконечное множество изображений. Если вам понадобится презентация множества бесконечных двоичных строк – то берите такой экран, потому что он сможет все их отобразить.

Ну а в ином случае просто обновите дисплей до 4К. У него будет очень много пикселей.

Упражнение для читателей

Если мы построим наш экран из бесконечного числа пикселей заданного размера, которые составят бесконечную сетку – будет ли на таком экране пикселей больше, чем на нашем изначальном, меньше, или столько же?