Математика · объяснение и практика
Почему все бесконечные двоичные последовательности нельзя перечислить
Как диагональная конструкция опровергает перечисление всех бесконечных двоичных последовательностей и почему увеличение списка не устраняет построенный контрпример.

В теме Доказательства и комбинаторные модели · Учебная карта
В маршруте Множества, отношения и мощности · 10 тем
Главная мысль
Для любого предполагаемого списка бесконечных двоичных последовательностей можно изменить диагональные биты и получить последовательность, отличающуюся от каждой строки хотя бы в одном месте.
Какой список пытаются построить
Предположим, все бесконечные последовательности нулей и единиц удалось разместить по натуральным номерам. Каждая строка бесконечна, и у каждой есть первый, второй и любой следующий бит. Список тоже бесконечен по вертикали. Требование полноты означает, что любая допустимая последовательность должна оказаться некоторой его строкой.
Обозначим бит в строке n и позиции n через aₙₙ. Построим новую последовательность b, выбрав bₙ=1−aₙₙ. В каждой позиции это по-прежнему ноль или единица, значит объект допустим. Для его задания не требуется закончить бесконечное вычисление: правило однозначно определяет любой запрошенный конечный номер бита.
Почему не подходит ни одна строка
С первой строкой b расходится в первой позиции, со второй — во второй, с произвольной строкой k — в позиции k. Значит b не равна ни одной строке списка. Довод не утверждает, что b отличается от каждой строки во всех позициях; одного гарантированного различия для каждой пары достаточно, чтобы исключить равенство.
Для наглядности пусть первые диагональные биты предполагаемого списка равны 0,1,1,0. Тогда b начинается с 1,0,0,1. Продолжение определяется оставшимися диагональными битами. Такой конечный фрагмент сам по себе не доказывает теорему: решающим является общее правило для любого номера строки, включая ещё не выписанные.
Пример
Предполагаемый полный список имеет диагональные биты a₁₁=1, a₂₂=0, a₃₃=1. Как начинается отсутствующая последовательность и чем она отличается от третьей строки?
Начало b равно 0,1,0. В третьей позиции у b стоит 0, а у третьей строки — 1. Значит b не является третьей строкой независимо от остальных её битов.
Что именно установлено
Если добавить найденную b в начало списка, получится другой список, к которому та же конструкция применится заново. Поэтому речь не о случайно пропущенном элементе одного неудачного перечисления. Произвольность исходного списка показывает невозможность полного перечисления по натуральным номерам. Множество таких последовательностей несчётно.
Двоичные последовательности здесь рассматриваются как самостоятельные объекты, а не как записи действительных чисел. Это избегает вопроса о двух позиционных записях одного числа, например хвосте из единиц и альтернативном хвосте из нулей. Для доказательства несчётности числового промежутка нужно отдельно учесть неоднозначность записи либо построить соответствие без неё.
От чтения к действию
А теперь — вы
Частые вопросы
Означает ли доказательство, что нельзя перечислить никакие последовательности?
Нет. Можно перечислить счётное подмножество. Невозможно включить в один такой список абсолютно все бесконечные двоичные последовательности.
Почему достаточно одного отличающегося бита?
Равенство последовательностей требует совпадения во всех позициях. Одно различие уже опровергает равенство двух объектов.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как взаимно однозначное соответствие доказывает равенство количеств
Как доказать равенство количеств без прямого перечисления, построить обратное соответствие и заметить потерянные или склеенные объекты при кодировании.
Открыть темуПочему множество всех подмножеств имеет два в степени n элементов
Почему все подмножества образуют новый набор из двух в степени n элементов, как кодировать выбор битами и что происходит при пустом исходном множестве.
Открыть тему