Dangerous Knowledge - Диагональный метод доказательства Кантора. Часть III (Russian)

См. также:
Dangerous Knowledge
Dangerous Knowledge - Бесконечное множество и интуиция.Часть I
Dangerous Knowledge - Парадокс брадобрея. Часть II
Dangerous Knowledge - Диагональный метод доказательства Кантора. Часть III
Dangerous Knowledge - Континуум-гипотеза. Часть IV
Dangerous Knowledge - Аксиома выбора. Часть V
Dangerous Knowledge - Теория меры. Часть VI
Dangerous Knowledge - Тест Тьюринга. Часть VII


UPDATE 02-11-2010:
Прикоснуться к бесконечности (ВИДЕО)
END OF UPDATE

UPDATE 03-02-2011:
Ещё раз о бесконечности
Всегда ли часть строго меньше целого?
END OF UPDATE

UPDATE 29-09-2014:
Infinity: does it exist?
END OF UPDATE

Как я уже говорил, есть некоторые вещи, которые явно не раскрыты в этой доке. Здесь, я продолжу писать про Кантора. Здесь я рассмотрю "диагональный метод" доказательства Кантора. «Гёдель, Эшер, Бах: эта бесконечная гирлянда», где он в частности подробно на этом останавливается. Перевод на русский можно найти тут. На английском эта книга называется «Gödel, Escher, Bach: An Eternal Golden Braid» by Douglas Hofstadter.

Цитата из английской википедии:

On its surface, GEB examines logician Kurt Gödel, artist M. C. Escher and composer Johann Sebastian Bach, discussing common themes in their work and lives. At a deeper level, the book is a detailed and subtle exposition of concepts fundamental to mathematics, symmetry, and intelligence.

Through illustration and analysis, the book discusses how self-reference and formal rules allow systems to acquire meaning despite being made of "meaningless" elements. It also discusses what it means to communicate, how knowledge can be represented and stored, the methods and limitations of symbolic representation, and even the fundamental notion of "meaning" itself.

In response to confusion over the book's theme, Hofstadter has emphasized that GEB is not about mathematics, art, and music but rather about how cognition and thinking emerge from well-hidden neurological mechanisms. In the book, he presents an analogy about how the individual neurons of the brain coordinate to create a unified sense of a coherent mind by comparing it to the social organization displayed in a colony of ants.

http://en.wikipedia.org/wiki/Gödel,_Escher,_Bach:_An_Eternal_Golden_Braid


Ниже есть продолжение.



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

Напомню, что два множества называются равномощными (в них есть "одинаковое количество элементов"), если между ними можно установить взаимно-однозначное соответствие.

1. Следующие множества попарно равномощны: множество натуральных чисел, множество целых чисел, множество рациональных чисел. Эти примеры счётных множеств.

2. Множество действительных чисел в отрезке [0, 1) несчётно ("диагональный метод Кантора").

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

Здесь я приведу идею неформального доказательства этой теоремы. Она доказывается с помощью "диагонального метода". Допустим от противного, что множество действительных чисел в отрезке [0, 1) счётно. Любое число на этом отрезке представимо в качестве бесконечной десятичной дроби. Так как это множество счётно мы можем написать следующий список:

x1=0,57893565778356...
x2=0,24896590783...
x3=0,672008765...
x4=0,9271456732...
...

Построим число x следующем способом. Оно будет начинаться на 0, чтобы принадлежать отрезку [0, 1). Первая его цифра после запятой будет любое число, но на такое, какое стоит на первом месте в числе x1, т.е. не 5. Вторая его цифра, будет не таким, как вторая цифра числа x2, т.е. не 4, и т.д. Очевидно, что это такое число будет отличаться от всех чисел, приведённых в списке выше. В самом деле, рассмотрим число x и некоторое число xk. Эти два числа различны. В самом деле, посмотрим на цифру k в десятичной записи этих чисел. В числе x эта цифра будет отличаться от цифры в числе xk, так как именно таким образом число x было "сконструировано". Итак, мы получили число, которого нет в нашем списке всех действительных чисел. Мы пришли к противоречию. Значит наше допущение о том, что множество действительных чисел в отрезке [0, 1) счётно неверно, а значит оно несчётно.


Маленькое замечание, несмотря на то, что в доказательстве использовано троеточие в построение списка, можно это построение задать абсолютно строго.

Где же в этом доказательстве была использована "ссылка на самого себя?". Делается это при рассмотрение цифры k. С одной стороны, это цифра в записи числа x, а с другой стороны оно использует как указатель на число xk (и там мы интересуемся местом k).

Если почитать доказательства Гёделя и Тьюринга именно с помощью подобных построений они доказали свои теоремы. Для неформальное ознакомления с этими доказательствами я опять порекомендую книгу Хофштадтера Дугласа «Гёдель, Эшер, Бах: эта бесконечная гирлянда». На английском эта книга называется «Gödel, Escher, Bach: An Eternal Golden Braid» by Douglas Hofstadter.