ZFC公理系

自己所属はまさにラッセルのパラドックスを引き起こす類の自己言及である;正則性は、毎回矛盾を導くのではなく、集合がどう構成され得るかについての構造的規則として、一度限りでそれを排除する。これにより数学者は所属関係上の帰納法・再帰法を安全に定義でき、通常の数学に登場する集合が決して自分自身を含まない理由もこれである。

矛盾を導くために、ある集合 $x$ が $x \in x$ を満たすと仮定する。

対の公理により、集合 $\{x\}$ が存在する($x$ を自分自身と対にする)。この集合は $x$ を含むので空でない。

空でない集合 $\{x\}$ に正則性公理を適用する:$\{x\} \cap y = \emptyset$ を満たす $y \in \{x\}$ が存在しなければならない。しかし $\{x\}$ の唯一の元は $x$ 自身なので $y = x$ であり、結論は $\{x\} \cap x = \emptyset$ となる。

ここで矛盾の仮定 $x \in x$ を思い出す。$x \in \{x\}$(対の定義により)かつ $x \in x$(我々の仮定)なので、元 $x$ は $\{x\}$ にも $x$ にも属し、したがって $x \in \{x\} \cap x$ である。これは $\{x\} \cap x$ が空でないことを意味し、上で得られた $\{x\} \cap x = \emptyset$ に直接矛盾する。

この矛盾により、仮定 $x \in x$ はどんな集合 $x$ に対しても不可能であることが示される;したがってすべての集合 $x$ に対して $x \notin x$ が、主張どおり成り立つ。

ツォルンの補題、選択公理、整列可能定理はまったく異なって見える——1つは順序と極大元について、1つは多くの集合から同時に選ぶことについて、1つは無限降下のない全順序について——しかしそれぞれが、無限に多くの制約のない選択を同時に行うという、まったく同じ根底の力を体現している。これが、代数学者が(極大イデアル、基底、代数的閉包といった)存在命題を証明する際に、選択公理単独よりも便利なツォルンの補題を用いる理由である。

選択公理 $\implies$ ツォルンの補題を証明する(他の同値性は標準的だがより長い;この方向は代数学で絶えず使われる方向である)。$(P, \le)$ をすべての鎖が $P$ 内に上界を持つ空でない半順序集合とし、矛盾を導くために $P$ に極大元がないと仮定する。

$P$ に極大元がないので、すべての $x \in P$ は $P$ 内に厳密な上界(ある元 $y$ で $x < y$)を持つ:さもなければその $x$ 自身が極大となる。特に、すべての鎖 $C \subseteq P$ は(仮定により)上界を持ち、その上界自体もまた厳密な上界を持つので、すべての鎖は $P$ 内に厳密な上界を持つ。

選択公理により、すべての鎖 $C \subseteq P$ に対して、鎖 $C$ の厳密な上界 $g(C)$ を選ぶ選択関数を固定する。$g$ を用いて、すべての順序数 $\alpha$ で添字づけられた超限列 $(a_\alpha)$ を構成する:$a_0 = g(\emptyset)$ とし、各順序数 $\alpha$ について、すべての $\beta < \alpha$ に対して $a_\beta$ がすでに定義されているとき、集合 $\{a_\beta : \beta<\alpha\}$ は鎖である(構成により、新しい各項はそれ以前のすべての項の厳密な上界である)ので、$a_\alpha = g(\{a_\beta : \beta<\alpha\})$ と定義し、これはそれ以前のすべての項の厳密な上界である。

これにより、順序数から $P$ への狭義単調増加な写像が得られる:$\alpha < \beta \implies a_\alpha < a_\beta$。しかし順序数全体は集合をなさない(すべての順序数からなる集合は存在しない)一方、$P$ は通常の集合である;順序数から $P$ への狭義単調増加な写像は、順序数の濃度が $P$ 以下であることを意味し、どんな集合もすべての順序数ほど大きな集まりの上へ単射で写ることはできないという事実(置換公理の帰結)に矛盾する。この矛盾は「$P$ に極大元がない」という仮定が偽であることを示し、よって $P$ は極大元を持ち、選択公理からツォルンの補題が証明される。