イプシロン誘導

スキーマを表現するためにクラスの言語を用いることができる。普遍クラスを次のように表す。${\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 \omega }$自然数の集合については、以下でさらに詳しく説明します。集合帰納法では、推移的な集合への帰納法が可能であり、${\displaystyle \omega }$これにより、超限帰納法と呼ばれるものが得られ、超限再帰によって定義されます。これは、実際には順序数の真のクラス全体を使用します。順序数を用いると、帰納法により、すべての集合が順序数ランクを持ち、順序数のランクはそれ自身であることが証明されます。

フォン・ノイマン順序数の理論は、そのような集合を記述し、そこで、${\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 R_{D}}$、 等々。

従来、集合上の関係の正則性は、すべての部分集合に対して最小要素が存在するという強い性質によって特徴づけられる。依存選択を用いる場合、無限下降連鎖が存在しないという弱い性質によっても特徴づけられる。

上記の含意における前件は次のように表現できる。${\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 }$-property は仮定が間違っていたことを示唆しています。つまり、${\displaystyle \Sigma =\{\}}$。

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

否定を伴う形式の対偶は構成的にさらに弱いが、正則性主張から二重否定除去を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 =\{\}}$

言い換えれば、少なくとも1つの集合が示す性質は、すべて「最小集合」も示す性質である。${\displaystyle x}$上記で定義したとおり。クラスに関して言えば、これはすべての非空クラスが${\displaystyle \Sigma }$メンバーがいる${\displaystyle x}$それはそれとは無関係である。

一階集合論では、一般的な枠組みとして、集合帰納原理は公理図式であり、任意の述語（つまりクラス）に対して公理を与えます。対照的に、規則性の公理は単一の公理であり、議論領域の要素、つまり集合に対してのみ全称量化子を用いて定式化されます。${\displaystyle \Sigma }$は集合であり、帰納図式が仮定されている。上記は、正則性の公理のインスタンスである。${\displaystyle \Sigma }$したがって、古典論理上の集合帰納法（すなわち排中律を仮定）を仮定すると、すべての規則性が成り立つ。

分離公理の文脈では、正則性は排中律も意味します（分離公理で許容される述語に関して）。一方、集合帰納法の図式は排中律を意味しませんが、前述のように、強い帰納原理を導くのに十分な強さを持っています。この図式は、例えば型理論モデルを持つ構成的集合論CZFで採用されています。したがって、このような集合論の枠組みでは、集合帰納法は正則性よりも厳密に弱い強い原理です。正則性と完全分離の公理を採用すると、CZFは標準ZFと等しくなります。

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

${\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}$一般的に。