Парадокс Рассела и кризис оснований

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

Парадокс Рассела — противоречие в наивной теории множеств: множество всех множеств, не содержащих себя, и содержит, и не содержит себя одновременно.

Наивная теория множеств и её обещание

В конце XIX века Готлоб Фреге строил всю математику на одном основании — множествах. Принцип неограниченной свёртки гласил: для любого свойства P существует множество всех объектов, обладающих P. Звучит безобидно: «множество всех чётных чисел», «множество всех красных предметов». Казалось, на этом можно построить всё.

Удар Рассела

В 1901 году Бертран Рассел задал свойство P(x) = «x не содержит себя в качестве элемента» и образовал множество R всех таких x. Затем спросил: содержит ли R само себя?

R = { x | x не принадлежит x }

Если R принадлежит R, то по определению R НЕ содержит себя:  противоречие.
Если R не принадлежит R, то R удовлетворяет свойству:        значит R принадлежит R.

R принадлежит R  тогда и только тогда, когда  R не принадлежит R   -- противоречие

Оба варианта ведут к противоречию. Это не ошибка вычисления — это дыра в самом основании. А из противоречия в логике выводится что угодно (принцип «ex falso quodlibet»): если система противоречива, в ней доказуемо всё, и она бесполезна.

Бытовая версия: парадокс брадобрея

Рассел пояснял парадокс притчей. В деревне брадобрей бреет всех, кто не бреет себя сам, и только их. Бреет ли брадобрей сам себя? Если бреет — значит, он из тех, кто бреет себя сам, а таких он не бреет. Если не бреет — значит, он из тех, кого он обязан брить. Замкнутый круг той же формы: самоприменение порождает противоречие.

Демонстрация самоприменения

Корень зла — неконтролируемое самоприменение: объект говорит о себе. Покажем, что обычное множество себя не содержит, а Расселово множество построить непротиворечиво нельзя.

normal = frozenset({1, 2, 3})
print("3 в normal      :", 3 in normal)
print("normal в normal :", normal in normal)   # False — обычное множество

# Расселово R потребовало бы множество, содержащее ровно те, что не содержат себя.
# Построить его непротиворечиво нельзя — поэтому такого объекта в теории НЕТ.
print("Расселово R не существует в непротиворечивой теории")

Вывод:

3 в normal      : True
normal в normal : False
Расселово R не существует в непротиворечивой теории

Как работает под капотом

Парадокс возникает из-за того, что наивная теория позволяет объекту быть аргументом самому себе без ограничений. Лекарство, которое предложит Рассел, — запрет на «смешение уровней»: объект и множество объектов живут на разных уровнях, и нельзя спрашивать «содержит ли множество само себя», потому что элемент и контейнер несравнимы по уровню. Этот запрет и есть зародыш понятия типа.

Частые ошибки

Считать парадокс чисто философским курьёзом. Он сделал работу Фреге неполной и заставил перестроить основания математики.
Думать, что проблема в «бесконечности». Проблема не в размере, а в неограниченном самоприменении и смешении уровней.
Путать парадокс Рассела с парадоксом лжеца. Они родственны (самореференция), но Рассел — про множества и свёртку, лжец — про истинность высказывания.

Итоги

Наивная свёртка «множество всех x со свойством P» приводит к противоречию Рассела.
Из противоречия выводимо всё — система становится бесполезной.
Корень — неограниченное самоприменение и смешение уровней объект/множество.
Решение через «уровни» (типы) родилось именно здесь.