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

редактировать

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

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

Содержание

1 Несколько слов о нотации и аксиоме выбора
2 Определение инфинитарных логик гильбертовского типа
3 Полнота, компактность и строгая полнота
4 Понятия, выражаемые в инфинитарной логике
5 Полные инфинитарные логики
6 Ссылки

Слово об обозначениях и избранной аксиоме

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

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

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

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

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

Дан набор формул $A = {A γ | γ < δ < α } {\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$ $A = \ {A _ {\ gamma} | \ gamma <\ delta <\ alpha \ }$ , затем $(A 0 ∨ A 1 ∨ ⋯) {\ displaystyle (A_ {0} \ lor A_ {1} \ lor \ cdots)}$ $(A_ {0} \ lor A_ {1} \ lor \ cdots)$ и $(A 0 ∧ A 1 ∧ ⋯) {\ displaystyle (A_ {0} \ land A_ {1} \ land \ cdots)}$ ${\ displaystyle (A_ {0} \ land A_ {1} \ land \ cdots)}$ - формулы. (В каждом случае последовательность имеет длину $δ {\ displaystyle \ delta}$ $\ delta$ .)
Дан набор переменных $V = {V γ | γ < δ < β } {\displaystyle V=\{V_{\gamma }|\gamma <\delta <\beta \}}$ $V = \ {V _ {\ gamma} | \ gamma <\ delta <\ beta \}$ и формула $A 0 {\ displaystyle A_ {0}}$ $A_ {0}$ , затем $∀ V 0: ∀ V 1 ⋯ (A 0) {\ displaystyle \ forall V_ {0}: \ forall V_ {1} \ cdots (A_ {0})}$ $\ forall V_ {0}: \ forall V_ {1} \ cdots (A_ {0})$ и $∃ V 0: ∃ V 1 ⋯ (A 0) {\ displaystyle \ exists V_ {0}: \ exists V_ {1} \ cdots (A_ {0})}$ $\ exists V_ {0}: \ exists V_ {1 } \ cdots (A_ {0})$ - формулы. (В каждом случае последовательность кванторов имеет длину $δ {\ displaystyle \ delta}$ $\ delta$ .)

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

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

Дан набор утверждений $A = {A γ | γ < δ < α } {\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$ $A = \ {A _ {\ gamma} | \ gamma <\ delta <\ alpha \ }$ , которые встречались ранее в доказательстве, то можно вывести утверждение $∧ γ < δ A γ {\displaystyle \land _{\gamma <\delta }{A_{\gamma }}}$ ${\ displaystyle \ land _ {\ gamma <\ delta} {A _ {\ gamma}}}$ .

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

$((∧ ϵ < δ ( A δ ⟹ A ϵ)) ⟹ ( A δ ⟹ ∧ ϵ < δ A ϵ)) {\displaystyle ((\land _{\epsilon <\delta }{(A_{\delta }\implies A_{\epsilon })})\implies (A_{\delta }\implies \land _{\epsilon <\delta }{A_{\epsilon }}))}$ ${\ displaystyle ((\ land _ {\ epsilon <\ delta} {(A _ {\ delta} \ подразумевает A _ {\ epsilon})}) \ implies (A _ {\ delta} \ implies \ land _ {\ epsilon <\ delta} {A _ {\ epsilon} }))}$
для каждый $γ < δ {\displaystyle \gamma <\delta }$ $\ gamma <\ delta$ , $((∧ ϵ < δ A ϵ) ⟹ A γ) {\displaystyle ((\land _{\epsilon <\delta }{A_{\epsilon }})\implies A_{\gamma })}$ ${\ displaystyle ((\ land _ {\ epsilon <\ delta} {A _ {\ epsilon}}) \ подразумевает A _ {\ gamma})}$
законы распределимости Чанга (для каждого $γ {\ displaystyle \ gamma}$ $\ gamma$ ): $(∨ μ < γ ( ∧ δ < γ A μ, δ)) {\displaystyle (\lor _{\mu <\gamma }{(\land _{\delta <\gamma }{A_{\mu,\delta }})})}$ ${\ displaystyle (\ lor _ {\ mu <\ gamma} {(\ land _ {\ delta <\ gamma } {A _ {\ му, \ дельта}})})}$ , где $∀ μ ∀ δ ∃ ϵ < γ : A μ, δ = A ϵ {\displaystyle \forall \mu \forall \delta \exists \epsilon <\gamma :A_{\mu,\delta }=A_{\epsilon }}$ $\ forall \ mu \ forall \ delta \ exists \ epsilon <\ gamma: A _ {\ mu, \ delta} = A _ {\ epsilon}$ или $A μ, δ = ¬ A ϵ {\ displaystyle A _ {\ mu, \ delta} = \ neg A _ {\ epsilon}}$ $A _ {\ mu, \ delta} = \ neg A _ {\ epsilon}$ и $∀ g ∈ γ γ ∃ ϵ < γ : { A ϵ, ¬ A ϵ } ⊆ { A μ, g ( μ) : μ < γ } {\displaystyle \forall g\in \gamma ^{\gamma }\exists \epsilon <\gamma :\{A_{\epsilon },\neg A_{\epsilon }\}\subseteq \{A_{\mu,g(\mu)}:\mu <\gamma \}}$ $\ forall g \ in \ gamma ^ {\ gamma} \ exists \ epsilon <\ гамма: \ {A _ {\ epsilon}, \ neg A _ {\ epsilon} \} \ substeq \ {A _ {\ mu, g (\ mu)}: \ mu <\ gamma \}$
Для $γ < α {\displaystyle \gamma <\alpha }$ $\ gamma <\ alpha$ , $((∧ μ < γ ( ∨ δ < γ A μ, δ)) ⟹ ( ∨ ϵ < γ γ ( ∧ μ < γ A μ, γ ϵ ( μ)))) {\displaystyle ((\land _{\mu <\gamma }{(\lor _{\delta <\gamma }{A_{\mu,\delta }})})\implies (\lor _{\epsilon <\gamma ^{\gamma }}{(\land _{\mu <\gamma }{A_{\mu,\gamma _{\epsilon }(\mu)})}}))}$ ${\ displaystyle ((\ land _ {\ mu <\ gamma} {(\ lor _ {\ delta <\ g amma} {A _ {\ mu, \ delta}})}) \ подразумевает (\ lor _ {\ epsilon <\ gamma ^ {\ gamma}} {(\ land _ {\ mu <\ gamma} {A _ {\ mu, \ gamma _ {\ epsilon} (\ mu)})}}))}$ , где ${γ ϵ: ϵ < γ γ } {\displaystyle \{\gamma _{\epsilon }:\epsilon <\gamma ^{\gamma }\}}$ $\ {\ gamma _ {\ epsilon }: \ epsilon <\ gamma ^ {\ gamma} \}$ - колодец упорядочение $γ γ {\ displaystyle \ gamma ^ {\ gamma}}$ $\ gamma ^ {\ gamma}$

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

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

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

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

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

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

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

∀ γ < ω V γ : ¬ ∧ γ < ω V γ + ∈ V γ. {\displaystyle \forall _{\gamma <\omega }{V_{\gamma }:}\neg \land _{\gamma <\omega }{V_{\gamma +}\in V_{\gamma }}.\,}

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

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

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

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

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

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

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

Ссылки

Карп, Кэрол Р. (1964), Языки с выражениями бесконечной длины, Амстердам: North-Holland Publishing Co., MR 0176910
Барвайз, Кеннет Джон (1969), «Бесконечная логика и допустимые множества», Journal of Symbolic Logic, 34 (2): 226–252, doi : 10.2307 / 2271099, JSTOR 2271099, MR 0406760