初歩的な順序集合
実数には大小関係という関係があってそれが重要な役割を果たすように、数学ではしばしば元の大小や順序というものが大切になってくる。ここでは半順序集合、全順序集合、整列集合、帰納的順序集合などの初歩的な順序構造を考える。
半順序集合、全順序集合、順序同型
定義 1 (半順序集合、全順序集合)
$X$ を集合とし、$X$ の $2$ 項関係 $\le$ が与えられているとする。
- $\le$ が次の $3$ 条件を満たすとき、$(X,\le)$ は半順序集合あるいは単に順序集合であるという。$2$ 項関係 $\le$ が文脈から明らかなときは単に $X$ を半順序集合などという。
- 任意の $x \in X$ に対して、$x \le x$ 。（反射律 ）
- 任意の $x$、$y \in X$ に対して、「 $x \le y$ かつ $y \le x \Rightarrow x=y$ 」。（反対称律 ）
- 任意の $x$、$y$、$z \in X$ に対して、「 $x \le y$ かつ $y \le z \Rightarrow x \le z$ 」。（推移律 ）
半順序集合 $X$ のふたつの元 $a$、$b$ に対して、 $a \le b$ または $b \le a$ が成り立つとき $a$ と $b$ は比較可能であるという。そうでないとき $a$ と $b$ は比較不可能であるという。
また、半順序集合 $(X,\le)$ と $x$、$y \in X$ に対して次のような言い方をする。$x \le y$ であることを、「 $x$ は $y$ 以下である」とか「 $y$ は $x$ 以上である」などという。$y \ge x$ と書いてもよい。また、$x \le y$ かつ $x \ne y$ であることを、$x < y$ または $y > x $ と書き、「 $x$ は $y$ より小さい」とか「 $y$ は $x$ より大きい」などという。
- 半順序集合 $(X,\le)$ がさらに次の性質を満たすとき、$(X,\le)$ は全順序集合であるという。
- 任意の $x$、$y \in X$ に対して、「 $x \le y$ または $y \le x$ 」（すなわち、任意のふたつの元は比較可能）。
例 2
- $\mathbb{R}$、$\mathbb{Q}$、$\mathbb{Z}$、$\mathbb{N}$ は通常の大小関係で半順序集合であり、全順序集合でもある。
- $X$ を集合とする。$X$ のべき集合 $2^X$ と集合 $X$ の包含関係の組 $(2^X,\subset)$ は半順序集合であるが、全順序集合ではない。例えば、 $X=\{1,2,3\} $、$A=\{1,2\}$、$B=\{2,3\}$ とおくと、$A \subset B$ でも $B \subset A$ でもないので $A$ と $B$ は比較不可能である。
- 自然数 $a$、$b \in \mathbb{N}$ に対して、$b$ が $a$ で割り切れるとき $a|b$ と書けば、$(\mathbb{N},|)$ は半順序集合であるが、全順序集合ではない。例えば、自然数 $2$ と $3$ を考えると、$2$ は $3$ で割り切れないし、 $3$ は $2$ で割り切れない。つまり、$2 | 3$ でも $3 | 2$ でもない。
- （双対順序）半順序集合 $(X,\le)$ に対して、「大小関係を逆にした順序」は再び半順序集合となる。つまり、$X$ の $2$ 項関係 $\le '$ を次で定義する。$x$、$y \in X$ に対して $x \le ' y \Leftrightarrow y \le x$ 。このとき、$(X, \le ')$ は半順序集合となる。この順序を$(X , \le)$ の双対順序という。元の集合が全順序であればその双対順序も全順序である。
- （部分順序）半順序集合 $(X,\le)$ と部分集合 $A \subset X$ に対して、$A$ の $2$ 項関係 $\le _{A}$ を次で定義する。$x$、$y \in A$ に対して $x \le _{A} y \Leftrightarrow x \le y$。つまり、$\le _{A}$ は $ \le$ を $A$ に制限したものである。たいていの場合混乱の恐れはないので $\le _{A}$ を単に $\le$ と書くことが多い。元の集合が全順序であればその任意の部分順序も全順序である。
- (全順序部分集合) 半順序集合 $(X,\le)$ と部分集合 $A \subset X$ に対して部分順序集合 $(A,\le)$ は一般的に全順序になるとは限らない。しかし、うまく $A$ を選ぶと $(A , \le)$ が全順序になることもある。このような $A$ を全順序部分集合という。
- ユークリッド平面 $\mathbb{R} ^2$ のべき集合 $\mathcal{P}(\mathbb{R} ^2)$ と $\mathbb{R} ^2$ の包含関係を順序とする半順序集合 $(\mathcal{P}(\mathbb{R} ^2) , \subset)$を考える（全順序ではない）。$\mathcal{P}(\mathbb{R} ^2)$ の部分集合である「原点を中心とする同心円全体」$\mathcal{D} = \{D(r) | r>0 \}$ （ここで $D(r)$ は原点を中心とする半径 $r$ の開円板 $D(r)=\{(x,y) \in \mathbb{R} ^2 | x^2 + y^2 <r^2 \}$ とする）を考えると $(\mathcal{D},\subset)$ は全順序である。つまり $\mathcal{D}$ は $\mathcal{P}(\mathbb{R} ^2)$ の全順序部分集合である。
新しい対象を定義したとき、次にするべきことは「どんなときに同じとみなすか」を定義することである。以下、半順序集合を単に順序集合という。
定義 3 (順序同型)
- $(X,\le _{X})$、$(Y,\le _{Y})$ を順序集合、$f \colon X \longrightarrow Y$ を写像とする。任意の $a$、$b \in X$ に対して $$a \le _{X} b ならば f(a) \le _{Y} f(b)$$ が成り立つとき、$f$ を単調写像、単調増加写像あるいは向きを保つ写像などという。 $$a \le _{X} b ならば f(b) \le _{Y} f(a)$$ が成り立つときは単調減少写像という。なお、単調増加または単調減少をまとめて単に単調と呼ぶこともあるが、本稿ではその定義は採用しない。
- $(X,\le _{X})$、$(Y,\le _{Y})$ を順序集合とする。全単射 $f \colon X \longrightarrow Y$ が
存在して、$f$ と $f^{-1}$ がともに単調写像であるとき、$f \colon X \longrightarrow Y$ あるいは単に 「$X$ と $Y$ 」は順序同型であるという。
$f \colon X \longrightarrow Y$ が順序同型であるとき、定義は後述するが、$a \in X$ に対して、「 $a$ は $X$ の最大元 $\Longleftrightarrow f(a)$ は $Y$ の最大元」や、「$X$ が整列集合$\Longleftrightarrow Y$ が整列集合」等が成り立つ。このような意味で、ふたつの同型な順序集合は同じ順序構造を持っていると考えられる。
定義 4 (最大、最小、極大、極小、有界、上限、下限)
$(X,\le)$ を順序集合、$A \subset X$ とし、$X$ の部分順序 $(A,\le)$ を考える（当然 $A = X$ の場合も考えられることに注意）。このとき次の用語を定義する。
- （最大元）$a \in A$ が「任意の $x \in A$ に対して $x \le a$ 」であるとき、この $a$ を $A$ の最大元（maximum element）であるという。後述するように最大元は存在すれば一意に定まる。そこで、その最大元を $\textrm{max} \, A$ と書く。
- （最小元）$a \in A$ が「任意の $x \in A$ に対して $a \le x$ 」であるとき、この $a$ を $A$ の最小元（minimum element）であるという。後述するように最小元は存在すれば一意に定まる。そこで、その最小元を $\textrm{min} \, A$ と書く。
- （極大元）$a \in A$ が「$a \lt x$ となるような $x \in A$ が存在しない」とき（つまり任意の $x \in A$ に対して、$x \le a$ または $x$ と $a$ は比較不可能）、この $a$ を $A$ の極大元（maximal element）であるという。
- （極小元）$a \in A$ が「$x \lt a$ となるような $x \in A$ が存在しない」とき（つまり任意の $x \in A$ に対して、$a \le x$ または $x$ と $a$ は比較不可能）、この $a$ を $A$ の極小元（minimal element）であるという。
- （上界：じょうかい）$a \in X$ が「任意の $x \in A$ に対して $x \le a$ 」であるとき、$a$ は $A$ の上界（upper bound）であるという。$A$ の上界が存在するとき $A$ は上に有界であるという。
- （下界：かかい）$a \in X$ が「任意の $x \in A$ に対して $a \le x$」であるとき、$a$ は $A$ の下界（lower bound）であるという。$A$ の下界が存在するとき $A$ は下に有界であるという。
- （有界）$A$ が上に有界かつ下にも有界であるとき、単に「 $A$ は有界」であるという。
- （上限）$A$ の上界全体を $A^{*}$ と置く。$A^{*}$ の最小元が存在するとき（存在すれば一意的）、これを $A$ の上限（supremum）といい、$\textrm{sup} \, A$ と書く。すなわち $\textrm{sup} \, A = \textrm{min} \, A^{*}$ である。
- （下限）$A$ の下界全体を $A_{*}$ と置く。$A_{*}$ の最大元が存在するとき（存在すれば一意的）、これを $A$ の下限（infimum）といい、$\textrm{inf} \, A$ と書く。すなわち $\textrm{inf} \, A = \textrm{max} \, A_{*}$ である。
なお、$X$ が数の集合の時は最大元を最大値と呼ぶこともある。最小値、極大値、極小値も同様。
$(X,\le)$ を順序集合とその部分集合 $A \subset X$ に対して次のことに注意。次の命題と例を参照のこと。
- $A$ の最大元や最小元は必ず存在するとは限らないが、存在すれば一意的であり、$A$ の元である（ $A$ の元であることは定義から明らか）。
- $A$ の極大元や極小元は存在したとしても一意とは限らないが、$A$ の元ではある（ $A$ の元であることは定義から明らか）。
- 上界や下界は存在したとしても一意とは限らない。
- $A$ の上限や下限は存在すれば一意に定まるが、これらが $A$ の元になるとは限らない。
命題 5
順序集合 $(X,\le)$の部分集合 $A$ を考える。
- $A$ の最大元や最小元は存在すれば一意に定まる。
- $A$ の最大元が存在すれば、その最大元が唯一の極大元である。
- $A$ の最小元が存在すれば、その最小元が唯一の極小元である。
- $A$ が全順序集合とする。このとき、極大元、極小元は存在すれば一意である。
- $A$ の上限や下限は存在すれば一意に定まる。
Proof.
- （最大元）$A$ にふたつの最大元 $m_1$、$m_2 \in A$ が存在したとする。このとき $m_1$ は $A$ の最大元であることと $m_2 \in A$ から $m_2 \le m_1$ が成り立つ。同様に $m_2$ は $A$ の最大元であることと $m_1 \in A$ から $m_1 \le m_2$ も成り立つ。よって $m_1 = m_2$ である。（最小元）最大元と同様。
- $a=\textrm{max} A$ とする。このとき最大元の定義から、$a \in A$ と「任意の $x \in A$ に対して $x \le a$」が成り立つので、「任意の $x \in A$ に対して $x \le a$ または $x$ と $a$ は比較不可能」も成り立つ。よって、$a$ は $A$ の極大元でもある。次に、もうひとつ $A$ の極大元 $b \in A$ が存在したとする。すると、$b \in A$ と $a$ の最大性から $b \le a$ が成り立つ。よって特に $a$ と $b$ は比較可能である。一方、$a \in A$ と $b$ の極大性より $a \le b$ または $a$ と $b$ は比較不可能であるが、$a$ と $b$ は比較可能であったので $a \le b$ である。以上から $a = b$ なのでこれが唯一の極大元である。
- 2. と同様。
- （極大元）$A$ が全順序であるとする。任意のふたつの元は比較可能であるから、$a \in A$ が $A$ の極大元であるとは、任意の $x \in A$ に対して、$x \le a$ ということである。これは最大元の定義に他ならない。よって最大元の一意性より極大元は存在すれば一意である。（極小元）極大元と同様。
- $\textrm{sup} \, A $ は 「$A$ の上界全体の最小元」なので最小元の一意性から明らか。$\textrm{inf} \, A$ も同様。
例 6
- $a<b$ とする。$\mathbb{R}$ の部分集合 $[a,b]$ と $(a,b)$ に対して、最大元、最小元、極大元、極小元、上界全体、下界全体、上限、下限を求める。結果は次の通り。
| 最大元(max) | 最小元(min) | 極大元 | 極小元 | 上界全体 | 下界全体 | 上限(sup) | 下限(inf) | |
|---|---|---|---|---|---|---|---|---|
| $[a,b]$ | $b$ | $a$ | $b$ | $a$ | $[b,\infty)$ | $(- \infty ,a)$ | $b$ | $a$ |
| $(a,b)$ | 存在しない | 存在しない | 存在しない | 存在しない | $[b,\infty)$ | $(- \infty ,a)$ | $b$ | $a$ |
Proof.
（$[a,b]$ について）最大元、極大元、上界全体、上限のみ示す。$[a,b] = \{x \in \mathbb{R} \,|\, a \le x \le b \} であるので、$b \in [a,b]$ である。さらに任意の $x \in [a,b]$ に対して $a \le x \le b$ なので特に $x \le b$ が成り立つ。よって \textrm{max} [a,b]$ は存在して \textrm{max} [a,b] = b$ である。次に、$b \gt x$ なる x \in \mathbb{R} を考えると （$(a,b)$）最小元、極小元、下界全体、下限のみ示す。
□整列集合
帰納的順序集合
集合論の初歩
論理と命題 / 集合の基本的な用語、集合の演算 / 全称記号と存在記号 / 写像、像、逆像、写像のグラフ / 写像の合成、写像の拡大と制限 / 選択公理について / 単射、全射、全単射、逆写像 / 部分集合族、べき集合 / （ 演算と代数構造 ） / （ 関係、同値関係、商集合 ） / （ 初歩的な順序集合 ） / （ Zornの補題 ） / （ 集合の濃度 ）
