無限論理

数理論理学または順序数の概念に詳しくない者はまずそちらの記事を参考にすることが推奨される。

無限論理 (むげんろんり、英: infinitary logic) は、無限に長い言明および／または無限に長い証明を許す論理である。

概要

いくつかの無限論理は標準的な一階述語論理とは異なる性質を持つ。特に、無限論理はコンパクト性や完全性を満たさないことが多い。コンパクト性や完全性の概念は、有限論理においては等価であることもあるが、無限論理においてはそうではない。無限論理においては強いコンパクト性や強い完全性の概念が定義される。この記事では、ヒルベルト型無限論理について主に述べる。この型はかなり研究されてきており、有限論理の最も直接的な拡張を構成している。しかしながら、これらは形式化されているまたは研究対象となっている唯一の無限論理ではない。

Ω-論理という無限論理が完全かどうかを考察することは連続体仮説の解明につながる。

表記法に関する語および選択公理

無限に長い式・句を伴う言語が存在すると、全ての式を書き下すことは不可能である。この問題を避けるには、多くの都合の良い表記法が使われる。これらの表記法自体は厳密に言うと形式言語の一部ではない。 ⋯ {\displaystyle \cdots } は無限に長い式を表すために用いられる。それが明確ではないところでは、式の列の長さが後で記される。この表記法は曖昧で紛らわしいので、濃度 δ {\displaystyle \delta } の式の集合の無限の論理和を示すために、 ∨ γ < δ A γ {\displaystyle \lor _{\gamma <\delta }{A_{\gamma }}} のような添字が用いられる。同じ表記法が、例えば ∀ γ < δ V γ : {\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}} のような量化子に応用されることもある。これは各 V γ {\displaystyle V_{\gamma }} に対する量化子の無限列を表すことを意味する。ここで γ < δ {\displaystyle \gamma <\delta } である。

添字および ⋯ {\displaystyle \cdots } の使用法は全て形式無限言語の一部ではない。選択公理は（無限論理が議論されたときによくなされるのだが）実用的な分配性法則を持つために必須であるとして仮定される。

ヒルベルト型無限論理の定義

一階無限論理Lα,β、ここでαは正則、β = 0 または ω ≤ β ≤ α、は有限論理と同じ記号の集合を持っており、有限論理の式の形成についての全ての規則といくつかの追加規則を用いる：

  • 変数 V = { V γ | γ < δ < β } {\displaystyle V=\{V_{\gamma }|\gamma <\delta <\beta \}} および式 A 0 {\displaystyle A_{0}} の集合について、 ∀ V 0 : ∀ V 1 ⋯ ( A 0 ) {\displaystyle \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})} は式である（それぞれの場合に量化子の列は長さ δ {\displaystyle \delta } を持つ）。
  • 式 A = { A γ | γ < δ < α } {\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}} の集合について、 ( A 0 ∨ A 1 ∨ ⋯ ) {\displaystyle (A_{0}\lor A_{1}\lor \cdots )} および ( A 0 ∧ A 1 ∧ ⋯ ) {\displaystyle (A_{0}\land A_{1}\land \cdots )} は式である（それぞれの場合に列は長さ δ {\displaystyle \delta } を持つ）。

束縛変数の概念は、同様の方法で無限文にも適用される。これらの式における括弧の数は常に有限であることに注意。有限論理と同じように、全ての変数が束縛されている式は文と呼ばれる。

無限論理 L α , β {\displaystyle L_{\alpha ,\beta }} における理論Tは、その論理における言明の集合である。理論Tからの無限論理における証明は以下の条件に従う長さ γ {\displaystyle \gamma } の文の列である：各文は論理的な公理Tの要素であるか、または推論規則を用いて過去の言明から推論（演繹）される。前述のものと同様に、無限論理における全ての推論規則と追加規則を用いることができる：

  • その証明において以前に生じている言明 A = { A γ | γ < δ < α } {\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}} の集合を持つとき、その言明 ∧ γ < δ A γ {\displaystyle \land _{\gamma <\delta }{A_{\gamma }}} は推論可能である。

無限論理に特徴的な論理的公理図式を以下に与える。 0 < δ < α {\displaystyle 0<\delta <\alpha } のような各 δ {\displaystyle \delta } および γ {\displaystyle \gamma } について、以下の論理的公理を持つ：

  • ( ( ∧ ϵ < δ ( A δ ⟹ A ϵ ) ) ⟹ ( A δ ⟹ ∧ ϵ < δ A ϵ ) ) {\displaystyle ((\land _{\epsilon <\delta }{(A_{\delta }\implies A_{\epsilon })})\implies (A_{\delta }\implies \land _{\epsilon <\delta }{A_{\epsilon }}))} 。
  • 各 γ < δ {\displaystyle \gamma <\delta } について、 ( ( ∧ ϵ < δ A ϵ ) ⟹ A γ ) {\displaystyle ((\land _{\epsilon <\delta }{A_{\epsilon }})\implies A_{\gamma })} である。
  • Changの分配性法則（各 γ {\displaystyle \gamma } について）： ( ∨ μ < γ ( ∧ δ < γ A μ , δ ) ) {\displaystyle (\lor _{\mu <\gamma }{(\land _{\delta <\gamma }{A_{\mu ,\delta }})})} 。ここで、 ∀ μ : ∀ δ : ∃ ϵ < γ : A μ , δ = A ϵ {\displaystyle \forall \mu :\forall \delta :\exists \epsilon <\gamma :A_{\mu ,\delta }=A_{\epsilon }} and ∀ 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 \}} 。
  • γ < α {\displaystyle \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 }})}}))} 。ここで、 γ ϵ {\displaystyle \gamma _{\epsilon }} は γ γ {\displaystyle \gamma ^{\gamma }} の整列である。

特定の集合は整列可能でなくてはならないので、最後の二つの公理図式は選択公理を必要とする。 Changの分配性法則が暗示するように最後の公理図式は厳密に言うと不要である。しかしながら、それは自然な論理の弱化を許す自然な方法として含まれる。

完全性、コンパクト性、そして強い完全性

ある理論は言明のあらゆる集合である。モデルにおける言明の真理は再帰によって定義され、両方が定義されるところの有限論理に対する定義と一致する。理論Tが仮定されると、ある言明はTの全てのモデルにおいて真ならば理論Tに対して妥当（恒真）であると言われる。

論理 L α , β {\displaystyle L_{\alpha ,\beta }} は、全てのモデルにおいて妥当な全ての文SについてSの証明が存在するならば完全である。Tにおいて妥当な全ての文Sに関するどんな理論Tについても、TからのSの証明が存在するならば、それは強く完全である。無限論理は強く完全でなくても完全であり得る。

濃度 α {\displaystyle \alpha } の全ての理論Tについて、Tの全ての部分集合Sがモデルを持つならばTはモデルを持つとき、論理はコンパクトである。全ての理論Tについて、Tの全ての部分集合Sがモデルを持つならばTはモデルを持つとき、論理は強くコンパクトである。 ここで、Sは濃度 < α {\displaystyle <\alpha } を持つ。もし論理が強くコンパクトかつ完全であるなら、強く完全である。

L κ , κ {\displaystyle L_{\kappa ,\kappa }} がコンパクトであるなら、濃度 κ ≠ ω {\displaystyle \kappa \neq \omega } は弱くコンパクトである。また、 L κ , κ {\displaystyle L_{\kappa ,\kappa }} が強くコンパクトなら、 κ {\displaystyle \kappa } は強くコンパクトである。

無限論理における概念表現可能性

集合論の言語において、以下の言明は正則性公理（基礎の公理）を表現する：

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

基礎の公理と違って、この言明は非標準の解釈を認めない。整礎性の概念は、個別の言明に無限に多くの量化子を許す論理においてのみ表現できる。その結果、有限論理においては適切に公理化できないペアノ算術を含む多くの理論は適切な無限論理において存在することができる。他の例は非アルキメデス体および捻れのない群の理論を含む。これら三つの群は無限の量化子なしで定義することができる。ここではただ無限の連結が必要となる。

完全無限論理

二つの無限論理は特に完全性が際立っている。それらは、 L ω , ω {\displaystyle L_{\omega ,\omega }} と L ω 1 , ω {\displaystyle L_{\omega _{1},\omega }} である。前者は標準的な有限一階論理で、後者は可算サイズの言明だけを許す無限論理である。

L ω , ω {\displaystyle L_{\omega ,\omega }} もまた強く完全、コンパクト、そして強くコンパクトである。

脚注

  • Karp, Carol R. (1964), Languages with expressions of infinite length, Amsterdam: North-Holland Publishing Co., MR0176910 
  • Barwise, Kenneth Jon (1969), “Infinitary logic and admissible sets”, J. Symbolic Logic 34 (2): 226–252, doi:10.2307/2271099, JSTOR 2271099, MR0406760, https://jstor.org/stable/2271099 

関連項目

外部リンク