Небольшое предисловие

Эта статья бала написана мной в качестве реферата по психологии (!) в аспирантуре в 1996 г. По замыслу, это план занимательной лекции по математике. Насколько она занимательна судить читателю.

Парадоксы теории множеств

Что такое множество? Слово это часто встречается в повседневной речи -- мы говорим о "множество дел" или "множестве людей", -- и фактически подспудно присутствовало в математике с момента ее возникновения. Однако, явным образом понятие множества подверглось систематическому изучению лишь во второй половине XIX века в работах немецкого математика Георга Кантора -- до этого в математике существовали "натуральные числа" или "целые числа", но не "множество натуральных чисел" и не "множество целых чисел". И вот когда "множество" как таковое стало предметом математического рассмотрения, в этом, на первый взгляд, простом и повседневном понятии выявились глубокие противоречия, подорвавшие традиционный взгляд на основания математики и научного знания вообще.

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

Одним из основных понятий, введенных Кантором, является мощность множества. Мощность есть обобщение количества элементов множества. Количество элементов множества {1, 2, 3} равно 3, и, соответственно, это множество меньше, чем множество {3, 4, 5, 7, 8}, в котором 5 элементов. Но сколько элементов в множестве всех натуральных чисел N? Бесконечно много, скажем мы. А в множестве целых чисел Z или вещественных чисел R? Тоже бесконечно много! Нельзя ли как-то сравнить эти бесконечности и определить, какая из этих бесконечностей больше?

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

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

При таком определении, оказывается, что множество всех целых чисел равномощно своему подмножеству -- множеству натуральных чисел. Этот парадоксальный, на первый взгляд факт, легко доказать. Выпишем целые числа в таком порядке:

0, 1, -1, 2, -2, 3, -3, ...

Ясно, что так мы выпишем все целые числа. Однако, если теперь мы занумеруем их всех слева направо натуральными числами 1, 2, 3, ..., то все целые числа "рассядутся в кресла" натуральных чисел. Таким образом установлено взаимно-однозначное соответствие между множествами N и Z, и, таким образом, они равномощны. Пока, впрочем, никакого парадокса нет -- просто к бесконечным множествам не всегда применимы наглядные представления.

Ну, а множество вещественных чисел R? Неужели и оно равномощно множеству натуральных чисел? Оказывается, R действительно больше N. Даже множество чисел интервала (0; 1) больше, чем множество натуральных чисел. Покажем это. Допустим, что нам удалось занумеровать все вещественные числа интервала (0; 1) натуральными числами. Выпишем тогда все эти числа в порядке номеров в виде десятичных дробей. Получится что-то вроде

1: 0.5678345345...
2: 0.0928942346...
3: 0.5675454323...
4: 0.9875376780...
и т.д.

Теперь составим вещественное число x таким образом. Если в числе № n на n-м месте стоит цифра 5, запишем в нашем числе x на n-м месте цифру 6; если же в числе № n на n-м месте стоит не пятерка, то запишем в числе x на n-м месте пятерку. Ясно, что x не совпадает ни с одним из перенумерованных чисел -- ведь от n-го числа оно отличается в n-ном знаке! Но x -- тоже число из интервала (0; 1), и потому тоже должно было быть занумеровано! Полученное противоречие показывает, что занумеровать все числа интервала (0; 1) невозможно, т.е. интервал (0; 1) больше множества N.

Есть ли еще большие множества? Да, и сейчас мы это увидим. Пусть S -- какое-то множество. Рассмотрим множество M(S) всех его подмножеств. Т.е. элементами M(S) являются подмножества множества S. Это может показаться слегка экзотичным, но мы ведь договорились, что элементами множеств может быть все, что угодно. Легко посчитать, что если S -- конечное множество из n элементов, то M(S) содержит 2ⁿ элементов. Сейчас мы покажем, что M(S) всегда больше S, даже если S бесконечно.

В самом деле, предположим, что нам удалось установить взаимно-однозначное соответствие между элементами S и элементами M(S), т.е. подмножествами S. Т.е. каждому x из S соответствует некоторое подмножество S_x. Рассмотрим теперь множество A всех тех x, которые не принадлежат своим S_x. Это -- тоже некоторое подмножество множества S (может случиться, что оно пусто, а может, совпадает со всем S). Раз так, оно соответствует некоторому конкретному x из S, т.е. A = S_x. Это x не может принадлежать A, т.к. A есть множество тех x, которые не принадлежат своим S_x. Но тогда, поскольку A есть множество всех тех x, которые не принадлежат своим S_x, x должно принадлежать A. Т.е. x и принадлежит, и не принадлежит A, что, конечно же, невозможно. Таким образом, взаимно-однозначное соответствие между S и M(S) невозможно.

Итак, множество M(R) всех подмножеств множества вещественных чисел больше, чем R, далее M(M(R)) больше, чем M(R) и т.д. (Кстати, M(N) равномощно R).

Теперь мы рассмотрим знаменитый парадокс Рассела. Назовем множество экстраординарным, если оно содержит себя в качестве элемента (вопрос о том, существуют ли такие множества, мы пока оставим в стороне). Остальные множества назовем ординарными. Рассмотрим теперь множество O всех ординарных множеств. Весьма экстравагантное множество, но, повторимся, мы допускаем любые объекты в качестве элементов множеств. Само-то O ординарно или нет? Если O ординарно, то, будучи множеством всех ординарных множеств оно должно содержать себя в качестве элемента, т.е. быть экстраординарным. Если же оно экстраординарно, то будучи множеством только ординарных множеств, оно не содержит себя в качестве элемента, и потому ординарно. Итак, если O ординарно, то оно экстраординарно, а если оно экстраординарно, то оно ординарно. Абсурд! Вся эта игра словами напоминает известный старинный парадокс брадобрея: если брадобрей бреет всех тех, и только тех, кто не бреется сам, то бреет ли он сам себя? Здесь, аналогично, если он бреет себя, то он не бреет себя, а если бреет -- то не бреет. Парадокс брадобрея, впрочем, разрешается весьма просто -- такого брадобрея не существует. Ни один брадобрей, как бы он не старался, не может выполнить условия брить всех тех, и только тех, кто не бреется сам -- это условие противоречиво, и потому невыполнимо. В случае множества O нам ничего не остается, как признать, что множества всех ординарных множеств не существует. Однако, в отличие от хитроумного брадобрея, потеря этого множества, хотя едва ли представляет практическую проблему, для оснований математики фатальна. Оно означает конец "наивной теории множеств", где элементами множества позволялось быть всем, чем угодно. Такая вольность в обращении с множествами привела нас к множеству, существование которого внутренне противоречиво. Т.к. такая ситуация в математике недопустима, приходится признать, что не все можно называть множеством. Нашего "монстра" O назвать множеством нельзя. Но что же это тогда? Ведь до сих пор подразумевалось, что существует любое множество, достаточно только это множество описать. И вот, мы описали множество, а оно не существует. Подчеркнем, не пусто, а именно не существует как таковое.

Другой парадокс, связанный с понятием мощности, проясняет, что причина противоречий кроется в "слишком больших" множествах. Рассмотрим множество всех множеств M. (Оно, кстати, экстраординарно). М(M) -- множество всех его подмножеств. Элементы М(M) -- множества, а т.к. M есть множество всех множеств, то все элементы М(M) являются также элементами M. Иными словами, М(M) есть подмножество M. Но ведь мы доказали, что мощность М(M) строго больше мощности M! Мощность подмножества не может быть строго больше мощности объемлющего множества. Таким образом для "монстров" типа M, понятие мощности отказывает. Т.е. множество всех множеств -- не множество.

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