無限論理

Logic that allows infinitely long proofs

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

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

Ω論理と呼ばれるある種の無限論理が完全であるかどうかを検討することは、連続体仮説に光を投げかけることになるだろう。^[3]

表記法と選択公理について

無限に長い式を持つ言語が提示されているため、そのような式を明示的に記述することはできません。この問題を回避するために、厳密に言えば形式言語の一部ではない表記法がいくつか使用されます。は、無限に長い式を指すために使用されます。不明瞭な場合は、シーケンスの長さが後で示されます。この表記があいまいまたは混乱を招く場合は、 などの接尾辞を使用して、基数の一連の式にわたる無限選言を示します。同じ表記が量指定子にも適用できます。たとえば、 です。これは、 のそれぞれに対する量指定子、つまり の無限シーケンスを表すことを意味します。 ${\displaystyle \cdots }$ ${\displaystyle \bigvee _{\gamma <\delta }{A_{\gamma }}}$ ${\displaystyle \delta }$ ${\displaystyle \forall _{\gamma <\delta }{V_{\gamma }:}}$ ${\displaystyle V_{\gamma }}$ ${\displaystyle \gamma <\delta }$

接尾辞およびのすべての使用は、正式な無限言語の一部ではありません。 ${\displaystyle \cdots }$

選択公理は（無限論理を議論するときによく行われるように）合理的な分配法則を持つために必要であるため、仮定されます。

形式言語

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

• を持つ式の集合が与えられた場合、およびは式です。(いずれの場合も、シーケンスの長さは です。) ${\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]カープはまた、無限基数を持つ言語と、関数記号と述語記号の無限引数を許容するより複雑な制限を定義し、関数記号の最大引数を制御し、述語記号を制御した。^[6] ${\displaystyle L_{\kappa \,\lambda o\pi }}$ ${\displaystyle \pi \leq \kappa }$ ${\displaystyle \mathrm {o} }$ ${\displaystyle \mathrm {o} }$ ${\displaystyle \pi }$

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

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

無限論理における理論とは 、論理における文の集合である。無限論理における理論からの証明とは、以下の条件を満たす（場合によっては無限の）文の列である。各文は、論理公理、 の要素、または推論規則を用いて前の文から演繹される。前述のように、有限論理におけるすべての推論規則に加えて、以下の追加の規則も使用できる。 ${\displaystyle T}$ ${\displaystyle L_{\alpha ,\beta }}$ ${\displaystyle T}$ ${\displaystyle T}$

• 証明の中で以前に現れた一連のステートメントが与えられれば、ステートメントは推論できる。^[7] ${\displaystyle A=\{A_{\gamma }|\gamma <\delta <\alpha \}}$ ${\displaystyle \land _{\gamma <\delta }{A_{\gamma }}}$

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

無限論理に特有の論理公理スキーマを以下に示します。グローバルスキーマ変数：およびとなるもの。 ${\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つの公理スキームは、特定の集合が整列可能である必要があるため、選択公理を必要とする。最後の公理スキームは、チャンの分配法則^[10]が示唆するように、厳密には不要であるが、論理の自然な弱化を可能にする自然な方法として含まれている。

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

理論とは、文の集合のことである。モデル内の文の真偽は再帰によって定義され、有限論理の定義と一致する。ただし、有限論理の定義と理論 T が共に定義されている場合は、その定義と一致する。理論Tが与えられた場合、ある文が理論Tの全てのモデルにおいて真であるとき、その文は理論Tに対して妥当であるとされる。

言語における論理が完全であるとは、あらゆるモデルにおいて妥当なすべての文Sに対してSの証明が存在する場合である。任意の理論Tにおいて、 Tにおいて妥当なすべての文Sに対して、 TからSの証明が存在する場合である。無限論理は、強く完全でなくても完全となり得る。 ${\displaystyle L_{\alpha ,\beta }}$

基数が弱コンパクトとは、最大で個数の論理式を含む の任意の理論 T に対して、基数が 未満の任意の S T がモデルを持つ場合、Tがモデルを持つ場合である。基数が強コンパクトとは、 の任意の理論Tに対して、サイズに制限なく、基数が 未満の任意のS Tがモデルを持つ場合、T がモデルを持つ場合である。 ${\displaystyle \kappa \neq \omega }$ ${\displaystyle L_{\kappa ,\kappa }}$ ${\displaystyle \kappa }$ ${\displaystyle \subseteq }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \neq \omega }$ ${\displaystyle L_{\kappa ,\kappa }}$ ${\displaystyle \subseteq }$ ${\displaystyle \kappa }$

無限論理で表現できる概念

集合論の言語では、次の文が基礎を表します。

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

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

可算言語の真理述語は で定義できる。^[12] ${\displaystyle {\mathcal {L}}_{\omega _{1},\omega }}$

完全な無限論理

完全性において際立った無限論理が2つあります。それはとの論理です。前者は標準的な有限一階述語論理であり、後者は可算サイズの文のみを許容する無限論理です。 ${\displaystyle L_{\omega ,\omega }}$ ${\displaystyle L_{\omega _{1},\omega }}$

の論理も、強力に完全、コンパクト、強力にコンパクトです。 ${\displaystyle L_{\omega ,\omega }}$

の論理はコンパクトではないが、（上記の公理の下では）完全である。さらに、クレイグの補間特性の変種も満たす。 ${\displaystyle L_{\omega _{1},\omega }}$

の論理が（上記の公理の下で）強く完全である場合、 は強くコンパクトです（これらの論理の証明では、与えられた公理の 1 つ以上を使用できないため）。 ${\displaystyle L_{\alpha ,\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

参考文献

1. ムーア、グレゴリー・H. (1997). 「無限論理の前史：1885–1955」.ダッラ・キアラ、マリア・ルイサ、ドゥーツ、キース、ムンディチ、ヨハン・ヴァン・ベンテム（編）. 『科学における構造と規範』 . シュプリンガー・サイエンス+ビジネスメディア. pp.  105– 123. doi :10.1007/978-94-017-0538-7_7. ISBN 978-94-017-0538-7。
2. 金森章弘(2004). 「ツェルメロと集合論」(PDF)。記号論理学の会報。10 (4): 487–553 .土井:10.2178/bsl/1102083759 。2023 年8 月 22 日に取得。
3. Woodin, W. Hugh (2011). 「連続体仮説、集合のジェネリック多元宇宙、そしてΩ予想」. Kennedy, Juliette ; Kossak, Roman (編). 『集合論、算術、そして数学の基礎：定理と哲学』 . Cambridge University Press. pp.  13– 42. doi :10.1017/CBO9780511910616.003. ISBN 978-0-511-91061-6. 2024年3月1日時点のオリジナルよりアーカイブ。2024年3月1日閲覧。
4. カープ 1964年、1～2頁。
5. Karp 1964、1ページ。
6. カープ 1964年、101～102ページ。
7. カープ 1964年、39～54頁。
8. カープ 1964年、127ページ。
9. JL Bell, "Infinitary Logic". スタンフォード哲学百科事典、2023年改訂。2024年7月26日にアクセス。
10. Chang, CC (1957). 「α完全ブール代数の表現について」.アメリカ数学会誌. 85 (1): 208– 218. doi : 10.1090/S0002-9947-1957-0086792-1 .
11. ベネット、デイビッド・W. (1980). 「ジャンクション」.ノートルダム形式論理ジャーナル. 21 (1): 111– 118. doi : 10.1305/ndjfl/1093882943 .
12. ポゴノフスキ、イェジ (2010 年 6 月 10 日)。 「対象モデルに対する言い知れぬ憧れ」（PDF）。ザクワド・ロジキ・ストソワニ。Uniwersytet im。アダマ・ミツキェヴィツァとポズナニウ。 p. 4. 2024 年 5 月 24 日のオリジナル(PDF)からアーカイブ。2024 年3 月 1 日に取得。

出典

• カープ、キャロル・R. (1964). 『無限長表現を持つ言語』ノースホランド出版社. doi :10.1016/S0049-237X(08)70423-3. ISBN 978-0-444-53401-9。 {{cite book}}: ISBN / Date incompatibility (help)
• バーワイズ、ジョン(1969). 「無限論理と許容集合」.記号論理学ジャーナル. 34 (2): 226– 252. doi :10.2307/2271099. JSTOR  2271099.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Infinitary_logic&oldid=1308825452"