イプシロン誘導

集合論において、イプシロン帰納法は、イプシロン帰納法や集合帰納法とも呼ばれ、すべての集合が特定の特性を満たすことを証明するために使用できる原理です。公理的原理として考えられ、集合帰納法の公理スキームと呼ばれます。 ${\displaystyle \in}$

この原理は超限帰納法と再帰法を暗示しています。また、整基礎関係における帰納法の一般的な文脈で研究することもできます。

スキーマは、集合の任意のプロパティに対するもので、すべての集合 に対して の真偽がのすべての要素に対する の真偽から導かれる場合、このプロパティはすべてのセットに対して成立することを述べています。記号で表すと、 ${\displaystyle \psi}$${\displaystyle x}$${\displaystyle \psi (x)}$${\displaystyle \psi}$ ${\displaystyle x}$${\displaystyle \psi}$

${\displaystyle \forall x.{\Big (}{\big (}\forall (y\in x).\psi (y){\big )}\,\to \,\psi (x){\Big )}\,\to \,\forall z.\psi (z)}$

が空集合を表す「下の場合」では、部分式はすべての命題およびに対して空虚に真であるため、その含意は を証明するだけで証明されることに注意してください。 ${\displaystyle x}$ ${\displaystyle \{\}}$${\displaystyle \forall (y\in x).\psi (y)}$${\displaystyle \psi (\{\})}$

言い換えれば、ある特性を持つ任意の集合を新しい集合に集めるときにその特性が持続し、空集合に対して真である場合、その特性は単純にすべての集合に対して真です。言い換えれば、集合形成に関する特性の持続性は、議論の領域内の各集合に到達するのに十分です。

スキーマを表現するために、クラスの言語を使用することができます。普遍クラス を で表します。を とし、 の略語としてを使用します。この原理は、任意の に対して、 ${\displaystyle \{x\mid x=x\}}$${\displaystyle {\mathbb {U} }}$${\displaystyle \Psi}$${\displaystyle \{x\mid \psi (x)\}}$${\displaystyle \Psi ={\mathbb {U} }}$${\displaystyle \forall zz\in \Psi }$${\displaystyle \Psi}$

${\displaystyle \forall (x\subseteq \Psi ).x\in \Psi \,\,\leftrightarrow \,\,\Psi ={\mathbb {U} }}$

ここで、量指定子はすべてのセットに渡って範囲を定めます。言葉で言えば、すべてのサブセットを含むクラスは、単にすべてのセットのクラスであるということです。

境界付き分離を仮定すると、は適切なクラスです。したがって、このプロパティは適切なクラス によってのみ示され、特にどのセットによっても示されません。実際、任意のセットはそれ自身のサブセットであり、さらにいくつかの仮定の下では、自己メンバーシップはすでに除外されることに注意してください。 ${\displaystyle {\mathbb {U} }}$${\displaystyle \forall (x\subseteq \Psi ).x\in \Psi }$${\displaystyle {\mathbb {U} }}$

他の特性と比較すると、クラスが推移的で あるためには、${\displaystyle \Sigma }$${\displaystyle \in}$

${\displaystyle \forall (x\in \Sigma ).x\subseteq \Sigma }$

推移的な集合、特に集合論的順序数は数多く存在します。

輸出はを証明します。 が何らかの述語 の場合、次のようになります。 ${\displaystyle (A\to (B\to C))\leftrightarrow (B\to (A\to C))}$${\displaystyle \psi (x)}$${\displaystyle (x\in \Sigma )\to P(x)}$${\displaystyle P}$

${\displaystyle \forall (x\in \Sigma ).{\Big (}{\big (}\forall (y\in (x\cap \Sigma )).P(y){\big )}\,\to \,P(x){\Big )}\,\to \,\forall (z\in \Sigma ).P(z)}$

ここで はとして定義されます。 が普遍的なクラスである場合、これもまたスキーマのインスタンスに過ぎません。 しかし、 が任意の-推移的なクラスである場合、 および に対する集合帰納法のバージョンがの内部で成立します。 ${\displaystyle y\in x\cap \Sigma }$${\displaystyle y\in x\land y\in \Sigma }$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle \in}$${\displaystyle \forall (x\in \Sigma ).(x\cap \Sigma =x)}$${\displaystyle P}$${\displaystyle \Sigma }$

順序数は推移集合の推移集合として定義できます。最初の無限順序数である自然数の集合における帰納法の状況については、以下で詳しく説明します。集合帰納法では を含む推移集合における帰納法が可能であるため、これは超限帰納法と呼ばれるものとなり、順序数の適切なクラス全体を使用して超限再帰による定義が行われます。順序数では、すべての集合が順序数の階数を持ち、順序数の階数はそれ自身であることが帰納法によって証明されます。 ${\displaystyle \omega}$${\displaystyle \omega}$

フォン ノイマン順序数の理論は、このような集合を記述し、そこでは、古典的には証明可能に三分法かつ全である順序関係 をモデル化します。興味深いのは、順序数を順序数にマップする後続操作です。古典的なケースでは、後続順序数の帰納法のステップは、プロパティが連続する順序数間で単に保持される必要があるように簡略化できます (これは、通常、超限帰納法として理解される定式化です)。集合は-well-founded です。 ${\displaystyle y\in x}$${\displaystyle y<x}$${\displaystyle x\mapsto x\cup \{x\}}$${\displaystyle \in}$

集合 上の二項関係 の場合、整基礎性は、調整された帰納的性質を要求することによって定義できます。では、条件 は に抽象化されます。つまり、上記のステートメントで使用されている共通部分の代わりに、常に が想定されます。 整基礎関係 の場合、無限降順の -シーケンスは存在せず、 も存在することがわかります。さらに、 を使用した再帰による関数定義は、そのドメイン上で定義でき、以下同様に続きます。 ${\displaystyle R_{D}}$${\displaystyle D}$${\displaystyle y\in x}$${\displaystyle R_{D}(y,x)}$${\displaystyle R_{D}(y,x)\land y\in D}$${\displaystyle y\in (x\cap D)}$${\displaystyle R_{D}}$${\displaystyle R_{D}}$${\displaystyle \forall y.\neg R_{D}(y,y)}$${\displaystyle R_{D}}$

古典的には、集合上の関係の整基礎性は、あらゆる部分集合に対して最小要素が存在するという強い性質によっても特徴付けられる。従属選択では、無限下降チェーンが存在しないという弱い性質によっても特徴付けられる。

この節では、否定形の述語に対する集合帰納法とその帰結について述べる。構成的には、結果として得られる文は、一般述語に対する集合帰納法よりも一般的に弱い。同値性を確立するには、次のような有効な原理が必要である。 ${\displaystyle \psi (x):=\neg S(x)}$

${\displaystyle \forall x.{\big (}A(x)\to \neg B(x){\big )}\,\leftrightarrow \,\neg \exists x.{\big (}A(x)\land B(x){\big )}}$、

は一般的に使用され、両側とも、2 つの述語とが、どの値に対しても同時に検証できないことを示しています。二重否定の除去が許可される状況については、次のセクションで説明します。 ${\displaystyle A}$${\displaystyle B}$

クラスを で表すと、これは上記の の特別な場合となり、任意の に対して、偽の命題 に等しい。 は で表されます。すべての集合がクラスのメンバーではないという命題 について と書くと、帰納法の図式は次のように簡約されます。 ${\displaystyle \{x\mid S(x)\}}$${\displaystyle \Sigma }$${\displaystyle x}$${\displaystyle P(x)}$${\displaystyle x\neq x}$${\displaystyle x\cap \Sigma =\{\}}$${\displaystyle \neg \exists (y\in \Sigma ).y\in x}$${\displaystyle \Sigma =\{\}}$${\displaystyle \Sigma }$

${\displaystyle \neg \exists (x\in \Sigma ).x\cap \Sigma =\{\}\,\,\leftrightarrow \,\,\Sigma =\{\}}$

言葉で言えば、 に対する極小集合が存在しないプロパティ（クラス）は、単に偽プロパティ（空集合）です。（関係に対する極小とは、を持つ別の関係が存在しない関係です。ここでは、 に制限されたメンバーシップ関係が検討されます。つまり、 に関する極小要素はを持たないものです。） ${\displaystyle \in}$${\displaystyle x}$${\displaystyle R}$${\displaystyle y}$${\displaystyle R(y,x)}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle y\in x\cap \Sigma }$

上記の含意における前提はと表現できます。これは空集合に対して空にが成り立ちます。 上の関数として任意の降順メンバーシップ チェーンが存在する場合、置換公理により、これも満たす集合の存在が証明されます。したがって、帰納原理を仮定すると、そのようなチェーンの存在は矛盾します。 ${\displaystyle \forall (x\in \Sigma ).\neg \neg \exists (y\in \Sigma ).y\in x}$${\displaystyle \omega}$${\displaystyle \Sigma }$

この段落では、帰納原理の代わりに従属選択公理を仮定します。上記の前提のあらゆる結果は、二重否定を除去することによって得られる -ステートメントによっても暗示され、これは構成的に、より強い条件です。この -特性を持つセットを考えてみましょう。セットが であると仮定すると、従属選択は、シーケンスとして無限の下降メンバーシップチェーン、つまり自然数上の関数の存在を意味します。したがって、 -特性を持つセットに対してそのようなチェーンが存在しないことを証明する（または仮定する）ことは、仮定が間違っていたことを意味します。 つまり、 でもあります。${\displaystyle \forall \exists }$ ${\displaystyle \Sigma }$${\displaystyle \forall \exists }$${\displaystyle \omega \to \Sigma }$${\displaystyle \forall \exists }$${\displaystyle \Sigma =\{\}}$

したがって、集合帰納法は、無限下降連鎖の非存在の公理に関係します。しかし、後者の場合に必要な追加の仮定を考慮すると、単なる非存在の公理は、比較すると比較的弱いものになります。

矛盾について、特定のプロパティとして、自身のシングルトン セット に等しいという特性を持つ、存在するセットが存在すると仮定します。形式的には、 であり、そこから が導かれ、また のすべてのメンバーがそのすべてのプロパティ (例 ) を共有します。原理の前の形式から、 が導かれ、矛盾が生じます。 ${\displaystyle s}$${\displaystyle s=\{s\}}$${\displaystyle \forall y.(y\in s\leftrightarrow y=s)}$${\displaystyle s\in s}$${\displaystyle s}$${\displaystyle \forall (y\in s).s\in y}$${\displaystyle s=\{\}}$

上で説明した他の補助用語を使用して、集合帰納法を、そのような と等しくない集合のクラスについて研究します。したがって、否定述語の観点で、は述語 であり、 を示す集合はの定義特性を持つことを意味します。集合構築記法を使用すると、 について考えます。 の特別な特性を想定すると、任意の空の共通部分のステートメントは に簡略化されます。 に関する定式化の原理は に簡略化されますが、これもまた矛盾です。非常に元の定式化に戻ると、およびはすべての集合の定義域にすぎないという結論が下されます。集合帰納法を含む理論では、説明した再帰特性を持つ は、そもそも集合ではありません。 ${\displaystyle \Psi}$${\displaystyle s}$${\displaystyle S(x)}$${\displaystyle x=s}$${\displaystyle S}$${\displaystyle s}$${\displaystyle \Sigma =\{s\}}$${\displaystyle s}$${\displaystyle x\cap s=\{\}}$${\displaystyle s\notin x}$${\displaystyle \Sigma }$${\displaystyle s\notin s}$${\displaystyle \forall z.z\neq s}$${\displaystyle \Psi }$${\displaystyle s}$

同様の分析は、より複雑なシナリオにも適用できます。たとえば、と が両方とも集合である場合、を組み合わせることで が存在することになりますが、これも-特性を持ちます。 ${\displaystyle u=\{0,v\}}$${\displaystyle v=\{1,u\}}$${\displaystyle \{v,u\}}$${\displaystyle \forall \exists }$

否定を伴う形式の逆否定は構成的にさらに弱いが、 の正則性の主張からは二重否定の除去が1つだけ離れている。 ${\displaystyle \Sigma }$

${\displaystyle \Sigma \neq \{\}\,\to \,\neg \neg \exists (x\in \Sigma ).x\cap \Sigma =\{\}}$

前提と結論に二重否定がある場合、前提を に置き換えると同等になります。 ${\displaystyle \exists z.(z\in \Sigma )}$

全称量化された述語に対する排中律は、古典的には次のように表現できる。すべての項に対してそれが成り立つか、述語が成り立たない項が存在するかのいずれかである。

${\displaystyle \forall z.P(z)\,\lor \,\exists x.\neg P(x)}$

これにより、選言三段論法を使用して、反例の可能性を排除することで、すべての項の特性を古典的に証明できます。この純粋に論理的な原理は、項間の他の関係、たとえば要素性 (または連続性、以下を参照) とは無関係です。これは古典的に同値であり、二重否定の除去も使用すると、帰納原理は次のステートメントに変換できます。 ${\displaystyle (B\lor \neg A)\to (A\to B)}$

${\displaystyle \forall z.P(z)\,\lor \,\exists x.{\Big (}\neg P(x)\,\land \,\forall (y\in x).P(y){\Big )}}$

これは、任意の述語 について、それがすべての集合に対して成り立つか、 に対して が成り立たない一方でが のすべての要素に対して同時に真である集合が存在することを表します。これを元の定式化に関連付けると、任意の集合 について、 がを意味することを証明 できれば(これには最下位のケース の証明が含まれます) 、失敗するケースは除外され、選言三段論法によって選言が成り立ちます。 ${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$${\displaystyle P}$${\displaystyle x}$${\displaystyle x}$${\displaystyle \forall (y\in x).P(y)}$${\displaystyle P(x)}$${\displaystyle P(\{\})}$${\displaystyle \forall z.P(z)}$

反例の存在を排除することによって 証明するというタスクでは、帰納原理は排中選言と同様の役割を果たしますが、前者は構成的フレームワークでも一般的に採用されています。${\displaystyle P}$

前の節の導出は、集合帰納法が古典的には以下を意味することを示している。

${\displaystyle \Sigma \neq \{\}\,\to \,\exists (x\in \Sigma ).x\cap \Sigma =\{\}}$

言葉で言えば、ある集合によって示される特性は、上で定義した「最小集合」によっても示されます。クラスに関して言えば、これは、空でないすべてのクラスには、それと素な メンバーが存在することを意味します。${\displaystyle x}$${\displaystyle \Sigma }$${\displaystyle x}$

共通の枠組みである一階集合論では、集合帰納法原理は公理スキームであり、任意の述語（つまりクラス）に対して公理を付与します。対照的に、正則性の公理は単一の公理であり、談話領域の要素、つまり集合に対してのみ全称量化子で定式化されます。 が集合であり、帰納法スキームが想定される場合、上記は に対する正則性の公理のインスタンスです。したがって、古典論理に対する集合帰納法を想定すると（つまり排中律 を想定すると）、すべての正則性のインスタンスが成立します。 ${\displaystyle \Sigma }$${\displaystyle \Sigma }$

分離公理のコンテキストでは、正則性は排中律も意味します (分離公理で許可されている述語の場合)。一方、集合帰納法スキーマは排中律を意味しませんが、上で説明したように、強い帰納原理を意味するのに十分強力です。次に、スキーマは、たとえば、型理論的モデルを持つ構成的集合論CZF で採用されています。そのため、このような集合論フレームワーク内では、集合帰納法は、正則性よりも厳密に弱い強い原理です。正則性公理と完全な分離を採用すると、CZF は標準ZFと等しくなります。

正則性の公理は、順序数の集合論的処理に用いられることから、 1925 年にフォン ノイマンによって定式化されました。その動機は、正則性や置換のない理論であるツェルメロ集合論 における無限下降連鎖についてのスコーレムの 1922 年の議論に遡ります。 ${\displaystyle {\mathsf {Z}}}$

この理論は、集合帰納法のすべてのインスタンスを証明するものではありません。 実証されているように、正則性は、否定文に対する集合帰納法の逆否定と古典的に同等です。 集合からクラスへの橋渡しは、以下で実証されています。 ${\displaystyle {\mathsf {Z}}}$

規則性を前提とすると、対偶の反転などの古典的な原理を使用できます。さらに、否定述語 に関して述べられた帰納法スキーマは、述語変数 に関して述べられたものと同じくらい強力です。これは、後者が単に に等しいためです。集合帰納法の対偶との同値性については説明してきたので、課題は規則性を一般クラス に関するステートメントに翻訳し直す​​ことです。分離公理により集合とクラス間の交差が許容されるため、最終的には機能します。規則性は集合内の交差にのみ関係し、推移集合を使用してこれを平坦化できます。 ${\displaystyle \neg S}$${\displaystyle P}$${\displaystyle \neg (\neg P)}$${\displaystyle \Sigma }$

証明は、規則性公理インスタンスの操作によって行われる。

${\displaystyle s\neq \{\}\,\to \,\exists (x\in s).x\cap s=\{\}}$

クラス の特定のサブセット について。クラスと任意の推移的なセットが与えられた場合、と も持つ を定義できることに注目してください。これにより、規則性インスタンスの結論で、 セット を常にクラス に置き換えることができます。${\displaystyle s\subseteq \Sigma }$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle t}$${\displaystyle s=t\cap \Sigma }$${\displaystyle x\in s\to (x\in \Sigma \land x\subseteq t)}$${\displaystyle (x\subseteq t)\to (x\cap s=x\cap \Sigma )}$${\displaystyle s}$${\displaystyle \Sigma }$

残りの目的は、前提部分でも を置き換えたステートメントを取得すること、つまり、より一般的な を仮定した場合に原理が成り立つことを証明することです。したがって、 があり、そのサブセットとして を持つ推移的なセットが存在すると仮定します。交差は説明されているように構築でき、 も存在します。 が と素であるかどうかの排中、つまり であるかどうかについて考えます。が空の場合、および自体も常に原理を満たします。それ以外の場合は、および の規則性により、説明したようにを に置き換えることでステートメントを操作できます。この場合、および だけではなく というより明確な情報が含まれているため、前のセクションのステートメントよりもわずかに強いステートメントが得られます。 ${\displaystyle \Sigma \neq \{\}}$${\displaystyle z\in \Sigma }$${\displaystyle t}$${\displaystyle z}$${\displaystyle s_{z}}$${\displaystyle (z\cap \Sigma )\subseteq s_{z}}$${\displaystyle t}$${\displaystyle \Sigma }$${\displaystyle s_{z}=\{\}}$${\displaystyle s_{z}}$${\displaystyle z\cap \Sigma =\{\}}$${\displaystyle x=z}$${\displaystyle \exists (x\in s_{z})}$${\displaystyle s_{z}}$${\displaystyle \Sigma }$${\displaystyle x\in s_{z}}$${\displaystyle x\in \Sigma }$

上記の証明は、任意の集合を含む推移的な集合が存在することを前提としています。これは推移的包含公理として仮定できます。

任意の集合に対する、帰属関係に関するより強い推移閉包の存在は、いくつかのより強い標準公理からも導くことができます。これには、集合としてのに対する無限大公理、 上の再帰関数、上の置換公理、そして最後にの和集合公理が必要です。つまり、べき集合 の公理を除いて、多くの標準公理が必要です。強い分離のないコンテキストでは、再帰関数の定義を可能にするために、適切な関数空間原理を採用する必要があるかもしれません。 マイナス無限大も、正則性が集合帰納法に昇格された 場合にのみ、推移閉包の存在を証明します。${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle {\mathsf {ZF}}}$

標準的な自然数の推移的フォン・ノイマン・モデルは 、最初の無限順序数です。そこでは、集合論の二項帰属関係「」が、自然数「」の厳密な順序を正確にモデル化します。そして、集合帰納法から導かれる原理は、完全帰納法です。 ${\displaystyle \omega }$${\displaystyle \in }$${\displaystyle <}$

このセクションでは、量指定子は1 階ペアノ算術 (またはヘイティング算術)の領域にわたると理解されます。シグネチャには、定数記号 " "、後継関数記号 " "、加算および乗算関数記号 " " resp " " が含まれます。これにより、自然数は半環 を形成します。これは常に標準的な非厳密な前順序 " " を伴い、非反射的はそれに基づいて定義できます。同様に、2 項順序関係も として定義できます。 ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {HA}}}$${\displaystyle 0}$${\displaystyle S}$${\displaystyle +}$${\displaystyle *}$${\displaystyle \leq }$ ${\displaystyle <}$${\displaystyle k<n}$${\displaystyle \exists m.k+Sm=n}$

任意の述語に対して、完全な帰納原理は次のようになる。 ${\displaystyle Q}$

${\displaystyle \forall n.{\Big (}{\big (}\forall (k<n).Q(k){\big )}\,\to \,Q(n){\Big )}\,\to \,\forall m.Q(m)}$

を利用すると、この原理は数学的帰納法の標準形式によってすでに暗示されている。後者は、決定可能な順序関係「」ではなく、基本記号、 ${\displaystyle {\big (}\forall (k<Sn).Q(k){\big )}\,\,\leftrightarrow \,\,{\big (}\forall (k<n).Q(k){\big )}\land Q(n)}$${\displaystyle <}$

${\displaystyle {\Big (}\phi (0)\,\land \,\forall n.{\big (}\phi (n)\,\to \,\phi (Sn){\big )}{\Big )}\,\to \,\forall m.\phi (m)}$

最後に、後続シンボルを使用するだけで集合帰納法を反映するステートメントが証明される可能性があります。新しい述語を と定義します。これは意図的にゼロに対して成立するため、集合帰納法の一番下の場合と同様に、その含意はと同等です。帰納法を使用して、すべてのがゼロであるか、を持つ計算可能な一意の先行 を持つことを証明します。したがって です。が の後続であるとき、 はを表します。場合分けにより、次が得られます。 ${\displaystyle Q_{\mathrm {-1} }(n)}$${\displaystyle (n=0)\lor \exists p.{\big (}Sp=n\land Q(p){\big )}}$${\displaystyle Q_{\mathrm {-1} }(0)\,\to \,Q(0)}$${\displaystyle Q(0)}$${\displaystyle {\mathsf {PA}}}$${\displaystyle n}$${\displaystyle q}$${\displaystyle Sq=n}$${\displaystyle Q_{\mathrm {-1} }(Sq)\leftrightarrow Q(q)}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle Q_{\mathrm {-1} }(n)}$${\displaystyle Q(n-1)}$

${\displaystyle \forall n.{\big (}Q_{\mathrm {-1} }(n)\,\to \,Q(n){\big )}\,\to \,\forall m.Q(m)}$

上で述べた古典的な原理を用いると、上記のことは次のように表現できる。

${\displaystyle \forall m.Q(m)\,\lor \,\exists n.{\big (}\neg Q(n)\,\land \,\forall (k<n).Q(k){\big )}}$

これは、任意の述語 に対して、すべての数に対して が成り立つか、または、すべての先行数に対して が成り立つにもかかわらず が成り立たない自然数が存在することを表します。 ${\displaystyle Q}$${\displaystyle Q}$${\displaystyle n}$${\displaystyle Q}$${\displaystyle Q}$

の代わりに、 を使って関連するステートメントを得ることもできます。これは、自然数の特性に対する反例を排除するタスクを制約します。つまり、一番下のケースが検証され、任意の数 に対して、特性が常に に渡されることを証明できる場合、これはすでに失敗ケースを排除しています。さらに、失敗ケースが存在する場合、最小数原理を使用して、そのような失敗ケースの最小の存在を証明することさえできます。 ${\displaystyle \forall (k<n).Q(k)}$${\displaystyle Q_{\mathrm {-1} }(n)}$${\displaystyle Q(0)}$${\displaystyle n}$${\displaystyle Q}$${\displaystyle Sn}$

集合論の場合と同様に、否定述語の帰納法を検討し、逆否定をとることができます。いくつかの古典的な論理的同値性を使用した後、条件付き存在の主張が得られます。

が性質 を成立させる自然数の集合を表すものとする。ノイマンモデルでは、自然数はより小さい数の集合と外延的に等しい。完全帰納法から得られる最小数原理 は、ここでは集合の用語で表現され、次のように表される。 ${\displaystyle \Theta }$${\displaystyle \{n\in \omega \mid T(n)\}}$${\displaystyle T}$${\displaystyle n}$${\displaystyle \{k\mid k<n\}}$${\displaystyle n}$

${\displaystyle \Theta \neq \{\}\,\to \,\neg \neg \exists (n\in \Theta ).n\cap \Theta =\{\}}$

言葉で言えば、ある数が という性質を持つことを否定できない場合、そのような数の最小値が存在することも一貫して否定することはできません。古典的な言葉で言えば、 が成り立つ数が存在する場合、 が成り立つような数も最小値が存在します。ここでの最小値は、が成り立つ他の数が存在しないことを意味します。この原理は、規則性と比較する必要があります。 ${\displaystyle T}$${\displaystyle n}$${\displaystyle T}$${\displaystyle T}$${\displaystyle k<n}$${\displaystyle T}$

決定可能およびで与えられた任意の については、すべてをテストできます。さらに、算術においてマルコフの原理を採用すると、一般に 決定可能 の二重否定を除去できます。${\displaystyle T}$${\displaystyle m}$${\displaystyle T(m)}$${\displaystyle k<m}$${\displaystyle T}$

• 構成的集合論
• 数学的帰納法
• 根拠のない集合論
• 超限帰納法
• 根拠のある帰納法