Последовательность

Непротиворечивость теории

В классической дедуктивной логике непротиворечивой является теория , которая не приводит к логическому противоречию . ^[1] Отсутствие противоречия можно определить как семантически , так и синтаксически . Семантическое определение гласит, что теория непротиворечива, если она имеет модель , т. е. существует интерпретация , при которой все формулы теории истинны. Этот смысл используется в традиционной аристотелевской логике , хотя в современной математической логике вместо этого используется термин «выполнимый» . Синтаксическое определение утверждает, что теория непротиворечива, если не существует формулы , в которой и то, и другое, а также ее отрицание являются элементами множества следствий . Пусть – набор закрытых предложений (неформально «аксиом») и набор закрытых предложений, доказуемых с помощью некоторой (заданной, возможно неявно) формальной дедуктивной системы. Набор аксиом непротиворечив , когда не существует такой формулы, что и . ^[2] ${\displaystyle T}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \lnot \varphi }$ ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle \langle A\rangle }$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi \in \langle A\rangle }$ ${\displaystyle \lnot \varphi \in \langle A\rangle }$

Если существует дедуктивная система, для которой эти семантические и синтаксические определения эквивалентны для любой теории, сформулированной в той или иной дедуктивной логике , то такая логика называется полной . ^{[ нужна цитата ]} Полнота исчисления предложений была доказана Полом Бернейсом в 1918 году ^{[ нужна цитата ] [3]} и Эмилем Постом в 1921 году, ^[4] , а полнота исчисления предикатов была доказана Куртом Гёделем в 1930 году, ^[5] а доказательства непротиворечивости арифметики, ограниченной схемой аксиом индукции, были доказаны Аккерманом (1924), фон Нейманом (1927) и Эрбраном (1931). ^[6] Более сильные логики, такие как логика второго порядка , не являются полными.

Доказательство непротиворечивости — это математическое доказательство непротиворечивости конкретной теории. ^[7] Раннее развитие математической теории доказательств было вызвано желанием обеспечить финитарные доказательства непротиворечивости для всей математики в рамках программы Гильберта . На программу Гильберта сильно повлияли теоремы о неполноте , которые показали, что достаточно сильные теории доказательств не могут доказать свою непротиворечивость (при условии, что они непротиворечивы).

Хотя непротиворечивость можно доказать с помощью теории моделей, часто это делается чисто синтаксическим способом, без необходимости ссылаться на какую-либо модель логики. Устранение разреза (или, что то же самое, нормализация основного исчисления , если таковое имеется) подразумевает непротиворечивость исчисления: поскольку не существует доказательства ложности без разрезов, то и противоречия в целом нет.

Непротиворечивость и полнота в арифметике и теории множеств

В теориях арифметики, таких как арифметика Пеано , существует сложная связь между непротиворечивостью теории и ее полнотой . Теория является полной, если для каждой формулы φ на ее языке хотя бы одна из φ или ¬φ является логическим следствием теории.

Арифметика Пресбургера — это система аксиом для слагаемых натуральных чисел. Это одновременно последовательно и полно.

Теоремы Гёделя о неполноте показывают, что любая достаточно сильная рекурсивно перечислимая теория арифметики не может быть одновременно полной и непротиворечивой. Теорема Гёделя применима к теориям арифметики Пеано (PA) и примитивно-рекурсивной арифметики (PRA), но не к арифметике Пресбургера .

Более того, вторая теорема Гёделя о неполноте показывает, что непротиворечивость достаточно сильных рекурсивно перечислимых теорий арифметики может быть проверена особым способом. Такая теория непротиворечива тогда и только тогда, когда она не доказывает конкретное предложение, называемое предложением Гёделя теории, которое представляет собой формализованное утверждение утверждения о том, что теория действительно непротиворечива. Таким образом, непротиворечивость достаточно сильной, рекурсивно перечислимой и непротиворечивой теории арифметики никогда не может быть доказана в самой этой системе. Тот же результат верен для рекурсивно перечислимых теорий, которые могут описать достаточно сильный фрагмент арифметики, включая теории множеств, такие как теория множеств Цермело – Френкеля (ZF). Эти теории множеств не могут доказать свое собственное предложение Гёделя — при условии, что они непротиворечивы, во что обычно верят.

Поскольку непротиворечивость ZF не доказуема в ZF, более слабое понятиеотносительная непротиворечивость интересна в теории множеств (и в других достаточно выразительных аксиоматических системах). ЕслиT—теория, аA— дополнительнаяаксиома,T+Aназывается непротиворечивым относительноT(или простоAнепротиворечиво сT), если можно доказать, что еслиTнепротиворечиво, тоT+Aнепротиворечиво. Если иA, и ¬AсогласуютсясT, тоговорят, чтоAнезависитотT.

Логика первого порядка

Обозначения

В следующем контексте математической логики символ турникета означает «доказуемый». То есть читается: b доказуемо из a (в некоторой заданной формальной системе). ${\displaystyle \vdash }$ ${\displaystyle a\vdash b}$

Определение

• Набор формул в логике первого порядка непротиворечив (записывается ), если не существует формулы такой, что и . В противном случае противоречиво (написано ). ${\displaystyle \Phi }$ ${\displaystyle \operatorname {Con} \Phi }$ ${\displaystyle \varphi }$ ${\displaystyle \Phi \vdash \varphi }$ ${\displaystyle \Phi \vdash \lnot \varphi }$ ${\displaystyle \Phi }$ ${\displaystyle \operatorname {Inc} \Phi }$
• ${\displaystyle \Phi }$называется просто непротиворечивым, если ни для одной формулы оба и отрицание не являются теоремами . ^{[ нужны разъяснения ]} ${\displaystyle \varphi }$ ${\displaystyle \Phi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \Phi }$
• ${\displaystyle \Phi }$называется абсолютно непротиворечивым или непротиворечивым по Посту, если хотя бы одна формула на языке не является теоремой . ${\displaystyle \Phi }$ ${\displaystyle \Phi }$
• ${\displaystyle \Phi }$называется максимально непротиворечивым, если оно непротиворечиво и для каждой формулы следует . ${\displaystyle \Phi }$ ${\displaystyle \varphi }$ ${\displaystyle \operatorname {Con} (\Phi \cup \{\varphi \})}$ ${\displaystyle \varphi \in \Phi }$
• ${\displaystyle \Phi }$говорят, что он содержит свидетелей , если для каждой формулы вида существует такой терм , что , где обозначает замену каждого в на ; см. также Логика первого порядка . ^{[ нужна цитата ]} ${\displaystyle \exists x\,\varphi }$ ${\displaystyle t}$ ${\displaystyle (\exists x\,\varphi \to \varphi {t \over x})\in \Phi }$ ${\displaystyle \varphi {t \over x}}$ ${\displaystyle x}$ ${\displaystyle \varphi }$ ${\displaystyle t}$

Основные результаты

1. Следующие действия эквивалентны:
   1. ${\displaystyle \operatorname {Inc} \Phi }$
   2. Для всех ${\displaystyle \varphi ,\;\Phi \vdash \varphi .}$
2. Каждый выполнимый набор формул непротиворечив, причем набор формул выполним тогда и только тогда, когда существует модель такая, что . ${\displaystyle \Phi }$ ${\displaystyle {\mathfrak {I}}}$ ${\displaystyle {\mathfrak {I}}\vDash \Phi }$
3. Для всех и : ${\displaystyle \Phi }$ ${\displaystyle \varphi }$
   1. если нет , то ; ${\displaystyle \Phi \vdash \varphi }$ ${\displaystyle \operatorname {Con} \left(\Phi \cup \{\lnot \varphi \}\right)}$
   2. если и , то ; ${\displaystyle \operatorname {Con} \Phi }$ ${\displaystyle \Phi \vdash \varphi }$ ${\displaystyle \operatorname {Con} \left(\Phi \cup \{\varphi \}\right)}$
   3. если , то или . ${\displaystyle \operatorname {Con} \Phi }$ ${\displaystyle \operatorname {Con} \left(\Phi \cup \{\varphi \}\right)}$ ${\displaystyle \operatorname {Con} \left(\Phi \cup \{\lnot \varphi \}\right)}$
4. Пусть – максимально непротиворечивый набор формул и пусть он содержит свидетели . Для всех и : ${\displaystyle \Phi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$
   1. если , то , ${\displaystyle \Phi \vdash \varphi }$ ${\displaystyle \varphi \in \Phi }$
   2. либо или , ${\displaystyle \varphi \in \Phi }$ ${\displaystyle \lnot \varphi \in \Phi }$
   3. ${\displaystyle (\varphi \lor \psi )\in \Phi }$тогда и только тогда, когда или , ${\displaystyle \varphi \in \Phi }$ ${\displaystyle \psi \in \Phi }$
   4. если и , то , ${\displaystyle (\varphi \to \psi )\in \Phi }$ ${\displaystyle \varphi \in \Phi }$ ${\displaystyle \psi \in \Phi }$
   5. ${\displaystyle \exists x\,\varphi \in \Phi }$тогда и только тогда, когда существует такой термин, что . ^{[ нужна цитата ]} ${\displaystyle t}$ ${\displaystyle \varphi {t \over x}\in \Phi }$

Теорема Хенкина

Пусть — набор символов . Пусть – максимально непротиворечивый набор -формул, содержащих свидетелей . ${\displaystyle S}$ ${\displaystyle \Phi }$ ${\displaystyle S}$

Определите отношение эквивалентности на множестве -термов с помощью if , где обозначает равенство . Обозначим через класс эквивалентности термов, содержащих ; и пусть где - набор терминов, основанный на наборе символов . ${\displaystyle \sim }$ ${\displaystyle S}$ ${\displaystyle t_{0}\sim t_{1}}$ ${\displaystyle \;t_{0}\equiv t_{1}\in \Phi }$ ${\displaystyle \equiv }$ ${\displaystyle {\overline {t}}}$ ${\displaystyle t}$ ${\displaystyle T_{\Phi }:=\{\;{\overline {t}}\mid t\in T^{S}\}}$ ${\displaystyle T^{S}}$ ${\displaystyle S}$

Определите - структуру над , также называемую терминальной структурой , соответствующей , следующим образом: ${\displaystyle S}$ ${\displaystyle {\mathfrak {T}}_{\Phi }}$ ${\displaystyle T_{\Phi }}$ ${\displaystyle \Phi }$

1. для каждого символа -арного отношения определите, если ^[8] ${\displaystyle n}$ ${\displaystyle R\in S}$ ${\displaystyle R^{{\mathfrak {T}}_{\Phi }}{\overline {t_{0}}}\ldots {\overline {t_{n-1}}}}$ ${\displaystyle \;Rt_{0}\ldots t_{n-1}\in \Phi ;}$
2. для каждого символа -арной функции определите ${\displaystyle n}$ ${\displaystyle f\in S}$ ${\displaystyle f^{{\mathfrak {T}}_{\Phi }}({\overline {t_{0}}}\ldots {\overline {t_{n-1}}}):={\overline {ft_{0}\ldots t_{n-1}}};}$
3. для каждого постоянного символа определите ${\displaystyle c\in S}$ ${\displaystyle c^{{\mathfrak {T}}_{\Phi }}:={\overline {c}}.}$

Определите назначение переменной для каждой переменной . Позвольте быть интерпретацией термина , связанной с . ${\displaystyle \beta _{\Phi }}$ ${\displaystyle \beta _{\Phi }(x):={\bar {x}}}$ ${\displaystyle x}$ ${\displaystyle {\mathfrak {I}}_{\Phi }:=({\mathfrak {T}}_{\Phi },\beta _{\Phi })}$ ${\displaystyle \Phi }$

Тогда для каждой -формулы : ${\displaystyle S}$ ${\displaystyle \varphi }$

${\displaystyle {\mathfrak {I}}_{\Phi }\vDash \varphi }$тогда и только тогда, когда ^{[ нужна ссылка ]} ${\displaystyle \;\varphi \in \Phi .}$

Эскиз доказательства

Есть несколько вещей, которые нужно проверить. Во-первых, это на самом деле отношение эквивалентности. Затем необходимо убедиться, что (1), (2) и (3) корректно определены. Это вытекает из того факта, что это отношение эквивалентности, а также требует доказательства независимости (1) и (2) от выбора представителей класса. Наконец, можно проверить индукцией по формулам. ${\displaystyle \sim }$ ${\displaystyle \sim }$ ${\displaystyle t_{0},\ldots ,t_{n-1}}$ ${\displaystyle {\mathfrak {I}}_{\Phi }\vDash \varphi }$

Теория моделей

В теории множеств ZFC с классической логикой первого порядка ^[9] несогласованная теория — это такая теория, в которой существует замкнутое предложение, содержащее как оба, так и его отрицание . Непротиворечивой теорией называется такая, в которой выполняются следующие логически эквивалентные условия : ${\displaystyle T}$ ${\displaystyle \varphi }$ ${\displaystyle T}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi '}$

1. ${\displaystyle \{\varphi ,\varphi '\}\not \subseteq T}$^[10]
2. ${\displaystyle \varphi '\not \in T\lor \varphi \not \in T}$

Смотрите также

• Философский портал

• Когнитивный диссонанс
• Эквисогласованность
• Проблемы Гильберта
• Вторая проблема Гильберта
• Ян Лукасевич
• Паранепротиворечивая логика
• ω-согласованность
• Доказательство непротиворечивости Генцена
• Доказательство от противного

Сноски

1. Тарский 1946 формулирует это так: «Дедуктивная теория называется последовательной или непротиворечивой, если никакие два утвержденных утверждения этой теории не противоречат друг другу, или, другими словами, если из любых двух противоречивых предложений… хотя бы одно не может быть доказано, (с. 135), где Тарский определяет противоречивое так: «С помощью слова ни одно не образует отрицания какого-либо предложения; два предложения, из которых первое есть отрицание второго, называются противоречивыми предложениями » (с. . 20). Это определение требует понятия «доказательство». Гёдель 1931 определяет это понятие следующим образом: «Класс доказуемых формул определяется как наименьший класс формул, который содержит аксиомы и замкнут по отношению «непосредственное следствие», т. е. формула c для a и b определяется как непосредственное следствие с точки зрения modus ponens или замены, ср. Gödel 1931, van Heijenoort 1967, p. 601. Тарский неформально определяет «доказательство» как «утверждения, следующие друг за другом в определенном порядке в соответствии с определенными принципами… и сопровождаемые соображениями, призванными установить». их обоснованность [истинное заключение] для всех истинных посылок – Reichenbach 1947, с. 68]» см. Тарский 1946, стр. 3. Клини 1952 определяет это понятие либо в отношении индукции, либо в качестве перефразирования) конечной последовательности формул, такой, что каждая формула в последовательности является либо аксиомой, либо «непосредственным следствием» предыдущие формулы; « Доказательство называется доказательством своей последней формулы, и эта формула называется (формально) доказуемой или (формальной) теоремой» (см. Kleene 1952, стр. 83).
2. Ходжес, Уилфрид (1997). Теория более коротких моделей . Нью-Йорк: Издательство Кембриджского университета. п. 37. Пусть – подпись, теория в и предложение в . Мы говорим, что это является следствием или что влечет за собой символы , если каждая модель является моделью . (В частности, если нет моделей, это влечет за собой .) Предупреждение : мы не требуем, чтобы if then существовало доказательство from . В любом случае, в случае с бесконечными языками не всегда ясно, что будет являться доказательством. Некоторые авторы имеют в виду, что это выводится из какого-то конкретного формального исчисления доказательств, и они пишут, исходя из нашего понятия следования (обозначение, которое противоречит нашему ). Для логики первого порядка два вида следствий совпадают по теореме о полноте рассматриваемого исчисления доказательств. Мы говорим, что это действительна или является логической теоремой в символах , если она истинна в каждой -структуре. Мы говорим, что это непротиворечиво , если истинно в некоторой -структуре. Точно так же мы говорим, что теория непротиворечива , если у нее есть модель. Мы говорим, что две теории S и T в L бесконечной омеге эквивалентны, если они имеют одинаковые модели, т. е. если Mod(S) = Mod(T). ${\displaystyle L}$ ${\displaystyle T}$ ${\displaystyle L_{\infty \omega }}$ ${\displaystyle \varphi }$ ${\displaystyle L_{\infty \omega }}$ ${\displaystyle \varphi }$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \varphi }$ ${\displaystyle T\vdash \varphi }$ ${\displaystyle T}$ ${\displaystyle \varphi }$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \varphi }$
   ${\displaystyle T\vdash \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle T}$ ${\displaystyle T\vdash \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle T}$ ${\displaystyle T\models \varphi }$ ${\displaystyle A\models \varphi }$
   ${\displaystyle \varphi }$ ${\displaystyle \vdash \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle L}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle L}$ ${\displaystyle T}$
   (Обратите внимание на определение Mod(T) на стр. 30...)
3. ван Хейеноорт 1967, с. 265 утверждает, что Бернейс определил независимость аксиом Principia Mathematica , результат не был опубликован до 1926 года, но он ничего не говорит о том, что Бернейс доказал их непротиворечивость .
4. Пост доказывает как непротиворечивость, так и полноту исчисления высказываний PM, см. комментарий ван Хейеноорта и Введение Поста в общую теорию элементарных предложений 1931 года в ван Хейеноорте 1967, стр. 264 и далее. Также Тарский 1946, стр. 134 и далее.
5. см. комментарий ван Хейеноорта и Гёделя 1930 г. « Полнота аксиом функционального исчисления логики» в ван Хейеноорте 1967, стр. 582 и далее.
6. см. комментарий ван Хейенорта и статью Эрбрана 1930 г. «О непротиворечивости арифметики» в ван Хейеноорте 1967 г., стр. 618 и далее.
7. Неофициально обычно предполагается теория множеств Цермело – Френкеля; некоторые диалекты неформальной математики обычно дополнительно предполагают аксиому выбора .
8. Это определение не зависит от выбора из- за свойств подстановки и максимальной непротиворечивости . ${\displaystyle t_{i}}$ ${\displaystyle \equiv }$ ${\displaystyle \Phi }$
9. общий случай во многих приложениях к другим областям математики, а также обычный способ рассуждения неформальной математики в исчислении и приложениях к физике, химии, технике
10. по законам Де Моргана

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

• Гёдель, Курт (1 декабря 1931 г.). «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I». Монашефте по математике и физике . 38 (1): 173–198. дои : 10.1007/BF01700692.
• Клини, Стивен (1952). Введение в метаматематику . Нью-Йорк: Северная Голландия. ISBN 0-7204-2103-9.10-е впечатление 1991 года.
• Райхенбах, Ганс (1947). Элементы символической логики . Нью-Йорк: Дувр. ISBN 0-486-24004-5.
• Тарский, Альфред (1946). Введение в логику и методологию дедуктивных наук (второе изд.). Нью-Йорк: Дувр. ISBN 0-486-28462-Х.
• ван Хейеноорт, Жан (1967). От Фреге до Гёделя: Справочник по математической логике . Кембридж, Массачусетс: Издательство Гарвардского университета. ISBN 0-674-32449-8.(пбк.)
• "Последовательность". Кембриджский философский словарь .
• Эббингауз, HD; Флум, Дж.; Томас, В. Математическая логика .
• Джевонс, WS (1870). Элементарные уроки логики .

Внешние ссылки

• Мортенсен, Крис (2017). «Несогласованная математика». Стэнфордская энциклопедия философии .