無限論理

無限論理とは、無限に長い命題や無限に長い証明を許容する論理である。^{[ 1 ]}この概念は1930年代にツェルメロによって導入された。 ^{[ 2 ]}

無限論理の中には、標準的な一階述語論理とは異なる性質を持つものがある。特に、無限論理はコンパクト性や完全性を満たさない場合がある。有限論理では同値なコンパクト性と完全性の概念が、無限論理ではそうでない場合もある。そのため、無限論理においては、強コンパクト性と強完全性の概念が定義される。本稿では、ヒルベルト型無限論理を取り上げる。これは、これまで広く研究されており、有限論理の最も直接的な拡張であるためである。しかし、これらは定式化または研究されてきた唯一の無限論理ではない。

Ω論理と呼ばれるある種の無限論理が完全であるかどうかを検討することは、連続体仮説に光を当てる可能性がある。^{[ 3 ]}

無限に長い数式を扱う言語を提示しているため、そのような数式を明示的に書き表すことは不可能です。この問題を回避するために、厳密には形式言語の一部ではないものの、いくつかの表記上の便宜が用いられます。${\displaystyle \cdots }$は無限に長い式を示すために使用されます。不明瞭な場合は、シーケンスの長さが後に記されます。この表記が曖昧または混乱を招く場合は、次のような接尾辞が使用されます。${\displaystyle \bigvee _{\ガンマ <\デルタ }{A_{\ガンマ }}}$は、基数を持つ式の集合に対する無限の選言を示すために使用される。${\displaystyle \delta }$同じ表記法は量化子にも適用できます。例えば${\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}}$これは無限の数列の量化子を表すことを意図しています。${\displaystyle V_{\gamma }}$どこ${\displaystyle \gamma <\delta }$。

接尾辞の使用と${\displaystyle \cdots }$これらは形式的な無限言語の一部ではない。

選択公理は（無限論理を議論する際によく行われるように）仮定される。なぜなら、これは妥当な分配法則を持つために必要だからである。

一次無限言語${\displaystyle L_{\kappa ,\lambda }}$、${\displaystyle \kappa }$通常、${\displaystyle \lambda =0}$または${\displaystyle \omega \leq \lambda \leq \kappa }$有限論理と同じ記号セットを持ち、有限論理の式形成のためのすべての規則に加えていくつかの追加規則を使用することができます。^{[ 4 ]}

• 一連の数式が与えられた${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$と${\displaystyle |\alpha |<\kappa }$それから${\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 |\beta |<\lambda }$そして数式${\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 }$）

言語には、有限個の項を持つ関数、関係、述語記号も含まれる可能性がある。^{[ 5 ]}カープは言語も定義した。${\displaystyle L_{\kappa \,\lambda o\pi }}$と${\displaystyle \pi \leq \kappa }$無限基数と、より複雑な制約${\displaystyle \mathrm {o} }$無限アリティの関数および述語記号を許容し、${\displaystyle \mathrm {o} }$関数シンボルの最大アリティを制御し、${\displaystyle \pi }$述語記号を制御する。^{[ 6 ]}

自由変数と束縛変数の概念は、無限式にも同様に適用される。有限論理と同様に、すべての変数が束縛されている式は文と呼ばれる。

理論​${\displaystyle T}$無限言語で${\displaystyle L_{\alpha ,\beta }}$は論理における文の集合である。理論からの無限論理の証明${\displaystyle T}$は、次の条件を満たす（おそらく無限の）一連のステートメントです。各ステートメントは、論理公理、または${\displaystyle T}$または、推論規則を用いて以前の記述から推論される。これまでと同様に、有限論理におけるすべての推論規則に加えて、次の規則も使用できる。

• 一連のステートメントが与えられた${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$証明の中で以前に発生したもの、そしてその記述${\displaystyle \land _{\gamma <\delta }{A_{\gamma }}}$推測できる。^{[ 7 ]}

もし${\displaystyle \beta <\alpha }$ただし、普遍閉包を形成することは必ずしも可能ではないが、結果として得られる充足可能性関係が同じままとなるように、各変数に定数記号を追加することができる。^{[ 8 ]}これを避けるために、一部の著者は言語の異なる定義を使用している。${\displaystyle L_{\alpha ,\beta }}$数式が${\displaystyle \beta }$自由変数。^{[ 9 ]}

無限論理に特有の論理公理スキーマを以下に示します。グローバルスキーマ変数：${\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 }}$

最後の 2 つの公理図式は、特定の集合が整列可能でなければならないため、選択公理を必要とします。最後の公理図式は、厳密に言えば、Chang の分配法則が示唆するように不要ですが^{[ 10 ]}、論理の自然な弱化を可能にする自然な方法として含まれています。

理論とは、文の集合のことである。モデルにおける命題の真偽は再帰によって定義され、両方が定義されている有限論理の定義と一致する。理論Tが与えられたとき、文が理論Tに対して有効であるとは、その文がTのすべてのモデルにおいて真である場合をいう。

言語における論理${\displaystyle L_{\alpha ,\beta }}$完全性とは、あらゆるモデルにおいて有効なあらゆる文Sに対して、 Sの証明が存在する場合をいう。強完全性とは、任意の理論Tにおいて、 Tにおいて有効なあらゆる文Sに対して、 TからSの証明が存在する場合をいう。無限論理は、強完全性を持たない場合でも完全であることがある。

枢機卿${\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 }}.\,}$

基礎公理とは異なり、この命題は非標準的な解釈を許容しません。整礎性の概念は、個々の命題に無限の数の量化子を許容する論理でのみ表現できます。 その結果、有限論理では適切に公理化できないペアノ算術を含む多くの理論は、適切な無限論理で表現できます。 他の例としては、非アルキメデス体とねじれのない群の理論があります。これら 3 つの理論は、無限量化を使用せずに定義できます。必要なのは無限の接合^{[ 11 ]}だけです。

可算言語の真理述語は以下のように定義できます。${\displaystyle {\mathcal {L}}_{\omega _{1},\omega }}$[ ^{12 ]​}

完全性において際立つ2つの無限論理がある。これらは次の論理である。${\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 }$（または、与えられた公理のうち複数）。

• カープ、キャロル・R. (1964). 『無限長表現を持つ言語』 ノースホランド出版。doi : 10.1016/S0049-237X(08)70423-3。ISBN 978-0-444-53401-9。{{cite book}}ISBN /日付の不一致（ヘルプ）
• Barwise, Jon (1969 ) . 「無限論理と許容集合」。『記号論理学ジャーナル』34 (2): 226–252。doi : 10.2307 /2271099。JSTOR 2271099。