Существуют ли несчетные множества?

Материал из synset
Перейти к: навигация, поиск
Перечислимые и разрешимые множества << Оглавление >> Формулы арифметики их номера

Исходным методом Кантора сравнения бесконечных множеств, было установление их равномощности. В основе идеи равномощности лежит понятие соответствия. Если каждый элемент одного множества можно поставить во взаимооднозначное соответствие элементу другого множества, то эти множества равномощны. Соответствие это, на самом деле — некоторый алгоритм, который и производит такую процедуру. Если бесконечное множество равномощно множеству натуральных чисел, то говорят, что оно счетно. На самом деле это означает, что известен алгоритм, который позволяет в некотором порядке перебирать все элементы этого множества и тем самым их нумеровать (ставить в соответствие натуральным числам). Другими словами, это должно быть перечислимое множество.

То, что множества являющиеся подмножествами натурального ряда (например, чётные числа) являются счётными особенного удивления не вызывает. Неожиданнее было то, что можно пронумеровать рациональные числа , которых явно "больше" чем натуральных. И алгоритм тривиален — после сокращения общих множителей необходимо перейти гёделевскому числу , поэтому множество пар перечислимо. Это обратимый алгоритм и по можно восстановить и . Аналогично, используя более длинный ряд простых чисел, можно пронумеровать и любые фиксированные наборы целых чисел.

Оригинальная нумерация Кантора состояла в расположении рациональных чисел в виде таблицы и перечисление их по диагоналям, начиная с левого верхнего угла: ; ; ;... так, что на каждой диагонали равно 2, 3, 4,...

Другой универсальный приём нумерации — это лексографическое упорядочивание (по длине, а при одинаковой длине по алфавиту). Записав рациональное число в виде строки , а целые и в 10-й системе счисления эти строки, очевидно, можно упорядочить, т.е. пересчитать. По этой же причине счётными оказываются алгебраические числа, т.е. корни уравнений с целочисленными коэффициентами. Часть из них (например, ) рациональными не является. Все нерациональные числа мы называем иррациональными.

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

Рассмотрим отрезок прямой, длина которого принята за единицу. Действительное число — это расстояние некоторой точки внутри этого отрезка от левого края (нуля). Как мы можем измерять длину отрезков меньших чем базовый? Можно при помощи геометрических построений (требующих своей аксиоматики) разбить отрезок на равных частей (или соединить одинаковых отрезков, объявив результат единичным).

Если можно выяснять какая точка лежит ближе к нулю, то расстояние выражается при помощи неравенства:

Racional real1.png

Взяв очень большим, можно сколь угодно сильно зажать диапазон неточности (границы неравенства), т.е. приблизить действительное число рациональными с любой заданной ошибкой. Хотя последние определяются только парой целых и , они всюду плотно покрывают отрезок . Какие бы две точки мы не взяли, не важно рациональные или иррациональные, между ними всегда будет находиться сколь угодно много рациональных чисел. И если натуральные числа, отложенные на прямой, очевидно "дырявые", то "между" рациональными "дырок" нет! Кавычки подчёркивают психологичность этого утверждения.

Второй способ измерения расстояния состоит в использовании иерархически уменьшающихся "линеек". Для этого будем использовать следующую кодировку для "изображения" числа. Напишем "". Затем разделим отрезок на две равные части и выясним в какой из них лежит точка. Если в левой, то дальше поставим 0, а если в правой, то 1:

Fracional real2.png

В данном случае она справа, поэтому имеем "". Правую половину опять делим на две равные части и выясняем в какой из них находится . Теперь слева, поэтому "". Повторяя эту процедуру, получим двоичное представление числа эквивалентное ряду:

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

Вернёмся к Георгу Кантору, и рассмотрим множество всех действительных чисел, определённых при помощи процедуры, описанной выше. Будем использовать двоичную систему счисления. Некоторые (даже рациональные) числа в ней будут бесконечной последовательностью нулей и единиц (например 1/3). Удобно считать все числа бесконечными, дописывая справа к конечным неограниченную последовательность нулей. Докажем, что множество таких чисел не счётно.

Естественно доказательство будет строиться по схеме "от противного". Пусть все действительные числа в интервале можно пронумеровать. Как бы мы это не сделали, получится некоторый список:

Невозможно разобрать выражение (неизвестная функция «\begin{array}»): {\displaystyle \begin{array}{ll} 1^е\;число :& 0.010010000100...\\ 2^е\;число :& 0.111110001110...\\ 3^е\;число :& 0.011101010101...\\ 4^е\;число :& 0.010001010101..., ... \end{array}}

Другими словами, у нас есть бинарная функция (равная 0 или 1) вида , где -номер числа, а -номер двоичной цифры в числе после точки. В примере выше . Построим число, первая цифра после точки которого не равна первой цифре первого числа, вторая не равна второй цифре второго числа, и т.д. Другими словами, , где введена бинарная операция инвертирования: и . В примере выше начало этого числа

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

Часто, на основании этого доказательства, говорят, что иррациональных чисел "больше" чем рациональных, которые счётны. Это неверно.

Во-первых, между любыми иррациональными числами всегда расположено бесконечно много рациональных чисел. У двух близких, но не равных иррациональных чисел первые цифр двоичного разложения совпадут. Мы всегда можем выбрать рациональное число в виде конечной рациональной дроби у которой цифр совпадают с первыми цифрами числа "" и дальше идут нули. Очевидно, что это рациональное число будет больше "" и меньше "". Если бы иррациональных чисел было "больше" чем рациональных, то мы получили бы довольно неприятную ситуацию: между любыми двумя иррациональными числами всегда путается бесконечное число рациональных, которых меньше!? Хотя, конечно, это слишком "психологичный" аргумент.

Во-вторых, достаточно трудно ответить на простой вопрос - а какие же действительные числа оказались несчетными? Множество рациональных и алгебраических чисел счетно. Поэтому, традиционный ответ — несчетными являются "все остальные" вещественные числа, а именно трансцендентные. К трансцендентным числам, в частности, относятся "" и "". В такой формулировке это утверждение тоже не верно.

Как появляются (определяются) в математике те или иные конкретные числа? Прежде всего — как решения каких либо уравнений. Например, это обозначение (имя!) числа, являющегося решением уравнения . Числа можно определить при помощи бесконечных рядов и пределов. Так "", или . Не смотря на то, что эти формулы выражают некоторые бесконечные действия, само определение числа "" — конечно. Так, многоточие в определении ряда лишь обозначает, что у нас есть конечный алгоритм, позволяющий получить любой, наперед заданный, его член. Еще одним способом определения числа является предъявление алгоритма вычисления любой цифры в его десятичном представлении. Таким является трансцендентное число Лиувилля: 0.1100010000000000000000010..., где -я единица стоит в позиции .

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

Каким бы ни было построение конкретного числа (конструктивным или неконструктивным),

все определения, всех чисел, с которыми мы имеем и когда-либо будем иметь дело в математике, задаются конечной последовательностью слов состоящих из букв конечного алфавита.

Такие определения и, следовательно, числа счетны по той же причине, по которой счетны формулы или алгоритмы.

Таким образом, все, хоть как-то определяемые вещественные числа, являются счетными. Что же тогда, мы не смогли посчитать?

Математическое рассуждение корректно, когда его логическая структура истинна в не зависимости от содержательного смысла участвующих в нем объектов. Вернёмся к Проблеме Остановки и представим такое "доказательство" несчётности вычислимых функций:

Рассмотрим множество всех вычислимых функций одной переменной. Пусть это множество счетно, т.е. каждая функция имеет номер : . Построим функцию . Она тоже определяется алгоритмом. Она не совпадает ни с одной функцией из . Мы пришли к противоречию. Поэтому, множество таких функций несчетно.

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

Не сложно видеть, что структура "доказательств" несчётности функций и действительных чисел эквивалентны. В случае функций мы твердо знали, что их множество счетно, так как получили этот результат прямым а не косвенным рассуждением. Счетны ли вещественные числа мы не знаем, поэтому, получив противоречие, с радостью делаем вывод что они несчетны. Однако, счётность это не единственное предположение. Мы верим, что для любого числа можно получить -ю цифру, а благодаря этому можно построить число отличное от всех других в уже упорядоченной последовательности.

Понятно, что каждая вычислимая и всюду определённая функция задаёт некоторое вещественное число. Такими функциями в доказательстве Кантора были . Можно расширить это определение вещественного числа на все возможные алгоритмы. Но тогда мы получим множество "не совсем" определённых вещественных чисел. Простейший пример такого числа следующий. Пусть -тая цифра двоичного представления числа равна 1, если -тый алгоритм всюду определён, и 0 в противном случае: Мы принципиально не можем предложить алгоритма, всегда определяющего остановку данной программы, поэтому для некоторых чисел, в некоторых позициях будет стоять неопределенная цифра "?". Следовательно, мы не можем сравнить это число с другим действительным числом (что и пытаемся делать в доказательстве Кантора). Вопрос: является ли таким образом заданный объект вообще числом? Например, к нему неприменимо то, что делает число собственно числом: арифметические действия и операции сравнения.

Конечно, можно рассуждать по другому. Пусть множество конструктивных вещественных чисел задается только при помощи всюду определенных вычислимых функций . И пусть еще существуют числа, которые не задаются ни одним алгоритмом, не являются решением ни одного уравнения или предела произвольного ряда. Двоичное представление этих чисел есть "просто" произвольное (случайное?) бесконечное множество цифр 0 и 1. Именно этот довесок и оказывается несчетным.

Выше мы уже договорились, что счетность (соответствие элементов множества) разумно понимать только в алгоритмическом смысле. Множество счетно, если можно построить алгоритм, позволяющий "пересчитать" элементы такого множества (произвести 1-1 соответствие). Однако, было бы странно требовать от алгоритма оперировать с актуально бесконечным объектом, который мы не можем не только определить, но и назвать. Но, в таком случае, несчетность становится фактом тривиальным. Нельзя применять алгоритм к неалгоритмическим объектам, поэтому нет такого алгоритма и, следовательно, такие "вещественные числа" несчетны по определению. Однако существуют ли они? Первый же пример (определение) такого числа сделает его счетным. Ситуация напоминает невидимого суслика, который "на самом деле" есть...

Двоичное представление вещественного числа тесно связано с другой задачей. Рассмотрим множество всех натуральных чисел. "Возьмём" множество всех его подмножеств, обозначив его . Каждое из таких подмножеств можно задать в виде двоичной последовательности 010100..., где 1 на -том месте означает, что — принадлежит этому множеству (например, если после "..." идут нули, то ). Происхождение названия связано с тем, что для конечного набора из элементов количество всех его подмножеств (включая пустое ) равно . Используя диагональное доказательство Кантора, не сложно показать, что множество всех подмножеств несчётно.

Однако, что такое ? Говоря о любом множестве, мы считаем, что оно состоит из объектов "хорошо различимых нашей мыслью". Понятно, что в есть конечные множества: , , ... Их множество счётно. Оно также состоит их бесконечных множеств ( "все простые числа", "чётные числа", и т.п.). Бесконечное множество мы можем задать только при помощи конечного алгоритма, и все такие множества счётны. Никак не определив множество, мы не можем его сравнивать т.е. различать с другими множествами. А ведь различимость элементов — это основа построения теории множеств! Содержит ли в качестве своих элементов такие "неясно определённые объекты"?


Перечислимые и разрешимые множества << Оглавление >> Формулы арифметики их номера

Истинность и доказуемость - о конструктивной математике, Канторе и Гёделе