Математика · объяснение и практика

Почему все бесконечные двоичные последовательности нельзя перечислить

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Множества, отношения и мощности · 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 в начало списка, получится другой список, к которому та же конструкция применится заново. Поэтому речь не о случайно пропущенном элементе одного неудачного перечисления. Произвольность исходного списка показывает невозможность полного перечисления по натуральным номерам. Множество таких последовательностей несчётно.

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

От чтения к действию

А теперь — вы

Если диагональ предполагаемого списка начинается 1,1,0,1, какой префикс получает последовательность bₙ=1−aₙₙ?

Частые вопросы

Означает ли доказательство, что нельзя перечислить никакие последовательности?

Нет. Можно перечислить счётное подмножество. Невозможно включить в один такой список абсолютно все бесконечные двоичные последовательности.

Почему достаточно одного отличающегося бита?

Равенство последовательностей требует совпадения во всех позициях. Одно различие уже опровергает равенство двух объектов.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться