順序集合 | 数学の基礎 | 天游ヶ丘数理学院

1 前順序、半順序および全順序

定義 1.1. $P$ を集合、 $\leq$ を $P$ 上の二項関係とする。 $\leq$ が次の二つを満たすとき、 $\leq$ を $P$ 上の前順序 (preorder) という。

任意の $x\in P$ に対して $x\leq x$ が成り立つ（反射律）。
任意の $x,y,z\in P$ に対して、 $x\leq y$ かつ $y\leq z$ ならば $x\leq z$ が成り立つ（推移律）。

前順序 $\leq$ を備えた組 $(P,\leq)$ を前順序集合 (preordered set) という。 $x\leq y$ が成り立たないことを $x\not\leq y$ と書く。 $P$ にも $\leq$ にも制限を置かない。とくに $P$ は空集合でもよい。

定義 1.2. $P$ を集合とする。 $P$ 上の前順序 $\leq$ が反対称律、すなわち「任意の $x,y\in P$ に対して、 $x\leq y$ かつ $y\leq x$ ならば $x=y$ が成り立つ」を満たすとき、 $\leq$ を $P$ 上の半順序 (partial order) という。半順序 $\leq$ を備えた組 $(P,\leq)$ をposet (partially ordered set) という。

半順序は定義により前順序であるから、poset は前順序集合である。

例 1.3.

集合 $X$ に対して、冪集合 $\mathcal P(X)$ に包含関係 $\subseteq$ を入れたものは poset である。反射律と推移律は包含関係の性質であり、反対称律は集合の相等の定義そのものである。
正の整数の全体に整除関係 $\mid$ を入れたものは poset である。各 $a$ は $a=a\cdot1$ から $a\mid a$ を満たし、 $a\mid b$ かつ $b\mid c$ ならば $b=ak$ と $c=bl$ から $c=a(kl)$ となる。また、正の整数 $a,b$ が $a\mid b$ かつ $b\mid a$ を満たすならば $b=ak$ かつ $a=bl$ であり、 $a=akl$ から $kl=1$ 、正の整数の積として $k=l=1$ 、すなわち $a=b$ である。
集合 $X$ の上で $x\leq y$ を $x=y$ によって定めた関係は半順序である。台集合が空集合である場合の唯一の二項関係も半順序である。
整数の全体に整除関係 $\mid$ を入れたものは前順序集合であるが poset ではない。反射律と推移律の確認は正の整数の場合と同じであり、一方で $-2\mid2$ かつ $2\mid-2$ でありながら $-2\neq2$ であるから、反対称律は成り立たない。
集合 $X$ と写像 $f\colon X\to\mathbb Z$ に対して、 $x\preceq y$ を $f(x)\leq f(y)$ によって定めると $\preceq$ は前順序である。 $f(x)=f(y)$ を満たす相異なる $x,y$ が存在すれば、 $x\preceq y$ かつ $y\preceq x$ かつ $x\neq y$ となるので、 $\preceq$ は半順序ではない。

定義 1.4. $(P,\leq)$ を前順序集合とし、 $x,y\in P$ とする。 $x\leq y$ または $y\leq x$ の少なくとも一方が成り立つとき、 $x$ と $y$ は比較可能 (comparable) であるといい、どちらも成り立たないとき比較不能 (incomparable) であるという。

$P$ の任意の二元が比較可能である半順序を $P$ 上の全順序 (total order) といい、全順序 $\leq$ を備えた組 $(P,\leq)$ を全順序集合 (totally ordered set) という。

例 1.5.

整数の全体、有理数の全体および実数の全体は、通常の大小関係について全順序集合である。
$\mathcal P(\{1,2\})$ は包含関係について四つの元 $\emptyset$ 、 $\{1\}$ 、 $\{2\}$ 、 $\{1,2\}$ をもつ poset である。 $\{1\}\not\subseteq\{2\}$ かつ $\{2\}\not\subseteq\{1\}$ であるから $\{1\}$ と $\{2\}$ は比較不能であり、この poset は全順序集合ではない。
集合 $X$ と poset $(Q,\leq_Q)$ に対して、 $X$ から $Q$ への写像の全体を考え、すべての $x\in X$ について $f(x)\leq_Qg(x)$ が成り立つときに $f\preceq g$ と定めると、 $\preceq$ は半順序である。反射律と推移律は各点で $\leq_Q$ の反射律と推移律を用い、反対称律は $f\preceq g$ かつ $g\preceq f$ から各点で $f(x)=g(x)$ を得て、写像の相等によって $f=g$ を得る。 $X$ が相異なる二元 $x_1,x_2$ をもち、 $Q$ が $q_1\leq_Qq_2$ かつ $q_1\neq q_2$ を満たす二元をもつならば、 $f(x_1)=q_1$ 、 $f(x_2)=q_2$ 、 $g(x_1)=q_2$ 、 $g(x_2)=q_1$ とし、 $x_1$ とも $x_2$ とも異なる $x$ については $f(x)=g(x)=q_1$ とした $f$ と $g$ は比較不能であるから、 $\preceq$ は全順序ではない。

定義 1.6. $(X,\leq)$ を poset とする。 $x,y\in X$ に対して、 $x\leq y$ かつ $x\neq y$ が成り立つときに $x<y$ と定め、 $<$ を $\leq$ に付随する狭義順序 (strict order) という。 $y>x$ は $x<y$ と同じ意味である。 $\leq$ が全順序であるとき、 $<$ を狭義全順序 (strict total order) という。

命題 1.7. $(X,\leq)$ を poset とし、 $<$ を $\leq$ に付随する狭義順序とする。

任意の $x\in X$ に対して、 $x<x$ は成り立たない。
$x<y$ かつ $y<z$ ならば $x<z$ である。
$\leq$ が $X$ 上の全順序であることと、相異なる任意の二元 $x,y\in X$ に対して $x<y$ または $y<x$ が成り立つこととは同値である。

証明. $x<x$ は $x\neq x$ を含むので、(1)が成り立つ。

$x<y$ かつ $y<z$ とすると、 $x\leq y$ と $y\leq z$ から推移律により $x\leq z$ である。ここで $x=z$ と仮定すると、 $y\leq z=x$ と $x\leq y$ から反対称律により $x=y$ となり、 $x<y$ に含まれる $x\neq y$ に反する。よって $x\neq z$ であり、 $x<z$ が成り立つ。

(3)の必要性を示す。 $\leq$ を全順序とし、 $x\neq y$ とする。 $x$ と $y$ は比較可能であるから $x\leq y$ または $y\leq x$ が成り立ち、 $x\neq y$ とあわせて $x<y$ または $y<x$ を得る。十分性を示す。相異なる任意の二元が $<$ について一方向に結ばれているとする。 $x,y\in X$ を取り、 $x=y$ ならば反射律により $x\leq y$ である。 $x\neq y$ ならば $x<y$ または $y<x$ であり、いずれの場合も $x\leq y$ または $y\leq x$ が成り立つ。よって任意の二元が比較可能であり、 $\leq$ は全順序である。▨

系 1.8. $(X,\leq)$ を全順序集合とし、 $<$ を $\leq$ に付随する狭義順序とする。任意の $x,y\in X$ に対して、 $x<y$ 、 $x=y$ 、 $y<x$ のちょうど一つが成り立つ。

証明. $x=y$ ならば、 $x<y$ と $y<x$ はいずれも $x\neq y$ を含むので成り立たない。 $x\neq y$ ならば、命題 1.7 (3)により $x<y$ または $y<x$ が成り立ち、 $x=y$ は成り立たない。最後に $x<y$ と $y<x$ が同時に成り立つと仮定すると、命題 1.7 (2)により $x<x$ となり命題 1.7 (1)に反する。よって三つのうち少なくとも一つが成り立ち、二つ以上が同時に成り立つことはない。▨

狭義順序を取る操作は、半順序のもつ情報を失わせない。

命題 1.9. $X$ を集合とする。

$\leq$ が $X$ 上の半順序ならば、付随する狭義順序 $<$ は非反射的かつ推移的である。
$R$ が $X$ 上の非反射的かつ推移的な二項関係ならば、 $xRy$ または $x=y$ が成り立つときに $x\leq y$ と定めた関係 $\leq$ は $X$ 上の半順序であり、 $\leq$ に付随する狭義順序は $R$ に一致する。
二つの構成は互いに逆である。すなわち、半順序 $\leq$ から $<$ を作り、 $<$ から(2)の規則で関係を作り直すと $\leq$ に戻る。
(2)で得られる $\leq$ が全順序であることと、相異なる任意の二元 $x,y\in X$ に対して $xRy$ または $yRx$ が成り立つこととは同値である。

証明.(1)は命題 1.7 (1)と命題 1.7 (2)である。

$R$ を非反射的かつ推移的な関係とし、 $xRy$ または $x=y$ が成り立つときに $x\leq y$ と定める。反射律は定義の第二の場合から従う。反対称律について、 $x\leq y$ かつ $y\leq x$ であって $x\neq y$ と仮定すると $xRy$ かつ $yRx$ であり、推移性により $xRx$ となって非反射性に反する。よって $x=y$ である。推移律について、 $x\leq y$ かつ $y\leq z$ とする。 $x=y$ ならば $y\leq z$ がそのまま $x\leq z$ を与え、 $y=z$ ならば $x\leq y$ がそのまま $x\leq z$ を与える。 $x\neq y$ かつ $y\neq z$ ならば $xRy$ かつ $yRz$ であり、推移性により $xRz$ 、したがって $x\leq z$ である。よって $\leq$ は半順序である。付随する狭義順序については、 $xRy$ ならば非反射性により $x\neq y$ であるから $x\leq y$ かつ $x\neq y$ であり、逆に $x\leq y$ かつ $x\neq y$ ならば定義の第一の場合が起こって $xRy$ である。よって(2)が成り立つ。

$\leq$ を半順序、 $<$ を付随する狭義順序とし、 $x<y$ または $x=y$ が成り立つときに $x\leq'y$ と定める。 $x<y$ は $x\leq y$ を含み、 $x=y$ のときは反射律により $x\leq y$ であるから、 $x\leq'y$ ならば $x\leq y$ である。逆に $x\leq y$ とすると、 $x=y$ であるか、または $x\neq y$ であって $x<y$ であるから、 $x\leq'y$ である。よって $\leq'$ は $\leq$ に一致し、(3)が成り立つ。

(4)は、(2)により $R$ が $\leq$ に付随する狭義順序であることと、命題 1.7 (3)を $\leq$ へ適用することから従う。▨

2 上界と下界、上限と下限および鎖

定義 2.1. $(P,\leq)$ を前順序集合、 $T$ を $P$ の部分集合とする。 $T$ には空でないことも有限であることも課さない。

$u\in P$ が $T$ の上界 (upper bound) であるとは、すべての $t\in T$ について $t\leq u$ が成り立つことである。 $T$ の上界の全体を $T$ の上界全体 (set of upper bounds) という。
$l\in P$ が $T$ の下界 (lower bound) であるとは、すべての $t\in T$ について $l\leq t$ が成り立つことである。 $T$ の下界の全体を $T$ の下界全体 (set of lower bounds) という。
$T$ が上界をもつとき $T$ は上に有界 (bounded above) であるといい、 $T$ が下界をもつとき $T$ は下に有界 (bounded below) であるという。
$s\in P$ が $T$ の上限 (supremum) であるとは、 $s$ が $T$ の上界であり、かつ $T$ の任意の上界 $u$ について $s\leq u$ が成り立つことである。
$m\in P$ が $T$ の下限 (infimum) であるとは、 $m$ が $T$ の下界であり、かつ $T$ の任意の下界 $x$ について $x\leq m$ が成り立つことである。

上限と下限は、 $P$ の元がもつ性質として定める。すなわち「 $s$ は $T$ の上限である」は $s$ についての条件であり、記号によって $P$ の特定の元を指すものではない。

注意 2.2. 前順序集合では、一つの部分集合が相異なる上限をもつ場合がある。 $P=\{a,b\}$ とし、 $\leq$ を四つの組すべてが成り立つ関係、すなわち $P\times P$ とする。反射律と推移律はこの関係について成り立つので $\leq$ は前順序である。 $T=\{a\}$ とすると、 $a\leq a$ かつ $a\leq b$ であるから $a$ と $b$ はともに $T$ の上界であり、 $a\leq b$ と $b\leq a$ からどちらも他方以下である。したがって $a$ と $b$ はいずれも $T$ の上限である。 $a\neq b$ であるから、上限は一意ではない。この $\leq$ は $a\leq b$ かつ $b\leq a$ かつ $a\neq b$ を満たすので、半順序ではない。

命題 2.3. $(P,\leq)$ を poset、 $T$ を $P$ の部分集合とする。 $T$ の上限は、存在すれば一意である。 $T$ の下限も、存在すれば一意である。

証明. $s$ と $s'$ をともに $T$ の上限とする。 $s'$ は $T$ の上界であり $s$ は $T$ の任意の上界以下であるから $s\leq s'$ であり、 $s$ と $s'$ の役割を入れ替えると $s'\leq s$ である。反対称律により $s=s'$ である。

$m$ と $m'$ をともに $T$ の下限とする。 $m'$ は $T$ の下界であり $T$ の任意の下界は $m$ 以下であるから $m'\leq m$ であり、役割を入れ替えると $m\leq m'$ である。反対称律により $m=m'$ である。▨

定義 2.4. $(P,\leq)$ を poset とする。

$C\subseteq P$ が $P$ の鎖 (chain) であるとは、 $C$ の任意の二元が比較可能であることである。この条件は $C$ が空集合である場合にも、 $C$ が一元集合である場合にも満たされる。
$u\in P$ が $C$ の上界であるとは、すべての $c\in C$ について $c\leq u$ が成り立つことである。
$m\in P$ が $P$ の極大元 (maximal element) であるとは、 $m<x$ を満たす $x\in P$ が存在しないことである。 $m\in P$ が $P$ の極小元 (minimal element) であるとは、 $x<m$ を満たす $x\in P$ が存在しないことである。
$T$ を $P$ の部分集合とする。 $g\in T$ が $T$ の最大元 (greatest element) であるとは、すべての $x\in T$ について $x\leq g$ が成り立つことである。 $b\in T$ が $T$ の最小元 (least element) であるとは、すべての $x\in T$ について $b\leq x$ が成り立つことである。 $T=P$ の場合の $g$ と $b$ を、それぞれ $P$ の最大元、 $P$ の最小元という。

鎖の上界について課した条件は、部分集合の上界について定義 2.1が置いた条件と同じ形であり、反対称律を用いない。

命題 2.5. $(P,\leq)$ を poset とする。

$P$ の最大元は、存在すれば一意である。 $P$ の最小元も、存在すれば一意である。
$P$ の最大元は極大元であり、 $P$ の最小元は極小元である。
$P$ が最大元 $g$ をもつならば、 $P$ の極大元は $g$ だけである。

証明. $g$ と $g'$ をともに $P$ の最大元とすると、 $g'$ が最大元であることから $g\leq g'$ であり、 $g$ が最大元であることから $g'\leq g$ である。反対称律により $g=g'$ である。最小元についても不等号の向きを入れ替えて同じ議論が成り立つ。

$g$ を $P$ の最大元とし、 $g<x$ を満たす $x\in P$ があると仮定する。 $g$ は最大元であるから $x\leq g$ であり、 $g<x$ に含まれる $g\leq x$ とあわせて反対称律から $g=x$ となるが、これは $g<x$ に含まれる $g\neq x$ に反する。よってそのような $x$ は存在せず、 $g$ は極大元である。最小元についても同様である。

$P$ が最大元 $g$ をもつとし、 $m$ を $P$ の極大元とする。 $g$ が最大元であることから $m\leq g$ である。 $m\neq g$ とすると $m<g$ となり、 $m$ が極大元であることに反する。よって $m=g$ であり、(2)とあわせて $P$ の極大元は $g$ だけである。▨

命題 2.6. 空集合の上界と下界について、次が成り立つ。

$(P,\leq)$ を前順序集合とすると、 $P$ のすべての元は空集合の上界であり、かつ空集合の下界である。
$(P,\leq)$ を poset とすると、 $s\in P$ が空集合の上限であることと $s$ が $P$ の最小元であることとは同値であり、 $m\in P$ が空集合の下限であることと $m$ が $P$ の最大元であることとは同値である。

証明. 上界の条件「すべての $t\in\emptyset$ について $t\leq u$ が成り立つ」は、 $\emptyset$ が元をもたないので、 $u\in P$ の取り方によらず成り立つ。下界の条件についても同様である。よって(1)が成り立つ。

$(P,\leq)$ を poset とする。(1)により空集合の上界全体は $P$ である。したがって「 $s$ が空集合の上限である」は「 $s\in P$ であり、 $P$ の任意の元 $u$ について $s\leq u$ が成り立つ」に等しく、これは $s$ が $P$ の最小元であることにほかならない。下限についても、空集合の下界全体が $P$ であることから同じ議論が成り立つ。▨

空集合が鎖であることと命題 2.6をあわせると、 $P$ が元をもつ限り空の鎖はつねに上界をもつ。「 $P$ のすべての鎖が上界をもつ」という条件を検査するときにこの場合を落とさないことが、「選択公理と Zorn の補題」で Zorn の補題を適用する際の第一段になる。

例 2.7. $a$ と $b$ を相異なる二元とし、 $P=\{a,b\}$ 、 $\leq$ を相等関係、すなわち $a\leq a$ と $b\leq b$ だけが成り立つ関係とする。これは相等関係であるから例 1.3により半順序である。 $a<x$ を満たす $x\in P$ は存在せず、 $b<x$ を満たす $x\in P$ も存在しないから、 $a$ と $b$ はいずれも極大元であり、同じ理由でいずれも極小元である。一方、 $b\leq a$ が成り立たないので $a$ は最大元ではなく、 $a\leq b$ が成り立たないので $b$ も最大元ではない。したがって $P$ は最大元をもたず、極大元を二つもつ。

$a$ と $b$ は比較不能であるから $\{a,b\}$ は鎖ではなく、 $P$ の鎖は $\emptyset$ 、 $\{a\}$ 、 $\{b\}$ の三つである。 $\emptyset$ の上界は命題 2.6 (1)により $a$ と $b$ の両方であり、 $\{a\}$ の上界は $a$ だけ、 $\{b\}$ の上界は $b$ だけである。よって $P$ のすべての鎖が上界をもつ。

例 2.8.

集合 $X$ に対して、 $(\mathcal P(X),\subseteq)$ と部分族 $\mathcal A\subseteq\mathcal P(X)$ を考える。 $\mathcal A$ の各元は $\bigcup\mathcal A$ に含まれ、 $\mathcal A$ のすべての元を含む $X$ の部分集合は $\bigcup\mathcal A$ を含むから、 $\bigcup\mathcal A$ は $\mathcal A$ の上限である。 $\mathcal A$ が空でないとき、 $\bigcap\mathcal A$ は $\mathcal A$ の各元に含まれ、 $\mathcal A$ のすべての元に含まれる部分集合は $\bigcap\mathcal A$ に含まれるから、 $\bigcap\mathcal A$ は $\mathcal A$ の下限である。 $\mathcal A$ が空のときは、命題 2.6 (2)により上限が $\emptyset$ 、下限が $X$ である。
正の整数の全体に整除関係を入れた poset（例 1.3）において、 $\{4,6\}$ の下限は $2$ であり、上限は $12$ である。実際、 $4$ の正の約数は $1,2,4$ 、 $6$ の正の約数は $1,2,3,6$ であるから、 $\{4,6\}$ の下界は $1$ と $2$ であり、 $1\mid2$ であるから $2$ が下限である。また、 $m$ を $4$ と $6$ の公倍数とし、 $m$ を $12$ で割った余りを $r$ とすると、 $r=m-12q$ は $4$ の倍数かつ $6$ の倍数であり $0\leq r<12$ を満たす。 $0<r<12$ を満たす $4$ の倍数は $4$ と $8$ だけであり、どちらも $6$ の倍数ではないから $r=0$ 、すなわち $12\mid m$ である。 $12$ 自身は $4$ と $6$ の公倍数であるから、 $12$ が上限である。この $2$ と $12$ は、 $4$ と $6$ の最大公約数と最小公倍数にほかならない。
上に有界であっても上限をもたない部分集合が存在する。 $P=\{a,b,c,d\}$ に、四つの反射的な関係と $a\leq c$ 、 $a\leq d$ 、 $b\leq c$ 、 $b\leq d$ だけが成り立つ関係を入れる。相異なる二元を二段つなぐ組が無いので推移律が成り立ち、相異なる二元の間に双方向の関係が無いので反対称律が成り立つ。 $T=\{a,b\}$ の上界は $c$ と $d$ である。 $c\leq d$ も $d\leq c$ も成り立たないので、 $c$ も $d$ も $T$ のすべての上界以下ではない。よって $T$ は上に有界であるが上限をもたない。

3 上方集合と下方集合

定義 3.1. $(P,\leq)$ を前順序集合、 $A$ を $P$ の部分集合とする。 $a\in A$ と $x\in P$ が $a\leq x$ を満たすとき必ず $x\in A$ となるならば、 $A$ を $P$ の上方集合 (upper set) という。 $a\in A$ と $x\in P$ が $x\leq a$ を満たすとき必ず $x\in A$ となるならば、 $A$ を $P$ の下方集合 (lower set) という。

命題 3.2. $(P,\leq)$ を前順序集合とする。

$A\subseteq P$ が上方集合であることと、 $P\setminus A$ が下方集合であることとは同値である。
上方集合からなる任意の族について、その和集合は上方集合である。族が空でなければ共通部分も上方集合である。下方集合についても同じことが成り立つ。
各 $p\in P$ に対して、 $\{x\in P\mid p\leq x\}$ は上方集合であり、 $\{x\in P\mid x\leq p\}$ は下方集合である。
各 $p,q\in P$ に対して、 $p\leq q$ であることと $\{x\in P\mid x\leq p\}\subseteq\{x\in P\mid x\leq q\}$ が成り立つこととは同値である。

証明. $A$ を上方集合とし、 $a\in P\setminus A$ と $x\leq a$ を取る。 $x\in A$ と仮定すると、 $A$ が上方集合であって $x\leq a$ であるから $a\in A$ となり、 $a\in P\setminus A$ に反する。よって $x\in P\setminus A$ であり、 $P\setminus A$ は下方集合である。逆に $P\setminus A$ を下方集合とし、 $a\in A$ と $a\leq x$ を取る。 $x\in P\setminus A$ と仮定すると、 $P\setminus A$ が下方集合であって $a\leq x$ であるから $a\in P\setminus A$ となり、 $a\in A$ に反する。よって $x\in A$ である。以上により(1)が成り立つ。

$(A_i)_{i\in I}$ を上方集合の族とする。 $a\in\bigcup_{i\in I}A_i$ と $a\leq x$ を取ると、 $a\in A_i$ を満たす $i$ があり、 $A_i$ が上方集合であるから $x\in A_i\subseteq\bigcup_{i\in I}A_i$ である。 $I$ が空でないとし、 $a\in\bigcap_{i\in I}A_i$ と $a\leq x$ を取ると、各 $i$ について $a\in A_i$ かつ $A_i$ が上方集合であるから $x\in A_i$ であり、 $x\in\bigcap_{i\in I}A_i$ である。下方集合については不等号の向きを入れ替えて同じ議論が成り立つ。

$p\leq a$ かつ $a\leq x$ ならば推移律により $p\leq x$ であるから、 $\{x\in P\mid p\leq x\}$ は上方集合である。 $a\leq p$ かつ $x\leq a$ ならば推移律により $x\leq p$ であるから、 $\{x\in P\mid x\leq p\}$ は下方集合である。

$p\leq q$ とし、 $x\leq p$ を取ると推移律により $x\leq q$ であるから、 $\{x\in P\mid x\leq p\}\subseteq\{x\in P\mid x\leq q\}$ である。逆にこの包含が成り立つとすると、反射律により $p$ は左辺に属するので $p$ は右辺に属し、 $p\leq q$ である。▨

上方集合と下方集合は、順序の向きを反転する操作によって互いに移り合う。

定義 3.3. $(P,\leq)$ を前順序集合とする。 $P$ 上の二項関係 $\leq^{\mathrm{op}}$ を

x\leq^{\mathrm{op}}y\iff y\leq x

によって定め、 $\leq^{\mathrm{op}}$ を $\leq$ の双対順序 (dual order) という。台集合 $P$ に $\leq^{\mathrm{op}}$ を備えた組を $P^{\mathrm{op}}$ と書く。

$\leq$ が半順序であるとき、付随する狭義順序 $<$ に対しても同じ規則で

x<^{\mathrm{op}}y\iff y<x

と定め、 $<^{\mathrm{op}}$ を $<$ の双対順序という。

命題 3.4. $(P,\leq)$ を前順序集合とする。

$\leq^{\mathrm{op}}$ は $P$ 上の前順序である。 $\leq$ が半順序ならば $\leq^{\mathrm{op}}$ は半順序であり、 $\leq$ が全順序ならば $\leq^{\mathrm{op}}$ は全順序である。
$(\leq^{\mathrm{op}})^{\mathrm{op}}$ は $\leq$ に一致する。
$\leq$ が半順序であるとき、 $\leq^{\mathrm{op}}$ に付随する狭義順序は $<^{\mathrm{op}}$ に一致する。

証明. 反射律について、 $x\leq x$ は $x\leq^{\mathrm{op}}x$ と同じ条件である。推移律について、 $x\leq^{\mathrm{op}}y$ かつ $y\leq^{\mathrm{op}}z$ は $y\leq x$ かつ $z\leq y$ であり、 $\leq$ の推移律により $z\leq x$ 、すなわち $x\leq^{\mathrm{op}}z$ である。よって $\leq^{\mathrm{op}}$ は前順序である。反対称律について、 $x\leq^{\mathrm{op}}y$ かつ $y\leq^{\mathrm{op}}x$ は $y\leq x$ かつ $x\leq y$ であるから、 $\leq$ が反対称律を満たせば $x=y$ である。比較可能性について、 $x\leq y$ または $y\leq x$ が成り立つことは、 $y\leq^{\mathrm{op}}x$ または $x\leq^{\mathrm{op}}y$ が成り立つことと同じ条件である。よって(1)が成り立つ。

$x$ と $y$ が $(\leq^{\mathrm{op}})^{\mathrm{op}}$ で結ばれることは $y\leq^{\mathrm{op}}x$ であり、これは $x\leq y$ である。よって(2)が成り立つ。

$\leq$ を半順序とする。(1)により $\leq^{\mathrm{op}}$ は半順序であり、それに付随する狭義順序は「 $x\leq^{\mathrm{op}}y$ かつ $x\neq y$ 」、すなわち「 $y\leq x$ かつ $y\neq x$ 」である。これは $y<x$ 、すなわち $x<^{\mathrm{op}}y$ にほかならない。▨

注意 3.5. $(P,\leq)$ を poset とする。 $P$ から $P^{\mathrm{op}}$ へ移ると、次の五つの対がそれぞれ交換される。

部分集合 $T$ の上界と下界。
$P$ の最大元と最小元。
$P$ の極大元と極小元。
部分集合 $T$ の上限と下限。
$P$ の上方集合と下方集合。

いずれの対についても、片方の条件は他方の条件で $\leq$ を $\leq^{\mathrm{op}}$ へ置き換えたものである。たとえば「すべての $t\in T$ について $t\leq u$ が成り立つ」は「すべての $t\in T$ について $u\leq^{\mathrm{op}}t$ が成り立つ」と同じ条件であるから、 $u$ が $(P,\leq)$ における $T$ の上界であることと、 $u$ が $P^{\mathrm{op}}$ における $T$ の下界であることとは同値である。残りの四対も同じ置き換えによって得られる。

4 順序を保つ写像と順序埋め込み

定義 4.1. $(P,\leq_P)$ と $(Q,\leq_Q)$ を前順序集合、 $f\colon P\to Q$ を写像とする。

すべての $x,y\in P$ について、 $x\leq_Py$ ならば $f(x)\leq_Qf(y)$ が成り立つとき、 $f$ を順序を保つ写像 (order-preserving map)、または単調写像 (monotone map) という。
すべての $x,y\in P$ について、 $x\leq_Py$ であることと $f(x)\leq_Qf(y)$ が成り立つこととが同値であるとき、 $f$ を順序埋め込み (order embedding) という。

定義 4.2. $(P,\leq_P)$ と $(Q,\leq_Q)$ を前順序集合とする。全単射 $f\colon P\to Q$ であって、 $f$ と逆写像 $f^{-1}$ がともに順序を保つものを順序同型 (order isomorphism) という。 $P$ から $Q$ への順序同型が存在するとき、 $P$ と $Q$ は順序同型であるという。

命題 4.3. $(P,\leq_P)$ 、 $(Q,\leq_Q)$ および $(R,\leq_R)$ を前順序集合とする。

恒等写像は順序を保ち、順序を保つ写像 $f\colon P\to Q$ と $g\colon Q\to R$ の合成 $g\circ f$ は順序を保つ。また、順序埋め込みの合成は順序埋め込みである。
順序埋め込みは順序を保つ写像である。 $P$ が poset であるとき、順序埋め込みは単射である。
全単射 $f\colon P\to Q$ について、 $f$ が順序同型であることと $f$ が順序埋め込みであることとは同値である。
$f\colon P\to Q$ を順序を保つ写像、 $T$ を $P$ の部分集合とする。 $u$ が $T$ の上界であるならば、 $f(u)$ は像 $f(T)$ の上界である。

証明. $x\leq_Py$ ならば $x\leq_Py$ であるから、恒等写像は順序を保つ。 $f$ と $g$ を順序を保つ写像とし $x\leq_Py$ とすると、 $f(x)\leq_Qf(y)$ であり、さらに $g(f(x))\leq_Rg(f(y))$ である。 $f$ と $g$ が順序埋め込みならば、 $x\leq_Py$ と $f(x)\leq_Qf(y)$ が同値であり、 $f(x)\leq_Qf(y)$ と $g(f(x))\leq_Rg(f(y))$ が同値であるから、 $x\leq_Py$ と $(g\circ f)(x)\leq_R(g\circ f)(y)$ は同値である。

順序埋め込みの条件の一方向が、順序を保つ条件そのものである。 $P$ を poset とし、 $f$ を順序埋め込み、 $f(x)=f(y)$ とする。 $f(x)\leq_Qf(y)$ と $f(y)\leq_Qf(x)$ がともに成り立つので、 $x\leq_Py$ と $y\leq_Px$ を得る。反対称律により $x=y$ であるから、 $f$ は単射である。

$f$ を全単射とする。 $f$ が順序同型であるとする。 $x\leq_Py$ ならば $f(x)\leq_Qf(y)$ である。逆に $f(x)\leq_Qf(y)$ とすると、 $f^{-1}$ が順序を保つことから $f^{-1}(f(x))\leq_Pf^{-1}(f(y))$ 、すなわち $x\leq_Py$ である。よって $f$ は順序埋め込みである。次に $f$ が順序埋め込みであるとする。 $f$ は順序を保つ。 $v\leq_Qw$ を取り、 $x=f^{-1}(v)$ 、 $y=f^{-1}(w)$ とおくと $f(x)\leq_Qf(y)$ であるから $x\leq_Py$ 、すなわち $f^{-1}(v)\leq_Pf^{-1}(w)$ である。よって $f^{-1}$ も順序を保ち、 $f$ は順序同型である。

$u$ を $T$ の上界とし、 $f(t)\in f(T)$ を取る。 $t\leq_Pu$ であるから $f(t)\leq_Qf(u)$ であり、 $f(u)$ は $f(T)$ の上界である。▨

例 4.4. 順序を保つ全単射が順序同型であるとは限らない。 $a$ と $b$ を相異なる二元とし、 $P=\{a,b\}$ に相等関係を入れ、 $Q=\{0,1\}$ に通常の全順序を入れる。 $f\colon P\to Q$ を $f(a)=0$ 、 $f(b)=1$ によって定めると、 $f$ は全単射である。 $P$ において $x\leq y$ が成り立つのは $x=y$ の場合だけであり、そのときは $f(x)=f(y)$ から $f(x)\leq f(y)$ であるから、 $f$ は順序を保つ。一方、 $f^{-1}(0)=a$ と $f^{-1}(1)=b$ について、 $0\leq1$ でありながら $a\leq b$ は成り立たないので、 $f^{-1}$ は順序を保たない。よって $f$ は順序同型ではなく、命題 4.3 (3)により順序埋め込みでもない。

例 4.5. $(P,\leq)$ を poset とし、 $\eta\colon P\to\mathcal P(P)$ を

\eta(p)=\{x\in P\mid x\leq p\}

によって定める。命題 3.2 (4)により $p\leq q$ と $\eta(p)\subseteq\eta(q)$ は同値であるから、 $\eta$ は $(\mathcal P(P),\subseteq)$ への順序埋め込みであり、命題 4.3 (2)により単射である。すなわち、任意の poset は自身の冪集合の poset へ順序埋め込みされる。「Dedekind–MacNeille 完備化」は、この埋め込みの像を下方集合の中で広げることによって、任意の poset を完備束の中へ収める。

例 4.6.命題 4.3 (4)は上界が像の上界へ移ることを述べるが、順序を保つ写像が上限を上限へ移すとは限らない。 $a$ 、 $b$ および $c$ を相異なる三元とし、 $P=\{a,b,c\}$ に、三つの反射的な関係と $a\leq c$ 、 $b\leq c$ だけが成り立つ関係を入れる。相異なる二元を二段つなぐ組が無いので推移律が成り立ち、相異なる二元の間に双方向の関係が無いので反対称律が成り立つ。 $T=\{a,b\}$ の上界は $c$ だけであるから、 $T$ の上限は $c$ である。

この $P$ について例 4.5の $\eta$ を考えると、 $\eta(a)=\{a\}$ 、 $\eta(b)=\{b\}$ 、 $\eta(c)=\{a,b,c\}$ である。例 2.8により $(\mathcal P(P),\subseteq)$ における $\eta(T)=\{\{a\},\{b\}\}$ の上限は $\{a\}\cup\{b\}=\{a,b\}$ であり、これは $\eta(c)$ とは異なる。よって $\eta$ は順序埋め込みでありながら、 $T$ の上限を $\eta(T)$ の上限へ移さない。

5 積順序、辞書式順序および整列順序

有限直積は「集合族」が定めた。以下では、直積 $X_1\times\cdots\times X_n$ （§E1.2 定義 1.3）の元を $x=(x_1,\dots,x_n)$ の形に書く。組の相等は成分ごとの相等である。

定義 5.1. $n$ を正の整数とし、 $(X_1,\leq_1),\dots,(X_n,\leq_n)$ を前順序集合とする。 $X_1\times\cdots\times X_n$ 上の二項関係 $\leq_{\mathrm{prod}}$ を、すべての $i\in\{1,\dots,n\}$ について $x_i\leq_iy_i$ が成り立つときに $x\leq_{\mathrm{prod}}y$ と定め、 $\leq_{\mathrm{prod}}$ を積順序 (product order) という。

命題 5.2. $n$ を正の整数とし、 $(X_1,\leq_1),\dots,(X_n,\leq_n)$ を前順序集合とする。

$\leq_{\mathrm{prod}}$ は $X_1\times\cdots\times X_n$ 上の前順序である。各 $\leq_i$ が半順序ならば $\leq_{\mathrm{prod}}$ は半順序である。
$n\geq2$ であり、 $X_1$ と $X_2$ がそれぞれ相異なる二元をもつ全順序集合であり、さらに $3\leq i\leq n$ を満たす各 $i$ について $X_i$ が空でないならば、 $\leq_{\mathrm{prod}}$ は全順序ではない。

証明. 各 $i$ について $x_i\leq_ix_i$ であるから $x\leq_{\mathrm{prod}}x$ である。 $x\leq_{\mathrm{prod}}y$ かつ $y\leq_{\mathrm{prod}}z$ ならば、各 $i$ について $x_i\leq_iy_i$ かつ $y_i\leq_iz_i$ であり、 $\leq_i$ の推移律により $x_i\leq_iz_i$ であるから $x\leq_{\mathrm{prod}}z$ である。各 $\leq_i$ が反対称律を満たすとし、 $x\leq_{\mathrm{prod}}y$ かつ $y\leq_{\mathrm{prod}}x$ とすると、各 $i$ について $x_i\leq_iy_i$ かつ $y_i\leq_ix_i$ であるから $x_i=y_i$ であり、組の相等が成分ごとの相等であることから $x=y$ である。

$n\geq2$ とする。 $X_1$ と $X_2$ は全順序集合であって相異なる二元をもつので、命題 1.7 (3)により $a_1<_1b_1$ を満たす $a_1,b_1\in X_1$ と $a_2<_2b_2$ を満たす $a_2,b_2\in X_2$ が存在する。 $3\leq i\leq n$ については、 $X_i$ が空でないので、その元 $c_i$ を一つずつ取ることができる。 $x=(a_1,b_2,c_3,\dots,c_n)$ 、 $y=(b_1,a_2,c_3,\dots,c_n)$ とおくと、第 $2$ 成分について $b_2\leq_2a_2$ が成り立たないので $x\leq_{\mathrm{prod}}y$ ではなく、第 $1$ 成分について $b_1\leq_1a_1$ が成り立たないので $y\leq_{\mathrm{prod}}x$ でもない。よって $x$ と $y$ は比較不能であり、 $\leq_{\mathrm{prod}}$ は全順序ではない。▨

積順序が全順序にならないのは、比較を全成分に同時に課すためである。

定義 5.3. $n$ を正の整数とし、各 $i\in\{1,\dots,n\}$ について $X_i$ を集合、 $<_i$ を $X_i$ 上の狭義全順序とする。座標の順序は $1,\dots,n$ に固定する。相異なる二つの組 $x=(x_1,\dots,x_n)$ と $y=(y_1,\dots,y_n)$ に対して、 $x_i\neq y_i$ を満たす添字 $i$ の全体は $\{1,\dots,n\}$ の空でない部分集合であるから、その最小の元が定まる。この最小の添字を $i$ とするとき、

x<_{\mathrm{lex}}y\iff x_i<_iy_i

と定める。 $x=y$ のときは $x<_{\mathrm{lex}}y$ が成り立たないものとする。この $<_{\mathrm{lex}}$ を $X_1\times\cdots\times X_n$ 上の辞書式順序 (lexicographic order) という。

命題 5.4. $n$ を正の整数とし、 $(X_1,\leq_1),\dots,(X_n,\leq_n)$ を全順序集合、 $<_i$ を $\leq_i$ に付随する狭義順序とする。このとき $<_{\mathrm{lex}}$ は $X_1\times\cdots\times X_n$ 上の狭義全順序である。すなわち、 $<_{\mathrm{lex}}$ は非反射的かつ推移的であり、相異なる任意の二元は $<_{\mathrm{lex}}$ について一方向に結ばれる。さらに、 $x<_{\mathrm{lex}}y$ または $x=y$ が成り立つときに $x\leq_{\mathrm{lex}}y$ と定めると、 $\leq_{\mathrm{lex}}$ は $X_1\times\cdots\times X_n$ 上の全順序であり、 $\leq_{\mathrm{lex}}$ に付随する狭義順序は $<_{\mathrm{lex}}$ に一致する。

証明. $x<_{\mathrm{lex}}x$ は定義により成り立たないので、 $<_{\mathrm{lex}}$ は非反射的である。

相異なる $x$ と $y$ を取り、 $i$ を $x_i\neq y_i$ を満たす最小の添字とする。 $\leq_i$ は全順序であり $x_i\neq y_i$ であるから、命題 1.7 (3)により $x_i<_iy_i$ または $y_i<_ix_i$ が成り立つ。 $y_j\neq x_j$ を満たす最小の添字も $i$ であるから、前者ならば $x<_{\mathrm{lex}}y$ 、後者ならば $y<_{\mathrm{lex}}x$ である。

推移性について、 $x<_{\mathrm{lex}}y$ かつ $y<_{\mathrm{lex}}z$ とし、 $i$ を $x$ と $y$ が食い違う最小の添字、 $j$ を $y$ と $z$ が食い違う最小の添字とする。 $i<j$ の場合、 $l<i$ については $x_l=y_l$ かつ $y_l=z_l$ であるから $x_l=z_l$ であり、添字 $i$ については $i<j$ から $y_i=z_i$ であるので $x_i<_iy_i=z_i$ となる。とくに $x_i\neq z_i$ であるから、 $x$ と $z$ が食い違う最小の添字は $i$ であり、 $x<_{\mathrm{lex}}z$ である。 $j<i$ の場合、 $l<j$ については $x_l=y_l=z_l$ であり、添字 $j$ については $j<i$ から $x_j=y_j$ であるので $x_j=y_j<_jz_j$ となる。よって $x$ と $z$ が食い違う最小の添字は $j$ であり、 $x<_{\mathrm{lex}}z$ である。 $i=j$ の場合、 $l<i$ については $x_l=y_l=z_l$ であり、添字 $i$ については $x_i<_iy_i$ かつ $y_i<_iz_i$ であるから、命題 1.7 (2)により $x_i<_iz_i$ であり、命題 1.7 (1)とあわせて $x_i\neq z_i$ である。よって $x$ と $z$ が食い違う最小の添字は $i$ であり、 $x<_{\mathrm{lex}}z$ である。

以上により $<_{\mathrm{lex}}$ は非反射的かつ推移的であるから、命題 1.9 (2)により $\leq_{\mathrm{lex}}$ は半順序であり、 $\leq_{\mathrm{lex}}$ に付随する狭義順序は $<_{\mathrm{lex}}$ に一致する。相異なる二元が $<_{\mathrm{lex}}$ について一方向に結ばれることと命題 1.9 (4)により、 $\leq_{\mathrm{lex}}$ は全順序である。▨

注意 5.5. 積順序と辞書式順序は異なる順序である。 $n=2$ とし、 $X_1=X_2=\{0,1\}$ に $0<1$ を満たす全順序を入れる。 $(0,1)$ と $(1,0)$ について、第 $2$ 成分では $1\leq0$ が成り立たないので $(0,1)\leq_{\mathrm{prod}}(1,0)$ ではなく、第 $1$ 成分では $1\leq0$ が成り立たないので $(1,0)\leq_{\mathrm{prod}}(0,1)$ でもない。よって $\leq_{\mathrm{prod}}$ についてこの二元は比較不能である。一方、二つの組が食い違う最小の添字は $1$ であり $0<1$ であるから、 $(0,1)<_{\mathrm{lex}}(1,0)$ である。

定義 5.6. $X$ を集合、 $\leq$ を $X$ 上の半順序とする。 $X$ の空でない任意の部分集合が最小元をもつとき、 $\leq$ を $X$ 上の整列順序 (well-order) という。

命題 5.7. 整列順序は全順序である。

証明. $\leq$ を $X$ 上の整列順序とし、 $x,y\in X$ を取る。 $S=\{x,y\}$ は $X$ の空でない部分集合であるから最小元 $m$ をもつ。 $m=x$ ならば $x\leq y$ であり、 $m=y$ ならば $y\leq x$ である。よって任意の二元が比較可能であり、 $\leq$ は全順序である。▨

例 5.8. $\mathbb N_{\geq0}$ 上の通常の大小関係は整列順序である。実際、 $S$ を $\mathbb N_{\geq0}$ の空でない部分集合とし、すべての $s\in S$ について $n\leq s$ が成り立つ自然数 $n$ の全体を $A$ とする。 $S$ が最小元をもたないと仮定する。 $0$ はすべての自然数以下であるから $0\in A$ である。 $k\in A$ とすると、 $k\in S$ ならば $k$ が $S$ の最小元になるので $k\notin S$ であり、したがってすべての $s\in S$ について $k<s$ 、すなわち $k+1\leq s$ が成り立つから $k+1\in A$ である。帰納法により $A=\mathbb N_{\geq0}$ となるが、 $S$ は空でないので $s\in S$ を取ると $s+1\in A$ から $s+1\leq s$ となって矛盾する。よって $S$ は最小元をもつ。

$\mathbb Z$ 上の通常の大小関係は全順序であるが整列順序ではない。実際、 $\mathbb Z$ 自身は空でない部分集合であり、 $m\in\mathbb Z$ に対して $m-1\in\mathbb Z$ かつ $m-1<m$ であるから、 $\mathbb Z$ は最小元をもたない。よって命題 5.7の逆は成り立たない。

補題 5.9. $I$ と $Y$ を集合、 $\leq$ を $I$ 上の整列順序、 $f\colon I\to Y$ を写像とし、 $S=f(I)$ とおく。 $f$ の終域を像 $S$ に制限して得る写像を $\bar f\colon I\to S$ とする。各 $y\in S$ に対して、 $f^{-1}(\{y\})$ の最小元を $s(y)$ とおくと、写像 $s\colon S\to I$ が定まり、

\bar f\circ s=\operatorname{id}_S

を満たす。したがって $s$ は単射である。この写像は、像の各元に対して標準的な原像代表を与える。この写像は $f$ と $I$ 上の整列順序から一意に定まり、その構成に選択公理を用いない。

証明. $y\in S$ を取る。 $S=f(I)$ であるから、 $f^{-1}(\{y\})$ は $I$ の空でない部分集合である。 $I$ 上の順序が整列順序であることにより、この部分集合は最小元をもつ。二つの最小元があれば、一方は他方以下であり、逆向きの不等式も成り立つので、反対称律により両者は等しい。したがって $s(y)$ は一意に定まり、 $s\colon S\to I$ は写像である。

$s(y)\in f^{-1}(\{y\})$ であるから $\bar f(s(y))=f(s(y))=y$ であり、 $\bar f\circ s=\operatorname{id}_S$ である。 $y,y'\in S$ が $s(y)=s(y')$ を満たすならば、両辺に $\bar f$ を施すことにより $y=y'$ を得る。よって $s$ は単射である。▨

定理 5.10. $n$ を正の整数とし、 $(X_1,\leq_1),\dots,(X_n,\leq_n)$ を全順序集合、 $\leq_{\mathrm{lex}}$ を命題 5.4が与える全順序とする。

各 $\leq_i$ が $X_i$ 上の整列順序であるならば、 $\leq_{\mathrm{lex}}$ は $X_1\times\cdots\times X_n$ 上の整列順序である。
すべての $X_i$ が空でなく、 $\leq_{\mathrm{lex}}$ が $X_1\times\cdots\times X_n$ 上の整列順序であるならば、各 $\leq_i$ は $X_i$ 上の整列順序である。

証明. 各 $\leq_i$ を整列順序とし、 $S$ を $X_1\times\cdots\times X_n$ の空でない部分集合とする。 $S_0=S$ とおき、 $i=1,\dots,n$ に対して、 $a_i$ を $\{x_i\mid x\in S_{i-1}\}$ の最小元とし、

S_i=\{x\in S_{i-1}\mid x_i=a_i\}

と順に定める。 $S_{i-1}$ が空でなければ $\{x_i\mid x\in S_{i-1}\}$ は $X_i$ の空でない部分集合であるから、 $\leq_i$ が整列順序であることにより $a_i$ が定まり、 $a_i$ を第 $i$ 成分にもつ $S_{i-1}$ の元が存在するので $S_i$ も空でない。 $S_0=S$ が空でないので、この構成は $i=n$ まで進み、各 $S_i$ は空でない。

$a=(a_1,\dots,a_n)$ とおく。 $S_n$ の元は各成分が $a_1,\dots,a_n$ に等しいので $S_n=\{a\}$ であり、とくに $a\in S$ である。 $x\in S$ を取り $x\neq a$ とし、 $i$ を $x_i\neq a_i$ を満たす最小の添字とする。 $l<i$ については $x_l=a_l$ であるから、 $S_1,\dots,S_{i-1}$ の定め方により $x\in S_{i-1}$ である。よって $a_i$ の最小性から $a_i\leq_ix_i$ であり、 $x_i\neq a_i$ とあわせて $a_i<_ix_i$ である。 $i$ は $a$ と $x$ が食い違う最小の添字であるから $a<_{\mathrm{lex}}x$ である。したがって $a$ は $S$ の最小元であり、(1)が成り立つ。

すべての $X_i$ が空でなく、 $\leq_{\mathrm{lex}}$ が整列順序であるとする。 $k\in\{1,\dots,n\}$ を固定し、 $T$ を $X_k$ の空でない部分集合とする。 $i\neq k$ を満たす各 $i$ について、 $X_i$ が空でないので、その元 $c_i$ を一つずつ取ることができる。

S=\{x\in X_1\times\cdots\times X_n\mid x_k\in T\ \text{かつ}\ i\neq k\ \text{のとき}\ x_i=c_i\}

とおくと、 $T$ が空でないので $S$ は空でない。 $\leq_{\mathrm{lex}}$ が整列順序であるから $S$ は最小元 $a$ をもつ。 $S$ の相異なる二元は第 $k$ 成分だけで食い違うので、 $x,y\in S$ について $x<_{\mathrm{lex}}y$ と $x_k<_ky_k$ は同値である。 $t\in T$ を取り、第 $k$ 成分が $t$ である $S$ の元を $x$ とすると、 $a\leq_{\mathrm{lex}}x$ から $a_k\leq_kt$ を得る。すなわち $a_k$ は $T$ の最小元であり、 $\leq_k$ は整列順序である。▨

注意 5.11.定理 5.10 (1)は因子の個数が有限であることに依存する。 $i\in\mathbb N_{\geq1}$ について $X_i=\{0,1\}$ とし、 $0<1$ を満たす全順序を入れる。各成分が $0$ または $1$ である列 $x=(x_1,x_2,\dots)$ の全体に、相異なる二つの列 $x$ と $y$ に対して $x_i\neq y_i$ を満たす最小の添字 $i$ を取り、 $x_i<y_i$ のときに $x<_{\mathrm{lex}}y$ と定める。 $\mathbb N_{\geq1}$ の空でない部分集合は最小元をもつので、この最小の添字は定まる。各 $X_i$ の順序は、二元しかもたないので整列順序である。

$k\in\mathbb N_{\geq1}$ に対して、第 $k$ 成分だけが $1$ で他の成分がすべて $0$ である列を $e_k$ と書く。 $k<l$ とすると、 $e_k$ と $e_l$ が食い違う最小の添字は $k$ であり、そこでの成分は $e_l$ が $0$ 、 $e_k$ が $1$ であるから $e_l<_{\mathrm{lex}}e_k$ である。よって $\{e_k\mid k\in\mathbb N_{\geq1}\}$ は最小元をもたず、この順序は整列順序ではない。

注意 5.12. 辞書式順序が整列順序であっても、各元より小さい元の全体が有限であるとは限らない。 $X_1=X_2=\mathbb N_{\geq0}$ に通常の大小関係を入れると、これは整列順序であるから、定理 5.10 (1)により $\mathbb N_{\geq0}\times\mathbb N_{\geq0}$ の辞書式順序も整列順序である。ここで $(1,0)$ より $<_{\mathrm{lex}}$ について小さい元は、第 $1$ 成分が $0$ である組にほかならないから、その全体は $\{0\}\times\mathbb N_{\geq0}$ であり、有限個の元からなる集合ではない。「基数算術」は、この点のために通常の辞書式順序とは別の順序を導入する。

6 演習

問題 6.1. $(P,\leq)$ を前順序集合、 $T$ を $P$ の部分集合、 $s\in P$ とする。 $s$ が $(P,\leq)$ における $T$ の上限であることと、 $s$ が $P^{\mathrm{op}}$ における $T$ の下限であることとが同値であることを証明せよ。

解答.

$u\in P$ について、 $u$ が $(P,\leq)$ における $T$ の上界であることと、 $u$ が $P^{\mathrm{op}}$ における $T$ の下界であることとは同値である。実際、前者は「すべての $t\in T$ について $t\leq u$ が成り立つ」ことであり、後者は「すべての $t\in T$ について $u\leq^{\mathrm{op}}t$ が成り立つ」ことであって、 $\leq^{\mathrm{op}}$ の定め方によりこの二つは同じ条件である。

$s$ を $(P,\leq)$ における $T$ の上限とする。 $s$ は $T$ の上界であるから、いま示した同値により $s$ は $P^{\mathrm{op}}$ における $T$ の下界である。 $x$ を $P^{\mathrm{op}}$ における $T$ の下界とすると、同じ同値により $x$ は $(P,\leq)$ における $T$ の上界であり、 $s$ が上限であることから $s\leq x$ 、すなわち $x\leq^{\mathrm{op}}s$ である。よって $s$ は $P^{\mathrm{op}}$ における $T$ の下限である。

逆に $s$ を $P^{\mathrm{op}}$ における $T$ の下限とする。 $s$ は $P^{\mathrm{op}}$ における $T$ の下界であるから、同じ同値により $s$ は $(P,\leq)$ における $T$ の上界である。 $u$ を $(P,\leq)$ における $T$ の上界とすると、同じ同値により $u$ は $P^{\mathrm{op}}$ における $T$ の下界であり、 $s$ が $P^{\mathrm{op}}$ における下限であることから $u\leq^{\mathrm{op}}s$ 、すなわち $s\leq u$ である。よって $s$ は $(P,\leq)$ における $T$ の上限である。▨

問題 6.2. $n$ を正の整数、 $(X_1,\leq_1),\dots,(X_n,\leq_n)$ を poset とし、 $X_1\times\cdots\times X_n$ に積順序を入れる。 $T$ を $X_1\times\cdots\times X_n$ の部分集合とし、 $T_i=\{x_i\mid x\in T\}$ とおく。 $T$ が上限をもつことと、すべての $i$ について $T_i$ が上限をもつこととが同値であり、そのとき $T$ の上限は各成分が $T_i$ の上限である組であることを証明せよ。

解答.

まず、 $u\in X_1\times\cdots\times X_n$ が $T$ の上界であることと、すべての $i$ について $u_i$ が $T_i$ の上界であることとは同値である。実際、 $u$ が $T$ の上界であることは「すべての $x\in T$ と各 $i$ について $x_i\leq_iu_i$ が成り立つ」ことであり、 $T_i$ の元は $T$ の元の第 $i$ 成分にほかならないからである。

すべての $i$ について $T_i$ が上限 $s_i$ をもつとし、 $s=(s_1,\dots,s_n)$ とおく。各 $s_i$ は $T_i$ の上界であるから $s$ は $T$ の上界である。 $u$ を $T$ の上界とすると、各 $i$ について $u_i$ は $T_i$ の上界であり、 $s_i$ が上限であることから $s_i\leq_iu_i$ である。よって $s\leq_{\mathrm{prod}}u$ であり、 $s$ は $T$ の上限である。

逆に $T$ が上限 $s$ をもつとする。 $s$ は $T$ の上界であるから、各 $i$ について $s_i$ は $T_i$ の上界である。 $k$ を固定し、 $v$ を $T_k$ の上界とする。第 $k$ 成分が $v$ であり、 $i\neq k$ の第 $i$ 成分が $s_i$ である組を $u$ とすると、各成分が対応する $T_i$ の上界であるから $u$ は $T$ の上界であり、 $s$ が上限であることから $s\leq_{\mathrm{prod}}u$ 、とくに $s_k\leq_kv$ である。よって $s_k$ は $T_k$ の上限である。以上により同値が成り立ち、 $T$ の上限は各成分が $T_i$ の上限である組である。▨

問題 6.3. $n\geq2$ とし、 $(X_1,\leq_1),\dots,(X_n,\leq_n)$ を全順序集合とする。恒等写像

\mathrm{id}\colon(X_1\times\cdots\times X_n,\leq_{\mathrm{prod}})\longrightarrow(X_1\times\cdots\times X_n,\leq_{\mathrm{lex}})

が順序を保つ写像であることを証明し、 $X_1$ と $X_2$ がそれぞれ相異なる二元をもち、かつ $3\leq i\leq n$ を満たす各 $i$ について $X_i$ が空でないときには順序埋め込みでないことを示せ。

解答.

$x\leq_{\mathrm{prod}}y$ とする。 $x=y$ ならば $x\leq_{\mathrm{lex}}y$ である。 $x\neq y$ ならば、 $x_i\neq y_i$ を満たす最小の添字 $i$ について $x_i\leq_iy_i$ かつ $x_i\neq y_i$ であるから $x_i<_iy_i$ であり、辞書式順序の定義により $x<_{\mathrm{lex}}y$ である。よって $\mathrm{id}$ は順序を保つ。

$X_1$ が $a_1<_1b_1$ を満たす二元をもち、 $X_2$ が $a_2<_2b_2$ を満たす二元をもち、 $3\leq i\leq n$ を満たす各 $i$ について $X_i$ が空でないとする。この各 $i$ について $X_i$ の元 $c_i$ を一つずつ取り、 $x=(a_1,b_2,c_3,\dots,c_n)$ 、 $y=(b_1,a_2,c_3,\dots,c_n)$ とおく。 $x$ と $y$ が食い違う最小の添字は $1$ であり $a_1<_1b_1$ であるから $x<_{\mathrm{lex}}y$ である。一方、第 $2$ 成分について $b_2\leq_2a_2$ が成り立たないので $x\leq_{\mathrm{prod}}y$ ではない。よって $\mathrm{id}(x)\leq_{\mathrm{lex}}\mathrm{id}(y)$ でありながら $x\leq_{\mathrm{prod}}y$ が成り立たず、 $\mathrm{id}$ は順序埋め込みではない。▨

順序の三つの水準と、上界、上限、鎖、極大元および整列順序の語は、以後の記事が繰り返し用いる。「束と完備束」は、任意の二元が上限と下限をもつ poset として束を定義し、poset では上限と下限が一意であることを根拠に、結びと交わりを二項演算として扱う。「順序数」は、本記事が定めた整列順序を出発点として整列集合と始切片を定め、超限帰納法の枠組みを作る。

§E1.8順序集合

1 前順序、半順序および全順序

2 上界と下界、上限と下限および鎖

3 上方集合と下方集合

4 順序を保つ写像と順序埋め込み

5 積順序、辞書式順序および整列順序

6 演習

参考文献

前提記事