Парадокс Скулема

Парадокс Скулема — противоречивое рассуждение, описанное впервые норвежским математиком Туральфом Скулемом, связанное с использованием теоремы Лёвенгейма — Скулема для аксиоматической теории множеств.

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

Формулировка

Если система аксиом любой аксиоматической теории множеств непротиворечива, то она, в силу теорем Гёделя и Лёвенгейма — Скулема, имеет модель и, более того, эта модель может быть построена на натуральных числах. То есть, всего лишь счётное множество объектов [math]\displaystyle{ M }[/math] (каждый из которых будет соответствовать уникальному множеству) требуется для того, чтобы подобрать значение предиката [math]\displaystyle{ x \in y }[/math] для каждой пары объектов, полностью удовлетворяющее аксиомам этой теории (например, [math]\displaystyle{ \mathrm{ZF} }[/math] или [math]\displaystyle{ \mathrm{ZFC} }[/math] — в предположении их непротиворечивости, см. Аксиоматика теории множеств). В такой ситуации для каждого объекта модели [math]\displaystyle{ y }[/math] лишь конечное или счётное количество объектов (больше просто нет в предметной области) могут входить в отношение [math]\displaystyle{ \ldots\in y }[/math]. Фиксируем такую модель [math]\displaystyle{ \mathfrak M }[/math] со счётным [math]\displaystyle{ M }[/math] в качестве предметной области.

В силу теорем [math]\displaystyle{ \mathrm{ZF} }[/math], вне зависимости от принятой модели в [math]\displaystyle{ \mathrm{ZF} }[/math] выводимо, например, существование терма [math]\displaystyle{ \mathcal P (\omega) }[/math], мощность которого несчётна. Но в счётной модели любое множество вынужденно не более, чем счётно — противоречие?

Разрешение

Проведём рассуждение аккуратно. Факт [math]\displaystyle{ \mathrm{ZF}\vdash\exists x (x=\mathcal P(\omega)) }[/math] означает, что существует такой объект [math]\displaystyle{ c\in M }[/math], что формула первого порядка, соответствующая выражению [math]\displaystyle{ x=\mathcal P(\omega) }[/math], истинна в модели [math]\displaystyle{ \mathfrak M }[/math] на оценке, при которой индивидной переменной [math]\displaystyle{ x }[/math] поставлен в соответствие объект [math]\displaystyle{ c }[/math]. Теорема Кантора утверждает, что [math]\displaystyle{ x }[/math] — несчётно, что по определению значит

[math]\displaystyle{ \mathrm{ZF}\vdash\neg\exists f(f }[/math] — биекция между [math]\displaystyle{ \mathcal P(\omega) }[/math] и [math]\displaystyle{ \omega)\land\exists f(f }[/math] — биекция между [math]\displaystyle{ \omega }[/math] и [math]\displaystyle{ \omega\cup{\omega}), }[/math]

где «[math]\displaystyle{ f }[/math] — биекция между [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math]» означает [math]\displaystyle{ \forall x\forall y(\langle x,\;y\rangle\in f\Leftrightarrow(x\in A\land y\in B)) }[/math], где [math]\displaystyle{ \langle x,\;y\rangle }[/math] — любое кодирование упорядоченных пар, например, [math]\displaystyle{ \langle x,\;y\rangle=\{x,\;y,\;\{x\}\} }[/math].

Но это значит лишь то, что среди элементов [math]\displaystyle{ M }[/math] нет такого [math]\displaystyle{ f }[/math], что в модели [math]\displaystyle{ \mathfrak M }[/math] оно удовлетворяло бы свойствам биекции между [math]\displaystyle{ \mathcal P(\omega) }[/math] и [math]\displaystyle{ \omega }[/math]. При этом не важно, что в отношение принадлежности с объектом из [math]\displaystyle{ M }[/math], соответствующим терму [math]\displaystyle{ \mathcal P(\omega) }[/math] может входить не более чем счётное число объектов из [math]\displaystyle{ M }[/math] — важно то, что среди объектов [math]\displaystyle{ M }[/math] не существует [math]\displaystyle{ f }[/math], осуществляющего необходимую биекцию.

Рассуждение «если модель счётна, то в отношение [math]\displaystyle{ \in }[/math] с любым объектом может входить не более чем счётное число объектов» есть рассуждение внешнее по отношению к изучаемой аксиоматической теории и никакой формуле в этой теории не соответствует. С внешней точки зрения на теорию [math]\displaystyle{ \mathrm{ZF} }[/math] «множество всех множеств» (второй раз слово «множество» здесь обозначает лишь некоторый объект предметной области [math]\displaystyle{ \mathrm{ZF} }[/math]) может существовать и даже быть счётным, что никак не связано (и потому не может противоречить) с выводимыми в [math]\displaystyle{ \mathrm{ZF} }[/math] формулами.

Литература

• Колмогоров А. Н., Драгалин А. Г. Математическая логика. — М.: УРСС, 2005. — 240 с.
• Френкель А. А., Бар-Хиллел И. Основания теории множеств. — М.: Мир, 1966. — 556 с.