Парадокс Скулема
Парадокс Скулема — противоречивое рассуждение, описанное впервые норвежским математиком Туральфом Скулемом, связанное с использованием теоремы Лёвенгейма — Скулема для аксиоматической теории множеств.
В отличие от парадокса Рассела, парадокса Кантора, парадокса Бурали-Форти, где при помощи логически верных выводов обнаруживается противоречие, «замаскированное» в исходных посылках, «противоречие» парадокса Скулема возникает от ошибки в рассуждениях, и аккуратное рассмотрение вопроса показывает, что это лишь мнимый парадокс. Тем не менее, рассмотрение парадокса Скулема имеет большую дидактическую ценность.
Формулировка
Если система аксиом любой аксиоматической теории множеств непротиворечива, то она, в силу теорем Гёделя и Лёвенгейма — Скулема, имеет модель и, более того, эта модель может быть построена на натуральных числах. То есть, всего лишь счётное множество объектов M {displaystyle M} (каждый из которых будет соответствовать уникальному множеству) требуется для того, чтобы подобрать значение предиката x ∈ y {displaystyle xin y} для каждой пары объектов, полностью удовлетворяющее аксиомам этой теории (например, ZF или ZFC — в предположении их непротиворечивости, см. Аксиоматика теории множеств). В такой ситуации для каждого объекта модели y {displaystyle y} лишь конечное или счётное количество объектов (больше просто нет в предметной области) могут входить в отношение … ∈ y {displaystyle ldots in y} . Фиксируем такую модель M {displaystyle {mathfrak {M}}} со счётным M {displaystyle M} в качестве предметной области.
В силу теорем ZF, вне зависимости от принятой модели в ZF выводимо, например, существование терма P ( ω ) {displaystyle {mathcal {P}}(omega )} , мощность которого несчётна. Но в счётной модели любое множество вынужденно не более, чем счётно — противоречие?
Разрешение
Проведём рассуждение аккуратно. Факт Z F ⊢ ∃ x ( x = P ( ω ) ) {displaystyle mathrm {ZF} vdash exists x(x={mathcal {P}}(omega ))} означает, что существует такой объект c ∈ M {displaystyle cin M} , что формула первого порядка, соответствующая выражению x = P ( ω ) {displaystyle x={mathcal {P}}(omega )} , истинна в модели M {displaystyle {mathfrak {M}}} на оценке, при которой индивидной переменной x {displaystyle x} поставлен в соответствие объект c {displaystyle c} . Теорема Кантора утверждает, что x {displaystyle x} — несчётно, что по определению значит
Z F ⊢ ¬ ∃ f ( f {displaystyle mathrm {ZF} vdash eg exists f(f} — биекция между P ( ω ) {displaystyle {mathcal {P}}(omega )} и ω ) ∧ ∃ f ( f {displaystyle omega )land exists f(f} — биекция между ω {displaystyle omega } и ω ∪ ω ) , {displaystyle omega cup {omega }),}где « f {displaystyle f} — биекция между A {displaystyle A} и B {displaystyle B} » означает ∀ x ∀ y ( ⟨ x , y ⟩ ∈ f ⇔ ( x ∈ A ∧ y ∈ B ) ) {displaystyle forall xforall y(langle x,;y angle in fLeftrightarrow (xin Aland yin B))} , где ⟨ x , y ⟩ {displaystyle langle x,;y angle } — любое кодирование упорядоченных пар, например, ⟨ x , y ⟩ = { x , y , { x } } {displaystyle langle x,;y angle ={x,;y,;{x}}} .
Но это значит лишь то, что среди элементов M {displaystyle M} нет такого f {displaystyle f} , что в модели M {displaystyle {mathfrak {M}}} оно удовлетворяло бы свойствам биекции между P ( ω ) {displaystyle {mathcal {P}}(omega )} и ω {displaystyle omega } . При этом не важно, что в отношение принадлежности с объектом из M {displaystyle M} , соответствующим терму P ( ω ) {displaystyle {mathcal {P}}(omega )} может входить не более чем счётное число объектов из M {displaystyle M} — важно то, что среди объектов M {displaystyle M} не существует f {displaystyle f} , осуществляющего необходимую биекцию.
Рассуждение «если модель счётна, то в отношение ∈ {displaystyle in } с любым объектом может входить не более чем счётное число объектов» есть рассуждение внешнее по отношению к изучаемой аксиоматической теории и никакой формуле в этой теории не соответствует. С внешней точки зрения на теорию ZF «множество всех множеств» (второй раз слово «множество» здесь обозначает лишь некоторый объект предметной области ZF) может существовать и даже быть счётным, что никак не связано (и потому не может противоречить) с выводимыми в ZF формулами.