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

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

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

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

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

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

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

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

Формальные языки

Бесконечный язык первого порядка $L_{\alpha ,\beta }$, $\alpha$ обычный , $\beta =0$ или $\omega \leq \beta \leq \alpha$, имеет тот же набор символов, что и финитная логика, и может использовать все правила формирования формул финитной логики вместе с некоторыми дополнительными:

• Учитывая набор формул $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 o\pi }$ с $\pi \leq \alpha$ бесконечный кардинал и некоторые более сложные ограничения на $\mathrm {o}$ которые допускают символы функций и предикатов бесконечной арности, с $\mathrm {o}$ контроль максимальной арности функционального символа и $\pi$ управляющие символы предикатов.

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

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

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

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

Если $\beta <\alpha$, формирование универсальных замыканий не всегда возможно, однако для каждой переменной можно добавить дополнительные константные символы, при этом результирующее отношение выполнимости останется прежним. Чтобы этого избежать, некоторые авторы используют другое определение языка. $L_{\alpha ,\beta }$ запрещающий формулам иметь более $\beta$ свободные переменные.

Ниже представлены схемы логических аксиом, характерные для бесконечной логики. Глобальные переменные схемы: $\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 }$

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

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

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

Логика в языке $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 .