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

В классической дедуктивной логике , последовательная теория является один , что не влечет за собой противоречие . ^[1] Отсутствие противоречий можно определить семантическими или синтаксическими терминами. Семантическое определение утверждает, что теория непротиворечива, если у нее есть модель , т. Е. Существует интерпретация, при которой все формулы в теории истинны. Именно в этом смысле используется традиционная аристотелевская логика , хотя в современной математической логике вместо этого используется термин выполнимый . Синтаксическое определение утверждает, что теория непротиворечива, если нет формулы ${\ displaystyle T}$ ${\ displaystyle \ varphi}$ такие, что оба и его отрицание являются элементами множества последствий . Позвольте быть набором закрытых предложений (неформально «аксиом») и набором закрытых предложений, доказываемых из- под некоторой (указанной, возможно, неявно) формальной дедуктивной системы. Множество аксиом является последовательным , когда без всякой формулы . ^[2] ${\ 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}$

Если существует дедуктивная система, для которой эти семантические и синтаксические определения эквивалентны любой теории, сформулированной в определенной дедуктивной логике , такая логика называется полной . ^{[ Править ]} Полнота сентенционного исчисления была доказана Павла Бернайсом в 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 , тоНазывается независимой от Т .

Логика первого порядка [ править ]

Обозначение [ править ]

${\ displaystyle \ vdash}$ (Символ турникета) в следующем контексте математической логики означает «доказуемо из». То есть читается так: b доказуемо из a (в некоторой указанной формальной системе). См. Список логических символов . В остальных случаях символ турникета может означать подразумевает; разрешает вывод. См .: Список математических символов . ${\ 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 \ существует х \, \ varphi}$ ${\ displaystyle t}$ ${\ Displaystyle (\ существует х \, \ varphi \ к \ varphi {т \ над х}) \ в \ Phi}$ $\varphi {t \over x}$ $x$ $\varphi$ $t$

Основные результаты [ править ]

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

Теорема Хенкина [ править ]

Позвольте быть набор символов . Пусть - максимально согласованный набор -формул, содержащий свидетелей . $S$ $\Phi$ $S$

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

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

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

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

Затем для каждой формулы : $S$ $\varphi$

${\mathfrak {I}}_{\Phi }\vDash \varphi$ если и только если ^[^{цитата необходима}^] $\;\varphi \in \Phi .$

Эскиз доказательства [ править ]

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

Теория моделей [ править ]

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

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

См. Также [ править ]

В Викицитатнике есть цитаты, связанные с: Последовательность

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

Сноски [ править ]

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

Ссылки [ править ]

Клини, Стивен (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.)
"Последовательность". Кембриджский философский словарь .
Эббингаус, HD; Flum, J .; Томас, В. Математическая логика .
Джевонс, WS (1870). Элементарные уроки логики .

Внешние ссылки [ править ]

Поищите согласованность в Викисловаре, бесплатном словаре.

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

[1] Tarski 1946 заявляет об этом так: «Дедуктивная теория называется последовательной или непротиворечивой, если никакие два утвержденных утверждения этой теории не противоречат друг другу, или, другими словами, если из любых двух противоречащих предложений… по крайней мере одно не может быть доказано, "(стр. 135), где Тарский определяет противоречие следующим образом:" С помощью слова ни одно из них не отрицает ни одно предложение; два предложения, из которых первое является отрицанием второго, называются противоречивыми предложениями "(стр. .20). Это определение требует понятия «доказательство». Гедель 1931 определяет это понятие следующим образом: «Класс доказуемых формулопределяется как наименьший класс формул, который содержит аксиомы и замыкается отношением «немедленное следствие», т. е. формула c для a и b определяется как непосредственное следствие в терминах modus ponens или подстановки; см. Gödel 1931 , van Heijenoort 1967 , p. 601. Тарский неформально определяет «доказательство» как «утверждения следуют одно за другим в определенном порядке согласно определенным принципам… и сопровождаются соображениями, призванными установить их достоверность [истинный вывод для всех истинных посылок - Райхенбах 1947 , стр. 68]» см. Тарский 1946 , стр. 3. Клини, 1952 годопределяет понятие относительно индукции или перефразирования) конечной последовательности формул, так что каждая формула в последовательности является либо аксиомой, либо «непосредственным следствием» предыдущих формул; «А Доказательство называется доказательством из его последней формулы, и эта формула называется (формально) доказуемо или быть (формальная) теорема» сравни Клини 1952 , стр. 83.

[2] Ходжес, Уилфрид (1997). Более короткая модельная теория . Нью-Йорк: Издательство Кембриджского университета. п. 37. Пусть будет подпись, теория в и предложение в . Мы говорим , что это следствие из , или , что влечет за собой , в символах , если каждая модель является моделью . (В частности, если нет моделей, то влечет .) Предупреждение : мы не требуем, чтобы если тогда было доказательство от . В любом случае, с бесконечными языками не всегда ясно, что будет доказательством. Некоторые писатели имеют в виду, что $L$ $T$ $L_{\infty \omega }$ $\varphi$ $L_{\infty \omega }$ $\varphi$ $T$ $T$ $\varphi$ $T\vdash \varphi$ $T$ $\varphi$ $T$ $T$ $\varphi$
$T\vdash \varphi$ $\varphi$ $T$ $T\vdash \varphi$ $\varphi$ выводится из некоторого конкретного формального исчисления доказательств, и они пишут для нашего понятия следования (обозначение, которое противоречит нашему ). Для логики первого порядка два вида следствия совпадают по теореме о полноте рассматриваемого исчисления доказательств. Мы говорим , что это действует , или является логической теоремой , в символах , если это верно в каждой -структуре. Мы говорим, что это непротиворечиво, если верно в некоторой -структуре. Точно так же мы говорим , что теория является последовательной , если она имеет модель. $T$ $T\models \varphi$ $A\models \varphi$
$\varphi$ $\vdash \varphi$ $\varphi$ $L$ $\varphi$ $\varphi$ $L$ $T$
Мы говорим, что две теории S и T в L infinity omega эквивалентны, если они имеют одинаковые модели, т.е. если Mod (S) = Mod (T). (Обратите внимание на определение Mod (T) на стр.30 ...)

[3] Хейенорт 1967 , стр. 265 утверждает, что Бернейс определил независимость аксиом Principia Mathematica , результат не публиковался до 1926 года, но он ничего не говорит о том, что Бернейс доказал их непротиворечивость .

[4] Пост доказывает как непротиворечивость, так и полноту исчисления высказываний PM, см. Комментарий ван Хейенурта и Введение Поста 1931 года в общую теорию элементарных предложений в van Heijenoort 1967 , стр. 264ff. Также Тарский 1946 , стр. 134 и далее.

[5] см. комментарий ван Хейенорта и Гёделя 1930 г. Полнота аксиом функционального исчисления логики у ван Хейенорта 1967 г. , стр. 582ff.

[6] см. комментарий ван Хейенорта и Хербранда 1930 г. О непротиворечивости арифметики у ван Хейенурта 1967 г. , стр. 618 и далее.

[7] Неформально обычно предполагается теория множеств Цермело – Френкеля; некоторые диалекты неформальной математики обычно дополнительно предполагают аксиому выбора .

[8] Это определение не зависит от выбора из-за свойств замещенияи максимальной согласованности. $t_{i}$ $\equiv$ $\Phi$

[9] общий случай во многих приложениях к другим областям математики, а также обычный способ рассуждений неформальной математики в исчислении и приложениях к физике, химии, технике

[10] согласно законам Де Моргана

[1]

vтеЛогическая истина ⊤
Функциональный:	значение истины функция истины ⊨ тавтология
Формально:	теория формальное доказательство теорема
Отрицание	⊥ ложь противоречие непоследовательность