【集合論】基本的な集合の階数(rank)を求めてみる[和集合, 順序対, 直積]

集合の階数(rank)

ある問題について考えているときに集合の階数について気になったので, 練習ついでに求めてみました.

集合の階数については演習問題になっている本が多く, 正確な証明が載っていませんでした. この機会に正確な証明を与えながら階数を求めて行きたいと思います.

集合の階数(rank)：階数の定義

順序数のクラスを\(\mathbb{ON}\)と表します. このとき, \(R\)を定義しましょう.

ここでは詳しく述べませんがZF集合論では基礎の公理によっていずれかの\(R(\alpha)\)に属している集合しか扱いません. すなわち,

\(\mathbb{WF} = \bigcup \{R(\alpha) : \alpha \in \mathbb{ON}\}\),

と定めたときに\(\mathbb{WF}\)に属する集合しか考えません.

集合の階数とは簡単に言えばこの\(\mathbb{WF}\)においてどの階層で現れるかを表したものになります.

以下では\(R(\alpha)\)が推移的であることは断りなく用います. 推移性に関する証明が気になる方はぜひ参考文献をご覧ください.

集合の階数(rank)：基本的な集合の階数

\(x, y\)を集合としたときに, \(\{x\}\), \(\{x, y\}\), \(\langle x, y \rangle\), \(x \cup y\), \(\bigcup x\), \(x \times y\)の階数を求めてみます.

集合の階数を求める際の基本的な補題

階数を求める上で便利ないくつかの補題を準備しておきます.

補題1：
\(\alpha \in \mathbb{ON}\)について, \(x \in R(\alpha)\)が成り立つことと\(\mathrm{rank}(x) < \alpha\)が成り立つことは同値.

補題2：
\begin{align}
x \in y \Longrightarrow \mathrm{rank} (x) < \mathrm{rank} (y). \end{align}

補題3：
\(\alpha \in \mathbb{ON}\)について,
\begin{align}
\alpha < \mathrm{rank} (x) \iff \exists y \in x (\alpha \leq \mathrm{rank} (y)). \end{align}

補題3は階数の下からの評価を得るときにとても便利です.

集合の階数：\(\{x\}\)

命題4：
\begin{align}
\mathrm{rank} (\{x\}) = \mathrm{rank} (x) + 1.
\end{align}

集合の階数：\(\{x, y\}\)

命題5：
\begin{align}
\mathrm{rank} (\{x, y\}) = \mathrm{max} (\mathrm{rank} (x), \mathrm{rank} (y)) + 1.
\end{align}

集合の階数：\(\langle x, y\rangle\)

命題6：
\begin{align}
\mathrm{rank} (\langle x, y\rangle) = \mathrm{max} (\mathrm{rank} (x), \mathrm{rank} (y)) + 2.
\end{align}

集合の階数：\(x \cup y\)

命題7：
\begin{align}
\mathrm{rank} (x \cup y) = \mathrm{max} (\mathrm{rank} (x), \mathrm{rank} (y)).
\end{align}

集合の階数：\(\bigcup x\)

命題8：
\begin{align}
\mathrm{rank} (\bigcup x) = \left\{
\begin{array}{ll}
\mathrm{rank} (x) – 1 & (\mathrm{rank} (x) \text{が後続型順序数のとき}), \\
\mathrm{rank} (x) & (\mathrm{rank} (x) \text{が極限順序数のとき}).
\end{array}
\right.
\end{align}

集合の階数：\(x \times y\)

命題9：
\(\alpha = \mathrm{max} (\mathrm{rank} (x), \mathrm{rank} (y))\)とする.
\begin{align}
\mathrm{rank} (x \times y) = \left\{
\begin{array}{ll}
\alpha + 2 & (\alpha \text{が後続型順序数のとき}), \\
\alpha & (\alpha \text{が極限順序数のとき}).
\end{array}
\right.
\end{align}

参考文献

[1] ケネス・キューネン, 集合論, 日本評論社，2008.