Бесконечная логика - Infinitary logic

An бесконечная логика это логика что позволяет бесконечно долго заявления и / или бесконечно долго доказательства.^[1] Некоторые бесконечные логики могут иметь свойства, отличные от стандартных. логика первого порядка. В частности, бесконечная логика может не быть компактный или полный. Понятия компактности и полноты, эквивалентные в финитарная логика Иногда это не так в бесконечной логике. Поэтому для инфинитарных логик определены понятия сильной компактности и сильной полноты. В этой статье рассматриваются инфинитарные логики гильбертовского типа, поскольку они широко изучены и представляют собой наиболее простые расширения финитной логики. Однако это не единственные сформулированные или изученные бесконечные логики.

Рассмотрение того, названа ли некоторая бесконечная логика Ω-логика полные обещания^[2] пролить свет на гипотеза континуума.

Несколько слов об обозначениях и аксиоме выбора

Поскольку представлен язык с бесконечно длинными формулами, невозможно записать такие формулы явно. Чтобы обойти эту проблему, используется ряд удобных обозначений, которые, строго говоря, не являются частью формального языка. ${\displaystyle \cdots }$ используется для обозначения бесконечно длинного выражения. Если это неясно, длина последовательности указывается позже. Если это обозначение становится двусмысленным или сбивающим с толку, суффиксы, такие как ${\displaystyle \bigvee _{\gamma <\delta }{A_{\gamma }}}$ используются для обозначения бесконечного дизъюнкция над набором формул мощность ${\displaystyle \delta }$. Такое же обозначение может быть применено к кванторам, например ${\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}}$. Это предназначено для представления бесконечной последовательности кванторов для каждого ${\displaystyle V_{\gamma }}$ где ${\displaystyle \gamma <\delta }$.

Любое использование суффиксов и ${\displaystyle \cdots }$ не являются частью формальных бесконечных языков.

Допускается аксиома выбора (как это часто делается при обсуждении бесконечной логики), поскольку это необходимо для разумных законов распределенности.

Определение инфинитарных логик гильбертова типа

Бесконечная логика первого порядка L_{α, β}, α регулярный, β = 0 или ω ≤ β ≤ α, имеет тот же набор символов, что и конечная логика, и может использовать все правила формирования формул конечной логики вместе с некоторыми дополнительными:

• Учитывая набор формул ${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$ тогда ${\displaystyle (A_{0}\lor A_{1}\lor \cdots )}$ и ${\displaystyle (A_{0}\land A_{1}\land \cdots )}$ формулы. (В каждом случае последовательность имеет длину ${\displaystyle \delta }$.)
• Учитывая набор переменных ${\displaystyle V=\{V_{\gamma }|\gamma <\delta <\beta \}}$ и формула ${\displaystyle A_{0}}$ тогда ${\displaystyle \forall V_{0}:\forall V_{1}\cdots (A_{0})}$ и ${\displaystyle \exists V_{0}:\exists V_{1}\cdots (A_{0})}$ формулы. (В каждом случае последовательность кванторов имеет длину ${\displaystyle \delta }$.)

Понятия свободных и связанных переменных одинаково применимы к бесконечным формулам. Как и в финитарной логике, формула, все переменные которой связаны, называется предложение.

А теория T в бесконечной логике ${\displaystyle L_{\alpha ,\beta }}$ это набор предложений в логике. Доказательство в инфинитарной логике из теории T - это последовательность утверждений длины ${\displaystyle \gamma }$ который подчиняется следующим условиям: каждое утверждение является либо логической аксиомой, либо элементом T, либо выводится из предыдущих утверждений с использованием правила вывода. Как и раньше, все правила вывода в финитарной логике можно использовать вместе с одним дополнительным:

• Учитывая набор утверждений ${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$ которые имели место ранее в доказательстве, то утверждение ${\displaystyle \land _{\gamma <\delta }{A_{\gamma }}}$ можно сделать вывод.^[3]

Схемы логических аксиом, характерные для бесконечной логики, представлены ниже. Глобальные переменные схемы: ${\displaystyle \delta }$ и ${\displaystyle \gamma }$ такой, что ${\displaystyle 0<\delta <\alpha }$.

• ${\displaystyle ((\land _{\epsilon <\delta }{(A_{\delta }\implies A_{\epsilon })})\implies (A_{\delta }\implies \land _{\epsilon <\delta }{A_{\epsilon }}))}$
• Для каждого ${\displaystyle \gamma <\delta }$, ${\displaystyle ((\land _{\epsilon <\delta }{A_{\epsilon }})\implies A_{\gamma })}$
• Законы распределительности Чанга (для каждого ${\displaystyle \gamma }$): ${\displaystyle (\lor _{\mu <\gamma }{(\land _{\delta <\gamma }{A_{\mu ,\delta }})})}$, где ${\displaystyle \forall \mu \forall \delta \exists \epsilon <\gamma :A_{\mu ,\delta }=A_{\epsilon }}$ или ${\displaystyle A_{\mu ,\delta }=\neg A_{\epsilon }}$, и ${\displaystyle \forall g\in \gamma ^{\gamma }\exists \epsilon <\gamma :\{A_{\epsilon },\neg A_{\epsilon }\}\subseteq \{A_{\mu ,g(\mu )}:\mu <\gamma \}}$
• Для ${\displaystyle \gamma <\alpha }$, ${\displaystyle ((\land _{\mu <\gamma }{(\lor _{\delta <\gamma }{A_{\mu ,\delta }})})\implies (\lor _{\epsilon <\gamma ^{\gamma }}{(\land _{\mu <\gamma }{A_{\mu ,\gamma _{\epsilon }(\mu )})}}))}$, где ${\displaystyle \{\gamma _{\epsilon }:\epsilon <\gamma ^{\gamma }\}}$ это хороший порядок ${\displaystyle \gamma ^{\gamma }}$

Последние две схемы аксиом требуют аксиомы выбора, потому что определенные множества должны быть хорошо заказывать. Последняя схема аксиом, строго говоря, не нужна, поскольку это следует из законов распределенности Чанга,^[4] однако он включен как естественный способ допустить естественное ослабление логики.

Полнота, компактность и сильная завершенность

Теория - это любой набор утверждений. Истинность утверждений в моделях определяется рекурсией и согласуется с определением для финитной логики, где определены оба. Для теории T утверждение считается справедливым для теории T, если оно верно для всех моделей T.

Логика ${\displaystyle L_{\alpha ,\beta }}$ является полным, если для каждого предложения S, допустимого в каждой модели, существует доказательство S. Оно является сильно полным, если для любой теории T для каждого предложения S, действительного в T, существует доказательство S из T. Бесконечная логика может быть полной без будучи сильно завершенным.

Кардинал ${\displaystyle \kappa \neq \omega }$ является слабо компактный когда для каждой теории T в ${\displaystyle L_{\kappa ,\kappa }}$ содержащие не более ${\displaystyle \kappa }$ много формул, если каждое S ${\displaystyle \subseteq }$ T мощности меньше ${\displaystyle \kappa }$ есть модель, то у T есть модель. Кардинал ${\displaystyle \kappa \neq \omega }$ является сильно компактный когда для каждой теории T в ${\displaystyle L_{\kappa ,\kappa }}$, без ограничения размера, если каждые S ${\displaystyle \subseteq }$ T мощности меньше ${\displaystyle \kappa }$ есть модель, то у T есть модель.

Концепции, выражаемые в бесконечной логике

На языке теории множеств следующее утверждение выражает Фонд:

${\displaystyle \forall _{\gamma <\omega }{V_{\gamma }:}\neg \land _{\gamma <\omega }{V_{\gamma +}\in V_{\gamma }}.\,}$

В отличие от аксиомы основания это утверждение не допускает нестандартных интерпретаций. Концепция чего-либо обоснованность может быть выражена только в логике, которая допускает бесконечно много кванторов в отдельном утверждении. Как следствие, многие теории, в том числе Арифметика Пеано, которые не могут быть должным образом аксиоматизированы в финитарной логике, могут быть в подходящей бесконечной логике. Другие примеры включают теории неархимедовы поля и группы без кручения.^[5] Эти три теории могут быть определены без использования бесконечной количественной оценки; только бесконечные переходы^[6] необходимы.

Полная инфинитарная логика

Выделяются своей законченностью две бесконечные логики. Эти ${\displaystyle L_{\omega ,\omega }}$ и ${\displaystyle L_{\omega _{1},\omega }}$. Первая - это стандартная финитная логика первого порядка, а вторая - бесконечная логика, допускающая только утверждения счетного размера.

${\displaystyle L_{\omega ,\omega }}$ также является сильно полным, компактным и сильно компактным.

${\displaystyle L_{\omega _{1},\omega }}$ не может быть компактным, но является полным (в соответствии с приведенными выше аксиомами). Кроме того, он удовлетворяет варианту Крейг интерполяция свойство.

Если ${\displaystyle L_{\alpha ,\alpha }}$ сильно полно (в соответствии с приведенными выше аксиомами), то ${\displaystyle \alpha }$ сильно компактно (поскольку доказательства в этих логиках не могут использовать ${\displaystyle \alpha }$ или более данных аксиом).

использованная литература

1. Мур, Грегори (1997). Предыстория бесконечной логики: 1885–1955 гг.. Структуры и нормы в науке. С. 105–123. Дои:10.1007/978-94-017-0538-7_7. ISBN  978-90-481-4787-8.
2. Вудин, У. Хью (2009). «Гипотеза континуума, мультивселенная общего положения множеств и гипотеза Ω» (PDF). Коллоквиум Гарвардского университета по логике.
3. Карп, Кэрол (1964). Глава 5 Бесконечная логика высказываний. Исследования по логике и основам математики. 36. С. 39–54. Дои:10.1016 / S0049-237X (08) 70423-3. ISBN  9780444534019.
4. Чанг, Чен-Чунг (1955). «Алгебра и теория чисел» (PDF). Бюллетень Американского математического общества. 61: 325–326.
5. Розингер, Элемер (2010). «Четыре направления по математике и физике». CiteSeerX  10.1.1.760.6726.
6. Беннетт, Дэвид (1980). «Узлы». Журнал формальной логики Нотр-Дам. XXI (1): 111–118. Дои:10.1305 / ndjfl / 1093882943.

• Карп, Кэрол Р. (1964), Языки с выражениями бесконечной длины, Амстердам: Издательство Северной Голландии, Г-Н  0176910
• Барвайз, Кеннет Джон (1969), «Бесконечная логика и допустимые множества», Журнал символической логики, 34 (2): 226–252, Дои:10.2307/2271099, JSTOR  2271099, Г-Н  0406760