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

Для использования в других целях см. Последовательность (значения).

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

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

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

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

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

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

Арифметика пресбургера является системой аксиом для натуральных чисел при сложении. Оно одновременно последовательное и полное.

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

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

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

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

Обозначение

${\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 \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}$-формулы, содержащие свидетели.

Определить отношение эквивалентности ${\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. для каждого ${\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 ;}$^[8]
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 .}$^{[нужна цитата ]}

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

Есть несколько вещей, которые нужно проверить. Во-первых, это ${\displaystyle \sim }$ фактически является отношением эквивалентности. Затем необходимо проверить, что (1), (2) и (3) правильно определены. Это выпадает из того факта, что ${\displaystyle \sim }$ является отношением эквивалентности и также требует доказательства того, что (1) и (2) не зависят от выбора ${\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 ошибка harvnb: нет цели: CITEREFGödel1931 (помощь) определяет это понятие следующим образом: "Класс доказуемые формулы определяется как наименьший класс формул, содержащий аксиомы и замкнутый относительно отношения «немедленное следствие», т. е. формулы c из а и б определяется как немедленное следствие с точки зрения modus ponens или замена; ср Гёдель 1931 ошибка harvnb: нет цели: CITEREFGödel1931 (помощь), van Heijenoort 1967, п. 601. Тарский неофициально определяет «доказательство» как «утверждения следуют друг за другом в определенном порядке в соответствии с определенными принципами ... и сопровождаются соображениями, предназначенными для установления их действительности [истинный вывод для всех истинных посылок - Райхенбах 1947 г., п. 68] "ср Тарский 1946, п. 3. Клини 1952 определяет понятие относительно индукции или перефразирования) конечной последовательности формул, так что каждая формула в последовательности является либо аксиомой, либо «непосредственным следствием» предыдущих формул; "А Доказательство называется доказательством из его последняя формула, и эта формула называется (формально) доказуемо или быть (формальная) теорема "ср. Клини 1952, п. 83.
2. Ходжес, Уилфрид (1997). Более короткая модельная теория. Нью-Йорк: Издательство Кембриджского университета. п. 37. Позволять ${\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}$ является последовательный если есть модель.
   Мы говорим, что две теории S и T в L infinity omega эквивалентны, если они имеют одинаковые модели, то есть если Mod (S) = Mod (T). (Обратите внимание на определение Mod (T) на стр.30 ...)
3. van Heijenoort 1967, п. 265 утверждает, что Бернейс определил независимость аксиом Principia Mathematica, результат не публиковался до 1926 года, но он ничего не говорит о том, что Бернейс доказал свою последовательность.
4. Пост доказывает непротиворечивость и полноту исчисления высказываний ПМ, см. Комментарий ван Хейенорта и пост 1931 года. Введение в общую теорию элементарных предложений в van Heijenoort 1967, стр. 264ff. Также Тарский 1946, pp. 134ff.
5. см. комментарий ван Хейенорта и Гёделя 1930 г. Полнота аксиом функционального исчисления логики в van Heijenoort 1967, стр. 582ff.
6. см. комментарий ван Хейенорта и труд Гербрана 1930 г. О последовательности арифметики в van Heijenoort 1967, стр. 618ff.
7. Неформально обычно предполагается теория множеств Цермело – Френкеля; некоторые диалекты неформальной математики обычно предполагают аксиома выбора Кроме того.
8. Это определение не зависит от выбора ${\displaystyle t_{i}}$ из-за свойств заместительности ${\displaystyle \equiv }$ и максимальная согласованность ${\displaystyle \Phi }$.
9. общий случай во многих приложениях к другим областям математики, а также обычный способ рассуждения неформальная математика в исчислении и приложениях к физике, химии, технике
10. в соответствии с Законы де Моргана

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

• Клини, Стивен (1952). Введение в метаматематику. Нью-Йорк: Северная Голландия. ISBN  0-7204-2103-9. 10-е впечатление 1991 г.
• Райхенбах, Ганс (1947). Элементы символической логики. Нью-Йорк: Дувр. ISBN  0-486-24004-5.
• Тарский, Альфред (1946). Введение в логику и методологию дедуктивных наук (Второе изд.). Нью-Йорк: Дувр. ISBN  0-486-28462-X.
• ван Хейеноорт, Жан (1967). От Фреге до Гёделя: Справочник по математической логике. Кембридж, Массачусетс: Издательство Гарвардского университета. ISBN  0-674-32449-8. (pbk.)
• "Последовательность". Кембриджский философский словарь.
• Ebbinghaus, H.D .; Flum, J .; Томас, В. Математическая логика.
• Джевонс, В. С. (1870). Элементарные уроки логики.

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

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