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

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

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

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

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

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

Разрешение

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

$\mathrm{ZF}\vdash \neg \exists f(f$ — биекция между $\mathcal P(\omega)$ и $\omega) \and \exists f(f$ - биекция между ω и $\omega \cup {\omega})$, где "f - биекция между A и B" означает $\forall x \forall y(<x, y> \in f \Leftrightarrow (x \in A \and y \in B))$, где < x,y > - любое кодирование пар, например, < x,y > = x,y,x.

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

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

Литература

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