イプシロン微積分学

概要

世紀の変わり目によってDavid HilbertとHenri Poincaréは、彼らの世代の最も重要な数学者として認識されました。 ヒルベルトの数学的関心の範囲は広く、数学の基礎への関心が含まれていた：幾何学の彼の基礎は1899年に出版され、1900年に国際数学者会議に提起された質問のリストのうち、三つははっきりとfoundationalissuesに取り上げられた。,

ラッセルのパラドックスの出版に続いて、ヒルベルトは1904年に第三回国際数学会議に演説し、そこで初めて、統語的矛盾性の証明を介して数学の厳密な基礎を提供するための彼の計画をスケッチした。 しかし、彼は真剣に主題に戻らなかった1917年まで、彼はPaul Bernaysの助けを借りて数学の基礎に関する一連の講義を始めました。, ヒルベルトは彼らのPrincipiaMathematicaでラッセルとホワイトヘッドの仕事に感銘を受けたが、彼は論理主義的な試みは、特に還元性の公理の非論理的な性格のために、論理に数学を還元することができないことを確信した。 当時、彼は数学にとって受け入れられないと判断した中間の法則の直観主義的な拒絶。 したがって、論理的および集合論的パラドックスの発見によって提起された懸念を排除するためには、現代数学的方法を正当化するための新しいアプローチが必要であった。,

1920年の夏までに、ヒルベルトはこのようなアプローチを定式化した。 まず、現代の数学的方法は正式な演繹で表現されるべきであったシステム。 第二に、これらの形式システムは、モデルを示したり、それらの一貫性を他のシステムに還元することによってではなく、”有限”文字の直接的なメタマティカルな議論によって、構文的に一貫していることが証明されるべきであった。 のアプローチになったknownasヒルベルト”sプログラム。 イプシロン微積分学はこのプログラムの最初のコンポーネントを提供することでしたが、彼のイプシロン置換法は次の秒を提供することでした。,

イプシロン計算は、その最も基本的な形式では、任意の真の存在式に対して、存在量指定子の証人を選ぶ”イプシロン操作”を持つ最初の述語論理の拡張である。 拡張はある意味で保守的です新しい一次の結果を追加しないということです。 しかし、逆に、量指定子はイプシロンの観点から定義することができ、イプシロン操作を含む量指定子自由な論理の観点から理解することができる。 この後者の特徴は、一貫性を証明する目的で微積分を便利にすることである。, イプシロン微積分学の適切な拡張により、数と集合のより強く量化的な理論を量化子のない微積分に埋め込むことができる。 ヒルベルトは、そのような拡張の一貫性を実証することができる。

イプシロン微積分学

1921年のハンブルク講義（1922年）で、ヒルベルトは算術のための正式なシステムにおけるエクスクルード-ミドルの原理を扱うためにこのような操作を使用するという考えを初めて提示した。, これらのアイデアは、1921年から1923年にかけての一連の講義でイプシロン微積分学とイプシロン置換法に発展し、1923年にはインヒルベルトのものとなった。 イプシロン-微積分の最終提示Wilhelm Ackermannの論文（1924）で見つけることができます。

この節では、一次論理に対応する微積分学のバージョンについて説明し、一次および二次対数論の拡張については以下で説明する。

\(L\)を一次言語、つまり指定されたアリティを持つ定数、関数、および関係記号のリストとします。\(L\)は、\(L\)を一次言語とします。\(L\)は、\(L\)を一次言語と, これらのイプシロン項の集合と\(L\)の式の集合は、

置換と自由変数と束縛変数の概念は、通常の方法で定義され、特に変数\(x\)は項\(\varepsilon X A\)で束縛される。 意図された解釈は、\(\varepsilon X A\)は\(A\)を満たすいくつかの\(x\)を表すということです。, したがって、イプシロン項は以下のaxiom（ヒルベルトの”超限公理”）によって支配される：\さらに、イプシロン微積分学には、古典的提案接続詞を支配する公理の完全なセットと、等価記号を支配する公理が含まれる。微積分学の唯一の規則は次のとおりです。

• Modus ponens
• 置換：\(A(x)\)から、任意の項\(tに対して\(A(t)\)を結論づけます。,\)

イプシロン計算の初期の形式（例えば、ヒルベルト1923年に提示されたもの）は、\(\varepsilon X A\)が\(A(x)\)を改ざんする値を返すイプシロン演算子の双対形式を使用する。 これはアッカーマンの論文（1924年）で用いられたものであり、これが標準となっている。

先ほど説明した微積分は量指定子フリーであることに注意してください。 量指定子は次のように定義することができます：\通常の量指定子の公理と規則はこれらから導き出すことができるので、上記の定義はイプシロン微積分に一階論理を埋め込むのに役立ちます。, しかしながら、イプシロンカルキュラスのすべての式が、これに基づく通常の定量化された式のイメージであるわけではありません。 したがって、イプシロン微積分学は、単にイプシロン項が量指定子よりも複雑な方法で組み合わせることができるため、予測微積分学よりも表現力豊かである。

イプシロンの定理

ヒルベルトとベルナイズのGrundlagen derMathematik（1939）の第二巻は、その時までに証明されていたイプシロン微積分学の結果の説明を提供します。, これには、一次論理への応用による第一および第二のイプシロン定理の議論、開いた帰納法による算術のためのイプシロン置換法、およびイプシロン微積分による解析（すなわち二次算術）の発展が含まれる。

第一のイプシロン定理と第二のイプシロン定理は次のとおりである。

第一のイプシロン定理では、”量指定子のない予測論理”は上記の置換規則を含むことを意図しているので、量指定子のない公理はそれらの普遍的な閉包のように振る舞う。, 第一イプシロン定理は一階述語論理を含んでいるので、第一イプシロン定理は、量詞のない定理を量詞のない公理から排除するために使用される一次述語論理を通した迂回は避けることができるということを意味する。 第二のイプシロン定理は、述語微積分の言語の公理から述語微積分の言語の定理を導出するために使用されるイプシロン微積分を通して、任意のものも避けることができることを示している。,

より一般的に、最初のイプシロン定理は、量指定子とイプシロンは、他の量指定子のない公式からaquantifierのない公式の証明から常に排除することができることを確立します。 これはヒルベルトのプログラムにとって特に重要であり、エプシロンは数学における理想的な要素の役割を果たす。 量子フリーの公式が数学理論の”実際の”部分に対応する場合、最初のイプシロン定理は、理想要素は実際の文の証明から排除することができ、公理も実,

このアイデアは、ヒルベルトとベルナイズが最初のイプシロン定理から派生したある一般的整合定理において正確になされ、\(F\)を定数記号、関数、および前記記号に加えて量指定子およびデプシロンフリーである真の公理による述語計算から生じる形式系とし、newlanguageにおける原子式の真実が決定可能であると仮定する。 そして、\(F\)は強い意味で一貫していますすべての導出可能な量指定子とイプシロンのない公式が真であるということです。,ヒルベルトとベルナイズはこの定理を用いて初等幾何学の有限な一貫性を与える(1939,Sec1.4)。

算術および分析のための一貫性の証明を与えることの難しさは、この結果を公理が理想的な要素、すなわちイプシロン項を含む場合に拡張することにある。

さらに読む。 イプシロン微積分とイプシロン定理（Ackermann1924,Hilbert&Bernays1939）に関する元の情報源は、ドイツ語でのみ利用可能である。 Leisenring1969は、英語でのイプシロン微積分学の比較的近代の本の長さの紹介です。,第一および第二のイプシロン定理はZach2017で詳細に記述されている。 Moser&ザッハ2006は、平等なしでケースの詳細な分析を与えます。 元の証明は公理のために与えられるε-微積分学の表現。 前原1955は、イプシロン項を持つ最初のシーケント微積分学であった。 彼はカット除去を用いて第二イプシロン定理を証明する方法を示し、その後拡張性のスキーマを含むように定理を強化した（前原1957）。 Baaz et al. 2018firstepsilon定理の改良版を与える。, 文献における誤りの訂正（ライセンリングの本を含む）は、フラナガン1975、フェラーリ1987、安原1982に見られる。 Skolemfunctionsに基づくepsilon calculusのバリエーションであり、したがって一次論理と互換性があり、Davis&Fechter1991で議論されています。

Herbrandの定理

ここで説明したHerbrandの定理のバージョンは、hilbertとBernaysの拡張された第一イプシロン定理からすぐに従います。, しかしながら、ヒルベルトとベルナイスは、第二のイプシロン定理の証明に関連する方法を用いて、ハーブランドの元の定式化と同様に、より多くの情報を提供するという結果を導いた。 理論の二つの部分を理解するためにそれは特定の例を考えるのに役立ちます。 \(A\)を式

\とします。\(B\)は量指定子のないものです。 \(A\)の否定は\によるスコレミズムと等価である。, これを否定すると、元の形式は\(A^H\)の行列のインスタンスを参照するときに\

と”等価”であることがわかります。\(A^H\)の行列のexpandedlanguageの項を代入することによって得られる式です。 これでHilbert andBernaysの

Herbrandの定理の定式化は、gentzenの”midsequent theorem”を介してcuteliminationを使用することによっても得ることができます。,”しかし、第二イプシロン定理を用いた証明は、ヘルブラントの定理の最初の完全かつ正しい証明であるという疑いがあります。 さらに，これはほとんど認識されないが，カット除去に基づく証明は，カットランクとカット公式の複雑さの関数としてのみハーブランド分離の長さに限界を与えるのに対し，イプシロン計算に基づく証明から得られた長さは，超限公理の適用数の関数としての限界を与え，そこに生じるイプシロン項のランクと次数としての限界を与える。, 言い換えれば、ハーブランドの論理和の長さは、関係する置換の複雑さにのみ依存し、例えば命題構造や論理和の長さにはまったく依存しない。

このセクションの冒頭で述べたHerbrandの定理のバージョンは、本質的に（2）の特別な場合であり、式\(A\)は存在します。 この特別なケースに照らして、(1)は、式\(A\)が一次述語論理で導出可能であるという主張と同値である。\(A^H\)がそうである場合に限り、式\(A\)が一次述語論理で導出可能であるという主張と同値である。, 実際には、任意の式\(A,A\rightarrow A^H\)は述語論理で導き出すことができます。\(A,A\rightarrow A^H\)は述語論理で導き出すことができます。\(A,A\rightarrow A^H\逆の方向を証明することは、\(A^H\)の関数シンボルであり、特に平等の存在でははるかに困難です。 イプシロン法が中心的な役割を果たすのはここです。

Herbrandの定理とそれに関連する方法の顕著な応用は、Luckhardtの(1989)Rothの定理の分析で発見されました。 Herbrandのメソッドの有用な拡張の議論については、Sieg1991を参照してください。,これのモデル理論的版はAvigad2002aで議論されています。

イプシロン置換法と算術

上記のように、歴史的に、イプシロンカルキュラスの主な関心は、整合性証明を得るための手段としてでした。1917年から1918年にかけてのヒルベルトの講義では、提案変数と公式を真理値0と1の範囲に取り込み、論理接続詞を対応する演算として解釈することによって、命題論理の一貫性を容易に証明できることが指摘されている。, 同様に、談話の宇宙が単一の要素を持つ解釈に特化することによって、予言論理（または純粋なイプシロン微積分）の一貫性を証明することができる。これらの考慮事項は、一貫性を証明するためのより一般的なプログラムを示唆しています。

• より大きな数学の部分を表すような方法でイプシロン微積分を拡張する。
• 有限メソッドを使用して、extendedsystem内の各証明が一貫した解釈を持つことを示します。,

上記のシステムが一貫性があることを示したいとします。つまり、式\(0=1\)の証明がないことを示したいとします。 すべての置換を公理に押し込み、自由変量を定数0に置き換えることによって、公理の閉インスタンスの有限集合から\(0=1\)の提案の証明が存在しないことを示すだけで十分である。 そのためには、公理の閉じたインスタンスの任意の有限集合が与えられたとき、すべての公理が解釈の下で真であるような方法で数値を割り当てることができることを示すことで十分である。, 算術演算\(+\)と\(\times\)は通常の方法で解釈できるので、唯一の難しさはイプシロン項に割り当てる適切な値を埋め込むことです。\(\times\)は、\(\times\)と\(\times\)の間にあります。

ヒルベルトのイプシロン置換法は、おおよそ次のように記述することができる：

連続した”修復”のこのプロセスが終了することを、afinitary acceptableな方法で示されると、有限整合性証明が得られる。 そうであれば、すべての臨界式epsilon-termsのない真の式です。,

この基本的な考え方（”Hilbertsche Ansatz”）は、ヒルベルトによって1922年の講演（1923年）で初めて設定され、1922-23年のlecturesinで詳述されました。 しかし、そこで与えられた例は、超限公理のすべてのインスタンスがアシングルイプシロン項\(\varepsilon x A(x)\)に対応する証明のみを扱う。 課題は、複数のイプシロン項へのアプローチ、ネストされたイプシロン項へのアプローチ、そして最終的には二次イプシロンへのアプローチを拡張することであった（算術だけでなく分析の証明を得るために）。,

これは拡張に関わる困難の単なるスケッチですhilbertのアイデアを一般的なケースにまで拡張することができます。 Ackermann(1924)は、与えられた段階で新しい解釈が以前の段階で既に見つかった解釈を修正する必要があるときはいつでも”バックトラック”する手続きを用いてこのような一般化を提供した。

アッカーマンの手順は、二次イプシロンの交差結合を排除するために二次項が制限されている二次項の系に適用された。, これは、おおよそ、利用可能な集合形成原理としての算術理解への制限になります（この項の最後の議論を参照）。 二次イプシロン項のさらなる困難さが表面化し、それが立ったときの証拠が誤っていたことがすぐに明らかになった。 しかし、ヒルベルトの学校の誰もゲーデルが彼の完全な結果を発表した1930年まで、この難しさの理由に気づいた人はいませんでした。, それまでは、証明（少なくともAckermannによって導入されたいくつかの修正を伴い、そのうちのいくつかはvon Neumannの（1927年）版のepsilonsubstitution methodからのアイデアに関与している）は、少なくとも一次部分について通過すると考えられていた。 Hilbert and Bernays(1939)は、使用される方法のみを示唆しているopeninductionによる一次算術の整合性証明を提供します。 1936年、ゲルハルト-ゲンツェンは、イプシロン記号のない論理に基づく定式化において、一次算術の一貫性の証明を与えることに成功した。, この証明は、\(\varepsilon_0\)までの半定理帰納法を使用します。 Ackermann(1940)はゲンツェンのアイデアを適応させて、エプシロン置換法を用いて一階算術の正しい一貫性証明を与えることができた。

解析、または二次算術は、任意の二次形式に対する理解スキーマを持つ一階算術の拡張である。 この理論は、暗黙のうちに定義される集合を含む、集合の宇宙全体に及ぶ量指定子を使用して自然数の集合を定義することを可能にするという点で非限定的である。, この理論の述語的な断片を得ることができるのは、理解において許容される式のタイプを制限することによってである。 例えば、上記のアッカーマンに関連して議論された制限は、式が二次量化を伴わない算術的な理解に対応する。 では、さまざまな形で取得の強化断片ofanalysisとしpredicatively正当化されます。, 例えば、順序数と集合変数を関連付けることによって分岐分析を得る：おおよそ、与えられたランクの集合の定義において、量指定子はより低いランクの集合、すなわち論理的定義が論理的に先行しているものにのみ範囲を及ぼす。

さらに読む。 ヒルベルトとアッカーマンの初期の証明については、Zach2003;2004で議論されている。 フォン-ノイマンの証明はBellotti2016のトピック。 アッカーマンの1940年の証明はヒルベルト&Bernays1970とWang1963によって議論されている。 モダンなプレゼンテーションはMoser2006によるgiven。, イプシロン置換の初期のアプリケーションは、無反例解釈（Kreisel1951）。

より最近の開発

このセクションでは、強力なシステムの一貫性の結果を得るためのepsilon-substitutionmethodの開発について説明します。 残念ながら、ここで証明の詳細を議論することはできませんが、イプシロン置換法はヒルベルトのプログラムで死ぬことはなく、かなりの量の現在の研究がイプシロン形式で行われていることを示したいと思います。,

ゲンツェンの算術のための一貫性の証明は、順序分析として知られる研究分野を開始し、順序表記を使用して数学理論の強さを測定するプログラムは、今日でも追求されている。 これは特に拡張されたヒルベルトのプログラムに関連しており、ゴールは古典数学を構成的、または構成的なシステムに対して正当化することである。, ゲンツェンのカット消去法（およびPaulLorentzen、Petr Novikov、およびKurt Schütteによって開発された無限論理の拡張）は、大部分がこれらの追求においてイプシロン置換法に取って代わっている。 しかし、イプシロンカルキュラス法は別のアプローチを提供し、ヒルベルト-アッカーマン法をストロンガー理論に拡張する方法については依然として活発な研究がある。 一般的なパターンは同じままです：

1. 調査中の理論を適切なepsiloncalculusに埋め込みます。
2. イプシロンタームへの割り当てを更新するプロセスを記述します。,
3. ショーは、手順が正規化されている、すなわち、任意のセットの与えられたタームは、assignmentthatが公理を満たす結果の更新のシーケンスがあります。

最後のステップは元の理論の一貫性を保証するので、基礎的観点からは正規化を証明するために使用される方法に興味があります。 たとえば、手順のステップに順序表記を割り当てることによって、各ステップとともに表記の値が減少するように、ordinalanalysisを取得します。,

1960年代、Tait(1960,1965,2010)はダッカーマンの方法を拡張して、超限帰納法の原理を用いた算術の拡張の順序解析を得た。 このアプローチのより多くのストリームラインと最新のバージョンは、Mints2001とAvigad2002bで見つけることができます。, より最近では、Mints、Tupailo、およびBuchholzhaveは、算術内包の理論および\(\Delta^{1}_1\)-理解規則（Mints,Tupailo&Buchholz1996;Mints&Tupailo1999;Mints2016も参照）を含む分析の断片をより強く、まだ予測的に正当であると考えていました。 Arai2002では、イプシロン置換法をプリミティブな井戸順序付けに沿って算術理解を繰り返すことができるように拡張している。, 特に、彼の作品は、超限ヒエアーキーと超限誘導を含む分析の述語フラグメントのためのordinalanalysesをもたらします。

impredicative理論の分析におけるepsilon substitutionmethodの使用において、いくつかの最初のステップが取られている（Arai2003、2006およびMints2015を参照）。

上記の手順3のバリエーションには、normalizationprocedureが更新の選択に敏感ではないこと、つまり、更新のシーケンスが終了することを示すことが含まれます。 これはstrongnormalizationと呼ばれます。, Mints1996は、多くの手続きこのより強い特性を持っていると考えられています。

証明理論の伝統的な基礎的な枝に加えて、今日、論理的な演繹に焦点を当てた主題の枝である構造的証明にはかなりの関心があります計算とその この研究は、自動計算、関数型プログラミング、およびコンピュータ支援検証に関係するコンピュータサイエンスに関連する問題と密接に関連しています。ここでも、Gentzenスタイルの方法が支配的になる傾向があります（再び証明理論のエントリを参照してください）。, しかし、イプシロン微積分はまた、貴重な洞察を提供することができます。 例えばAguilera&Baaz2019、または上記のherbrandの定理の議論。

証明理論におけるイプシロン微積分学の調査とは別に、二つの応用を挙げるべきである。 一つは、ブルバキのTheorie des ensembles（1958）におけるイプシロンノテーションの使用である。第二に、おそらくより大きな現在の関心のあるものは、定理証明システムHOLとIsabelleにおけるtheepsilon-operatorの使用であり、epsilon-termsの表現力が重要な実用的な利点をもたらす。,

言語学、哲学、および非古典論理学におけるイプシロン演算子

イプシロン演算子を不定選択演算子（”an\(x\)such that\(A(x)\)”）として読むことは、形式意味論における不定および明確な名詞句の分析において有用なツールであることを示唆している。 イプシロン記法は実際にそのように使用されており、このアプリケーションは、アナフォリック参照を扱う上で特に有用であることが証明され

おなじみの例を考えてみましょう

1. ロバを所有しているすべての農家はそれを打ち負かします。,したがって、分析は、何らかの形で平行にすべきです文3の分析は4で与えられます：

   しかし、最も近い可能な形式化、

   1. \(\forall x((\mathrm{Farmer}(x)\wedge\exists y(x)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(X)\wedge\exists y(x)\wedge\exists y(X)\wedge\exists y(x)\wedge\exists y(x)\wedge\exists y(x)\wedge\exists y(x)\wedge\\mathrm{donkey}(y)\wedge\mathrm{owns}(x,y))\rightarrow\mathrm{beats}(X,y))\)

   von heusinger(1994)によって指摘されているように、これはnealeが明確な記述\((\iota\)-式)とwhe式の間であいまいである代名詞にコミットされていることを示唆している。, Heusingerは、選択関数によってインデックス付けされたイプシロン演算子を使用することを提案している（コンテキストに依存する）。 このアプローチによれば、(1)の分析は

   選択関数によってイプシロン演算子を使用して代名詞を扱うこのアプローチは、von Heusingerが幅広い状況に対処することを可能にする（Egli and von Heusinger,1995;von Heusinger,2000を参照）。

   形式意味論におけるイプシロン演算子の適用、および一般的なchoicefunctionsは、最近では大きな関心を集めている年。, Von Heusinger and Egli(2000a)は、とりわけ次のように、質問の表現(Reinhart,1992)、特定の定義(Reinhart1992;1997;Winter1997)、E型代名詞(Hintikka and Kulas1985;Slater1986;Chierchia1992,Egli and vonHeusinger1995)、および明確な名詞句(von Heusinger1997,2004)をリストしている。

   イプシロン演算子の問題と応用についての議論については、言語の言語学と哲学では、B.H.を参照してください。, イプシロン計算に関するSlaterの記事（以下の他のインターネットリソースセクションで引用）、およびコレクションvon Heusinger and Egli2000およびvon Heusinger and Kempson2004。

   Meyer Viol(1995a,1995b)には、イプシロン微積分学、特に直観主義的イプシロン計算のさらなる証明およびモデル理論研究が含まれている。 ここで、イプシロン定理はもはや成り立たない、すなわち、イプシロン項の導入は直観論理の非保守的拡張を生じる。 直観論的論理におけるイプシロン作用素の他の調査は、Shirai(1971)、Bell(1993a,1993b)およびDeVidi(1995)に見られる。, 多値論理におけるイプシロン作用素については、mostowski(1963),for modal epsilon calculus,Fitting(1975)を参照してください。

   さらに読む。 以下は、いくつかの出版物のリストですepsiloncalculusとその応用に関連する言語および言語学の分野で。 読者は、特にコレクションvon Heusinger&Egli(eds.)2000and von Heusinger&Kempson(eds.,) 2004 for further discussion and references: Bell1993a, 1993b; Chierchia 1992; DeVidi 1995;Egli & von Heusinger1995; Fine 1985; Fitting 1975; von Heusinger 1994, 1997, 2000, 2004;von Heusinger & Egli (eds.) 2000; von Heusinger & Kempson(eds.) 2004; Hintikka & Kulas 1985; Kempson, Meyer Viol, &Gabbay 2001; Meyer Viol 1995a, 1995b, Neale 1990; Mostowski 1963;Reinhart 1992, 1997; Slater 1986, 1988, 1994, 2000; and Winter1997.

---