Парадокс Сколема - Википедия - Skolems paradox

В математическая логика и философия, Парадокс Сколема кажущееся противоречие, возникающее снизу Теорема Левенгейма – Сколема. Торальф Сколем (1922) был первым, кто обсудил кажущиеся противоречивыми аспекты теоремы и открыл относительность теоретико-множественных понятий, ныне известных как не-абсолютность. Хотя это не актуально антиномия подобно Парадокс Рассела, результат обычно называют парадокс, и было описано как «парадоксальное положение дел» Сколемом (1922: с. 295).

Парадокс Сколема в том, что каждый счетный аксиоматизация из теория множеств в логика первого порядка, если это последовательный, имеет модель это счетно. Это кажется противоречивым, потому что с помощью тех же аксиом можно доказать предложение, которое интуитивно говорит (или точно говорит в стандартной модели теории), что существуют несчетные множества. Таким образом, кажущееся противоречие состоит в том, что модель, которая сама счетна и, следовательно, содержит только счетные множества, удовлетворяет предложение первого порядка, которое интуитивно заявляет, что «есть бесчисленные множества».

Математическое объяснение парадокса, показывающее, что это не противоречие в математике, было дано Сколемом (1922). Работы Сколема были резко восприняты Эрнст Цермело, который выступал против ограничений логики первого порядка, но результат быстро был принят математическим сообществом.

Философские последствия парадокса Сколема получили много исследований. В одном из вопросов возникает вопрос, правильно ли утверждение, что любое предложение первого порядка на самом деле утверждает, что «существует бесчисленное множество множеств». Эту мысль можно продолжить, чтобы задать вопрос, является ли какое-либо множество бесчисленным в абсолютном смысле. Совсем недавно в статье «Модели и реальность» Хилари Патнэм, и ответы на него, привели к возобновлению интереса к философским аспектам результата Сколема.

Фон

Один из самых ранних результатов теория множеств, опубликовано Георг Кантор в 1874 г. существовало бесчисленный наборы, такие как powerset из натуральные числа, набор действительные числа, а Кантор набор. Бесконечный набор Икс счетно, если существует функция, которая дает индивидуальная переписка между Икс и натуральные числа, и неисчислим, если нет такой функции соответствия. Когда Цермело предложил свои аксиомы для теории множеств в 1908 году, он доказал, что Теорема кантора от них, чтобы продемонстрировать свою силу.

Левенхайм (1915) и Сколем (1920, 1923) доказали Теорема Левенгейма – Сколема. Обратная форма этой теоремы показывает, что если счетный первый заказ аксиоматизация удовлетворяется любым бесконечным структура, то этим же аксиомам удовлетворяет некоторая счетная структура. В частности, это означает, что если варианты аксиом теории множеств Цермело первого порядка выполнимы, то они выполнимы в некоторой счетной модели. То же самое верно и для любой последовательной аксиоматизации первого порядка теории множеств.

Парадоксальный результат и его математические последствия

Сколем (1922) указал на кажущееся противоречие между теоремой Левенгейма – Сколема, с одной стороны, из которой следует, что существует счетная модель аксиом Цермело, и теоремой Кантора, с другой стороны, которая утверждает, что существуют несчетные множества, и которая доказуемо из аксиом Цермело. «Насколько мне известно, - пишет Сколем, - никто не обратил внимания на это своеобразное и, казалось бы, парадоксальное положение вещей. С помощью аксиом мы можем доказать существование высших мощностей ... Как же это может быть тогда, что весь домен B [счетная модель аксиом Цермело] уже может быть перечислена с помощью конечных положительных целых чисел? »(Сколем 1922, стр. 295, перевод Бауэра-Менгельберга)

В частности, пусть B быть счетной моделью аксиом Цермело. Тогда есть какой-то набор ты в B такой, что B удовлетворяет формуле первого порядка, согласно которой ты бесчисленное множество. Например, ты можно было бы принять как набор действительных чисел в B. Теперь, потому что B счетно, есть только счетное количество элементов c такой, что c ∈ ты в соответствии с B, потому что есть только счетное количество элементов c в B начать с. Таким образом, получается, что ты должно быть счетным. Это парадокс Сколема.

Сколем объяснил, почему нет противоречия. В контексте конкретной модели теории множеств термин «множество» не относится к произвольному множеству, а только к множеству, которое фактически включено в модель. Определение счетности требует наличия определенного взаимно однозначного соответствия, которое само является набором. Таким образом, можно распознать, что конкретный набор ты является счетным, но не счетным в конкретной модели теории множеств, потому что в модели нет набора, который дает взаимно однозначное соответствие между ты и натуральные числа в этой модели.

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

Сколем использовал термин «относительный» для описания этого положения дел, когда одно и то же множество включено в две модели теории множеств, может быть исчислено в одной модели и не подсчитано в другой модели. Он назвал это «наиболее важным» результатом в своей статье. Современные теоретики множеств описывают концепции, которые не зависят от выбора переходная модель в качестве абсолютный. С их точки зрения, парадокс Сколема просто показывает, что счетность не является абсолютным свойством в логике первого порядка. (Кунен, 1980, с. 141; Эндертон, 2001, с. 152; Берджесс, 1977, с. 406).

Сколем описал свою работу как критику теории множеств (первого порядка), призванную проиллюстрировать ее слабость как фундаментальной системы:

«Я считал, что было настолько ясно, что аксиоматизация в терминах множеств не является удовлетворительным окончательным основанием математики, что математики по большей части не будут уделять ей особого внимания. Но в последнее время я, к своему удивлению, заметил, что так много математиков думают, что эти аксиомы теории множеств обеспечивают идеальную основу для математики, поэтому мне казалось, что пришло время для критики ». (Эббингаус и ван Дален, 2000, с. 147)

Прием со стороны математического сообщества

Центральной целью ранних исследований теории множеств было найти аксиоматизацию первого порядка для теории множеств, которая была категоричный, что означает, что у аксиом будет ровно одна модель, состоящая из всех множеств. Результат Сколема показал, что это невозможно, что породило сомнения относительно использования теории множеств в качестве основы математики. Потребовалось время, чтобы теория логики первого порядка была развита настолько, чтобы математики смогли понять причину результата Сколема; Никакое решение парадокса не было широко принято в 1920-е годы. Френкель (1928) все еще описывал результат как антиномию:

«Еще не закрыты книги по антиномии, и еще не достигнуто соглашение о ее значении и возможном решении». (Ван Дален и Эббингаус, 2000, с. 147).

В 1925 г. фон Нейман представил новую аксиоматизацию теории множеств, которая превратилась в Теория множеств NBG. Хорошо зная о работе Сколема 1922 года, фон Нейман подробно исследовал счетные модели своих аксиом. В своих заключительных замечаниях фон Нейман отмечает, что не существует категориальной аксиоматизации теории множеств или любой другой теории с бесконечной моделью. Говоря о влиянии парадокса Сколема, он писал:

«В настоящее время мы можем лишь отметить, что у нас есть еще одна причина для сомнений по поводу теории множеств, и что в настоящее время не известно ни одного способа реабилитации этой теории» (Эббингаус и ван Дален, 2000, стр. 148). )

Цермело сначала считал парадокс Сколема мистификацией (van Dalen and Ebbinghaus, 2000, p. 148 ff.) И выступал против него, начиная с 1929 года. Результат Сколема применим только к тому, что сейчас называется логика первого порядка, но Цермело возражал против финишный метаматематика которые лежат в основе логики первого порядка (Kanamori 2004, p. 519 ff.). Цермело утверждал, что его аксиомы следует изучать в логика второго порядка, настройка, в которой результат Сколема не применяется. Цермело опубликовал аксиоматизацию второго порядка в 1930 году и доказал несколько результатов категоричности в этом контексте. Дальнейшая работа Цермело по основам теории множеств после статьи Сколема привела к открытию им теории множеств. совокупная иерархия и оформление бесконечная логика (Ван Дален и Эббингаус, 2000, примечание 11).

Fraenkel и другие. (1973, стр. 303–304) объясняют, почему результат Сколема был настолько неожиданным для теоретиков множеств в 1920-х годах. Теорема Гёделя о полноте и теорема компактности не были доказаны до 1929 г. Эти теоремы пролили свет на поведение логики первого порядка и установили ее конечную природу, хотя первоначальное доказательство теоремы о полноте Гёделя было сложным. Леон Хенкин Альтернативное доказательство теоремы о полноте, которое сейчас является стандартной техникой для построения счетных моделей непротиворечивой теории первого порядка, не было представлено до 1947 года. Таким образом, в 1922 году особые свойства логики первого порядка, допускающие парадокс Сколема пройти еще не разобрались. Теперь известно, что парадокс Сколема уникален для логики первого порядка; если теория множеств изучается с помощью логика высшего порядка с полной семантикой он не имеет никаких счетных моделей из-за используемой семантики.

Текущее математическое мнение

Современные математические логики не считают парадокс Сколема какой-либо фатальной ошибкой в ​​теории множеств. Клини (1967, с. 324) описывает результат как «не парадокс в смысле прямого противоречия, а скорее как своего рода аномалию». Изучив аргумент Сколема о том, что результат не является противоречивым, Клини приходит к выводу, что «не существует абсолютного понятия счетности». Хантер (1971, стр. 208) описывает это противоречие как «вряд ли даже парадокс». Fraenkel и другие. (1973, с. 304) объясняют, что современных математиков не больше беспокоит отсутствие категоричности теорий первого порядка, чем их беспокоит заключение Теорема Гёделя о неполноте что нет полного последовательного, эффективного и достаточно сильного набора аксиом первого порядка.

Счетные модели ZF стали обычным инструментом в изучении теории множеств. Принуждение, например, часто объясняется с помощью счетных моделей. Тот факт, что эти счетные модели ZF все еще удовлетворяют теореме о несчетных множествах, не считается патологией; ван Хейеноорт (1967) описывает это как «новую и неожиданную особенность формальных систем». (ван Хейеноорт 1967, стр. 290)

Рекомендации

внешняя ссылка