FANDOM


\(\mathcal{L}_2\)

構造

\(\mathcal{M}=\{ 0,S,+,\cdot,<,=,\in\}\)

すべての自然数からなる集合と、そのいくつかの部分集合からなる集合は構成可能なため、一階論理で表現できる。

一階部分の領域が ω であれば ω モデル。さらに S が P(ω) であれば標準モデル。

理論

量化子のない公理と、推論規則に演繹しかない立場では、普遍性を証明するのに無限の時間がかかり、集合も外延的な手法で可能なものしか定義できない。

有限の時間で普遍性を証明する手段に帰納法があり、無限集合を定義するのには内包公理がある。数学の帰納法は本当は帰納ではない。

普遍性に関する帰納的な証明をすべて演繹に変えたとき、その証明の長さの上限を証明論的順序数と呼ぶ。

\(Z_2\) の公理

ロビンソン算術:1階部分を担当

数学的帰納法:厳密な定義には1階の述語なりクラス変数なりを量化しなければならない

内包公理:2階部分を担当

ロビンソン算術と数学的帰納法でペアノ算術になる。

\(RCA_0\) と \(WKL_0\)

内包公理をΔ_1-内包公理に制限したものがRCA_0。RCA_0のモデルでは、任意の集合は任意の自然数につきそれが要素に含まれるかどうかを判別するアルゴリズムを持つ、また、ゲーデル数化の技術により任意の自然数を判別するアルゴリズムが存在すればそれはΔ_1集合であることが分かる。

\(ACA_0\)

算術的な述語で述語を定義することができる。\(\Sigma^0_1-CA_0\) や \(\Pi^0_1-CA_0\) と同値。

\(\forall x_1(\forall x_2\forall x_3\cdots\forall x_n\forall x(\phi(x_1,x_2,x_3,\cdots,x_n,x)\leftrightarrow x_1\in A_1)\)

\(\forall x_2(\forall x_1\forall x_3\cdots\forall x_n\forall x(x_1\not\in A_1\land\lnot\phi(x_1,x_2,x_3,\cdots,x_n,x)\leftrightarrow x\in A_2))\)

\(\forall x_3(\forall x_1\forall x_2\cdots\forall x_n\forall x(x_1\not\in A_1\land x_2\not\in A_2\land\phi(x_1,x_2,x_3,\cdots,x_n,x)\leftrightarrow x_3\in A_3))\)

...

こんな感じ

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki