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

Множество всех множеств, которые не содержат сами себя, одновременно и содержит, и не содержит себя — парадокс Рассела подорвал наивную теорию множеств и изменил основы логики.

Definition

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

Scope

Эта тема охватывает логические и теоретико-множественные парадоксы, а также фундаментальные ответы, которые они вызвали. Она рассматривает парадокс Рассела о множестве всех несамопринадлежащих множеств, парадокс Бурали-Форти о наибольшем порядковом числе и парадокс Кантора об универсальном множестве; диагностику Рассела через принцип порочного круга и вытекающую из него разветвленную теорию типов в «Началах математики» (Principia Mathematica); а также альтернативный подход аксиоматической теории множеств (Цермело-Френкеля), которая ограничивает принцип свертывания (comprehension) для избежания парадоксов.

Core questions

• Какое допущение в наивной теории множеств порождает парадокс Рассела?
• Требует ли избегание парадоксов принципа порочного круга и ограничений типов?
• Чем отличаются теория типов и аксиоматическая теория множеств как подходы к решению проблемы?
• Являются ли логические парадоксы по своей сути такими же, как семантические?

Key concepts

• неограниченное свертывание
• парадокс Рассела
• парадоксы Бурали-Форти и Кантора
• принцип порочного круга
• теория типов
• аксиома выделения

Key theories

Разветвленная теория типов

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

Ограниченное свертывание

Аксиоматическая теория множеств (Цермело-Френкеля) отказывается от неограниченного свертывания в пользу аксиом выделения и замены, так что никакое множество всех несамопринадлежащих множеств не может быть образовано, что разрешает парадокс Рассела без иерархии типов.

History

Рассел открыл свой парадокс в 1901 году, изучая логицизм Фреге, что подорвало Основной закон V Фреге. Теория типов Рассела 1908 года и «Начала математики» 1910 года предложили одно решение; аксиоматизация Цермело 1908 года, позднее расширенная Френкелем, предложила другое, и оба подхода лежат в основе современных фундаментов и простой теории типов, используемой в логике и информатике.

Debates

Теория типов против аксиоматической теории множеств

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

Key figures

• Bertrand Russell
• Alfred North Whitehead
• Gottlob Frege
• Ernst Zermelo
• Cesare Burali-Forti

Seminal works

• russell1908
• whiteheadrussell1910

Frequently asked questions

Что такое парадокс Рассела простыми словами?

Рассмотрим множество R всех множеств, которые не являются элементами самих себя. Спросим, является ли R элементом самого себя. Если оно является, то по своему определению оно не должно им быть; если оно не является, то оно соответствует условию и должно им быть. Любой ответ противоречит другому, что показывает ошибочность предположения наивной теории множеств о том, что любое свойство определяет множество.