無限公理

空集合 ${\displaystyle \varnothing }$ を元とし、任意の元 ${\displaystyle x}$ について ${\displaystyle x\cup \left\{x\right\}}$ も元とする集合が存在する。ただし、下記の論理式は、外延性公理を定めたときに有効な表記である。

${\displaystyle \exists A\left[\varnothing \in A\land \forall x\left[x\in A\Rightarrow x\cup \left\{x\right\}\in A\right]\right]}$

一階述語論理の原始的な記号だけを用いて、この公理を表記すると下記である^[2]。

${\displaystyle \exists \mathrm {I} \left[\exists o\left[o\in \mathrm {I} \land \forall n\left[n\not \in o\right]\right]\land \forall x\left[x\in \mathrm {I} \Rightarrow \exists y\left[y\in \mathrm {I} \land \forall a\left[a\in y\Leftrightarrow \left[a\in x\lor a=x\right]\right]\right]\right]\right]}$

一部の数学者は、この方法で構成された集合を英語でinductive set（英語: inductive set）と呼ぶ。

Summarize Timeline Fact Check

この公理は、 フォン・ノイマンによる自然数の構成法と密接に関連する。この構成法では、${\displaystyle x}$ の後続を ${\displaystyle x\cup \left\{x\right\}}$ と再帰的に定める。${\displaystyle x}$ が集合であるとき、集合論の他の公理から、${\displaystyle x}$ の後続もまた一意に定義される。後続を使うことで、自然数の集合論的な表現を定義できる。

この方法では、${\displaystyle 0}$ を空集合とする。

${\displaystyle 0=\varnothing }$

任意の自然数について、その後続も定義する。

${\displaystyle 1=0\cup \left\{0\right\}=\varnothing \cup \left\{0\right\}=\left\{0\right\}=\left\{\varnothing \right\}}$ ${\displaystyle 2=1\cup \left\{1\right\}=\left\{0\right\}\cup \left\{1\right\}=\left\{0,\,1\right\}=\left\{\varnothing ,\,\left\{\varnothing \right\}\right\}}$ ${\displaystyle 3=2\cup \left\{2\right\}=\left\{0,\,1\right\}\cup \left\{2\right\}=\left\{0,\,1,\,2\right\}}$ ${\displaystyle 4=3\cup \left\{3\right\}=\left\{0,\,1,\,2\right\}\cup \left\{3\right\}=\left\{0,\,1,\,2,\,3\right\}}$

この定義より、任意の自然数は、それより前の全ての自然数からなる集合である（数学的帰納法）。各集合の最上位の要素の数はその集合が表す自然数と一致し、もっとも深く入れ子になった空集合の深さとも一致する。

自然数全体の集合 ${\displaystyle \omega =\left\{0,\,1,\,2,\,\dots \right\}}$（順序数の概念を明言しない文脈では、${\displaystyle \mathbb {N} _{0}}$ とも）の存在は、ZFC公理上の他の公理から証明できない。よって、この存在を公理とし、無限公理と呼ぶ。無限公理は、ある集合 ${\displaystyle \mathrm {I} }$ が存在し、${\displaystyle \mathrm {I} }$ が ${\displaystyle 0}$ を要素とし、${\displaystyle \mathrm {I} }$ が後続を取る操作について閉じていることを定める。すなわち、${\displaystyle \mathrm {I} }$ の任意の要素について、その後続もまた ${\displaystyle \mathrm {I} }$ の要素である。

以上のことから、この公理の本質として「すべての自然数を要素とする集合 ${\displaystyle \mathrm {I} }$ が存在する」。

この公理はフォン・ノイマン＝ベルナイス＝ゲーデル集合論においても公理である。

Summarize Timeline Top Qs Fact Check

無限集合Iはすべての自然数を含んでいるが。自然数全体が集合となることを示すために、分出公理を使って不要な要素を取り除いて、残った集合Nが自然数全体からなる集合である。この集合は外延性の公理により一意である。

自然数を抽出するために、どの集合が自然数であるかを定義する必要がある。外延性の公理とaxiom of induction（英語: epsilon-induction）以外の公理を使わずに自然数を定義することが可能である。nが自然数であるとは0であるか何かの後続であり、かつ、nの各要素も0であるかnの要素の後続であることと定める。形式的に書くと、

${\displaystyle \forall n(n\in \mathbf {N} \iff ([n=\emptyset \,\,\lor \,\,\exists k(n=k\cup \{k\})]\,\,\land \,\,\forall m\in n[m=\emptyset \,\,\lor \,\,\exists k\in n(m=k\cup \{k\})]))}$

である。

より形式化して書くと

${\displaystyle \forall n(n\in \mathbf {N} \iff ([\forall k(\lnot k\in n)\lor \exists k\forall j(j\in n\iff (j\in k\lor j=k))]\;\land }$

${\displaystyle \forall m(m\in n\Rightarrow [\forall k(\lnot k\in m)\lor \exists k(k\in n\land \forall j(j\in m\iff (j\in k\lor j=k)))])))}$

である。

以下のような他の方法もある。${\displaystyle \Phi (x)}$を「xは帰納的である」という論理式とする。つまり、${\displaystyle \Phi (x)=(\emptyset \in x\wedge \forall y(y\in x\to (y\cup \{y\}\in x)))}$とする。おおざっぱに言うとすべての帰納的な集合の共通部分をとりたいわけである。これを形式的に書くと、次のような集合${\displaystyle W}$が一意に存在することを示したい。

${\displaystyle \forall x(x\in W\leftrightarrow \forall I(\Phi (I)\to x\in I))}$ (*)

存在については、無限公理と分出公理を使って証明する。${\displaystyle I}$を無限公理によって保証された帰納的集合とする。分出公理を使って集合${\displaystyle W=\{x\in I:\forall J(\Phi (J)\to x\in J)\}}$を取り出す。つまり${\displaystyle W}$は${\displaystyle I}$の要素のうち、あらゆる帰納的集合に含まれているものを集めてきた集合である。明らかに(*)を満たす。なぜなら、${\displaystyle x\in W}$と仮定すると、${\displaystyle x}$はすべての帰納的集合に含まれているし、${\displaystyle x}$がすべての帰納的集合に含まれているとすると、もちろん${\displaystyle I}$にも含まれているから、${\displaystyle W}$にも含まれている。

一意性については、(*)を満たす集合はそれ自体帰納的集合であることに注意する。なぜなら、0はすべての帰納的集合に含まれているし、${\displaystyle x}$がすべての帰納的集合に含まれているとすると、その後続もすべての帰納的集合に含まれている。よって${\displaystyle W'}$を別の帰納的集合とすると、${\displaystyle W}$が帰納的であるため${\displaystyle W'\subseteq W}$が成り立ち、${\displaystyle W'}$が帰納的であることから${\displaystyle W\subseteq W'}$も成り立つ。よって${\displaystyle W=W'}$。この集合を${\displaystyle \omega }$と書く。

この定義は数学的帰納法を容易に導けるため便利である。実際、${\displaystyle I\subseteq \omega }$が帰納的と仮定すると、${\displaystyle \omega \subseteq I}$であり、${\displaystyle I=\omega }$となる。

いずれの方法においても二階の算術（英語版）の公理系をみたす構造を与える。なぜなら、冪集合公理により${\displaystyle \omega }$の冪集合に関する量化が可能であるからである。よってこれらは同型であることがわかり、この同型は恒等写像であるため、同値でなければならない。

いくつかの文献では以下の弱そうに見えるバージョンが使われている。

${\displaystyle \exists x\,(\exists y\,(y\in x)\,\land \,\forall y(y\in x\,\rightarrow \,\exists z(z\in x\,\land \,y\subsetneq z)))\,.}$

これはxは空でなく、xの任意の要素yについて、xの要素zで、yはzの真部分集合であるものが存在すると主張している。このことから、xの構造については特に考えることなく、これが無限集合であることが分かる。ZFの他の公理を使うことで、この公理からωの存在を示すことができる。最初に、xの冪集合をとる、この冪集合はxの有限部分集合をすべて含んでいる。これらの有限部分集合の存在を示すにはaxiom of separationかまたは対の公理と和集合の公理を使う。次にxの冪集合に対して置換公理を使い、各要素をそれと同じ濃度をもつ始順序数へ置換する(そのような順序数がない場合は0とする)。この結果は順序数からなる無限集合である。和集合の公理を使いω以上の順序数をえる。