定義 1.7.1. 集合X 関係≤ 次 条件を , 関係を順序(order)
半順序(partial order) . 1.（反射律, reflexive law ） x≤x
2.（反対称律, antisymmetric law ） x≤y y≤x , x=y 3.（推移律, transitive law ） x≤y y≤z , x ≤z
集合X 順序≤ 次 , 順序を全順序(total order) 線型順序(linear order) .
4. 任意 x, y ∈X 対 , x ≤y y≤x 少 一方 必 成立 .
定義 1.7.2. 集合X 上 順序≤ 組(X,≤)を順序集合(ordered set) 半順序集合(partially ordered set, poset) .
混乱 ≤を省略 単 順序集合X 書 多 . 注意 . 順序関係を表 記号 必 ≤を使 .
記号≤を用 場合, 以下 記法 用 .
• x≤y y ≥x 書 .
• x≤y x̸=y x < y 書 .
• x < y y > x 書 . 問 26. x < y y≤z , x < z.
定義 1.7.3. X, Y を順序集合, f: X →Y を写像 .
1. 任意 x, x′ ∈X 対 , x≤ x′ f(x)≤f(x′) , f を順序を保 写像(order preserving map) .
2. 順序を保 写像f , 順序を保 写像g: Y →X , g◦f = idX, f ◦g = idY を 存在 , 順序同型写像(order isomorphism) . 3. X Y 順序同型写像 存在 , X Y 順序同型 . 注意 . 順序を保 全単射 必 順序同型写像 . 例1.7.4参照.
問 27. X, Y を順序集合, f: X →Y を全単射 . 次を示 .
1. f 順序同型写像 必要十分条件 , 任意 x, x′ ∈X 対 x ≤x′ ⇔
1.7 順序関係 59 f(x)≤f(x′) .
2. X 全順序集合 , f 順序を保 , f 順序同型写像 .
例 1.7.4. X を集合 . 関係 = 明 順序関係 . X 元を二 以上含
, 順序 全順序 .
≤をX 上 順序 . 明 恒等写像id : (X,=)→(X,≤) 順序を保 .
例 1.7.5. (X,≤)を順序集合 . 関係 ≺をx≺ y⇔
defx ≥ y 定 , ≺ 順
序関係 . を≤ 双対(dual) opposite .
普通 順序を（≺等 使 ）≥ 書 . ≤op 書 . 順序集合X 双対順序を 順序集合をXop 書 .
例 1.7.6. (X,≤)を順序集合, A⊂Xを部分集合 . A上 関係≺をa≺b⇔
defa ≤b
（右辺 a, b ∈AをX 元 ） 定 , ≺ 順序関係 . 普通 順序を（≺等 使 ）≤ 書 . , 順序集合 部分集合を順 序集合 考 順序を使 .
X 全順序集合 , 順序 A 全順序集合 . X 全順序集合
, 順序 A 全順序集合 .
例 1.7.7. N Z 普通 順序（数 大小関係） 全順序 .
例 1.7.8. N m nを割 切 関係m|n 順序 .
問 28. Z 関係m|n 順序 ？
例 1.7.9. X を集合 . P(X)上 包含関係A ⊂B 順序 . P(X)を順序集合 考 順序を使 .
X 元を二 以上含 , P(X) 順序 全順序 .
例 1.7.10. (P,≤)を順序集合, Xを集合 . PX 元f, g 対 , f ≤g⇔
def∀x∈X : f(x)≤g(x) 定 , PX 上 順序 .
問 29. を示 .
例 1.7.11. [2] ={0,1} Z 部分集合 順序（0<1） 入 . 2X 元a, b 対 , a≤b⇔
def∀x∈X :a(x)≤b(x) 定 順序 .
例 1.7.12. χ: P(X) → 2X 上 例 1.7.9, 例 1.7.11 順序 関 順序同型写像 .
実際, A ⊂ B ⊂ X . x ∈ A , A ⊂ B , x ∈ B
χB(x) = 1 χA(x) ≤ χB(x). x ̸∈ A χA(x) = 0 , 明 χA(x)≤ χB(x). 任意 x ∈ X 対 χA(x) ≤χB(x), χA ≤ χB
. χ(A) =χA ≤χB =χ(B).
χ 逆写像を φ: 2X → P(X) . φ(a) = a−1(1) . a ≤ b ∈ 2X . a(x) = 1 b(x) ≥ a(x) = 1 b(x) = 1 . φ(a) = a−1(1) ⊂ b−1(1) =φ(b).
例 1.7.13. P, Qを順序集合 . 1. 直積P ×Q上 (p, q)≤(p′, q′)⇔
defp≤p′∧q≤q′ 定 関係 順序 . を直積順序(product order) .
2. 直積P×Q上 (p, q)≤(p′, q′)⇔
defp < p′∨(p=p′∧q ≤q′) 定 関係 順序 . を辞書式順序(lexicographical order) .
ん, （２文字 単語 載 ）辞書 単語 並ん 順番 .
例 P = Q={a, b, c} a < b < c 順序を , {a, b, c}2 直積順序を を図示（小 方 大 方 矢印 書 . 図を 図 . 定義 1.7.16を見 .）
(c, a) //(c, b) //(c, c)
(b, a) //
OO
(b, b) //
OO
(b, c)
OO
(a, a) //
OO
(a, b) //
OO
(a, c)
OO
. 順序 例 (a, b) (b, a) 間 大小関係 無 . 一方, 辞書式順序を
(c, a) //(c, b) //(c, c)
(b, a) //(b, b) //(b, c)
ii
(a, a) //(a, b) //(a, c)
ii
.
1.7 順序関係 61 直積順序 辞書式順序 三 以上 順序集合 積 対 同様 定義
. , 辞書式順序 全順序集合 対 用 多 .
問 30. P, Qを順序集合 , P ×Q上 直積順序を≤prod, 辞書式順序を≤lex 表 .
1. ≤prod ≤lex 順序 を示 .
2. 恒等写像
id : (P ×Q,≤prod)→(P ×Q,≤lex), id : (P ×Q,≤lex)→(P ×Q,≤prod) 順序を保 ？
3. P, Q 全順序集合 , ≤lex 全順序 を示 .
例 1.7.14. P を順序集合 . 集合P[2] 例 1.7.10 順序を, P2 直積順序を . 写像
P[2] //
e= (ev0,ev1) : P2 f∈ //
(f(0), f(1))
∈
順序同型写像 .
定義 1.7.15. Xを順序集合, a, b∈X . 1.
[a, b] :={x∈X a≤x≤b} をa, bを端点 閉区間(closed interval) . 2.
(a, b) :={x∈X a < x < b} をa, bを端点 開区間(open interval) .
3. a < b (a, b) =∅ , aをb 直前(predecessor) 元, bをa 直 後(successor) 元 .
他半開区間[a, b)等 記号 使 . 意味 明 .
注意! . 開区間 記号 (a, b) 直積集合X ×X 元を表 記号 同 注意 必要
, 通常文脈 意味 判断 .
以下 二 exercise , x > b x∈X 存在 場合 解答
. （ ん, 場合 考 .）
問 31. X を順序集合, a, b∈X, a ≤b , A=∩
x>b[a, x) .
1. A ⊃[a, b] を示 .
2. X 順序 全順序 A= [a, b] を示 .
3. A ̸= [a, b] 例を挙 .
問 32. X を順序集合, a, b∈ X, a ≤b , A = ∩
x>b[a, x] . 次 二 条件を 考 .
(i) A = [a, b].
(ii) ∀y > b,∃x > b:x < y.
1. X 全順序集合 , (i) (ii) 同値 を示 .
2. X 順序 全順序 , (i)⇒(ii) 成 立 ？ 成 立 証明 , 成 立 場合 例を挙 .
3*. X 順序 全順序 , (ii)⇒(i) 成 立 ？ 成 立 証明 , 成 立 場合 例を挙 .
定義 1.7.16 ( 図, Hasse diagram). 有限順序集合を図示 有用 図
(Hasse diagram)を紹介 . （ , 人 手 苦労 書 元 数
少 場合 限 , 見 意味を読 取 元 数
多 無 場合 .）
(X,≤)を有限順序集合 . X 元を頂点 ,x 直後 元 y x y 矢印を書 . , 矢印同士 頂点同士以外 交 . 矢印を書 煩雑 , 矢印を使 大 元 上 書 多 .
与 順序集合 対 , 図 一通 書 , （正 書
） 図 順序関係を復元 .
具体的 例を挙 .
1. 冪集合 包含関係 順序を .
P([1]) {0}
∅
P([2]) {0,1}
{0} {1}
∅
1.7 順序関係 63 P([3]) {0,1,2}
{0,2} {0,1} {1,2}
{0} {2} {1}
∅
2. [2] ={0,1} 0<1 順序を 直積 直積順序を .
[2] 1
0
[2]2 (1,1)
(1,0) (0,1)
(0,0) [2]3 (1,1,1)
(1,0,1) (1,1,0) (0,1,1)
(1,0,0) (0,0,1) (0,1,0)
(0,0,0)
3. 自然数 集合 割 切 順序を .
({1,2},|) 2
1
({1,2,3,6},|) 6
2 3
1
({1,2,3,5,6,10,15,30},|) ({2,3,4,5,6},|) 30
10 6 15
2 5 3
1
4 6
2 3 5
4. 冪集合 空集合を除 包含関係 順序を . P([1])\ {∅} {0}
P([2])\ {∅} {0} // {0,1}oo {1}
P([3])\ {∅} {2}
{0,2}
&& {1,2}
xx{0,1,2}
{0}
FF //{0,1}
OO
{1}
XX
oo
定義 1.7.17. X を順序集合, A ⊂X を部分集合 . 1. m∈X A 上界(upper bound) ⇔
def ∀a∈A:a ≤m.
2. l ∈X A 下界(lower bound) ⇔
def ∀a ∈A:l ≤a.
注意! . 上界, 下界 一 .
3. A 上界を持 A 上 有界(bounded from above) .
A 下界を持 A 下 有界(bounded from below) .
上 下 有界 有界(bounded) .
定義 「A 有界⇔ ∃l, m∈X,∀a ∈A:l ≤a≤m 」 分 .
1.7 順序関係 65 注意 . l ∈ X A 下界 l ∈ Xop A 上界 同
. , 順序を 双対 得 （ 不等号 向 を全 逆
得 ）概念を 双対 . 下界 上界 , 上界 下界 双対 . 任意 順序集合 対 成立 命題 , （Xopを考 ）不等号 向 を逆
命題 成立 . を順序 対 双対原理(duality principle) . 問 33. X を順序集合, A, B ⊂X .
1. B 有界 , A ⊂B , A 有界.
2. X を全順序集合 . A, B 有界 , A∪B 有界.
3. A, B 有界 , A∪B 有界 例 挙 .
例 1.7.18. X ̸= ∅を順序集合 . 任意 x ∈ X ∅ ⊂ X 上界 下界 .
実際, ∀a ∈ ∅:a≤x, ∀a ∈ ∅:x ≤a （前提 偽 ）成 立 . X ̸=∅ , ∅ ⊂X 有界 .
定義 1.7.19. Xを順序集合, A ⊂Xを部分集合 . 1. M ∈X A 最大元(maximum element)
def⇔ {
(i) M ∈A
(ii) M A 上界 . ∀a∈A :a ≤M
M = max
a∈Aa = max
A a = maxA等 書 . 2. m∈X A 最小元(minimum element)
⇔def
{
(i) m∈A
(ii) m A 下界 . ∀a∈A :m≤a
m= min
a∈Aa = min
A a= minA等 書 . 注意 . 最大元 最小元 互 双対 .
命題 1.7.20. A⊂X 最大元(最小元) 存在 一意的 .
証明. 実際, M1, M2 を A 最大元 定義 次 成 立 . (i1) M1 ∈A
(ii1) ∀a∈A :a≤M1
(i2) M2 ∈A
(ii2) ∀a∈A :a≤M2
(i1) (ii2) M1 ≤M2. 同様 M2 ≤M1. 順序 性質 M1 =M2.
最小元 同様 示 ,双対性原理 成 立 . ,m∈X
A 最小元 m∈ Xop A 最大元 同
注意 最大元 示 十分 .
例 1.7.21. N m|n 順序を . minN = 1 . 一方, min (N\ {1}) 存在
. 実際, p ∈ N 素数 , m|p m ∈ N 1, p . ,
2,3∈N\ {1} 対 , m|2 m|3 m∈N\ {1} 存在 . 例 1.7.22. maxP(X) =X, minP(X) =∅.
問 34. を確 .
例 1.7.23. [2] 0 < 1 順序を , min{p, q} = p∧q = pq. max{p, q} = p∨q.
問 35. を確 .
問 36. X を順序集合, a, b∈X, a ≤b . max[a, b] =b, min[a, b] =aを示 . 例 1.7.24. Q 数 大小関係 順序を . a, b ∈ Q, a < b . max(a, b),
min(a, b) 存在 .
実際, 任意 x ∈(a, b) , x 最小元 以下 分 .
x ∈(a, b) a < x < b. c= x+a2 , c−a= x+a
2 −a= x−a
2 >0 x−c=x− x+a
2 = x−a 2 >0
a < c < x. x < b c < b. c∈(a, b) c < x. x 最小元
. 最大元 同様.
問 37. 最大元 示 .
定義 1.7.25. X を順序集合, A ⊂X .
1. A 上界全体 集合 最小元 存在 をA 上限 (supremum)
sup
a∈A
a supA
表 . A 上界全体を UA :={
x∈X x A 上界}
1.7 順序関係 67 , supA = minUA.
2. A 下界全体 集合 最大元 存在 をA 下限(infimum)
a∈Ainf a infA 表 . A 下界全体を
LA:={
x∈X x A 下界} , infA = maxLA.
注意 . 上限, 下限 互 双対 . , 上限, 下限 存在 一意的 . 例 1.7.26. X を順序集合 . minX 存在 sup∅ = minX . maxX
存在 inf∅= maxX .
実際, minX maxX 存在 X ̸= ∅ ∅ ⊂ X 有界 , U∅ =
L∅ =X .
命題 1.7.27. maxA 存在 supA= maxA.
証明. M = maxA . A 上界全体 集合をUA 書 .
最大元 定義(ii) M A 上界 , M ∈UA.
最大元 定義(i) M ∈A. 従 , A 任意 上界m∈UA 対 M ≤m.
M = minUA, A 上限 .
命題 1.7.28. Xを全順序集合, A⊂X . s= supA ⇔
{
(i) ∀a∈A:a ≤s,
(ii) ∀x∈X : (x < s→ ∃a ∈A:x < a).
注意! . 特徴 全順序集合 一般 正 . 証明. 条件(i) s A 上界 を .
一方対偶を考 条件(ii) 「x A 上界 , s ≤x」 同値.
(i),(ii) s A 上界 最小元 を .
問 38. 1. 上 証明 X 全順序集合 を用 ?
2. 一般 順序集合 命題 1.7.28 ⇒ 成 立 ? 成 立 証明 ,
成 立 反例を挙 .
3*. 一般 順序集合 命題 1.7.28 ⇐ 成 立 ? 成 立 証明 ,
成 立 反例を挙 .
例 1.7.29. Q 数 大小関係 順序を . a, b ∈ Q, a < b . sup(a, b) = b, inf(a, b) =a .
証明. b= sup(a, b) を, 命題 1.7.28を使 示 .
x ∈ (a, b) a < x < b b (a, b) 上界 . b 命
題 1.7.28 条件(i)を .
条件 (ii) を調 . c < b . d = max{a, c} , d < b.
y = (b+d)/2∈Q d < y < b . a ≤d 注意 a < y < b,
y ∈(a, b) . c≤d c < y. 条件(ii) 成 立 . 従
b= sup(a, b).
inf(a, b) =a 同様. 問 39. 下限 方を示 .
例 1.7.30. A ⊂ P(X) 対 , supA = ∪
A∈AA, infA = ∩
A∈AA . ,
A =∅ ∩
A∈AA=X 約束 . （§1.5節 Remark参照.） 証明. 下限 方を示 . A ̸=∅ を考 .
B ⊂X A 下界⇔
def∀A∈ A:B ⊂A
⇔B⊂ ∩
A∈A
A
∩
A∈AA A 下界 最大元, infA .
A=∅ , maxP(X) =X inf∅= maxP(X) =X 成立.
問 40. 上限 方を示 .
定義 1.7.31. X を順序集合, A ⊂X を部分集合 . 1. M ∈X A 極大元(maximal element)
⇔def
{
(i) M ∈A,
(ii) ∀a ∈A :M ̸< a.
, M A 元 , M 大 元 A 中 M A
極大元 .
2. m∈X A 極小元(minimal element)
⇔def
{
(i) m∈A,
(ii) ∀a∈A :a̸< m.
1.7 順序関係 69
, m A 元 , m 小 元 A 中 m A
極小元 .
命題 1.7.32. 最大元 極大元 , 最小元 極小元 .
証明. a ≤M ⇒M ̸< a.
命題 1.7.33. 全順序部分集合 極大元 最大元 , 極小元 最小元 .
証明. 全順序集合 M ̸< a⇒M ≥a.
例 1.7.34. 一般 極大元, 極小元 一意 . N m|n 順序を . n ∈
N\ {1} 極小 n 素数 同値 .
定義 1.7.35. 一般 順序集合 対 定義 , 上界, 下界 存在
場合上極限, 下極限を定義 . X を順序集合, a: N → X を写像 . （ をX 点列 .）数列 場合 同様, 普通 a(n) ∈X をan 書 , 点列を{an}n∈N, {an}等 表 .
1. 点列{an}をan := sup{ai|i ≥n} ∈ X 定 . X 部分集合{an n∈N}
下限を点列{an} 上極限 , lim supan liman 書 . lim supan = inf{an}= inf{sup{ai|i≥n} |n∈N}.
2. 点列{an}をan := inf{ai|i ≥n} 定 . X 部分集合{an n∈N} 上限を 点列{an} 下極限 , lim infan liman 書 .
lim infan = sup{an}= sup{inf{ai|i≥n} |n∈N}.
例 1.7.36. P(X) 点列{An}n∈N 対 , 定義 上極限, 下極限 定義 1.5.9
定義 同 .
問 41. X, Y を順序集合, f: X →Y を順序を保 写像, A ⊂X .
1. m∈X A 上界 f(m) f(A) 上界 .
2. m= maxA f(m) = maxf(A).
3. 上限 同様 言 ？ X, Y, f 適当 条件を 何 言
？
4. m A 極大元 , f(m) f(A) 極大元 例を挙 .
問 42. X を集合,P を順序集合,PX 各点毎 順序（例 1.7.10）を . F ⊂PX .
1. maxF 存 在 . 任 意 x ∈ X 対 , (maxF)(x) = max{f(x) f ∈F} .
2. 任意 x ∈X 対 , max{f(x) f ∈F} 存在 . maxF
存在 ？
3. supF 存 在 . 任 意 x ∈ X 対 , (supF)(x) =
sup{f(x) f ∈F} .
4. 任意 x ∈ X 対 , sup{f(x) f ∈F} 存在 , fs ∈ PX をfs(x) =
sup{f(x) f ∈F} 定 . fs= supF .