二階論理

論理学と数学において、第二階論理は第一階論理の拡張であり、第一階論理自体は命題論理の拡張である。^[1]第二階論理は、さらに高階論理と型理論によって拡張される。

第一階述語論理は、個体（談話領域の要素）にわたる変数のみを量化します。第二階述語論理は、さらに関係を量化します。たとえば、第二階述語文は、すべての式Pおよびすべての個体xについて、Px が真であるか、そうでないか（Px）が真であるかのいずれかであると述べています（これは排中律です）。第二階述語論理には、集合、関数、およびその他の変数の量化も含まれます（下のセクションを参照）。第一階述語論理と第二階述語論理はどちらも談話領域（単に「領域」または「宇宙」と呼ばれることが多い）という概念を使用します。領域は、個々の要素を量化できる集合です。 ${\displaystyle \forall P\,\forall x(Px\lor \neg Px)}$

一階述語論理は個体に対しては量化できるが、性質に対しては量化できない。つまり、Cube( b )のような原子文に対して、名前を変数に置き換えて量化子を付けることで量化文を得ることができる。^[2]

∃ x立方体( x )

しかし、述語では同じことはできません。つまり、次の式です。

∃PP( b ) は

は一階述語論理の文ではないが、これは二階述語論理の正当な文である。ここで、Pは述語変数であり、意味的には個体の集合である。^[2]

その結果、2 階論理は 1 階論理よりも表現力が高くなります。たとえば、1 階論理ではすべての立方体と四面体の集合を識別する方法はありません。しかし、この集合の存在は 2 階論理で次のように主張できます。

∃P ∀ x (Px ↔ (Cube( x ) ∨ Tet( x )))。

次に、この集合の特性を主張することができます。たとえば、次の式は、すべての立方体と四面体の集合には十二面体は含まれないことを示しています。

∀P (∀ x (Px ↔ (Cube( x ) ∨ Tet( x ))) → ¬ ∃ x (Px ∧ Dodec( x )))。

第二階量化は、到達可能性プロパティを表現できるため、特に便利です。たとえば、 Parent( x、y ) がx がyの親であることを示す場合、第一階論理ではxがyの祖先であるというプロパティを表現できません。第二階論理では、 y を含み、 Parent 関係で閉じられているすべての人々の集合にx が含まれると表現できます。

∀P ((P y ∧ ∀ a ∀ b ((P b ∧ Parent( a , b )) → P a )) → P x )。

注目すべきは、二階述語論理では述語の変数はあるが、述語のプロパティの変数はないということである。例えば、述語P Cube、Tet、Dodecに対して真となるプロパティSh​​ape( P )があると言うことはできない。これには三階述語論理が必要となる。^[3]

2 階論理の構文は、どの式が適切に形成された式であるかを示します。1階論理の構文に加えて、2 階論理には、変数の新しい種類(型と呼ばれることもあります) が多数含まれています。これらは次のとおりです。

• 個体の集合にわたる変数の一種。S がこの種の変数で t が一階項である場合、式t ∈ S ( S ( t ) または括弧を省略するために St とも表記される)は原子式である。個体の集合は、ドメイン上の単項関係として見ることもできる。
• それぞれの自然数kに対して、個体のすべてのk項関係にわたる一種の変数が存在します。Rがそのようなk項関係変数であり、t ₁ ,..., t _kが 1 次項である場合、式R ( t ₁ ,..., t _k ) は原子式です。
• 各自然数kに対して、定義域のk個の要素を取り、定義域の単一の要素を返すすべての関数にわたる一種の変数が存在します。 f がそのようなk項関数変数であり、t ₁ ,..., t _kが 1 次項である場合、式f ( t ₁ ,..., t _k ) は 1 次項です。

定義した変数はそれぞれ、普遍的および/または存在的に量化して、式を構築することができます。したがって、変数の種類ごとに 2 つの量化子があり、多くの種類があります。第 2 階述語論理の文は、第 1 階述語論理と同様に、自由変数 (いかなる種類も) のない整形式の式です。

上記の定義では関数変数の導入を省略することが可能です (一部の著者はこれを行っています)。これは、n項関数変数は、 n +1項の関係変数と、関係のn +1 番目の引数における「結果」の一意性を表す適切な式で表すことができるためです(Shapiro 2000、p. 63)。

モナディック二階論理(MSO) は二階論理の制限であり、一項関係 (つまり集合) 上の量化のみが許可されます。関数上の量化は、前述の関係と同値であるため、許可されません。これらの制限のない二階論理は、モナディックバージョンと区別するために完全二階論理と呼ばれることがあります。モナディック二階論理は、グラフ理論におけるアルゴリズムのメタ定理であるクールセルの定理のコンテキストで特に使用されます。完全な無限二分木 ( S2S ) の MSO 理論は決定可能です。対照的に、任意の無限集合上の完全二階論理 (またはたとえば (、+) 上の MSO 論理) は、真の二階算術を解釈できます。 ${\displaystyle \mathbb {N} }$

1 階論理と同様に、2 階論理には特定の 2 階言語の非論理記号を含めることができます。ただし、これらには制限があり、それらが形成するすべての項は、1 階項 (1 階変数に置き換えることができる) または 2 階項 (適切な種類の 2 階変数に置き換えることができる) のいずれかである必要があります。

2 階論理の式は、その量指定子 (普遍的または存在的) が 1 階の変数のみに及ぶ場合 (2 階の自由変数を持つ場合もある)、1 階の (または と表記されることもある) と言われます。 (存在 2 階) 式は、2 階の変数に存在量指定子がいくつか追加されている式、つまり、ここで は1 階の式です。存在 2 階式のみで構成される 2 階論理のフラグメントは存在 2 階論理と呼ばれ、ESO、、または ∃SO と略されます。式のフラグメントは双対的に定義され、普遍 2 階論理と呼ばれます。より表現力豊かなフラグメントは、任意のk > 0 に対して相互再帰によって定義されます。はの形式を持ち、ここで は式であり、同様に は の形式を持ち、ここでは式です。( 2 階算術の類似した構築については、解析階層を参照してください。) ${\displaystyle \Sigma _{0}^{1}}$${\displaystyle \Pi _{0}^{1}}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$${\displaystyle \phi}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Sigma _{k+1}^{1}}$${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$${\displaystyle \phi}$${\displaystyle \Pi _{k}^{1}}$${\displaystyle \Pi _{k+1}^{1}}$${\displaystyle \forall R_{0}\ldots \forall R_{m}\phi }$${\displaystyle \phi}$${\displaystyle \Sigma _{k}^{1}}$

2 階論理の意味論は、各文の意味を確立します。1 つの標準意味論しかない 1 階論理とは異なり、2 階論理では、標準意味論とHenkin 意味論という 2 つの異なる意味論が一般的に使用されます。これらの意味論のそれぞれにおいて、1 階の量指定子と論理接続子の解釈は、1 階論理の場合と同じです。2 種類の意味論で異なるのは、2 階変数の量指定子の範囲だけです (Väänänen 2001)。

標準セマンティクス (完全セマンティクスとも呼ばれる) では、量指定子は適切な種類のすべての集合または関数に渡って範囲を持ちます。この条件を満たすモデルは完全モデルと呼ばれ、これらは 2 階量指定子の範囲がモデルの 1 階部分のべき集合であるモデルと同じです。 (2001) したがって、1 階変数のドメインが確立されると、残りの量指定子の意味は固定されます。2 階論理に表現力を与えるのはこれらのセマンティクスであり、この記事の残りの部分ではこれらを前提とします。

レオン・ヘンキン(1950) は、2 階および高階の理論に対して別の種類の意味論を定義した。この意味論では、高階領域の意味は、型理論に基づいて、その範囲に含まれる集合または関数の特性の明示的な公理化によって部分的に決定される。ヘンキン意味論は、標準意味論のように意味論が標準モデルだけに固定されるのではなく、公理のモデルのクラスが存在する、多ソート 1 階意味論の一種である。ヘンキン意味論のモデルは、高階領域の解釈として集合の集合または関数の集合を提供し、これはその種類のすべての集合または関数の適切な部分集合であってもよい。ヘンキンは、この公理化において、 1 階論理に当てはまるゲーデルの完全性定理とコンパクト性定理が、ヘンキン意味論を持つ 2 階論理にも当てはまることを証明した。スコーレム・レーヴェンハイムの定理はヘンキン意味論にも当てはまるので、リンドストロームの定理はヘンキンモデルが単なる偽装された一階モデルであることを意味する。^[4]

2 階算術などの理論では、高階領域の非標準的な解釈の存在は、ヘンキンが使用した型理論から導かれた特定の公理化の欠陥だけではなく、ゲーデルの不完全性定理の必然的な結果でもあります。つまり、ヘンキンの公理は、標準的な解釈が唯一の可能なモデルであることを保証するために、これ以上補足することはできないということです。ヘンキンの意味論は、2 階算術の研究ではよく使用されます。

Jouko Väänänen (2001) は、2 階述語論理の Henkin 意味論と完全意味論の区別は、前者が Lowenheim-Skolem 定理やコンパクト性などのモデル理論的特性に従い、後者がカテゴリ性現象を持つという点で、ZFCの証明可能性とVの真理性の区別に類似していると主張しました。たとえば、「で定義されている が実際の であるかどうかを意味のある形で問うことはできません。しかし、の内部で再定式化すると、再定式化された は可算モデルを持ち、したがってカテゴリカルにはならないことがわかります。」 ${\displaystyle V}$${\displaystyle \mathrm {ZFC} }$${\displaystyle V}$${\displaystyle \mathrm {ZFC} }$${\displaystyle \mathrm {ZFC} }$${\displaystyle \mathrm {ZFC} }$

2 階述語論理は、1 階述語論理よりも表現力が豊かです。たとえば、ドメインがすべての実数の集合である場合、1 階述語論理では、 ∀ x ∃ y ( x + y = 0) と記述して各実数の加法逆数の存在を主張できますが、実数集合の最小上限プロパティを主張するには 2 階述語論理が必要です。これは、すべての有界で空でない実数集合には上限が存在するというものです。ドメインがすべての実数 の集合である場合、次の 2 階述語文 (2 行に分割) は最小上限プロパティを表します。

(∀ A) ([ (∃ w ) ( w ∈ A) ∧ (∃ z )(∀ u )( u ∈ A → u ≤ z ) ]

→ (∃ x )(∀ y )([(∀ w )( w ∈ A → w ≤ x )] ∧ [(∀ u )( u ∈ A → u ≤ y )] → x ≤ y ) )

この式は、「すべての空でない有界集合A には最小上限 がある」を直接形式化したものです。この特性を満たす任意の順序付き体は、実数体と同型であることが示されます。一方、実数で有効な 1 階文の集合は、コンパクト性定理により、任意の大きさのモデルを持ちます。したがって、最小上限特性は、1 階論理の任意の文の集合では表現できません。(実際、すべての実数閉体は、シグネチャで実数と 同じ 1 階文を満たします。)${\displaystyle \langle +,\cdot ,\leq \rangle }$

第二階述語論理では、「定義域は有限である」または「定義域は可算 濃度である」という形式文を書くことができます。定義域が有限であると述べるには、定義域からそれ自身へのすべての全射関数は単射である、という文を使用します。定義域が可算濃度である、という述べるには、定義域のすべての 2 つの無限部分集合の間には一対一が存在する、という文を使用します。コンパクト性定理と上向きレーヴェンハイム・スコーレム定理から、第一階述語論理ではそれぞれ有限性または可算性を特徴付けることはできないこと がわかります。

ESO のような特定の二階述語論理の断片は、完全な二階述語論理より表現力が劣るとはいえ、一階述語論理より表現力が豊かです。ESO は、ヘンキン量指定子で拡張された一階述語論理、ヒンティッカとサンドゥの独立性に適した論理、およびヴァアネネンの依存性論理など、量指定子の依存関係の非線形順序付けを可能にする一階述語論理の拡張と翻訳同等性も備えています。

論理の演繹体系は、どの式のシーケンスが有効な証明を構成するかを決定する一連の推論規則と論理公理です。2 階論理にはいくつかの演繹体系を使用できますが、いずれも標準的な意味論 (以下を参照) に対して完全ではありません。これらの体系はそれぞれ健全であり、つまり、証明に使用できる文はいずれも適切な意味論において論理的に有効であることを意味します。

使用できる最も弱い演繹システムは、第1階述語論理の標準的な演繹システム（自然演繹など）に第2階述語の置換規則を加えたものである。^{[5]この演繹システムは}、第2階算術の研究でよく使用される。

シャピロ（1991）とヘンキン（1950）が考えた演繹システムは、拡張された一階演繹体系に、理解公理と選択公理の両方を追加している。これらの公理は、標準的な二階意味論では妥当である。理解公理と選択公理を満たすヘンキンモデルに限定されたヘンキン意味論では妥当である。^[6]

完全な 2 階意味論を持つ実数の 2 階理論を、次のように 1 階理論に縮小しようと試みる人もいるかもしれません。まず、ドメインをすべての実数の集合から 2 ソートされたドメインに拡張し、2 番目のソートにすべての実数集合を含めます。言語に新しい 2 項述語、つまりメンバーシップ関係を追加します。すると、2 階だった文が 1 階になり、以前は 2 階だった量指定子が 2 番目のソートにまたがるようになります。この縮小は、1 ソート理論で、要素が数か集合かを示す単項述語を追加し、ドメインを実数の集合と実数のべき集合の和集合とすることで試みることができます。

ただし、ドメインが実数のすべての集合を含むと主張されていることに留意してください。この要件は、レーヴェンハイム・スコーレム定理が示すように、一階の文に還元することはできません。この定理は、実数の可算無限部分集合（そのメンバーを内部数と呼ぶ）と、内部数の集合の可算無限コレクション（そのメンバーを「内部集合」と呼ぶ）が存在することを意味しており、内部数と内部集合からなるドメインは、実数と実数集合のドメインが満たすのとまったく同じ一階の文を満たします。特に、これは、事実上、次のような一種の最小上限公理を満たします。

すべての内数の集合が可算であることは（それらが密に順序付けられた集合を形成するという事実と併せて）、その集合が最小上限公理を完全には満たさないことを意味します。すべての内集合の集合が可算であることは、それがすべての内数の集合のすべての部分集合の集合ではないことを意味します（カントールの定理は、可算無限集合のすべての部分集合の集合が非可算無限集合であることを意味するため）。この構成は、スコーレムのパラドックスと密接に関連しています。

したがって、実数と実数の集合の 1 階理論には多くのモデルがあり、そのうちのいくつかは可算です。ただし、実数の 2 階理論にはモデルが 1 つしかありません。これは、アルキメデスの完全 順序体は1 つしかないという古典的な定理と、アルキメデスの完全順序体のすべての公理が 2 階論理で表現可能であるという事実からわかります。これは、実数の 2 階理論にはモデルが 1 つしかないが、対応する 1 階理論には多くのモデルがあるという意味で、実数の 2 階理論を 1 階理論に還元できないことを示しています。

標準的な意味論を持つ二階述語論理の方が一階述語論理よりも表現力に富んでいることを示す、より極端な例があります。連続体仮説が成り立つ場合は実数のみをモデルとし、連続体仮説が成り立たない場合はモデルを持たない有限の二階述語理論があります (cf. Shapiro 2000, p. 105)。この理論は、実数を完全なアルキメデスの順序体として特徴付ける有限理論と、その領域が最初の非可算な濃度であるという公理から構成されます。この例は、二階述語論理の文が一貫しているかどうかという問題が極めて微妙であることを示しています。

2 次論理の追加の制限については、次のセクションで説明します。

ゲーデルの不完全性定理の帰結として、2階の論理式には、これら3つの望ましい属性を同時に満たす演繹体系（つまり証明可能性の概念）は存在しない： ^[7]

• (健全性) 証明可能なすべての 2 階文は普遍的に有効であり、つまり、標準的な意味論の下ではすべての領域で真です。
• (完全性) 標準的な意味論の下では、普遍的に有効な 2 階論理式はすべて証明可能です。
• (有効性)与えられた記号列が証明であるかどうかを正しく判断できる証明確認アルゴリズムが存在します。

この帰結は、二階述語論理は完全な証明理論を許容しない、と表現されることがある。この点で、標準的な意味論を持つ二階述語論理は一階述語論理とは異なる。クワインは（1970、pp. 90-91）は、二階述語論理は厳密に言えば論理ではないと考える理由として、完全な証明体系が存在しないことを指摘した。

前述のように、ヘンキンは、一階述語論理の標準的な演繹体系がヘンキン意味論を持つ二階述語論理に対して健全で完全かつ効果的であること、また、理解と選択の原理を持つ演繹体系がこれらの原理を満たすモデルのみを使用してヘンキン意味論に対して健全で完全かつ効果的であることを証明しました。

コンパクト性定理とレーヴェンハイム・スコーレム定理は、 2階述語論理の完全なモデルでは成立しない。ただし、ヘンキンモデルでは成立する。^{[8] : xi}

述語論理は、二階述語論理という用語を作ったCS ピアースによって数学界に導入され、その記法は現代の形式に最も近い (Putnam 1982)。しかし、今日、ほとんどの論理学の学生はフレーゲの著作のほうがよく知られている。フレーゲはピアースより数年前に著作を発表していたが、バートランド・ラッセルとアルフレッド・ノース・ホワイトヘッドによって有名になるまで、その著作はあまり知られていなかった。フレーゲは、オブジェクトに対する量化と、プロパティおよび集合に対する量化を区別するために異なる変数を使用したが、彼は自分が2つの異なる種類の論理を行っているとは考えてはいなかった。ラッセルのパラドックスが発見された後、彼の体系に何か問題があることが認識された。最終的に、論理学者は、フレーゲの論理をさまざまな方法で、現在では一階述語論理と呼ばれているものに制限することで、この問題が解消されることを発見した。集合とプロパティは、一階述語論理だけでは量化できない。現在標準的な論理の階層構造はこの時期に遡る。

集合論は、一階述語論理の装置内で公理化されたシステムとして定式化できることが発見され（いくつかの種類の完全性が犠牲になるが、ラッセルのパラドックスほどひどいものではない）、これは実際に行われた（ツェルメロ-フランケル集合論を参照）。集合は数学にとって不可欠だからである。 算術、メレオロジー、その他さまざまな強力な論理理論は、一階述語量化以上の論理装置に頼ることなく公理的に定式化することができ、ゲーデルとスコーレムの一階述語論理への固執とともに、二階述語論理（またはそれ以上の階数）の研究は全体的に衰退した。^[要出典]

この否定は、一部の論理学者、特にWV クワインによって積極的に進められました。クワインは、^Fxのような述語言語の文では、「x 」^はオブジェクトを表す変数または名前として考えるべきであり、したがって「すべてのものについて、… である」のように量化できるという見解 [要出典] を提唱しました。ただし、「^F 」は不完全な文の省略形として考えるべきであり、オブジェクトの名前 (プロパティのような抽象的なオブジェクトの名前でさえも) ではありません。たとえば、「… は犬である」という意味かもしれません。しかし、このようなものを量化できると考えるのは意味がありません (このような立場は、概念とオブジェクトの区別に関するフレーゲ自身の議論と非常に一致しています)。したがって、述語を変数として使用することは、個々の変数だけが占めるべき名前の場所を述語が占めることです。この推論は、ジョージ ブーロスによって却下されました。^[要出典]

近年^{[いつ? ] 、}第 2 階の論理は、第 2 階の量化を第 1 階の量化と同じオブジェクトのドメイン上の複数の量化と解釈した Boolos の解釈によって、ある程度回復しました(Boolos 1984)。Boolos はさらに、「一部の批評家はお互いだけを賞賛している」や「フィアンケットの部下の中には、他の誰も同伴せずに倉庫に入った者もいる」などの文が第 1階の量化が不可能であると主張されていることを指摘し、これらの文は第 2 階の量化の完全な力によってのみ表現できると主張しています。ただし、一般化された量化と部分的に順序付けられた(または分岐した) 量化は、第 1 階の量化が不可能であると主張されている特定のクラスの文を表現するのに十分である場合もあり、これらは第 2 階の量化には適していません。

有限構造上のさまざまな形式の第 2 階論理の表現力は、計算複雑性理論と密接に結びついています。記述複雑性の分野では、どの計算複雑性クラスが、そのクラスで言語 (有限文字列の集合) を表現するために必要な論理の力によって特徴付けられるかを研究します。有限アルファベットA内の文字列w  =  w ₁ ··· w _nは、ドメインD  = {1,..., n }、各a  ∈  Aに対してw _i  =  aとなるインデックスiによって満たされる単項述語P _a 、およびどのインデックスがどのインデックスであるかを一意に識別するのに役立つ追加の述語 (通常は、 D上の後続関数のグラフまたは順序関係 < を取り、場合によっては他の算術述語も使用します) を持つ有限構造で表現できます。逆に、任意の有限構造 (有限シグネチャ上) のCayley テーブルは、有限文字列によってエンコードできます。

この識別により、有限構造上の二階論理のさまざまなバリエーションの次のような特徴付けが導かれます。

• REG（正規言語）は、モナドの2階の論理式で定義できる言語の集合である（ビュッヒ・エルゴット・トラクテンブロートの定理、1960年）
• NP は、存在論的な 2 階の式によって定義できる言語の集合です ( Fagin の定理、1974)。
• co-NP は、普遍的な 2 次式によって定義できる言語の集合です。
• PH は、2 次式で定義できる言語の集合です。
• PSPACE は、推移閉包演算子が追加された 2 次式で定義可能な言語のセットです。
• EXPTIME は、最小固定小数点演算子を追加した 2 次式で定義可能な言語のセットです。

これらのクラス間の関係は、有限構造上の論理の相対的な表現力に直接影響します。たとえば、PH  =  PSPACEの場合、2 階論理に推移閉包演算子を追加しても、有限構造上の表現力は向上しません。

• 一階論理
• 高階論理
• レーヴェンハイム数
• オメガ言語
• 第二階命題論理
• モナド二階論理

• アンドリュース、ピーター (2002)。『数理論理学と型理論入門：証明を通して真実へ』（第 2 版）。Kluwer Academic Publishers。
• Boolos, George (1984)。「存在するということは、変数の値であること（またはいくつかの変数のいくつかの値であること）」。Journal of Philosophy。81 ( 8): 430–50。doi : 10.2307 /2026308。JSTOR  2026308。Boolos, Logic, Logic and Logic（1998年）に再録。
•  ヘンキン、 L . (1950)。「型理論における完全性」。記号論理学ジャーナル。15 (2): 81–91。doi : 10.2307/2266967。JSTOR 2266967。S2CID 36309665  。
• Hinman, P. (2005).数学論理学の基礎. AK Peters. ISBN 1-56881-262-0。
• パトナム、ヒラリー（1982）。「論理学者ピアース」。数学史。9 （3）：290-301。doi ：10.1016 /0315-0860（82）90123-9。ヒラリー・パトナム（1990年）『人間の顔をしたリアリズム』ハーバード大学出版局、252-260頁に再録。
• WVクワイン（1970年）。論理の哲学。プレンティスホール。ISBN 9780674665637。
• Rossberg, M. (2004) 「一階論理、二階論理、完全性」(PDF)。V. Hendricks 他編『一階論理の再考』。ベルリン: Logos-Verlag。
• シャピロ，S.（2000）[1991]。基礎主義のない基礎: 第二階論理の事例オックスフォード：クラレンドン・プレス。ISBN 0-19-825029-0。
• Väänänen, J. (2001). 「第 2 階論理と数学の基礎」(PDF) . Bulletin of Symbolic Logic . 7 (4): 504–520. CiteSeerX  10.1.1.25.5579 . doi :10.2307/2687796. JSTOR  2687796. S2CID  7465054.

• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde ; Weinstein, Scott (2007).有限モデル理論とその応用。理論計算機科学テキスト。EATCS シリーズ。ベルリン: Springer- Verlag。ISBN 978-3-540-00428-8.ZBL1133.03001  。​

• Väänänen, Jouko. Edward N. Zalta (編)。第二階論理と高階論理。スタンフォード哲学百科事典 (2021年秋版)。