第4章同値関係と順序（数学の言葉：論理・集合・写像）

この章の目標

二項関係の反射律・対称律・反対称律・推移律を判定できる

同値関係から同値類・商集合・自然な射影を作り、同値関係と分割の対応を説明できる

商集合上の写像や演算の well-definedness（代表元の取り方によらないこと）を確かめられる

写像の標準分解 $X \to X/{\sim} \to f(X) \to Y$ を述べ、証明できる

半順序・全順序、最大元と極大元、上界と上限の違いを例で説明でき、整列集合と超限帰納法の考え方を理解する

前提：第2章、第3章

数学では「違うものを同じとみなす」操作が頻繁に現れる。時計の上では 14 時と 2 時は同じ位置にあり、分数 $1/2$ と $2/4$ は同じ数を表し、原点を通る直線上の点はどれも同じ「方向」を表す。こうした「同一視」を正確に行う道具が同値関係と商集合である。同一視したものの上で写像や演算を定義するときには、それが矛盾なく定まること（well-definedness）を確かめる義務が生じる。これは大学数学で最初につまずきやすい点の一つなので、丁寧に扱う。後半では、大小関係を抽象化した順序を学ぶ。

4.1 二項関係

定義 4.1（二項関係）集合 $X$ に対し、直積の部分集合 $R \subset X \times X$ を $X$ 上の二項関係 (binary relation) といい、 $(x, y) \in R$ であることを $x \mathrel{R} y$ と書く。二項関係 $R$ について、次の性質を考える。

反射律 (reflexivity)： $\forall x \in X,\ x \mathrel{R} x$

対称律 (symmetry)： $\forall x, y \in X,\ (x \mathrel{R} y \Rightarrow y \mathrel{R} x)$

反対称律 (antisymmetry)： $\forall x, y \in X,\ (x \mathrel{R} y \land y \mathrel{R} x \Rightarrow x = y)$

推移律 (transitivity)： $\forall x, y, z \in X,\ (x \mathrel{R} y \land y \mathrel{R} z \Rightarrow x \mathrel{R} z)$

写像をグラフとして定義したのと同じく、関係も「関係にある組の集合」として定義する。

例 4.2 いくつかの関係について、性質を調べる（○は成り立つ、×は成り立たない）。

関係	反射律	対称律	反対称律	推移律
集合 $X$ 上の $x = y$	○	○	○	○
$\mathbb{R}$ 上の $x \leq y$	○	×	○	○
$\mathbb{R}$ 上の $x < y$	×	×	○	○
$\mathbb{N}$ 上の $a \mid b$ （ $a$ は $b$ を割り切る）	○	×	○	○
$\mathbb{Z}$ 上の $a \mid b$	○	×	×	○
$\mathcal{P}(X)$ 上の $A \subset B$ （ $X \neq \emptyset$ ）	○	×	○	○
$\mathbb{R}$ 上の $\lvert x - y \rvert < 1$	○	○	×	×

いくつか補足する。 $x < y$ の反対称律は、前提「 $x < y$ かつ $y < x$ 」が決して成り立たないので空虚に真である。 $\mathbb{Z}$ 上の $\mid$ は $1 \mid -1$ かつ $-1 \mid 1$ なので反対称律が破れる。 $\lvert x - y \rvert < 1$ は $0$ と $0.6$ 、 $0.6$ と $1.2$ がそれぞれ関係にあるのに $0$ と $1.2$ は関係にないので、推移律が破れる。

4.2 同値関係と同値類

定義 4.3（同値関係）反射律・対称律・推移律を満たす二項関係を同値関係 (equivalence relation) という。同値関係は $\sim$ や $\equiv$ などの記号で表すことが多い。

例 4.4

(1) どんな集合でも、等号 $=$ は同値関係である。

(2) $n \in \mathbb{N}$ を固定する。 $a, b \in \mathbb{Z}$ について、 $n \mid (a - b)$ のとき $a \equiv b \pmod{n}$ と書き、 $a$ と $b$ は $n$ を法として合同 (congruent) であるという。これは同値関係である。実際、反射律は $a - a = n \cdot 0$ から、対称律は $a - b = nk$ ならば $b - a = n(-k)$ から、推移律は $a - b = nk$ 、 $b - c = nl$ ならば $a - c = n(k + l)$ から従う。

(3) $\mathbb{R}$ 上で $x - y \in \mathbb{Z}$ のとき $x \sim y$ と定めると、(2) と同様に同値関係になる。

(4) 写像 $f\colon X \to Y$ に対し、 $f(x) = f(x')$ のとき $x \sim_f x'$ と定めると、等号の性質から同値関係になる。「誕生日が同じ」（ $f$ = 誕生日）はこの形である。実は、どんな同値関係もこの形に書ける（定理 4.7 (4)）。

注意 4.5（反射律は省けない）「対称律と推移律から反射律が出る： $x \sim y$ なら対称律で $y \sim x$ 、推移律で $x \sim x$ 」という議論は誤りである。この議論は $x \sim y$ となる $y$ が存在することを暗黙に仮定している。実際、 $X = \lbrace 1, 2 \rbrace$ 上の $R = \lbrace (1, 1) \rbrace$ は対称律と推移律を満たすが、 $2 \mathrel{R} 2$ でないので反射律を満たさない。

定義 4.6（同値類・商集合） $\sim$ を集合 $X$ 上の同値関係とする。

$x \in X$ に対し、 $[x] := \lbrace y \in X \mid x \sim y \rbrace$ を $x$ の同値類 (equivalence class) という。

同値類全体の集合 $X/{\sim} := \lbrace [x] \mid x \in X \rbrace$ を $X$ の $\sim$ による商集合 (quotient set) という。

写像 $\pi\colon X \to X/{\sim}$ 、 $x \mapsto [x]$ を自然な射影 (canonical projection) という。

同値類 $C$ の元を $C$ の代表元 (representative) という。各同値類からちょうど一つずつ元を含む部分集合 $S \subset X$ を完全代表系 (complete system of representatives) という。

同値類 $[x]$ は $\overline{x}$ や $[x]_{\sim}$ とも書く。商集合 $X/{\sim}$ は「同値なものを一つにまとめた」集合であり、その元は $X$ の部分集合である。

定理 4.7 $\sim$ を $X$ 上の同値関係とし、 $x, y \in X$ とする。

$x \in [x]$ 。特に同値類は空でない。

$x \sim y \iff [x] = [y]$

$[x] \cap [y] \neq \emptyset$ ならば $[x] = [y]$ 。すなわち、二つの同値類は一致するか交わらないかのどちらかである。

自然な射影 $\pi$ は全射であり、 $\pi(x) = \pi(y) \iff x \sim y$ である。

証明. (1) 反射律による。

(2) ( $\Rightarrow$ ) $x \sim y$ とする。 $z \in [y]$ なら $y \sim z$ であり、推移律より $x \sim z$ 、すなわち $z \in [x]$ 。よって $[y] \subset [x]$ 。対称律より $y \sim x$ なので、同じ議論で $[x] \subset [y]$ 。( $\Leftarrow$ ) (1) より $y \in [y] = [x]$ なので $x \sim y$ 。

(3) $z \in [x] \cap [y]$ とすると $x \sim z$ かつ $y \sim z$ 。対称律で $z \sim y$ 、推移律で $x \sim y$ となり、(2) より $[x] = [y]$ 。

(4) 商集合の定義から $\pi$ は全射であり、後半は (2) の言いかえである。 $\square$

(4) は、同値関係 $\sim$ が写像 $\pi$ から例 4.4 (4) の方法で得られることを意味する。

例 4.8 (1) 例 4.4 (2) の合同による商集合を $\mathbb{Z}/n\mathbb{Z}$ と書く。 $a$ の同値類は $[a] = \lbrace a + nk \mid k \in \mathbb{Z} \rbrace$ である。除法の定理（任意の $a \in \mathbb{Z}$ に対し $a = qn + r$ 、 $0 \leq r < n$ を満たす整数 $q, r$ がただ一組存在する。代数学第1章）より $[a] = [r]$ となる $r \in \lbrace 0, 1, \dots, n-1 \rbrace$ がある。また $0 \leq r, r' < n$ で $[r] = [r']$ なら、 $n \mid (r - r')$ かつ $\lvert r - r' \rvert < n$ より $r = r'$ である。よって

\mathbb{Z}/n\mathbb{Z} = \lbrace [0], [1], \dots, [n-1] \rbrace

はちょうど $n$ 個の元をもち、 $\lbrace 0, 1, \dots, n-1 \rbrace$ は完全代表系である。 $n = 2$ なら $[0]$ は偶数全体、 $[1]$ は奇数全体である。

(2) 例 4.4 (3) の商集合を $\mathbb{R}/\mathbb{Z}$ と書く。区間 $[0, 1)$ は完全代表系である（問題 4.6）。

4.3 分割と同値関係

定理 4.7 は、同値類たちが $X$ を重なりなく覆うことを示している。この性質を抜き出す。

定義 4.9（分割）集合 $X$ の部分集合からなる集合 $\mathcal{A}$ が次を満たすとき、 $\mathcal{A}$ を $X$ の分割 (partition) という。

各 $A \in \mathcal{A}$ は空でない。

$A, B \in \mathcal{A}$ かつ $A \neq B$ ならば $A \cap B = \emptyset$

$\bigcup \mathcal{A} = X$

定理 4.10（同値関係と分割の対応）集合 $X$ について次が成り立つ。

$\sim$ が $X$ 上の同値関係ならば、 $X/{\sim}$ は $X$ の分割である。

$\mathcal{A}$ が $X$ の分割ならば、「 $x, y \in A$ となる $A \in \mathcal{A}$ がある」とき $x \sim_{\mathcal{A}} y$ と定めた関係 $\sim_{\mathcal{A}}$ は同値関係であり、 $X/{\sim_{\mathcal{A}}} = \mathcal{A}$ である。

同値関係 $\sim$ に対し、分割 $X/{\sim}$ から (2) で作った同値関係はもとの $\sim$ に一致する。

したがって、 $X$ 上の同値関係と $X$ の分割とは一対一に対応する。

証明. (1) 定理 4.7 の (1)(3) と、各 $x$ が $[x]$ に属することから従う。

(2) 反射律： $x \in X = \bigcup \mathcal{A}$ なので $x \in A$ となる $A \in \mathcal{A}$ がある。対称律は定義から明らか。推移律： $x, y \in A$ 、 $y, z \in B$ （ $A, B \in \mathcal{A}$ ）とすると $y \in A \cap B$ なので、分割の条件 2 より $A = B$ 、よって $x, z \in A$ 。次に、 $x \in A \in \mathcal{A}$ のとき $[x] = A$ であることを示す。 $y \in A$ なら $x \sim_{\mathcal{A}} y$ なので $A \subset [x]$ 。逆に $y \in [x]$ なら $x, y \in B$ となる $B \in \mathcal{A}$ があり、 $x \in A \cap B$ より $B = A$ 、よって $y \in A$ 。以上から各同値類は $\mathcal{A}$ の元であり、また各 $A \in \mathcal{A}$ は空でないので元 $x$ をもち $A = [x]$ となる。よって $X/{\sim_{\mathcal{A}}} = \mathcal{A}$ 。

(3) $x, y$ がある同値類 $[z]$ に属するなら $z \sim x$ 、 $z \sim y$ より $x \sim y$ 。逆に $x \sim y$ なら $x, y \in [x]$ 。よって「同じ同値類に属する」ことは $x \sim y$ と同値である。 $\square$

同値関係を与えることと、集合を「重なりのない空でない部分」に分けることは、同じことの二つの見方なのである。

4.4 商集合上の写像と well-definedness

商集合上に写像を定義したいとき、「 $\overline{f}([x]) := f(x)$ 」のように代表元を使って書くのが自然である。しかし一つの同値類には多くの代表元があるので、どの代表元を使っても同じ値になることを確かめなければ、写像を定義したことにならない。このことを、写像が well-defined（矛盾なく定義されている）であるという。

定理 4.11（商集合からの写像） $\sim$ を $X$ 上の同値関係、 $\pi\colon X \to X/{\sim}$ を自然な射影、 $f\colon X \to Y$ を写像とし、
$\forall x, x' \in X,\ (x \sim x' \Rightarrow f(x) = f(x'))$
が成り立つとする。このとき $\overline{f} \circ \pi = f$ 、すなわち $\overline{f}([x]) = f(x)$ （ $x \in X$ ）を満たす写像 $\overline{f}\colon X/{\sim} \to Y$ がただ一つ存在する。

証明. $G := \lbrace ([x], f(x)) \mid x \in X \rbrace \subset (X/{\sim}) \times Y$ が写像のグラフであることを示す。存在：各 $C \in X/{\sim}$ はある $x$ により $C = [x]$ と書け、 $([x], f(x)) \in G$ である。一意性： $(C, y), (C, y') \in G$ とすると、 $C = [x] = [x']$ 、 $y = f(x)$ 、 $y' = f(x')$ となる $x, x'$ がある。定理 4.7 (2) より $x \sim x'$ なので、仮定より $y = f(x) = f(x') = y'$ 。よって $G$ は写像 $\overline{f}$ を定め、 $\overline{f}([x]) = f(x)$ である。 $g \circ \pi = f$ となる写像 $g$ がもう一つあれば、 $g([x]) = f(x) = \overline{f}([x])$ がすべての $x$ で成り立ち、 $\pi$ は全射なので $g = \overline{f}$ 。 $\square$

逆に $\overline{f} \circ \pi = f$ となる $\overline{f}$ があれば、 $x \sim x'$ のとき $f(x) = \overline{f}([x]) = \overline{f}([x']) = f(x')$ となる。つまり定理の仮定は必要十分である。状況は次の図式で表される。

\begin{array}{ccc} X & \xrightarrow{f} & Y \\ {\scriptstyle \pi}\downarrow & \nearrow{\scriptstyle \overline{f}} & \\ X/{\sim} & & \end{array}

商集合上の二項演算「 $[x] \ast [y] := [x \ast y]$ 」の場合も同様で、「 $x \sim x'$ かつ $y \sim y'$ ならば $x \ast y \sim x' \ast y'$ 」を確かめればよい（グラフ $\lbrace (([x], [y]), [x \ast y]) \mid x, y \in X \rbrace$ について定理 4.11 と同じ議論をする）。

注意

「 $\overline{f}([x]) := f(x)$ と定める」と書いた瞬間に、「 $x \sim x'$ ならば $f(x) = f(x')$ 」を示す義務が生じる。これを怠った「定義」は、写像を定義したことにならない。well-definedness の確認は、代表元を二つとって（ $x \sim x'$ を仮定して）結果が一致することを示す、という形で書く。

例 4.12（ $\mathbb{Z}/n\mathbb{Z}$ の演算） $\mathbb{Z}/n\mathbb{Z}$ に加法と乗法を $[a] + [b] := [a + b]$ 、 $[a][b] := [ab]$ で定める。これは well-defined である。

証明. $a \equiv a'$ 、 $b \equiv b' \pmod{n}$ とし、 $a - a' = nk$ 、 $b - b' = nl$ と書く。 $(a + b) - (a' + b') = n(k + l)$ より $a + b \equiv a' + b'$ 。また

ab - a'b' = a(b - b') + (a - a')b' = n(al + kb')

より $ab \equiv a'b'$ 。 $\square$

たとえば $\mathbb{Z}/12\mathbb{Z}$ （時計の計算）で $[9] + [5] = [14] = [2]$ 、 $\mathbb{Z}/6\mathbb{Z}$ で $[2][3] = [6] = [0]$ である。 $\mathbb{Z}/n\mathbb{Z}$ は代数学の最も基本的な対象の一つになる。

例 4.13（well-defined でない例）

「 $\mathbb{Z}/6\mathbb{Z} \to \mathbb{Z}/4\mathbb{Z}$ 、 $[a]_6 \mapsto [a]_4$ 」は well-defined でない。 $[0]_6 = [6]_6$ だが $[0]_4 \neq [6]_4 = [2]_4$ である。一方「 $\mathbb{Z}/6\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$ 、 $[a]_6 \mapsto [a]_3$ 」は well-defined である。 $6 \mid (a - a')$ ならば $3 \mid (a - a')$ だからである。
$\mathbb{Z}/3\mathbb{Z}$ 上に「 $[a] \leq [b] \iff a \leq b$ 」と関係を定めようとしても、 $0 \leq 1$ だが $[0] = [3]$ で $3 \leq 1$ でないので、関係として定まらない。写像だけでなく関係も well-definedness の確認が必要である。
例 3.3 (5) の「 $m/n \mapsto m + n$ 」も同じ理由で写像にならない。なお、各同値類から「標準的な代表元」（分数なら分母が正の既約分数）を一つ選んで値を決めるやり方もある。これは完全代表系を使って写像を定義していることになり、その場合は well-definedness の問題は起こらない。

例 4.14（有理数の構成）分数 $a/b$ は整数の組 $(a, b)$ で表されるが、 $(1, 2)$ と $(2, 4)$ は同じ数を表す。そこで $X = \mathbb{Z} \times (\mathbb{Z} \setminus \lbrace 0 \rbrace)$ 上に

(a, b) \sim (c, d) \iff ad = bc

と定める。これは同値関係である。反射律（ $ab = ba$ ）と対称律は明らか。推移律： $(a, b) \sim (c, d)$ 、 $(c, d) \sim (e, f)$ とすると $ad = bc$ 、 $cf = de$ である。 $adf = bcf = bde$ より $d(af - be) = 0$ であり、 $d \neq 0$ だから $af = be$ 、すなわち $(a, b) \sim (e, f)$ 。ここで $b, d, f \neq 0$ という条件が本質的に使われている。

$\mathbb{Q} := X/{\sim}$ と定め、 $(a, b)$ の同値類を $a/b$ と書く。加法を $a/b + c/d := (ad + bc)/(bd)$ で定めると（ $b, d \neq 0$ より $bd \neq 0$ ）、これは well-defined である。実際 $(a, b) \sim (a', b')$ 、すなわち $ab' = a'b$ とすると

(ad + bc)(b'd) - (a'd + b'c)(bd) = (ab' - a'b) d^2 = 0

なので $(ad + bc, bd) \sim (a'd + b'c, b'd)$ 。第 2 引数を取り替えても同様である。両方の引数を同時に取り替えるときは、一つずつ取り替えて推移律を使えばよい。乗法 $(a/b)(c/d) := (ac)/(bd)$ の well-definedness は問題 4.5、体としての性質と順序は第7章で扱う。

例 4.15（射影平面） $X = \mathbb{R}^3 \setminus \lbrace 0 \rbrace$ 上に「 $y = \lambda x$ となる $\lambda \in \mathbb{R} \setminus \lbrace 0 \rbrace$ が存在する」とき $x \sim y$ と定める。反射律は $\lambda = 1$ 、対称律は $x = \lambda^{-1} y$ 、推移律は $y = \lambda x$ 、 $z = \mu y$ から $z = (\mu\lambda) x$ （ $\mu\lambda \neq 0$ ）で確かめられる。商集合 $\mathbb{R}P^2 := X/{\sim}$ を実射影平面 (real projective plane) といい、 $(x_0, x_1, x_2)$ の同値類を $[x_0 : x_1 : x_2]$ と書く（同次座標）。 $x$ の同値類は「原点と $x$ を通る直線から原点を除いたもの」なので、 $\mathbb{R}P^2$ の点は原点を通る直線と一対一に対応する。

ここでも well-definedness が問題になる。「 $[x_0 : x_1 : x_2] \mapsto x_0$ 」は $[1 : 0 : 0] = [2 : 0 : 0]$ なので関数として定まらない。しかし条件「 $x_0 = 0$ 」は $\lambda x_0 = 0 \iff x_0 = 0$ なので well-defined であり、関数 $[x_0 : x_1 : x_2] \mapsto x_0^2/(x_0^2 + x_1^2 + x_2^2)$ も $\lambda^2$ が約分されるので well-defined である。射影空間は多様体や代数幾何学の基本的な例である。

4.5 写像の標準分解

どんな写像も、同値関係を使って「全射・全単射・単射」の三つに分解できる。

定理 4.16（写像の標準分解） $f\colon X \to Y$ を写像とし、 $x \sim x' \iff f(x) = f(x')$ で $X$ 上の同値関係 $\sim$ を定める。このとき
$\overline{f}\colon X/{\sim} \to f(X), \qquad [x] \mapsto f(x)$
は well-defined な全単射であり、自然な射影 $\pi\colon X \to X/{\sim}$ と包含写像 $\iota\colon f(X) \to Y$ を用いて $f = \iota \circ \overline{f} \circ \pi$ と分解される。ここで $\pi$ は全射、 $\iota$ は単射である。

\begin{array}{ccc} X & \xrightarrow{f} & Y \\ {\scriptstyle \pi}\downarrow & & \uparrow{\scriptstyle \iota} \\ X/{\sim} & \xrightarrow{\overline{f}} & f(X) \end{array}

証明. $x \sim x'$ なら定義より $f(x) = f(x')$ なので、定理 4.11（ $f$ を $X \to f(X)$ とみなして適用）により $\overline{f}$ は well-defined である。全射： $y \in f(X)$ なら $y = f(x)$ となる $x$ があり、 $\overline{f}([x]) = y$ 。単射： $\overline{f}([x]) = \overline{f}([x'])$ なら $f(x) = f(x')$ 、すなわち $x \sim x'$ なので $[x] = [x']$ 。最後に、各 $x$ で $\iota(\overline{f}(\pi(x))) = f(x)$ である。 $\square$

「 $f$ で区別できない元どうしを同一視すると、 $X$ は $f$ の像と一対一に対応する」というのがこの定理の内容である。これは群論の準同型定理 $G/\operatorname{Ker} f \cong \operatorname{Im} f$ （代数学第2章）や、線形写像についての $V/\operatorname{Ker} f \cong \operatorname{Im} f$ （線形代数第3章）の原型であり、そこでは $\overline{f}$ が演算も保つことを追加で確かめる。

例 4.17 $S^1 := \lbrace (u, v) \in \mathbb{R}^2 \mid u^2 + v^2 = 1 \rbrace$ とし、 $p\colon \mathbb{R} \to \mathbb{R}^2$ 、 $p(t) = (\cos 2\pi t, \sin 2\pi t)$ とする。 $p(\mathbb{R}) = S^1$ であり、三角関数の周期性から $p(t) = p(t') \iff t - t' \in \mathbb{Z}$ である。よって $p$ が定める同値関係は例 4.4 (3) のものであり、標準分解から全単射 $\mathbb{R}/\mathbb{Z} \to S^1$ 、 $[t] \mapsto p(t)$ が得られる。円周は「実数直線を整数だけずらしたものどうし同一視したもの」とみなせる。

4.6 順序

実数の大小関係 $\leq$ から「対称律を捨てて反対称律を課したもの」を抽象化する。

定義 4.18（半順序・全順序）反射律・反対称律・推移律を満たす二項関係 $\leq$ を半順序 (partial order) といい、半順序が与えられた集合 $(X, \leq)$ を半順序集合 (partially ordered set, poset) という。さらに任意の $x, y \in X$ について $x \leq y$ または $y \leq x$ が成り立つとき、 $\leq$ を全順序 (total order)、 $(X, \leq)$ を全順序集合 (totally ordered set) という。半順序集合の部分集合で、その中のどの二元も比較可能なもの（制限した順序が全順序になるもの）を鎖 (chain) という。

$x \leq y$ かつ $x \neq y$ のとき $x < y$ と書き、 $x \leq y$ を $y \geq x$ とも書く。半順序集合の部分集合は、順序を制限して再び半順序集合とみなす。

例 4.19

$(\mathbb{N}, \leq)$ 、 $(\mathbb{Z}, \leq)$ 、 $(\mathbb{Q}, \leq)$ 、 $(\mathbb{R}, \leq)$ は全順序集合である。
$(\mathcal{P}(X), \subset)$ は半順序集合である。 $X$ が異なる二元 $a, b$ をもてば、 $\lbrace a \rbrace$ と $\lbrace b \rbrace$ はどちらも他方に含まれないので全順序ではない。
$(\mathbb{N}, \mid)$ は半順序集合であり（例 4.2）、 $2$ と $3$ が比較不能なので全順序ではない。
$\mathbb{R}^2$ 上の辞書式順序 (lexicographic order)「 $(a, b) \leq (c, d) \iff a < c \lor (a = c \land b \leq d)$ 」は全順序である。一方、成分ごとの順序「 $(a, b) \leq (c, d) \iff a \leq c \land b \leq d$ 」は半順序だが全順序ではない。

定義 4.20（最大元・極大元） $(X, \leq)$ を半順序集合、 $A \subset X$ とする。

$a \in A$ が $A$ の最大元 (maximum) であるとは、 $\forall x \in A,\ x \leq a$ が成り立つことをいう。 $\max A$ と書く。

$a \in A$ が $A$ の極大元 (maximal element) であるとは、 $a < x$ となる $x \in A$ が存在しないこと、すなわち $\forall x \in A,\ (a \leq x \Rightarrow x = a)$ が成り立つことをいう。

最小元 (minimum) $\min A$ と極小元 (minimal element) も不等号を逆にして同様に定める。

最大元は「すべての元以上」、極大元は「それより真に大きい元がない」である。比較できない元がありうる半順序集合では、両者は大きく異なる。

例 4.21 $X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ に割り切る関係 $\mid$ で順序を入れる。 $1$ はすべての元を割り切るので最小元である。 $4, 5, 6$ は $X$ の中に自分以外の倍数をもたないので極大元である。一方、たとえば $4 \nmid 6$ なので、どれも最大元ではなく、最大元は存在しない。同様に $X = \lbrace a, b, c \rbrace$ のとき、 $(\mathcal{P}(X) \setminus \lbrace X \rbrace, \subset)$ の極大元は $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ の三つで、最大元はない。

定理 4.22 $(X, \leq)$ を半順序集合、 $A \subset X$ とする。

$A$ の最大元は、存在すればただ一つである。

$A$ の最大元は $A$ の極大元であり、このとき $A$ の極大元は最大元以外にない。

$\leq$ が全順序ならば、 $a$ が $A$ の極大元であることと最大元であることは同値である。

証明. (1) $a, a'$ がともに最大元なら $a \leq a'$ かつ $a' \leq a$ なので、反対称律より $a = a'$ 。

(2) $a = \max A$ とする。 $a \leq x$ （ $x \in A$ ）なら、 $x \leq a$ でもあるので $x = a$ 。よって $a$ は極大元である。 $b$ を極大元とすると、 $b \leq a$ であり、 $b$ の極大性から $a = b$ 。

(3) (2) より最大元は極大元である。逆に $a$ を極大元とし、 $x \in A$ とする。全順序なので $x \leq a$ または $a \leq x$ であり、後者なら極大性より $x = a$ となって、いずれにせよ $x \leq a$ 。よって $a$ は最大元である。 $\square$

定義 4.23（上界・上限） $(X, \leq)$ を半順序集合、 $A \subset X$ とする。

$u \in X$ が $\forall a \in A,\ a \leq u$ を満たすとき、 $u$ を $A$ の上界 (upper bound) という。上界をもつ $A$ は上に有界 (bounded above) であるという。

$A$ の上界全体の集合に最小元があるとき、それを $A$ の上限 (supremum, least upper bound) といい $\sup A$ と書く。

下界 (lower bound)、下に有界、下限 (infimum) $\inf A$ も同様に定める（下限は下界全体の最大元）。

上界は $A$ の元である必要はなく、 $X$ の元であればよい。 $s = \sup A$ であることは、次の二条件と同値である：(i) $s$ は $A$ の上界である、(ii) $A$ のどの上界 $u$ についても $s \leq u$ である。

例 4.24

$(\mathbb{R}, \leq)$ で $A = (0, 1)$ とすると、上界全体は $[1, \infty)$ で、 $\sup A = 1$ である。 $1 \notin A$ なので $A$ に最大元はない。
$(\mathbb{Q}, \leq)$ で $A = \lbrace x \in \mathbb{Q} \mid x > 0,\ x^2 < 2 \rbrace$ は上に有界（たとえば $2$ が上界）だが、 $\mathbb{Q}$ の中に上限をもたない（第7章）。 $\mathbb{R}$ の中では $\sup A = \sqrt{2}$ である。上に有界な空でない部分集合がつねに上限をもつことこそ、実数を特徴づける性質である（微分積分学第1章）。
$(\mathcal{P}(X), \subset)$ では、任意の $\mathcal{A} \subset \mathcal{P}(X)$ が上限 $\bigcup \mathcal{A}$ をもつ。実際 $\bigcup \mathcal{A}$ は各 $A \in \mathcal{A}$ を含むので上界であり、各 $A$ を含む $U$ は $\bigcup \mathcal{A}$ を含む。同様に $\mathcal{A} \neq \emptyset$ なら下限は $\bigcap \mathcal{A}$ である。
$(\mathbb{N}, \mid)$ では $\sup \lbrace a, b \rbrace$ は最小公倍数、 $\inf \lbrace a, b \rbrace$ は最大公約数である（公倍数がすべて最小公倍数の倍数になることによる。代数学第1章）。
$X = \lbrace a, b, c, d \rbrace$ に、 $a < c$ 、 $a < d$ 、 $b < c$ 、 $b < d$ 以外に（反射律によるもの以外の）関係がない半順序を入れる。 $\lbrace a, b \rbrace$ の上界は $c$ と $d$ だが、この二つは比較できないので上界全体に最小元がなく、上限は存在しない。

定理 4.25 $(X, \leq)$ を半順序集合、 $A \subset X$ とする。

$\sup A$ は、存在すればただ一つである。

$A$ が最大元 $a$ をもてば、 $\sup A = a$ である。

$\sup A$ が存在して $\sup A \in A$ ならば、 $\sup A = \max A$ である。

証明. (1) 上界全体の最小元なので、定理 4.22 (1)（の最小元版）により一意である。(2) $a$ は最大元なので上界である。 $A$ の任意の上界 $u$ について、 $a \in A$ より $a \leq u$ 。よって $a$ は上界全体の最小元である。(3) $s = \sup A$ は上界なので、 $s \in A$ ならば $A$ の最大元である。 $\square$

4.7 整列集合と超限帰納法

自然数の帰納法が使えるのは、 $\mathbb{N}$ の空でない部分集合がつねに最小元をもつからである（第7章で証明する）。この性質だけを抜き出す。

定義 4.26（整列集合）全順序集合 $(W, \leq)$ の空でない任意の部分集合が最小元をもつとき、 $(W, \leq)$ を整列集合 (well-ordered set) といい、 $\leq$ を整列順序 (well-order) という。

例 4.27

$(\mathbb{N}, \leq)$ は整列集合である（整列性、第7章）。有限の全順序集合も整列集合である。
$(\mathbb{Z}, \leq)$ は整列集合でない（ $\mathbb{Z}$ 自身に最小元がない）。 $([0, 1], \leq)$ も整列集合でない（ $(0, 1]$ に最小元がない）。最小元をもつだけでは足りず、すべての空でない部分集合が最小元をもつ必要がある。
$\mathbb{N} \times \mathbb{N}$ に辞書式順序「 $(m, n) \leq (m', n') \iff m < m' \lor (m = m' \land n \leq n')$ 」を入れると整列集合になる（問題 4.8）。並べると $(1,1) < (1,2) < (1,3) < \cdots < (2,1) < (2,2) < \cdots < (3,1) < \cdots$ となる。 $(2, 1)$ の前には無限個の元があり、 $(2, 1)$ の「直前の元」は存在しない。
$\mathbb{N} \cup \lbrace \infty \rbrace$ に、 $\mathbb{N}$ の順序に加えてすべての $n \in \mathbb{N}$ について $n < \infty$ と定めた順序は整列順序である。

例 4.27 (3)(4) のように、整列集合には「直前の元をもたない元」（極限的な元）がありうる。そのため「 $P(x)$ ならば $P(x$ の次 $)$ 」という形の帰納法ではすべての元に届かない。代わりに完全帰納法の形を使う。

定理 4.28（超限帰納法, transfinite induction） $(W, \leq)$ を整列集合、 $P(x)$ を $W$ 上の条件とし、
$\forall x \in W,\ \Bigl[ \bigl( \forall y \in W,\ y < x \Rightarrow P(y) \bigr) \Rightarrow P(x) \Bigr]$
が成り立つとする。このとき、すべての $x \in W$ について $P(x)$ が成り立つ。

証明. 結論が成り立たないと仮定すると、 $S := \lbrace x \in W \mid P(x) \text{ でない} \rbrace$ は空でないので、最小元 $x_0$ をもつ。 $y < x_0$ なる $y \in W$ は、 $x_0$ の最小性から $S$ に属さないので $P(y)$ が成り立つ。すると仮定より $P(x_0)$ が成り立ち、 $x_0 \in S$ に矛盾する。 $\square$

$W = \mathbb{N}$ のとき、これは完全帰納法（定理 1.34）そのものである。

注意 4.29（超限再帰と順序数）整列集合に沿って、各 $x$ での値を「 $x$ より前のすべての値」から決めるという仕方で、ものを帰納的に定義することもできる（超限再帰, transfinite recursion）。その厳密な定式化は、第7章の帰納的定義の定理を一般化したものになる（本教材では扱わない）。また、整列集合を順序を保つ全単射で同一視したときの「型」を表すのが順序数 (ordinal number) である。「任意の集合に整列順序を入れられる」という主張（整列可能定理）は選択公理と同値であり、第6章で扱う。そこでは順序数を使わずに、超限帰納法と同じ考え方でツォルンの補題を証明する。

まとめ

二項関係は $X \times X$ の部分集合であり、反射律・対称律・反対称律・推移律で分類される。
同値関係は反射律・対称律・推移律を満たす関係である。同値類は $X$ を重なりなく覆い、同値関係と分割は一対一に対応する。
商集合 $X/{\sim}$ は同値類全体であり、自然な射影 $\pi\colon X \to X/{\sim}$ は全射である。
商集合上の写像 $\overline{f}([x]) := f(x)$ が定まるための必要十分条件は「 $x \sim x' \Rightarrow f(x) = f(x')$ 」（well-definedness）である。 $\mathbb{Z}/n\mathbb{Z}$ の演算、 $\mathbb{Q}$ の構成、射影平面はその典型例である。
どんな写像も $f = \iota \circ \overline{f} \circ \pi$ （全射・全単射・単射）と標準分解できる。これは準同型定理の原型である。
半順序では最大元と極大元、上界と上限を区別する。最大元は極大元だが逆は一般に成り立たず、全順序なら一致する。
整列集合ではすべての空でない部分集合が最小元をもち、超限帰納法が使える。

演習問題

問題 4.1 ★ 次の関係について、反射律・対称律・反対称律・推移律のそれぞれが成り立つか判定せよ。 (a) $\mathbb{Z}$ 上で $a + b$ が偶数のとき $a \mathrel{R} b$ (b) $\mathbb{Z}$ 上で $ab > 0$ のとき $a \mathrel{R} b$ (c) $\mathcal{P}(\lbrace 1, 2 \rbrace)$ 上で $A \cap B \neq \emptyset$ のとき $A \mathrel{R} B$ (d) $\mathbb{R}$ 上で $x - y \in \mathbb{Q}$ のとき $x \mathrel{R} y$

解答

(a) 反射律 ○（ $2a$ は偶数）、対称律 ○、反対称律 ×（ $0 \mathrel{R} 2$ 、 $2 \mathrel{R} 0$ ）、推移律 ○（ $a + c = (a + b) + (b + c) - 2b$ は偶数）。同値関係である（偶奇が等しい）。 (b) 反射律 ×（ $0 \cdot 0 = 0$ ）、対称律 ○、反対称律 ×（ $1 \mathrel{R} 2$ 、 $2 \mathrel{R} 1$ ）、推移律 ○（ $ab > 0$ 、 $bc > 0$ なら $a, b, c$ はすべて $0$ でなく同符号なので $ac > 0$ ）。 (c) 反射律 ×（ $\emptyset \cap \emptyset = \emptyset$ ）、対称律 ○、反対称律 ×（ $\lbrace 1 \rbrace \mathrel{R} \lbrace 1, 2 \rbrace$ かつ逆も成り立つ）、推移律 ×（ $\lbrace 1 \rbrace \mathrel{R} \lbrace 1, 2 \rbrace$ 、 $\lbrace 1, 2 \rbrace \mathrel{R} \lbrace 2 \rbrace$ だが $\lbrace 1 \rbrace \cap \lbrace 2 \rbrace = \emptyset$ ）。 (d) 反射律・対称律・推移律は例 4.4 (2) と同様（ $\mathbb{Q}$ が加法と $-1$ 倍で閉じていることによる）に成り立ち、反対称律は ×（ $0 \mathrel{R} 1$ 、 $1 \mathrel{R} 0$ ）。同値関係である。

問題 4.2 ★ $X = \mathbb{R}^2 \setminus \lbrace (0, 0) \rbrace$ 上で、 $(x', y') = (tx, ty)$ となる $t > 0$ があるとき $(x, y) \sim (x', y')$ と定める。これが同値関係であることを示し、同値類を図形として述べよ。また単位円周 $S^1$ が完全代表系であることを示せ。

解答

反射律は $t = 1$ 、対称律は $(x, y) = (t^{-1}x', t^{-1}y')$ （ $t^{-1} > 0$ ）、推移律は $t, s > 0$ なら $st > 0$ から従う。 $(x, y)$ の同値類は $\lbrace (tx, ty) \mid t > 0 \rbrace$ 、すなわち原点から $(x, y)$ の方向にのびる半直線（原点を除く）である。

$r := \sqrt{x^2 + y^2} > 0$ とおくと $(x/r, y/r) \in S^1$ かつ $(x, y) \sim (x/r, y/r)$ （ $t = 1/r$ ）なので、各同値類は $S^1$ の元を含む。 $(u, v), (u', v') \in S^1$ が同値なら $(u', v') = (tu, tv)$ 、 $1 = u'^2 + v'^2 = t^2$ 、 $t > 0$ より $t = 1$ なので一致する。よって各同値類は $S^1$ の元をちょうど一つ含む。

問題 4.3 ★ 集合 $\lbrace 1, 2, 3 \rbrace$ 上の同値関係はいくつあるか。すべて（対応する分割の形で）書き出せ。

解答

定理 4.10 より分割の個数を数えればよい。 $\lbrace \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace \rbrace$ 、 $\lbrace \lbrace 1, 2 \rbrace, \lbrace 3 \rbrace \rbrace$ 、 $\lbrace \lbrace 1, 3 \rbrace, \lbrace 2 \rbrace \rbrace$ 、 $\lbrace \lbrace 2, 3 \rbrace, \lbrace 1 \rbrace \rbrace$ 、 $\lbrace \lbrace 1, 2, 3 \rbrace \rbrace$ の $5$ 個である。最初のものは等号 $=$ 、最後のものはすべての組が同値である関係に対応する。

問題 4.4 ★★ 次の「写像」が well-defined かどうか判定せよ。 (a) $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ 、 $[a] \mapsto [a^2 + 1]$ (b) $m, n \in \mathbb{N}$ について $\mathbb{Z}/m\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ 、 $[a]_m \mapsto [a]_n$ （ $m, n$ に関する条件を求めよ） (c) $\mathbb{Q} \to \mathbb{Q}$ 、 $a/b \mapsto (a + 1)/b$ (d) $\mathbb{Q} \to \mathbb{Q}$ 、 $a/b \mapsto a^2/b^2$

解答

(a) well-defined。例 4.12 より $a \equiv a'$ なら $a^2 \equiv a'^2$ 、よって $a^2 + 1 \equiv a'^2 + 1$ 。 (b) well-defined $\iff$ $n \mid m$ 。( $\Leftarrow$ ) $m \mid (a - a')$ なら $n \mid (a - a')$ 。( $\Rightarrow$ ) $[0]_m = [m]_m$ なので $[0]_n = [m]_n$ 、すなわち $n \mid m$ が必要。 (c) well-defined でない。 $1/2 = 2/4$ だが、 $2/2 = 1$ と $3/4$ は異なる。 (d) well-defined。 $(a, b) \sim (a', b')$ なら $ab' = a'b$ で、両辺を 2 乗して $a^2 b'^2 = a'^2 b^2$ 、すなわち $(a^2, b^2) \sim (a'^2, b'^2)$ 。

問題 4.5 ★★ 例 4.14 の $\mathbb{Q}$ で、乗法 $(a/b)(c/d) := (ac)/(bd)$ が well-defined であることを示せ。

解答

$(a, b) \sim (a', b')$ 、すなわち $ab' = a'b$ とする。 $(ac)(b'd) = (ab')cd = (a'b)cd = (a'c)(bd)$ なので $(ac, bd) \sim (a'c, b'd)$ 。第 2 引数についても同様であり、両方を取り替える場合は一つずつ取り替えて推移律を使えばよい。

問題 4.6 ★★ 例 4.8 (2) の $\mathbb{R}/\mathbb{Z}$ について、区間 $[0, 1)$ が完全代表系であることを示せ。ただしアルキメデスの性質と、 $\mathbb{Z}$ の空でない部分集合が上に有界なら最大元をもつことは使ってよい。

解答

$x \in \mathbb{R}$ とする。 $S := \lbrace n \in \mathbb{Z} \mid n \leq x \rbrace$ は、アルキメデスの性質より $-x$ より大きい自然数 $m$ があって $-m \in S$ となるので空でなく、 $x$ で上から押さえられる。よって最大元 $n_0$ がある。 $n_0 \leq x$ かつ $n_0 + 1 > x$ なので $t := x - n_0 \in [0, 1)$ であり、 $x - t \in \mathbb{Z}$ より $x \sim t$ 。一意性： $t, t' \in [0, 1)$ かつ $t - t' \in \mathbb{Z}$ なら $\lvert t - t' \rvert < 1$ より $t - t' = 0$ 。よって各同値類は $[0, 1)$ の元をちょうど一つ含む。

問題 4.7 ★★ 半順序集合 $(\mathbb{N} \setminus \lbrace 1 \rbrace, \mid)$ の極小元は素数であり、極大元は存在しないことを示せ。また $(\lbrace 2, 3, \dots, 10 \rbrace, \mid)$ の極大元と極小元をすべて求めよ。

解答

$p$ が素数なら、 $d \mid p$ となる $d \in \mathbb{N} \setminus \lbrace 1 \rbrace$ は $p$ だけなので $p$ は極小元である。 $n$ が素数でなければ $1 < d < n$ となる約数 $d$ があり、 $d \mid n$ 、 $d \neq n$ なので $n$ は極小元でない。また任意の $n$ について $n \mid 2n$ かつ $2n \neq n$ なので極大元はない。

$\lbrace 2, \dots, 10 \rbrace$ では、極大元は集合内に自分以外の倍数をもたない $6, 7, 8, 9, 10$ 、極小元は集合内に自分以外の約数をもたない $2, 3, 5, 7$ である（ $7$ は両方）。

問題 4.8 ★★ $\mathbb{N} \times \mathbb{N}$ 上の辞書式順序（例 4.27 (3)）が整列順序であることを示せ。

解答

全順序であること：反射律は明らか。反対称律： $(m, n) \leq (m', n')$ かつ $(m', n') \leq (m, n)$ なら、 $m < m'$ と $m' < m$ は両立せず、 $m < m'$ なら第 2 の不等式が成り立たないので $m = m'$ 、すると $n \leq n'$ かつ $n' \leq n$ より $n = n'$ 。推移律：場合分けで確かめられる（第 1 成分で真に小さくなる段があれば全体でも第 1 成分が真に小さく、なければ第 1 成分が等しく第 2 成分で比較される）。比較可能性： $m \neq m'$ なら第 1 成分で、 $m = m'$ なら第 2 成分で比較できる。

最小元の存在： $S \neq \emptyset$ とする。 $\mathbb{N}$ の整列性より $m_0 := \min \lbrace m \mid \exists n,\ (m, n) \in S \rbrace$ 、さらに $n_0 := \min \lbrace n \mid (m_0, n) \in S \rbrace$ がとれる。 $(m, n) \in S$ なら $m \geq m_0$ であり、 $m > m_0$ なら $(m_0, n_0) < (m, n)$ 、 $m = m_0$ なら $n \geq n_0$ なので $(m_0, n_0) \leq (m, n)$ 。よって $(m_0, n_0) = \min S$ 。

問題 4.9 ★★ 半順序集合 $(X, \leq)$ の部分集合 $A \subset B$ がともに上限をもつとき、 $\sup A \leq \sup B$ を示せ。また、 $A$ の上限が存在しても $A$ の部分集合の上限が存在するとは限らないことを、例で示せ。

解答

$\sup B$ は $B$ の上界であり、 $A \subset B$ なので $A$ の上界でもある。 $\sup A$ は $A$ の上界の最小元なので $\sup A \leq \sup B$ 。

例：例 4.24 (5) の $X = \lbrace a, b, c, d \rbrace$ に最大元 $e$ を付け加え（ $a, b, c, d < e$ ）、 $A = X$ とする。 $\sup A = e$ だが、部分集合 $\lbrace a, b \rbrace$ の上界は $c, d, e$ で、 $c$ と $d$ は比較できず、最小の上界がないので上限は存在しない。

問題 4.10 ★★★ (a) 集合 $X$ 上の同値関係の族 $(R_\lambda)_{\lambda \in \Lambda}$ （ $\Lambda \neq \emptyset$ 、各 $R_\lambda \subset X \times X$ ）の共通部分 $\bigcap_\lambda R_\lambda$ は同値関係であることを示せ。 (b) 任意の二項関係 $R \subset X \times X$ に対し、 $R$ を含む最小の同値関係が存在することを示せ（ $R$ が生成する同値関係）。 (c) $X = \mathbb{Z}$ 、 $R = \lbrace (n, n + 2) \mid n \in \mathbb{Z} \rbrace$ のとき、 $R$ が生成する同値関係を求めよ。

解答

(a) 反射律：各 $R_\lambda$ が $(x, x)$ を含むので共通部分も含む。対称律： $(x, y)$ がすべての $R_\lambda$ に属せば $(y, x)$ もすべてに属す。推移律も同様に各 $\lambda$ ごとに確かめればよい。

(b) $R$ を含む同値関係全体を $\mathcal{E}$ とすると、 $X \times X \in \mathcal{E}$ なので $\mathcal{E} \neq \emptyset$ 。(a) より $E := \bigcap \mathcal{E}$ は同値関係で $R$ を含み、 $R$ を含む任意の同値関係に含まれる。

(c) $2$ を法とする合同 $\equiv$ である。 $\equiv$ は同値関係で $R$ を含む（ $(n + 2) - n = 2$ ）ので、生成する同値関係 $E$ は $\equiv$ に含まれる。逆に $a \equiv b$ とし $b = a + 2k$ と書く。 $k \geq 0$ のとき、 $(a, a + 2) \in R \subset E$ と推移律から、 $k$ についての帰納法で $(a, a + 2k) \in E$ がわかる。 $k < 0$ のときは $(b, a) \in E$ に対称律を使う。 $k = 0$ は反射律。よって $\equiv$ は $E$ に含まれ、 $E$ は $\equiv$ に一致する。