共終部分集合について
自分用のノート
定義
半順序集合$P$の部分集合$A$が$P$の共終部分集合(cofinal subset)であるとは、以下を満たすこと。
- $\forall x \in P, \exists a \in A; x \le a$
共終部分集合を取り出す
無限半順序集合$C$から、以下の方法で$\alpha < \beta ⇒ d_\alpha < d_\beta$を満たす整列集合
$D=(d_\alpha)_{\alpha < \kappa}$
を取り出すことができる。
選択関数$F: \mathcal{C}(P) \setminus \{\varnothing\} \to C$ を1つ固定する。
$d_0$を$C$の適当な元とする。
ある順序数$\alpha$について、$\beta < \alpha$に対し $d_\beta \in C$が既に定義されているとする。
$U_\alpha = \{ y \in C \mid \forall \beta < \alpha,\ d_\beta < y \}$と定める。
$U_\alpha$に対して、次のルールで$d_\alpha$を定める。
$U_\alpha \neq \varnothing$の場合：$d_\alpha = F(U_\alpha)$と定義する。
$U_\alpha = \varnothing$の場合：列の構成をここで停止する。
$U_\alpha=\varnothing$となる最小の$\alpha$を$\kappa$と置く。
$D = \set{d_\alpha \in C \ |\ \alpha < \kappa}$と置く。
ルールより、$\alpha < \beta ⇒ d_\alpha < d_\beta$
補題1で、さらに$C$が全順序なら、$D$は$C$の共終部分集合になる。
[$D$は$C$の共終部分集合]
補題1と同じように$U_\alpha$と$\kappa$と$D$を定義する。
$D$が共終でないと仮定する。
$D$は共終でないから、
$\exists z \in C;\ \forall \alpha < \kappa,\ d_\alpha \not\ge z$
が成り立つ。
そのような$z$を取る。($C$は全順序であるから、$d_\alpha \le z$が言える。)
$C$は最大元を持たないから、$z < y$なる$y \in C$が取れる。
この時、任意の$\alpha < \kappa$に対して$d_\alpha \le z < y$であるから、
$y \in U_\kappa$が成り立つ。
これは、$U_\kappa = \varnothing$に矛盾。
従って、$D$は$C$において共終である。
補題1で、さらに$C$が極大元を持たないなら、$\kappa$は極限順序数になる。
[$\kappa$は極限順序数]
補題1と同じように$U_\alpha$と$\kappa$を定義する。
$\kappa$は$0$ではない。
$\kappa = \alpha + 1$と仮定すると、$U_\alpha$は空でない。
$x \in U_\alpha$を取る。
$C$は極大元を持たないから、$x < y$なる$y \in C$が取れる。
この時、$y \in U_{\kappa}$であり、これは$U_\kappa = \varnothing$に矛盾。
よって、$\kappa$は極限順序数
任意の順序数$\alpha$は極限順序数$\gamma$(または$0$)と自然数$n$の和として一意に書ける。
$n$が偶数の時、$\alpha$を偶順序数
$n$が奇数の時、$\alpha$を奇順序数
と呼ぶことにする。
最大元を持たない鎖$C$に対し、以下を満たす部分集合$A,B$が存在する。
- $A \cap B = \varnothing$
- $A \cup B = C$
- $A$と$B$は$C$の共終部分集合
このような$A,B$を$C$の共終分割(cofinal partition)と言う。
$C$の共終部分集合$D=(d_\alpha)_{\alpha < \kappa}$を取る。($\alpha < \beta ⇒ d_\alpha < d_\beta,\ \kappa$は極限順序数)
$c \in C$に対し、$\alpha_c = \min\set{\alpha < \kappa\ |\ c \le d_\alpha }$と置く。
$A = \set{c \in C\ |\ \alpha_c \text{が偶順序数}}$
$B = \set{c \in C\ |\ \alpha_c \text{が奇順序数}}$
と定める。
これは$A \cap B = \varnothing$と$A \cup B = C$を満たす。
[$A$の共終性]
$c \in C$を取る。
$D$の共終性より、$c \le d_\alpha$を満たす$d_\alpha \in D$が取れる。
$d_\alpha$または$d_{\alpha+1}$は$A$に入っている。
[$B$の共終性]
同様
同じ方法で任意有限個の共終分割が得られる。
無限個の共終分割が得られるかどうかは面白い話題である。
(共終数などで検索するといいと思う。)
応用
極大元を持たない半順序集合$P$上の共終部分集合$A$は極大元を持たない。
背理法により示す。
$m$を$A$の極大元とする。
$P$は極大元を持たないから、$m < x$なる$x \in P$が取れる。
$A$は$P$の共終部分集合だから、$x \le a$なる$a \in A$が取れる。
この時、$m < a$
これは$m$が極大元であることに矛盾。
従って、$A$は極大元を持たない。
$D \underset{cofinal}{\subset} C \subset P$の時、$C$と$D$の上界全体は一致する。
$D \subset C$であるから、明らかに$↑^PC \subset ↑^PD$が成り立つ。
[$↑^PD \subset ↑^PC$]
$\indent$$x \in ↑^PD$を取る。
$\indent$[$x \in ↑^PC$]
$\dindent$$c \in C$を取る。
$\dindent$$D$は$C$の共終部分集合であるから、ある$d \in D$が存在して$c \le d$となる。
$\dindent$そのような$d$を取る。
$\dindent$$x$は$D$の上界であるから$d \le x$であり、推移律より$c \le x$となる。
従って、$↑^PC = ↑^PD$
半順序集合$P$と上限を持たない鎖$C \subset P$に対し、以下を満たす鎖$D$が取れる。
- $D \subset C$
- $D$は$C$の共終部分集合
- $D$は整列集合
- $D$は$P$において上限を持たない
- $D$は最大元を持たない
$D$として$C$の整列共終部分集合を取る。
$C$と$D$の上界全体は一致する。
$C$が最小上界を持たないから、$D$も最小上界を持たない。
[$D$は最大元を持たない]
$D$が最大元$d$を持つとする。
$d$は$D$の上界である。
任意の$e \in ↑^PD$に対し、$d \le e$であるから、$d$は$e \in ↑^PD$の最小元である。
これは$D$が最小上界を持たないことに矛盾。
従って、$D$は最大元を持たない。
この記事を高評価した人
この記事に送られたバッジ
投稿者
