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

Бесконечная логика — это логика , допускающая бесконечно длинные утверждения и/или бесконечно длинные доказательства . Эта концепция была представлена ​​Цермело в 1930-х годах.

Некоторые бесконечные логики могут иметь свойства, отличные от свойств стандартной логики первого порядка . В частности, бесконечные логики могут не быть компактными или полными . Понятия компактности и полноты, эквивалентные в финитной логике, иногда не являются таковыми в бесконечной логике. Поэтому для инфинитарных логик определены понятия сильной компактности и сильной полноты. В этой статье рассматриваются бесконечные логики гильбертова типа , поскольку они были тщательно изучены и представляют собой наиболее прямое расширение финитной логики. Однако это не единственные бесконечные логики, которые были сформулированы или изучены.

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

об обозначениях и аксиоме

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

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

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

гильбертова

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

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

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

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

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

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

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

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

Полнота, компактность и сильная полнота

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

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

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

выражаемые в

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

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

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

Предикаты истинности для счетных языков определяются в ${\mathcal {L}}_{\omega _{1},\omega }$.

Полная бесконечная логика

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

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

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

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

Источники

• Карп, Кэрол Р. (1964). Языки с выражениями бесконечной длины . Издательство Северной Голландии. дои : 10.1016/S0049-237X(08)70423-3 . ISBN  978-0-444-53401-9 .
• Барвайз, Джон (1969). «Бесконечная логика и допустимые множества». Журнал символической логики . 34 (2): 226–252. дои : 10.2307/2271099 . JSTOR   2271099 .