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

Слово парадокс – греческого происхождения, дословно переводится как неожиданный. Оно обычно употребляется, когда встречаются с неожиданным утверждением, рассуждением или выводом, противоречащим здравому смыслу. Парадокс – это рассуждение, доказывающее как истинность, так и ложность некоторого суждения. Суть всех парадоксов обусловлена особенностями всех естественных языков и логикой нашего мышления. К таким парадоксам относится парадокс «Лжец», считающийся королем парадоксов. Другие парадоксы явно связаны с канторовским понятием множества. Самым известным из них является парадокс Б. Рассела, который он обнаружил в 1902 г. всего лишь через пять лет после официального признания теории множеств на Первом международном конгрессе математиков, проходившем в Париже.

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

Большинство рассматриваемых множеств относятся к типу нормальных. Однако в природе встречаются и нормальные множества. Примером ненормального множества может служить множество всех абстрактных понятий. Действительно, понятие множества само является абстрактным и поэтому должно принадлежать множеству абстрактных понятий.

Приведем другой пример ненормального множества. Пусть мы имеем дело с множеством простых предложений. Мы хотим объявить об этом предложением, например, таким: «Здесь записано множество всех простых предложений». Для сокращения записи это простое предложение обозначим буквой А, а все другие простые предложения соответствующими малыми буквами с индексами. Тогда, так как само предложение А простое, то оно должно входить во множество всех простых предложений. Таким образом, будем иметь

.

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

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

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

Таким образом, брадобрей должен себя брить и в то же время не должен себя брить. Но так быть не может. Это и есть явное противоречие.

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

Парадокс каталог всех нормальных каталогов получается так. Некая библиотека решила составить библиографический каталог, в который входили бы все те и только те каталоги, которые являются нормальными, т.е. не содержат ссылки на себя. Спрашивается, где должен быть упомянут составленный каталог? Если он будет упомянут в составленном каталоге, т.е. в самом себе, то составленный каталог окажется ненормальным. А по условию этого не должно быть. Если же составленный каталог не будет упомянут, то этот составленный нормальный каталог окажется нигде не зафиксированным, хотя по условию должны быть упомянуты все нормальные каталоги.

С описанными ситуациями, аналогичными приведенным парадоксам, в повседневной жизни мы встречаемся довольно часто. Так в конце или начале любой книги приводится ее содержание или оглавление, где указаны главы, параграфы, пункты с указанием той страницы, с которой начинается соответствующая глава или параграф. Спрашивается, где указывать номер страницы, с которой начинается оглавление? Она, как правило, и не указывается.

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

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

Вопросы для самоконтроля

1. Дайте определение множества по Кантору. Определите конечное и бесконечное, счетное и несчетное множества.

2. Какие существуют два основных способа задания множеств? Приведите примеры задания множеств.

3. Поясните понятие подмножество, как символически записывают отношение между множествами?

4. Какими свойствами может обладать отношение включения?

5. Какие подмножества множества называются несобственными?

6. Что такое множество-степень и чему равна его мощность?

7. В чем состоит различие между max и sup, min и inf?

8. Приведите символическую запись операции объединения множеств и дайте ее интерпретацию с помощью кругов Эйлера.

9. Приведите символическую запись операции пересечения множеств и дайте ее интерпретацию с помощью кругов Эйлера.

10. Приведите символическую запись операции вычитания множеств и дайте ее интерпретацию с помощью кругов Эйлера.

11. Приведите символическую запись операции дополнения множеств и дайте ее интерпретацию с помощью кругов Эйлера.

12. Что такое универсальное множество и дайте его интерпретацию с помощью кругов Эйлера.

13. Приведите символическую запись симметрической разности двух множеств и дайте ее интерпретацию с помощью кругов Эйлера.

14. Как определяется сумма двух множеств, дайте ее геометрическую интерпретацию.

15. Приведите формальные записи коммутативности, ассоциативности и дистрибутивности множеств.

16. Приведите формальные записи операций объединения и пересечения для одного множества с пустым и универсальным множествами.

17. Приведите формальные записи идемпотентности множеств, законов де Моргана и поглощения.

18. Поясните сущность отношений на множествах.

19. Что такое кортеж, декартово произведение?

20. Дайте определение отношения и раскройте его содержательный смысл.

21. Что такое область определения, значений и график отношения?

22. Как формально записывается обратное отношение и в чем его смысл?

23. Приведите формальную запись операций объединения, пересечения, разности и инверсии отношений. Приведите примеры.

24. Приведите формальную запись операций композиции и сужения отношений. Приведите примеры.

25. Приведите основные свойства отношений и соответствующие примеры.

26. Охарактеризуйте понятие функции как отношения на множествах.

27. Дайте определение инъективного, сюръективного и биективного отображения. Приведите примеры.

28. Дайте определение отношению эквивалентности. Приведите примеры эквивалентных и неэквивалентных отношений.

29. Поясните понятия отношений частичного и строгого порядка.

30. В чем суть парадоксов теории множеств. Приведите какой-нибудь пример парадокса и объясните его.