На прошлой неделе я обновил свои мониторы. Выбросил 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К. У него будет очень много пикселей.
Упражнение для читателей
Если мы построим наш экран из бесконечного числа пикселей заданного размера, которые составят бесконечную сетку – будет ли на таком экране пикселей больше, чем на нашем изначальном, меньше, или столько же?
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Комментарии (126)
michael_vostrikov
01.06.2015 05:47На самом деле, во множестве бесконечных двоичных строк есть 2 взаимно не пересекающихся множества:
0000(0) 1000(0) 0100(0) 1100(0) ... ... 0111(0) 1111(0)
и
1111(1) 0111(1) ... ... 1100(1) 0100(1) 1000(1) 0000(1)
Каждое из них счетно, и может быть соспоставлено множеству целых чисел (особено наглядно это видно по первому). Бесконечная диагональная строка нулей из первого множества в инвертированном виде принадлежит второму множеству.
EndUser
01.06.2015 06:27Итого бесконечное множество двоичных дробей счётно? Мы можем произвести нумерацию натуральными числами так, что нечётные индексы нумеруют последовательно строки первого множества, чётные индексы — второго.
michael_vostrikov
01.06.2015 06:44Хм… Да, вы правы. Задумался о целых числах, и упустил из виду, что могут быть строки вида 0000(01), или вообще непериодические. Хотя, если под дробью подразумевать отношение двух целых чисел a / b, то это множество счетно.
Duduka
01.06.2015 07:17Конечно — счетно, мы разбиваем все части отрезка на две части, «число» — это индекс в этом разбиении( 0- исходный, (1,2) — первое разбиение, (3,4,5,6) — второе...), мы не можем разбить отрезок на дробное количество частей, поэтому и счетно.
ignat99
01.06.2015 07:52-910 000 следующее за ним и есть бесконечное число. А разрешение не заметное глазу дисплеев нужно будет для создания голограмм на базе этих дисплеев и соответственно 3D, 4D, 5D, etc…
Вот если сейчас биты винчестера посчитать затраченные на будущее видео в 6D, вот там точно будет бесконечность сравнимая с числом битов в дата — центрах Google :-)
mwizard
01.06.2015 10:00Позвольте уточнить, что в вашем понимании 4D, 5D и 6D?
fshp
01.06.2015 10:24+10Брызги, тряска и пуки (уж простите за откровенность).
belkamax05
01.06.2015 15:04+1Брызги, тряска и пуки (уж простите за откровенность).
Главное порно в таком режиме не смотреть
ignat99
01.06.2015 12:11Да я в рекламе читал телевизоров. ;-) А так вообщем так теория. А так теоретическая часть практики. А так прикладная часть «делаем электрочайник». Далее выход на инженерное Чарт-Флоу редактирование физических моделей.
Другими словами: 3 измерения, 4 глубина для матрицы, 3 оси для цвета. Можно это слегка упростить октонионами.
По теории есть видео выступление. Спасибо за внимание.
smilepavel
01.06.2015 08:39+2Автор, как и многие другие, путает два понятия 4K и UltraHD. Разрешение 3840 на 2160 пикселей называют UltraHD (UHD) и используют в потребительской технике (например в упомянутых в статье мониторах). Под названием 4K скрывается разрешение 4096 на 2160 пикселей, оно используется в профессиональных устройствах для кинематографа.
AYrm
01.06.2015 09:044096 на 2160 почти 9 мегапикселей. Это максимум, что можно вытянуть из 35 мм кадра.
vedenin1980
01.06.2015 09:09-6Что-то я не вкурил с доказательством несчетности бинарных строк, известен алгоритм преобразования любой двоичной строчки в десятичное число (тот который любой программист проходит на 1 курсе), соответственно всегда можно сделать биекцию любого множества двоичных строчек на множество натуральных чисел. Тут явно проблема подбора биекции одного множества на другое.
Несчетность вещественных чисел понятна, а вот несчетность двоичных чисел (при том что это по сути другая запись натуральных чисел) совершенно нелогична для меня.
zagayevskiy
01.06.2015 09:38+6известен алгоритм преобразования любой двоичной строчки в десятичное число (тот который любой программист проходит на 1 курсе)
Уточнение — любой конечной двоичной строки. А здесь речь о бесконечных. Разные вещи немного;)
topa
01.06.2015 13:23А если модифицировать алгоритм и разворачивать двоичное представление неотрицательных чисел справа-налево, добавляя справа нули:
0 = 000(0)
1 = 100(0)
2 = 010(0)
3 = 110(0)
4 = 001(0)
5 = 101(0)
…
Достаточно счётно?)ignat99
01.06.2015 13:36Извините если мой ответ рефлективный и ассоциативный (в гуманитарном смысле этих слов), но Кантор всё таки математик а не физик. Физик бы не стал утверждать со 100% вероятностью что есть физическая возможность точно провести измерение количества рабочих пикселов на экране или количество битов во всём множестве хранилищ данных. Так же физик стал бы учитывать измерение ситуации во времени.
В итоге бы всё свелось к измерению изменения скажем температуры посредством отклонения стрелки, которая закреплена на магнитной катушке. Ну или тонкие измерения через спектрограф. А хороший физик, ещё бы предварительно провёл серию оценок и последующих измерений отдельных частей системы и их взаимного влияния.
ildarz
01.06.2015 14:03+1Вы посчитали не все бесконечные двоичные строки, а их подмножество — строки, у которых справа бесконечное количество нулей. :)
topa
01.06.2015 14:11Ставлю 100 рублей и шоколадную медальку, что Вы не сможете найти ни одного элемента из множества строк бесконечной длины из нулей и единиц, для которого не получилось бы подобрать единственное неотрицательное число по предложенному выше правилу.
Обратная однозначность, кстати, тоже должна работать, для биективности отображения.ildarz
01.06.2015 14:19Я не думаю, что ваш приз заинтересует Кантора, а мне за чужие заслуги его получать как-то неудобно. Диагонализация прямо в статье же описана, что именно в её алгоритме непонятно?
zagayevskiy
01.06.2015 14:52+3Могу указать способ подобрать строку бесконечной длины, которую вы не занумеруете не только своим способом, но и любым другим. Более того, я процитирую:
если мы в n-ной строке выберем n-ную цифру и составим из них новое бесконечное число, при этом заменяя 0 на 1, а 1 на 0, то мы получим новую строчку
…
Полученная строка тоже будет бесконечной и двоичной. Так что она будет принадлежать к нашему множеству. Но её не будет в биекции. Почему? Потому, что мы именно так её построили: новая строка отличается от любой строки из нашего списка минимум на 1 символ.
Решайте, кому вы должны шоколадку, мне, SLY_G или же Кантору…
Тут, видите ли, всё дело в бесконечности. Вам придётся либо понять это, либо просто смириться=)topa
01.06.2015 14:59Точно! Спасибо, zagayevskiy! Строка из всех единиц не найдет, куда ей отобразиться по данному мною правилу! Да, нужно всегда проверять граничные случаи, в них ведь вся соль)
Пишите номер телефона/электронного кошелька для отправки денег и адрес для отправки шоколадной медальки в ЛС :)zagayevskiy
01.06.2015 15:07Более того, потеряются все строки, заканчивающиеся на бесконечное число единиц (как-то неуклюже звучит, но смысл вроде понятен).
Пожертвуйте на какой-нибудь опенсорс, а шоколадку отдайте первому попавшемуся ребенку на улице. Несите в мир добро=)vedenin1980
02.06.2015 00:02Штука в том что доказано что множество всех целых чисел тоже счетно (да, это против интуиции, но это факт), следовательно возможен следующий алгоритм, у нас есть бесконечное множество нулей и единиц, если множество начинается с 1 это обычное двоичное число, которое можно преобразовать в десятичное число, если множество начинается с 0, мы инвертируем первый символ на 1, получим обычное двичное число и запишем его обычным отрицательным десятичным числом. У меня получается вывод — либо множество целых чисел несчетное, либо множество бесконечных нулей и единиц тоже счетное. Если я не прав, покажите где.
vedenin1980
02.06.2015 00:08На всякий случай, сумма степеней двойки это вычислимое число (то есть число которое всегда может быть однозначно получено по заданному алгоритму), а вычислимые числа тоже счетные.
vedenin1980
02.06.2015 00:28-1Или другой вариант, построим некое множество (1):
1: 10010101001010101010…
2: 01001010100101001001…
3: 10010011110001001000…
4:…
и построим второе множество (2):
-1: 011010101101010…
-2:…
Каждый элемент которого будет инвертирован относительно множества (1), в результате невозможно будет построить диагональным методом такое число которое бы гарантировано не существовало во объединении множеств (1) и (2).zagayevskiy
02.06.2015 04:24Множество целых нумеруется очевидным образом:
0:0
1:1
2:-1
3:2
4:-2
…
Объединение ваших множеств нумеруется точно таким же образом, после чего производится диагонализация. Начало искомого числа будет таким:
001010...(продолжайте ваши множества, я продолжу диагонализацию)vedenin1980
02.06.2015 08:02Чтобы не копипастить
Вопрос действительно диагонализация работает некоторыми математиками ставится под сомнение и тыц.ildarz
02.06.2015 12:08+1Там автор критикует не доказательство Кантора, а свое собственное понимание вопроса. Сходу — он утверждает, что теорема Кантора доказывается «от противного», тогда как на деле доказательство прямое.
zagayevskiy
02.06.2015 06:32Я вашу мысль не понял до конца, но сдаётся мне, что вы пытаетесь увеличить количество чисел для перечисления «в два раза» и на этом вырулить. Нет, объединение конечного или счётного числа счётных множеств счётно, поэтому всегда можно будет перенумеровать элементы натуральными числами и произвести диагонализацию.
vedenin1980
02.06.2015 07:53-1Смотрите есть последовательность a1 a2 a3 a4… aN, где N стремиться к бесконечности, а каждое число aN принимает значение 1 или 0, её всегда можно представить в виде последовательности aN*2^N + aN-1*2^(N-1)… для aN = 1 и в виде последовательности -(1*2^N + aN-1*2^(N-1)...) если aN=0 (обычный алгоритм перевода двоичного числа в десятичное). Нам известно что любая вычислимая последовательность — счетна, и то что последовательность целых (положительных и отрицательных) тоже счетна. Следовательно бесконечная последовательность a1 a2 a3 a4… aN тоже счетна, так мы установили однозначное соответствие между тремя множествами два из которых счетны.
zagayevskiy
02.06.2015 08:18Вы можете это сделать только для каждого сколь угодно большого фиксированного N. Как только N не фиксировано, вы уже не можете так делать.
vedenin1980
02.06.2015 08:35-1Почему? При N стремящийся к бесконечности, мы получим бесконечное число, однако формула останется верной. Множество степеней двойки и факториалов счетно, даже при бесконечных N. Получается что инверсию значений при диагональном методе делать можно, а перевод из одной системы счисления в другую нельзя? Поставим вопрос там существует ли такое число N, каким большим оно не было, при котором не будет существовать этого однозначного соответствия? Если такого числа нет, значит однозначное соответствие будет и при бесконечном кол-ве элементов.
zagayevskiy
02.06.2015 09:00Формула не останется верной, потому что операция возведения 2 в степень бесконечность не определена, так же как и «бесконечность минус один».
Во второй части утверждения вы снова фиксируете N. Повторюсь, какое бы большое конечное число вы не взяли — всё будет ок. Но с бесконечностью это не прокатит.vedenin1980
02.06.2015 09:25-1lim(2^x) при x -> бесконечности = бесконечности
lim(x) — 1 при х -> бесконечности = бесконечности
операция возведения 2 в степень бесконечность = бесконечности
«бесконечность минус один» = бесконечности
Простейшие пределы же, или я чего-то в этой жизни не понимаю?zagayevskiy
02.06.2015 11:09И при чем тут пределы? Как они вам помогают понумеровать строки?
vedenin1980
02.06.2015 11:28-1Ну, как возведение в степени помешает счетности? Если посмотрите внимательно ссылку увидите, что и {1,1/2, 1/3 ...1/n} и {2, 2^2,2^3,...2^n...} и {1^3,2^3,...n^3,..} счетные множества, которые прекрасно могут быть пронумерованы. Так что ваше замечание «операция возведения 2 в степень бесконечность не определена» совершенно не понятно, прекрасно она определена и множество 2^n счетное.
vedenin1980
02.06.2015 08:50-1Можете написать какое закон математики мешает это сделать? Насколько понимаю все доказательства равенства множеств главное показать что при любом N будет выполнятся условие взаимно однозначное соответствие.
>>Определение. Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если:
>> 1) каждому элементу множества A соответствует только один элемент множества B;
Можно установить такое соотвествие по алгоритму выше — можно? Можно
>> 2) каждый элемент множества B при этом соответствует некоторому элементу множества A;
Можно обратить алгоритм обратно? И получить для любого целого числа свою бинарную строку? Да, можно.
>> 3) разныи элементам множества A соответствуют разные элементы множества B.
Из свойства двоичных чисел это выполняется всегда, для каждой комбинации нулей и единиц будет одно и только одно целое число.
Duduka
02.06.2015 10:10Вы не можете указать спосов (как и Кантор) по следующим причинам: Кантор не указал способ деления(нумерации) отрезков, Кантор не указал способа отличия различных сечений, Кантор не указал способа доказательства полноты своего сечения… по этому, доказав неполноту своего сечения он получает столь странный результат.
Если бы Кантор был программистом, то он запрограммировал три «сумашедшие» бесконечности: перечислить счетное множество нельзя, не описав алгоритма сопоставления объектов и счетного множества; используя «сумашедший» цикл по всему множеству, прокручивает и создает «невозможное» число, не указав способа постоения исходного объекта.
Как математик Кантор ошибся в выборе объектов: имея отрезки, Кантор поименовал их числами, и дальше иперирует ими как числами: на самом деле просто выбирает отличное от исходного разбиение и говорит, что оно иное, возможно( их действительно бесконечное множество ), но мощность их одна и таже — счетное множество.zagayevskiy
02.06.2015 11:16+1Кантору не надо указывать способ, ибо он говорит: «Для любого способа нумерации». Не нужен способ (алгоритм) сопоставления объектов и счетного множества, в доказательстве предполагается, что он есть.
Мне кажется, спорящие не понимают сути. Кантор не предлагает нумеровать бесконечное число строк конечной длины, т.е.
0, 1, 00, 01, 10, 11, 000, 001,…
Такое множество действительно будет счетным. А Кантор предлагает нумеровать бесконечное число строк бесконечной длины. В этом вся соль.Duduka
02.06.2015 16:24«Для любого способа нумерации» — второе действие (выбрать и поменять бит) невозможная операция. Суть в том, что любой отрезок не может быть числом, он бесконечное число раз делим (и любой «бесконечный» индекс обмечает бесконечное количесво подотрезков)
Деление происходит на отрезки
(индекс-заголовок(0)… индекс-заголовок(1)]
и чем глубже (длиннее индекс, поколение) тем мельче отрезки, но никогда не схлопываетяс в точку (счетное множество не имеет верхней грани) и никак не влияет на рассуждение.
А вот если если сменить способ нумерации…
возьмем точку (0.5), построим первое множество: все числа отличающиеся от него на 1 бит, второе: все числа отличающиеся от него на 2 бита, третье… Посторение Кантора рассыпается.
chersanya
02.06.2015 16:35В предложенном вами способе не будет пронумеровано, например, число 0.(10) а также все остальные, которые отличаются на бесконечное количество бит. Одно из них как раз и получится канторовской диагонализацией.
Duduka
02.06.2015 16:38-2они будут, именно по постоению, в множестве с бесконечным множеством отличающихся бит, как и бесконечно-1 и т.д. и каждое мащностью — бесконечность…
chersanya
02.06.2015 17:59+1В множестве натуральных чисел нет таких элементов, как «бесконечность», а тем более «бесконечность — 1» и т.п.
chersanya
02.06.2015 18:02Да это в общем-то и не важно. Вот смотрите, вы каким-то образом (не важно, как) построили нумерацию действительных чисел, так? Всё, фиксируем её и больше не меняем. После этого применим метод Кантора. Он вам даст число, которого у вас нет — всё!
Duduka
03.06.2015 07:59-3На первый вопрос — ru.wikipedia.org/wiki/Интуиционизм… за их подход — всеми лапками, но Кантоповский континум — это классическая математика, в которой — есть.
Второй вопрос — именно! Если плюнуть на математику и пременять вольности (как одностороннюю фиксацию индекса при продолжении перечислиния(… применим метод Кантора ...) ) можно доказать, что любая бесконечность — конечна. Ниже, за меня это сделали…chersanya
03.06.2015 08:15Не понял, какой «первый» вопрос, и «второй»? У меня только один вопросительный знак в той паре сообщений :)
Ваш первый ответ я вообще не понял, если честно. Ну да, есть интуиционизм, но когда явно не указывается подразумевается всё-таки классическая математика.
Второй — не понял, что именно вы имеете в виду под вольностями, но методом Кантора конечно же нельзя доказать то, о чём вы говорите (конечность бесконечности).Duduka
03.06.2015 08:34-31) habrahabr.ru/post/259217/#comment_8444935
Я рад, что в ошибочном сообщении нет даже вопроса… если нужно, то напомню: «в диалоге нет утвердительных фраз, иначе это монолог». Я извеняюсь, за то что помешал самоутвердиться.
2) habrahabr.ru/post/259217/#comment_8444945
см. habrahabr.ru/post/259217/#comment_8444787 без проблем!chersanya
03.06.2015 08:361. Вы действительно думаете, что в классической математике в множестве натуральных чисел есть бесконечность? Тогда действительно не о чем говорить, раз даже определения не знаете.
Duduka
03.06.2015 09:46-3Если кардинальность множества натуральных чисел — бесконечность, очевидно — да, что ваше утверждение — обоюдоострое (да, определения вашего мира — я не знаю), и надеюсь, что меня минует каша сия.
PsyHaSTe
03.06.2015 10:26+1Бесконечность не является числом по определению, о чем тут спорить.
Duduka
03.06.2015 11:30-2Никто не спорит, что у конструктивистов/интуиционистов нет такого понятия, но Вы в ветке классической математики, а «деды» считали что она входит в множество натуральных, и как бесконечно малое — является числом, над которыми определены операции… Поосторожнее с определениями… Вы спутали, видимо, с NaN, но и тут есть алгебры в которых оно — число.
PsyHaSTe
03.06.2015 11:42+2Деды считали аксиомами Пеано, в которых нет никакой бесконечности. И еще раз, бесконечность настолько же число, насколько им является плюс или минус — это просто математический символ. Даже ноль не входит в множество натуральных чисел.
grossws
03.06.2015 18:39У кого как. Иногда входит, если это удобнее в конкретной области. Но это вопрос аксиоматики.
PsyHaSTe
03.06.2015 18:59Есть так называемое «Расширенное множество натуральных чисел», но оно потому так и называется, потому что это другое множество. Про него даже на вики написано.
grossws
03.06.2015 19:06В американской литературе часто под натуральными числами понимают это самое расширенное множество и аксиоматику Пеано формулируют с учётом этого. Удобнее это тем, что появляется нейтральный элемент и получается моноид (полугруппа с нейтральным элементом).
zagayevskiy
03.06.2015 12:04Зачем вы ссылаетесь на мой коммент в подтверждении своей ереси?
Я в нем вам показал, что число, которое вы предложили построить для множества четных чисел, не входит в это множество, в отличии от оригинальной бесконечной строки.
zagayevskiy
02.06.2015 16:38Я не понимаю вас, честно. Опишите свою терминологию, пожалуйста.
По определению, счётное множество это множество, элементы которого можно пронумеровать. Вы его нумеруете, следовательно каждому элементу ставится в соответствие конечное число n. Неважно, каким способом вы это сделаете. Далее вы у n-го элемента инвертируете n-ный символ. Из этих инвертированных символов, в том же порядке собираете новую строку. Всё, это алгоритм построения строки, которой нет в биекции. Вы её так построили, что она отличается от всех других строк.Duduka
02.06.2015 16:43-1Пронумеруйте все четные числа и поменяйте у индекса бит… что получится? Кантор делает тоже самое.
ildarz
02.06.2015 16:50+1У какого индекса? Что у вас за отрезки с «подотрезками»? Вы не могли бы одним комментарием, четко и последовательно изложить, какое именно утверждение вы опровергаете, и каким способом?
zagayevskiy
02.06.2015 17:02А как поменять бит? Как бы вы их не пронумеровали, одно из чисел 2, 4, 6, 8, 10 будет иметь номер больше или равный 5, т.е. надо будет менять как минимум пятый бит, а их максимум 4… Значит добиваем нулями начало? Значит все они имеют «равную» (насколько это применимо к бесконечности) битовую длину? Значит число, которое вы построите, не будет чётным, не будет входить в ваше множество.
Duduka
03.06.2015 07:40Да, тем же методом Кантора, 5ый бит — 0…
Не только не четным, но и натуральным, и… множество счетных — не счетно ) Если позволить такую канторовскую вольность! Просто операция над индексом — только одна: перечисление. Конструирование новых — вольность.zagayevskiy
03.06.2015 07:48Окей и вам. Спорить надоело, вы аргументы не слушаете, а несете какую-то чушь.
Duduka
03.06.2015 08:15-1Вы сами выше доказали, что Кантор ошибся, и при этом я несу чушь? Я все услышал, и меня печалит, что Вы не можете признать заблуждение, которое, в общем никак не влияет на ваше мировозрение.
Mithgol
01.06.2015 12:07-1известен алгоритм преобразования любой двоичной строчки в десятичное число
Если я правильно понял, о каком Вы пишете алгоритме, то надо сказать о нём вот что: он не обеспечивает взаимно однозначное преобразование, так как сперва отбрасывает начальные нули.
Так что при рассмотрении проблемы биекции он может несколько запутать всё дело.
Например, что будет, если диагональная замена Кантора заменит в первой строке ноль (который отбрасывался бы) на единицу? А если наоборот?vedenin1980
02.06.2015 00:00-1Штука в том что доказано что множество всех целых чисел тоже счетно (да, это против интуиции, но это факт), следовательно возможен следующий алгоритм, у нас есть бесконечное множество нулей и единиц, если множество начинается с 1 это обычное двоичное число, которое можно преобразовать в десятичное число, если множество начинается с 0, мы инвертируем первый символ на 1, получим обычное двичное число и запишем его обычным отрицательным десятичным числом. У меня получается вывод — либо множество целых чисел несчетное, либо множество вещественных чисел счетное. Докажите где я не прав.
vedenin1980
02.06.2015 00:10-1На всякий случай, сумма степеней двойки это вычислимое число (то есть число которое всегда может быть однозначно получено по заданному алгоритму), а вычислимые числа тоже счетные.
zagayevskiy
02.06.2015 06:38+2Я вас, наверное, удивлю, но и множество рациональных чисел тоже счетно, а их, интуитивно, «еще больше», чем целых. Ну и что?
fshp
01.06.2015 10:26+3Значит, полный булеан для положительных целых будет выглядеть как-то так:
Лучше и не скажешь.
Sadler
01.06.2015 10:32+12Но что, если они не перестанут? Что, если они будут делить пиксели бесконечно?
Тогда планковская длина быстро вернёт замечтавшихся математиков на грешную Землю.PsyHaSTe
02.06.2015 13:36Планковская длина не является минимально возможной, хотя скорее всего, какая-то дискретная величина существует, но не все теории её предсказывают.
bachin
01.06.2015 12:23+1Количество пикселей на экране — это не «счетное» множество, а «конечное» множество.
Ибо число атомов на нашей планете «конечно», что задаёт верхнюю границу для мощности множества пикселей.
deniskreshikhin
01.06.2015 13:31-2Любое конечное множество счётно.
fshp
01.06.2015 13:37+1Нет. Не существует биекции между конечным множеством и множеством натуральных чисел.
deniskreshikhin
01.06.2015 13:48Ну это зависит от определения.
In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a natural number.
Some authors use countable set to mean infinitely countable alone.[1] To avoid this ambiguity, the term at most countable may be used when finite sets are included and countably infinite, enumerable, or denumerable[2] otherwise. Countable_set
Но обычно такое обговаривается, если под счётным имеется ввиду исключительно бесконечные счётные. А т.к. об этом речи не шло, то я предположил что имеются ввиду просто счётные множества, т.е. которые можно пересчитать, без предположения об их конечности или бесконечности.bachin
01.06.2015 14:27-1Речь о бесконечном множестве шла. Взгляните на сабжект.
deniskreshikhin
01.06.2015 20:46-1Да не важно о чем шла речь, надо уточнять определение перед тем как им пользоваться. Понятие счётность не подразумевает бесконечности, точно так же как натуральные числа не подразумевают ноль и т.д.
bachin
02.06.2015 11:48+1> Понятие счётность не подразумевает бесконечности
Извините. В русской википедии (другого компетентного источника знаний под рукой не было) недвусмысленно сказано:
> В теории множеств, счётное мно?жество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами.
sci_nov
03.06.2015 04:57Странно, так тогда всё можно пронумеровать, только нумерация никогда не завершится… Всё-таки лучше в Infinity не лезть. Никакое устройство всё равно не работает с такими вещами (АЦП — конечные, алфавит — конечен и так далее). Это не конструктивно.
zagayevskiy
03.06.2015 05:17ОМГ. Учите матчасть.
sci_nov
03.06.2015 19:16Infinity и пиксели монитора — не пересекающиеся вещи. «Экран с бесконечным количеством пикселей» — это несуществующая (ни в теории, ни на практике) вещь, здесь ничего учить-то и не надо.
deniskreshikhin
03.06.2015 11:20Конечно, теперь очевидно что существует два определения.
Но согласитесь, что упрёк
Количество пикселей на экране — это не «счетное» множество, а «конечное» множество.
выглядит странным. Когда понятие счётность трактуется по разному, в частности сам Кантор под счётными подразумевал как раз таки в т.ч. и конечные множества.
bachin
04.06.2015 11:23-1> Конечно, теперь очевидно что существует два определения.
Бесконечно. Неочевидно. Не существует. :)
Определить можно и восьмью способами. Надо использовать слова русского математического языка по своему назначению. Так, чтобы было понятно *большинству* и как написано в *большинстве* учебников. Есть множества по мощности конечные, есть множество счётное (оно не является конечным по определению конечности), есть несчетные (ни те, ни другие).
Определение конечного множества (пишу не заглядывая в учебник, прошу простить если ошибусь):
Множество равномощное множеству натуральных чисел, среди которых есть максимальное число.
Сами термины, которые мы вкладываем в понятие «бесконечность» — это скорее всего «неопределяемые понятия», которые нельзя выразить с помощь других терминов. Вот мощность множества точек отрезка вроде как бесконечна, хотя сам отрезок имеет «концы». Тут скорее смысл «больше, чем бесконечный»zagayevskiy
04.06.2015 13:16Определение конечного множества (пишу не заглядывая в учебник, прошу простить если ошибусь):
Wat? Не прощаю. Не заглядываете в учебник — включайте мозг. Множество отрицательных целых чисел, это раз. Второе, кто вам сказал, что вы можете сравнивать элементы множества? Третье — конечное множество, это множество, в котором конечное число элементов. А равномощное — это значит, что между этими множествами существует биекция.
Множество равномощное множеству натуральных чисел, среди которых есть максимальное число.bachin
04.06.2015 14:00Не понял ваших претензий. Может быть я что-то забыл с школьных времен?
Отрицательные целые цисла не являются натуральными. Если вас что-то покоробило — приведите контр-пример. Я написал выше по сути дела что конечное множество — это множество, которое может быть поставлено во взаимно-однозначное соответствие какому-то множеству натуральных чисел с максимумом. Чем не нравится определение?
> конечное множество, это множество, в котором конечное число элементов
Вам не кажется, что определять понятие «конечный» с помошью прилагательного «конечный» как-то некузяво? :) Ах, да. Понятия «натуральное число», «множество», «соответствие», «максимум множества натуральных чисел» не просите меня определить. Их надо почувствовать :)zagayevskiy
04.06.2015 14:24+2Вы изменяете свои формулировки на ходу.
Определение конечного множества (пишу не заглядывая в учебник, прошу простить если ошибусь):
Я вам привел в пример множество отрицательных целых, которое равномощно множеству натуральных и имеет максимум (-1).
Множество равномощное множеству натуральных чисел, среди которых есть максимальное число.
конечное множество — это множество, которое может быть поставлено во взаимно-однозначное соответствие какому-то множеству натуральных чисел с максимумом.
Тут что-то вроде начинает проясняться, судя по всему, вы имеете в виду подмножество натуральных, ибо не бывает «какого-то множества натуральных чисел», оно одно — N. Тем не менее, так становится понятнее, что вы имеете в виду, и это даже похоже на правду. Но, вы привлекаете больше понятий, чем требуется, ИМХО, следует отдать предпочтение более простой формулировке.
Вам не кажется, что определять понятие «конечный» с помошью прилагательного «конечный» как-то некузяво? :)
Я не определял понятие «конечный», я определял понятие «конечное множество». Можно так же спросить: «Вам не кажется, что определять понятие „множество“ с помощью существительного „множество“ как-то некузяво?» (оффтоп, что такое кузяво?:) ).
Мне не нужно определять понятие «конечный», оно очевидно. Определение лишь разъясняет смысл словосочетания «конечное множество» — оно не находит «на конце чего-то», это не «последнее множество»(конец), это всего лишь множество, у которого конечное число элементов.
deniskreshikhin
04.06.2015 15:13Математика международная наука, большинство учебников по теории множеств англоязычных авторов. Само слово счётность калька с английского countable. Поэтому упрёк так и остаётся непонятен.
То что вы подразумеваете под счётностью именуется строгой счётностью (most countable). Но это определение не очень продуктивно на самом деле, и это легко продемонстрировать.
Например, можете ли вы сказать является ли последовательность чисел Мерсенна счётной? (используя ваше определение)
Определение конечного множества (пишу не заглядывая в учебник, прошу простить если ошибусь):
Множество равномощное множеству натуральных чисел, среди которых есть максимальное число.
Мощность конечных множеств измеряется ординалами, а бесконечных кардиналами. Эти числа несравнимы. (или я не понял фразы)
Alex222
01.06.2015 15:09Статья== разжевывание на пальцах- красивое- вещей из теории множеств, про мощности множеств и это все, в МАИ это на втором курсе проходили, все достаточно просто.
Там и про мощность континуума было, и про отображения
lexfrei
01.06.2015 16:03У меня одного в таблицах текст не виден? Если нажать на cmd+r, то он «мигнёт» не секунду и пропадёт опять.
Последний стабильный хром на osx и win.
ogamespec
01.06.2015 19:43+3Разрешение монитора будет бесконечным, если размер пикселя сделать таким, который не видно невооруженным глазом.
Глаз то ведь тоже дискретный, количество колбочек/палочек ограничено.
Я где-то читал что глаз может в принципе задетектить отдельный фотон, но что-то сомневаюсь)
Garrett
01.06.2015 22:49+1и стоить оно тоже будет бесконечно, как и время производства. даже после покупки вы будете до бесконечности выплачивать его стоимость и его до бесконечности будут строить
vvagr
02.06.2015 00:54+2Рекомендую ряд полезных утверждений: множество рациональных чисел счётно, множество пар рациональных чисел счётно, между любыми двумя числами есть рациональное число, тем самым разбиение любой фигуры на бесконечное множество квадратиков тоже содержит не более счётного числа элементов.
Две этих разных мощности довольно часто встречаются, поэтому у них есть свои названия.
Есть, но вы одно из них не знаете :-(
Множество с такой же мощностью, как у множества бесконечных двоичных строк, называется несчётным.
Континуум оно называется.grossws
02.06.2015 16:49самым разбиение любой фигуры на бесконечное множество квадратиков тоже содержит не более счётного числа элементов
Если в разбиении используются квадраты со стороной, длина которой по отношению к референсному отрезку представляется рациональным числом.
sci_nov
02.06.2015 11:05И неважно, как далеко мы зайдём – всегда найдётся элемент в одном множестве, соответствующий элементу в другом. Поэтому мощность этих множеств одинаковая. Звучит странно, но это так.
Действительно странно… и в этом вся соль и ошибка Кантора. Нельзя свойства конечного (счётность) переносить на бесконечное. Infinitum Actu Non Datur. Если интересно, прочтите интервью проф. Стахова А.П. в журнале De Lapide Philosophorum, DLP (IV) 2015.pdf, по ссылке de-lapide-philosophorum.umi.ru/filemanager/download/118ildarz
02.06.2015 12:05+2Говоря о математической ошибке, принято приводить доказательство, а не интервью в довольно странном журнале. :)
soltpain
Это же пятничный пост!