稠密順序集合と前者/後者について
自分用のノート
ちょっと整理しきれてなくて冗長かもしれない。
定義
半順序集合$P$が稠密(dense)であるとは、以下を満たすことを言う。
- $\forall x, y \in P(x < y),\ \exists z \in P;\ x < z < y$
濃度が2以上の鎖を持たない順序集合は稠密である。このような稠密順序集合を自明な稠密順序集合と呼ぶことにする。
強制法や位相空間での意味とは異なるので注意。
半順序集合$P$上の二項関係を以下で定める。
$x \preceq y :⇔ x \le y$かつ$(\forall z \in P\ (x \le z \le y),\ z = x$または$z = y)$
$x \prec y :⇔x \preceq y$かつ$x \not= y$
$x \prec y$の時、$x$は$y$に被覆されると言う。
半順序集合$P$において、以下は同値。
- $P$は稠密でない
- 被覆関係を持つ2元が存在する
[1 ⇒ 2]
$x < y$を間に入る元がない$x,y \in P$とする。
この時、$x \prec y$である。
[2 ⇒ 1]
$x \prec y$なる$x,y \in P$を取る。
$x < z < y$なる$z \in P$は存在しない。
よって、$P$は稠密でない。
半順序集合$P$において、以下は同値。
- $\forall x \in P\ (xは極大元でない),\ \exists y \in P;\ x \prec y$
- $\forall x \in P\ (xは極大元でない),\ ↑^Px \setminus \set{x}$は極小元を持つ
この命題を後者条件と呼ぶことにする。
[1 ⇒ 2]
$x \in P\ (xは極大元でない)$を取る。
$x \prec y$となる$y \in P$を取る。
[$y$は$↑^Px \setminus \set{x}$の極小元]
$y \in ↑^Px \setminus \set{x}$である。
$z < y$となる$z \in ↑^Px \setminus \set{x}$があると仮定すると、$x < z < y$であり、これは$x \prec y$に矛盾。
従って、$y$は$↑^Px \setminus \set{x}$の極小元である。
[2 ⇒ 1]
$x \in P\ (xは極大元でない)$を取る。
$↑^Px \setminus \set{x}$の極小元$y$を取る。
[$x \prec y$]
$x < z \le y$なる$z \in P$を取ると、$y$の極小性より、$z \not< y$
よって、$z = y$
従って、$x \prec y$
半順序集合$P$において、以下は同値。
- $\forall x \in P\ (xは極小元でない),\ \exists y \in P;\ y \prec x$
- $\forall x \in P\ (xは極小元でない),\ ↓^Px \setminus \set{x}$は極大元を持つ
この命題を前者条件と呼ぶことにする。
略
後者条件と前者条件は必要条件でも十分条件でもない。
$$X = \set{\frac{1}{n+1} \mid n \in \N} \cup \set{0}$$と定める。
$X$は$\set{0,\cdots , \frac{1}{4}, \frac{1}{3}, \frac{1}{2},1}$となっている。
$X$は前者条件は満たすが、後者条件は満たさない($0$に後者がない)。
逆も同様。
前者/後者と稠密性の関係
半順序集合$P$において、以下は必要条件でも十分条件でもない。
- 非自明な稠密部分集合を持たない
- 前者条件と後者条件を満たす
[2を満たすが1を満たさない例]
$\Q$と$\Z$の左辞書式順序集合を考える。
$P = \Q \ _d\times \Z$
[$P$は2を満たす]
$(q,n) \in P$を取る。
$(q,n-1) \prec (q,n) \prec (q,n+1)$である。
[$P$は1を満たさない]
$\set{(q,0) \in P \mid q \in \Q}$は$P$の非自明な稠密部分集合である。
[1を満たすが2を満たさない例]
$P = \left\{ \frac{1}{n+1} \mid n \in \N \right\} \cup \{ 0 \}$と置く。
[$P$は2を満たさない]
$P$は後者条件を満たさない。よって2を満たさない。
[$P$は1を満たす]
$S \subset P$を取る。($|S| \ge 2$)
$x,y \in S\ (x < y)$を取る。
$x < y$かつ$P$の元はすべて$0$以上であることから、$y > 0$である。
したがって、ある$n \in \mathbb{N}$を用いて$y = \frac{1}{n+1}$と表すことができる。
ここで、開区間$(x, y) \cap S$が空集合か否かで場合分けを行う。
[空集合の場合]
$x < z < y$を満たす$z \in S$が存在しないため、稠密の定義より、$S$は稠密でない。
[空集合でない場合]
$x < w < y$を満たす元$w \in S$を1つ固定する。
$y = \frac{1}{n+1}$であり、$x < w < y$であることから、$w$もまた$0$ではなく、ある$k \in \mathbb{N} \ (k > n)$を用いて$w = \frac{1}{k+1}$と表せる。
このとき、$w$と$y$の間にある$P$の元をすべて書き出すと、
$$\left\{ \frac{1}{k}, \frac{1}{k-1}, \dots, \frac{1}{n+2} \right\}$$
となり、これは高々$(k - n - 1)$個の有限集合である。
従って、その部分集合である$(w, y) \cap S$も有限集合である。
もし$(w,y) \cap S$が空集合ならば、その時点で$S$は稠密でない。
もし$(w,y) \cap S$が空でないならば、その有限個の集合は（空でない有限全順序集合なので）必ず最小元$z_{\min}$を持つ。
このとき、$w < z_{\min} < y$であり、$z_{\min}$の最小性から、$w < z' < z_{\min}$を満たすような$z' \in S$は存在し得ない。
従って、この場合も$S$は稠密でない。
よって、$P$は非自明な稠密部分集合を持たず、1を満たす。
半順序集合$P$において、以下は必要条件でも十分条件でもない。
- 非自明な稠密部分集合を持たない
- 前者条件または後者条件を満たす
[2を満たすが1を満たさない例]
上の例
[1を満たすが2を満たさない例]
$A = \set{a_1 < a_2 < a_3 < \dots < a_\infty}$
$B=\set{b_1 > b_2 > b_3 > \dots > b_\infty}$
$P=A \cup B$と定める。
上の例と同様に$P$は非自明な稠密部分集合を持たない。
しかし、$b_\infty$は極大でないのに後者をもたず、$a_\infty$は極小でないのに前者を持たない。
従って、$P$は2を満たさない。
命題
稠密順序集合$P$の任意の区間は稠密である。
区間$[a,b]$について考える。
[$b < a$または$b$と$a$が比較不能の場合]
$[a,b] = \varnothing$であり、これは自明な稠密順序集合である。
[$a = b$の場合]
$[a,b] = \set{a}$であり、これは自明な稠密順序集合である。
[$a < b$の場合]
$x,y \in [a,b]$を取る。($x < y$)
$P$は稠密だから、ある$z \in P$があって、$x < z < y$
$a \le x < z < y \le b$だから、$z \in [a,b]$
稠密順序集合$P$の任意の極大鎖は稠密である。
$P$の極大鎖$C$を取る。
$x,y \in C$を取る。($x < y$)
$P$は稠密だから、ある$z \in P$があって、$x < z < y$
$C \cup \set{z}$も鎖である。
$C$は極大鎖だから、$z \in C$
定理
最大元と最小元を持たない可算な稠密全順序集合は$\Q$と順序同型である。
非自明な稠密部分集合を持たない半順序集合を散在順序集合(scattered ordered set)と呼ぶ。
「散在全順序集合」のクラスは、以下の操作で構築できる最小の全順序集合のクラスである：
- すべての整列集合を含む。
- 順序の反転について閉じている。
- 辞書式和について閉じている。
この記事を高評価した人
この記事に送られたバッジ
投稿者
