Nにおける∈の無反射性

※集合\(n\)に対し\(n\cup\{n\}\)(これは対の公理と和集合の公理により集合をなす)を\(n'\)と書く。

\(x\in x\)となる集合\(x\)が存在しないことを示すには基礎の公理が必要となるが、\(\mathbb{N}\)の要素に限定すれば、つまり\(\forall x\in\mathbb{N}[x\notin x]\)を示すだけならば、基礎の公理は不要である。
補題】\(\mathbb{N}\)上の関係\(\in\)は推移的である。
(証明)\(l,m\in\mathbb{N}\)を任意にとって固定し、\(\psi(n):l\in m\in n\rightarrow l\in n\)とおく。\(n\)に関する帰納法により\(\forall n\in\mathbb{N}[\psi(n)]\)を示す。まず\(\psi(\varnothing)\)は\(m\notin\varnothing\)により真である。次に\(n\in\mathbb{N}\)に対し\(\psi(n)\)を仮定し\(\psi(n')\)を導く。\(l\in m\in n'\)と仮定すると\(l\in m\in n\)または\(l\in m=n\)となるが、前者なら\(\psi(n)\)から、後者ならただちに\(l\in n\)を得る。これと\(n\subset n'\)から\(l\in n'\)である。■

【定理】\(\mathbb{N}\)上の関係\(\in\)は無反射的である。
(証明)帰納法による。まず\(\varnothing\notin\varnothing\)である。次に\(n\in\mathbb{N}\)に対し\(n\notin n\)を仮定して、\(n'\notin n'\)すなわち\(n'\notin n\wedge n'\neq n\)を導く。仮定と\(\mathbb{N}\)の推移性および\(n\in n'\)から\(n'\notin n\)である。また、同じ仮定と\(n\in n'\)から\(n'\neq n\)である。■