3. Парадокс брадобрея / Парадоксы теории множеств

Иван Ященко

Комментарии: 0

Содержание

<<< |1|2|3|4|5|6|7|8|…|17| >>>

3. Парадокс брадобрея

"To shave or not to shave…"

Это довольно известная история, и у нее есть много версий.

В одном полку жил-был полковой парикмахер, которого по историческим причинам называют брадобреем. Однажды командир приказал ему брить тех и только тех, кто не бреется сам^*5. Брадобрей, получив приказ, сначала обрадовался, потому что многие солдаты умели бриться сами, побрил тех, кто бриться сам не умел, а потом сел на пенек и задумался: а что ему с собой-то делать? Ведь если он будет брить себя, то нарушит приказ командира не брить тех, кто бреется сам. Брадобрей уже решил было, что брить себя не будет. Но тут его осенила мысль, что если он сам себя брить не будет, то окажется, что он сам не бреется, и по приказу командира он должет все-таки себя побрить…

^*5 Приказ довольно разумный: если солдат бреется сам, то зачем тратить на него время полковому парикмахеру? Наверное, полк был большой, и брадобрей просто не справлялся.

Что с ним стало, история умалчивает.

Причем же здесь теория множеств? А вот причем: командир пытался определить множество людей, которых брадобрею нужно брить, таким образом:

$\{$ те и только те, кто не бреется сам $\}$ .

Казалось бы, обычное множество, описывается несколькими русскими словами, чем оно хуже, например, множества

$\{$ все ученики школы $\}$ ?

Но с этим множеством тут же возникает проблема: непонятно, принадлежит ли этому множеству брадобрей.

Вот другая версия этого парадокса.

Прилагательное русского языка назовем рефлексивным, если оно обладает свойством, которое определяет. Например, прилагательное "русский" — рефлексивное, а прилагательное "английский" — нерефлексивное, прилагательное "трехсложный" — рефлексивное (это слово состоит из трех слогов), а прилагательное "четырехсложный" — нерефлексивное (состоит из пяти слогов)^*6. Вроде бы ничто не мешает нам определить множество

$\{$ все рефлексивные прилагательные $\}$ .

Но давайте рассмотрим прилагательное "нерефлексивный". Оно рефлексивное или нет?

^*6 Интересно, а прилагательное "трудновыговариваемое" является рефлексивным?

Можно заявить, что прилагательное "нерефлексивный" не является ни рефлексивным, ни нерефлексивным. Но как тогда быть с таким заклинанием:

верно либо утверждение, либо его отрицание?

(Это заклинание называется законом исключенного третьего; на нем, собственно, и основан метод от противного.)

Наконец, третья версия парадокса. Рассмотрим множество

$M$ = $\{$ множества $A$ , такие что $A \notin A$ $\}$

— мы включаем во множество $M$ только те множества $A$ , которые принадлежат сами себе. Бывают же множества, которые содержат другие множества. Например, пусть

$A = \{1,2,3\}$ , $B = \{\{1,2\},3\}$ ,

множеству $A$ принадлежат числа $1, 2, 3$ , а множеству $B$ — два элемента: множество $\{1,2\}$ и число $3$ . Возвращаясь к коробкам, это можно сказать так: одни коробки можно класть в другие коробки. (Оказывается, что в каждой такой последовательности вложенных коробок всегда конечное число элементов — этому есть глубокие причины.)

Рассмотренное множество $M$ — это своего рода "брадобрей". Если предположить, что $M \in M$ , сразу приходим к выводу, что $M \notin M$ . Если же предположить, что $M \notin M$ — получаем, что $M \in M$ .

Столкнувшись с этими парадоксами, создатели теории множеств осознали, что нельзя задавать множества произвольными словосочетаниями. После этого они стали бороться с парадоксами двумя способами.

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

$A$ = $\{$ множество учащихся школы $\}$ ,
$B$ = $\{$ множество непрерывных функций $\}$

(эти множества "встречаются в природе"), из них можно получить объединение $A \cup B$ , пересечение $A \cap B$ . Можно даже умножить множество $A$ на множество $B$ : по определению

$A \times B = \{(a,b) \colon a \in A, b \in B\}$

— множество пар, в которых первый элемент из первого множества, а второй — из второго. В нашем случае $A \times B$ — это множество пар, в которых первый элемент — учащийся школы, а второй — какая-нибудь непрерывная функция.

Другой способ — аксиоматический. Этот способ преодоления парадоксов развивали Цермело и Френкель (система аксиом Цермело–Френкеля), Гедель и Бернайс (система аксиома Геделя–Бернайса). Согласно этой теории, множество — это нечто, удовлетворяющее аксиомам, например, следующим{1}.

Записи аксиом дублируются на "языке кванторов". Вот значения используемых кванторов:
$\forall x$ — для любого $x$ ;
$\exists x$ — существует $x$ ;
$\exists! x$ — существует единственный $x$ ;
$\mathrm{Set}\{\dots \}$ — $\{\dots \}$ является множеством;
$\{x \colon \varphi(x)\}$ — множество тех и только тех $x$ , которые удовлетворяют условию $\varphi(x)$ ;
$\lor$ — логическое "или";
$\land$ — логическое "и".

1. Аксиома объемности. Множество определяется своими элементами: множества, состоящие из одних и тех же элементов, равны.

$\forall z\, (z \in x \Leftrightarrow z \in y) \Rightarrow x = y$ .

2. Аксиома объединения. Объединение всех элементов множества есть множество.

$\mathrm{Set}\{z \colon \exists y \in x\, (z \in y)\}$ .

3. Аксиома выделения. Для каждого множества $A$ и каждого условия $\varphi$ существует множество

$B = \{x \colon x \in A,\, \varphi(x)\}$

— подмножество элементов множества $A$ , удовлетворяющих условию $\varphi$ .

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

$\forall x\, (\varphi(x) \Rightarrow x \in y) \Rightarrow \mathrm{Set}\{x \colon \varphi(x)\}$ .

4. Аксиома степени. Множество всех подмножеств данного множества есть множество.

$\mathrm{Set}\{y \colon y \subseteq x\}$ .

5. Аксиома подстановки. Пусть $X$ — множество, а $\varphi(y,z)$ — произвольная формула. Тогда если для каждого $y$ существует и единственен $z$ , такой что истинно $\varphi(y,z)$ , то существует множество всех $z$ , для которых найдется $y \in X$ , такой что $\varphi(y,z)$ истинно.

$\forall y\ \exists! z\ \varphi(y,z) \Rightarrow \mathrm{Set}\{z \colon \exists y \in x \ \varphi(y,z)\}$ .

6. Аксиома фундирования. Не существует бесконечной последовательности вложенных множеств: каждая цепочка множеств

$A_1 \supset A_2 \supset A_3 \supset \dots$

конечна.

$\exists y\, (y \in x) \Rightarrow \exists y \in x\ \forall z \in y (z \notin x)$ .

7. Аксиома бесконечности. Существуют бесконечные множества, т. е. такие множества $A$ , что $A$ равномощно $A \cup \{A\}$ .

$\exists x \, ((\exists y \in x\ \forall z \, (z \notin y)) \land \forall y \in x\ \exists z \in x \, (w \in z \Leftrightarrow w \in y \lor w = y))$ .

8. Аксиома выбора. Еще одна очень сложная, но и очень очевидная аксиома — о ней позже.

{1}. Подробнее об аксиоматике теории множеств см. книгу [4].

<<< |1|2|3|4|5|6|7|8|…|17| >>>

Содержание

Комментарии: 0

Похожее

Парадоксы теории множеств и их философская интерпретация

Парадоксы являются следствием дихотомии языка и мышления, выражением глубоких диалектических (теорема Гёделя позволила проявить диалектику в процессе познания) и гносеологических трудностей, связанных с понятиями предмета и предметной области в формальной логике, множества (класса) в логике и теории множеств, с употреблением принципа абстракции, позволяющего вводить в рассмотрение новые (абстрактные) объекты (бесконечность), со способами определения абстрактных объектов в науке и т. п. Поэтому не может быть дано универсального способа устранения всех парадоксов.
А нужен ли выбор? (альтернатива аксиоме выбора в теории множеств)

Михаил Раскин

Современная математика в качестве своего основания использует теорию множеств. Традиционно при анализе теоретико-множественных тонкостей используется аксиоматика Цермело-Френкеля с аксиомой выбора, обозначаемая ZFC. На аксиому выбора опираются доказательства наличия базиса в любом векторном пространстве и существования неизмеримого множества в математическом анализе. К сожалению, теория множеств обязана работать и со множествами, которые не описываются достаточно подробно и конкретно, чтобы мы могли себе их представить. В курсе будет рассмотрен один пример, к чему это приводит. Оказывается, ценой ослабления аксиомы выбора можно получить теорию множеств, в которой любая ограниченная функция на отрезке интегрируема по Лебегу. То, что используется аксиома выбора, в каком-то смысле, произошло исторически. Курс основан на статье Р.М. Соловэя о построении теории множеств, в которой все множества вещественных чисел измеримы.
«Мы не можем ждать милостей от природы», или применение метода вынуждения в построении моделей теории множеств

Михаил Раскин

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

Виктор Викторов

Основные понятия, операции над множествами, тождества, свойства дополнения, правило Де Моргана, свойства симметрической разности; отображение (функция), факторотображение, отношение эквивалентности, парадокс брадобрея; упорядоченные множества, минимальный, наименьший, максимальный и наибольший элементы в упорядоченном множестве, мажоранта и миноранта; аксиома выбора, вполне упорядоченное множество.
Числа и многочлены

Проскуряков И. В.

Целью этой книги является строгое определение чисел, многочленов и алгебраических дробей и обоснование их свойств, уже известных из школы, а не ознакомление читателя с новыми свойствами. Поэтому читатель не найдет здесь новых для него фактов (за исключением, быть может, некоторых свойств, действительных и комплексных чисел), но узнает, как доказываются вещи, хорошо ему известные, начиная с «дважды два — четыре» и кончая правилами действий с многочленами и алгебраическими дробями. Зато читатель познакомится с рядом общих понятий, играющих в алгебре основную роль.
Математика на шахматной доске

Гик Е. Я.

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

Питер Эткинз

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

Смаллиан Рэймонд

В книге «Алиса в Стране Смекалки» кэрролловская Алиса из Страны Чудес и ее друзья раскрывают перед читателем нескончаемую вереницу задач-головоломок. Они доставят удовольствие всем любителям занимательной математики, а почитателям творчества Льюиса Кэрролла в особенности.
Математическое понимание природы

Владимир Арнольд

Сборник «Задачи для детей от 5 до 15 лет» вызвал много отзывов. И дети, и взрослые читатели часто сожалели, что там были только математические задачи, — ведь и все естествознание заслуживает столь же активного, творческого к себе отношения. Теперь я отвечаю на эти пожелания — следуя скорее Яну Амосу Каменскому, чем современным педагогам, то есть всегда стремясь быть понятным читателю, не имеющему предварительных знаний (но столь же любознательному, как большинство подростков).
Невероятные числа профессора Стюарта

Отрывок из книги «Невероятные числа профессора Стюарта» заслуженного профессора математики Уорикского университета, известного популяризатора науки Иэна Стюарта, посвященной роли чисел в истории человечества и актуальности их изучения в наше время.

Далее >>>

∀ x, y, z

3. Парадокс брадобрея / Парадоксы теории множеств

Иван Ященко

3. Парадокс брадобрея

Теги

Похожее