Dangerous Knowledge - Бесконечное множество и интуиция.Часть I

См. также:
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


Как я уже говорил, есть некоторые вещи, которые явно не раскрыты в этой доке. Здесь, я напишу про то, что же такое открыл Кантор.

Во-первых, я советую прочитать короткую статью "О Бесконечном", которая в начале вкратце рассказывает, почему эта концепция противоречива. Ещё одно предварительное замечание, мат. анализ оперирует потенциальной бесконечностью $\infty$, а теория множеств - актуальной.

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

Давайте попробуем разобраться как мы считаем. Для начала попробуем решить простую задачку. Задача 1. У Пети и Коли есть яблоки, у кого из них яблок больше?

Существует два принципиально разных подхода к решению этой задачки.

Подход первый. Давайте "посчитаем" сколько есть яблок у Пети, скажем, их 5, сколько яблок есть у Коли, скажем их 3. Т.к. $5>3$, то ясно, что у Пети больше яблок, чем у Коли.

Подход второй. У нас не спрашивают сколько у кого яблок, нам важно лишь узнать у кого больше. Давайте, попросим Колю и Пети дать нам по одному яблоку. Если они могут удовлетворить нашу просьбу, попросим нам дать следующую пару. Если мы обнаружим, что Петя нам даёт очередное яблоко, а у Коли яблок не осталось, значит у Пети было яблок больше в самом начале. Если яблоки у них кончились одновременно, значит, у них было одинаковое количество яблок.

Давайте попробуем чуть глубже понять, что мы только что сделали. Если обозначить множество яблок у Пети через $X$, множество яблок у Коли через $Y$, то мы по сути пытались задать взаимно-однозначное соответствие между ними, как указано на рисунке:



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

Итак, во-втором подходе, мы находим взаимно-однозначное соответствие между элементами множества. Что же мы делаем в первом подходе? Как мы считаем?

Если вы вспомните начальную школу или детский сад, вы вспомните как по-начало трудно вам давались эти самые цифры. 3 яблока, 3 стула, 3 вообще... Какое следующее число после 3? А предыдущее? У тебя 3 яблока, сколько яблок тебе нужно дать, чтобы у тебя было 5 яблок?.. По-сути, вас учили устанавливать взаимно-однозначное соответствие между произвольно взятым множеством и конечным подмножеством натуральных чисел. Не понятно?

Хорошо, попробую объяснить иначе. В первом подходе, вы делали почти то же самое, что и во-втором, только используя промежуточный, "эталонный", "хорошо изученный", "понятный" набор для сравнения.



В начале мы нашли такое подмножество натурального ряда, у которое есть взаимно-однозначное соответствие с множеством $X$, множеством яблок Пети, затем мы нашли другое подмножество натурального ряда и нашли взаимно-однозначное соответствие с множеством $Y$, множеством яблок Коли. Теперь мы свели задачу к тому, чтобы определить какие из этих двух множеств больше. Этому наш учили ещё в начальных классах, мы без труда можем установить, что первое множество больше второго, так как $5>3$. Говорят, что мощность первого множества больше, мощности второго.

Однако, по сути, в обоих случаях мы находили взаимно-однозначное соответствие! Только в первом случае, мы не отдавали себе в этом отсчёт.

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

Я приведу лишь несколько простых примеров, чтобы обосновать последний тезис.

Задача 2. Каких числе больше, всех натуральных чисел (без ноля), множесво $N$, или натуральные числа с добавленных к ним нолём, множество $M$?

Казалось бы, наша интуиция, явно основана на первом методе, точнее тому, чему наш учили в начальных классах, говорит, что множество $M$ больше. Как же, там есть всё то, что есть в $M$ да ещё и "лишний" 0.

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



Чуть более формально для каждое числа $n \in N$ мы можем найти число $m \in M$, так что $m=n-1$.

Мы, как бы всё время отстаём на один шаг, когда берём числа из $N$, но так как $N$ бесконечное множество, у нас всё время будут под рукой числа, для того чтобы продолжить это построения. Таким образом, для любого числа $n \in N$, мы можем указать, на каком именно конечном шаге построения оно будет использовано (в $N$ не останется "лишних" чисел), и для любого числа $m \in M$ мы можем указать с каким числом оно будет "спаровано", $m=n-1$. А это значит, что в $N$ и в $M$ есть одинаковое количество чисел или что они равномощны !


Задача 3. Каких чисел больше чётных или натуральных?

Опять-таки наша интуиция говорит, что натуральных. В самом деле, чётные числа - это часть целых чисел. А нам всем, хорошо известно, что часть всегда меньше целого. Всегда ли?

Если мы вспомним предыдущий пример, там тоже множество $N$ было частью множества $M$, но оказалось в том конкретном случае, что часть может быть равна целому!

В этом случае дело обстоит точно также. Взаимно-однозначное соответствие выглядит следующем образом. Возьмём чётное число $m=2k$ (число чётное!). Поставим в соответствие этому числу, число $k$. Нетрудно убедится, что это взаимно-однозначное соответствие.

Более того, оказывается, что имеет место следующая теорема:

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


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

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

Наброски доказательства (можно спокойно его пропустить, тем более оно не полное). Докажем сначала, что если множество бесконечно, то существует собственное подмножество равномощное заданному.

Из определения бесконечного множества (я его не приводил здесь) следует существование подмножества $A \subseteq F$ равномощное натуральному ряду. Рассмотрим множество $B=F \setminus A$. Это множество либо конечно либо бесконечно.

Если множество $B$ конечно, то так как $F= A \cup B$, где $A$ равномощно натуральному ряду, а $B$ конечно, получаем, что и наше множество $F$ равномощно натуральному ряду. Для такого множества легко доказать теорему используя тот факт, что чётные числа равномощные натуральными.

Если множество $B$ бесконечно, то осталось показать, что оно равномощно искомому множеству $F$. Это делается используя тот факт, что если $X \subseteq Y $, то мощность X не больше, чем мощность $Y$.

Теперь докажем, что если существует собственное подмножество равномощное заданному, то такое множество бесконечно.
Лемма. Любое подмножество конечного множества - конечно. (Доказывается непосредственно из определений бесконечного и конечного множества).
Идея доказательства. Допустим от противного что существует собственное подмножество равномощное заданному, и такое множество конечно. Используя лемму, получим, что это собственное подмножество тоже конечно. В конечном множестве мощность множества совпадает с количеством элементов множества (это предположение делать не обязательно, я его использую в иллюстративных целях). Обозначим, мощность заданного множества за $n$, мощность (конечного) собственного подмножества за $к$, где $n, к$ натуральные числа или ноль. Вообще говоря либо $n>k$ либо $n<k$ либо $n=k$.

Так как подмножество собственное, из этого следует, что $k\neq0$ и что $k\neqn$. С другой стороны так как мощность подмножества должно равняться мощности множества, должно выполнятся $n=k$. Мы пришли к противоречию. Значит наше допущение было не верно, значит верна утверждение теоремы.