第 12 章順序集合

157

第

12

本章では

,

.

12.1

集合

A

≼

3

(順序の公理という)

A

(i) [反射律] x ≼ x.

(ii) [反対称律] x ≼ y, y ≼ x ⇒ x = y.

(iii) [推移律] x ≼ y, y ≼ z ⇒ x ≼ z.

記法の便利さのために

x ≼ y

y ≽ x

さらに,等号なしの順序関係

≺

A

≺

x ≺ y ⇔ x ≼ y, x ̸ = y

(i

) x ≺ y

y ≺ x

. (ii

) [推移律] x ≺ y, y ≺ z ⇒ x ≺ z.

逆に

, (i

), (ii

)

≺

,

A

関係

≼

x ≼ y ⇔ x ≺ y

x = y

≼

A

順序集合 順序関係

≼

≺

A

≼ )

(A, ≺ )

順序集合と明確に区別したければ,半順序集合という. 順序関係があらかじめ明 らかなときは, 集合の記号

A

全順序集合 順序集合

(A, ≼ )

2

x, y ∈ X

x ≼ y

y ≼ x

2

(iv)

x, y ∈ X

x ≼ y

y ≼ x

とき, (A,

≼ )

(iv)

≺

補 題

12.1

(A, ≺ )

x, y ∈ X

x ≺ y, x = y, y ≺ x

1

.

部分順序集合

(A, ≼ )

B ⊂ A

x, y ∈ B

A

≼

B

(B, ≼ )

A

. A

B

.

, A

B

例

12.2 (実数の大小)

x, y ∈ R

x ≤ y

R

.

, ≤

(i)–(iv)

R , ≤ )

R

Q , Z , N

( R , ≤ )

,

.

≤

例

12.3 (自然数の整除関係)

x, y ∈ N

y

x

(あるいは, x

y

x | y

|

(i)–(iii)

N , | )

集合ではない

.

, 3

5

.

1)空集合∅上にはただ1つの二項関係が存在する(∅ × ∅の部分集合は1つしかないから). そ れが全順序の公理を満たすのは自明な論理である. この意味で,空集合も順序集合として扱う.

12.1.

159

例

12.4 (集合の包含関係)

X

1

2

A, B ∈ 2

A ⊂ B

2

, ⊂ )

(

2.3)

(i)–(iii)

.

( | X | ≤ 1)

, (2

, ⊂ )

ハッセ図 順序集合

(A, ≼ )

.

A

x ≺ y

x ≺ z

z ≺ y

z

(このとき, y

x

x

y

例

12.5

A = { 1, 2, 3, 4, 5, 6, 10, 12 }

x | y

(A, | )

12.1(左)

2 ∈ A

1 | 2

, 1 | z

z | 2

z

, 2

1

4

1 | 4

| z

z | 4

z

z = 2

4

例

12.6

X = { 1, 2, 3 }

A = 2

= {∅ , { 1 } , { 2 } , { 3 } , { 1, 2 } , { 2, 3 } , { 1, 3 } , { 1, 2, 3 }}

に包含関係を与えた順序集合

(A, ⊂ )

12.1(右)

1

2

3

4

5

6

10

12

1

2

3

f ^{{ }}

{ }

{ }

{ } { }1,2

{ }1,3

2,3 { }1,2,3

図

12.1:

12.5 (A, | )

12.6 (A, ⊂ )

最大元と最小元

(A, ≼ )

A

a ∈ A

A

,

x ∈ A

x ≼ a

A

同様に,

a ∈ A

A

x ∈ A

a ≼ x

min A

極大元と極小元

(A, ≼ )

A

a ∈ A

A

, a ≺ x

x ∈ A

.

a ∈ A

A

x ≺ a

x ∈ A

.

,

例

12.7

12.5

min A = 1

max A

12

12.6

min A = ∅ ,

max A = { 1, 2, 3 }

∅

{ 1, 2, 3 }

例

12.8 ( N , ≤ )

.

,

1

,

例

12.9

1

A = N\{ 1 }

(A, | )

問

12.1 (A, ≼ )

. a ∈ A

A

,

a ∈ A

A

問

12.2

上界と下界・上限と下限

(X, ≼ )

A

このとき

,

(A, ≼ )

,

,

,

, A

A

.

, A

X

すべての

a ∈ A

a ≼ x

x ∈ X

A

A

U (A) = { x ∈ X |

a ∈ A

a ≼ x }

12.2.

161

とする.

U (A)

U (A)

A

sup A

a ∈ A

x ≼ a

x ∈ X

A

A

L(A) = { x ∈ X |

a ∈ A

x ≼ a }

が空ではなく

, max L(A)

,

A

inf A

.

12.10

12.5

B = { 2, 4, 6 }

U (B) = { 12 } , L(B) = { 1, 2 }

である. したがって, max

B

sup B = 12

min B = inf B = 2

例

12.11

12.6

,

B = {{ 1 } , { 2 } , { 1, 2 }}

, U(B) = {{ 1, 2 } , { 1, 2, 3 }} , L(B) = {∅}

である. したがって, max

B = sup B = { 1, 2 }

B

inf B = ∅

.

問

12.3

( N , | )

A = { 6, 10, 12, 18, 36, 60 }

問

12.4 Q

A, B

A = { x ∈ Q | x > 0, x

< 2 } , B = {

1 − 1 n

n ∈ N }

.

12.2

(X, ≼

)

(Y, ≼

)

f : X −→ Y

x

, x

∈ X, x

≼

x

⇒ f (x

) ≼

f (x

)

を満たすとき,順序を保つ写像または単調な写像という. もし,

f : X −→ Y

, f, f

, f

.

X, Y

X

Y

例

12.12 X = N , Y = Z

f (x) = 2x − 5

f : X −→ Y

例

12.13 X = Y = Z

f(x) = x + 1

f : X −→ Y

例

12.14 X = {∅ , { 1 } , { 2 } , { 1, 2 }} , Y = { 1, 2, 3, 4 }

X

, Y

.

f : X −→ Y

f : ∅ 7→ 1, f : { 1 } 7→ 2, f : { 2 } 7→ 3, f : { 1, 2 } 7→ 4,

で与える

.

, f : X −→ Y

, f

: Y −→ X

定 理

12.15 X, Y

f : X −→ Y

f

: Y −→ X

.

証 明

X, Y

≼

, ≼

. y

, y

∈ Y

y

≼

y

f

y

= f (x

), y

= f (x

)

x

, x

∈ X

x

= f

(y

)

x

= f

(y

)

X

(i) x

≼

x

,

(ii) x

≼

x

が成り立つ

.

(ii)

, f

f (x

) ≼

f (x

)

y

≼

y

y

≼

y

y

= y

x

= x

x

≼

x

f

(y

) ≼

f

(y

)

定 理

12.16 X, Y

, f : X −→ Y

. X

A

a ∈ A

A

(または最小元,

f (a)

f (A)

(または最小元,

証 明 任意の

y ∈ f (A)

f

(y) ∈ A

a = max A

f

(y) ≼

a

.

f

, y ≼

f (a)

かる. これは,

f (a) = max f (A)

例

12.17

R ,

Q ,

Z ,

N

≤

R

3

12.2.

163

とは濃度が異なるのでそもそも全単射が存在せず, 順序同型になり得ない. 次 に,自然数

N

min N = 1

Q

Z

N

Q , N

Z

(定理 12.16).

最後に

, Q

Z

.

f : Z −→ Q

f (1) < f (2)

a = (f(1) + f (2))/2

a ∈ Q

f (1) < a < f (2)

f

: Q −→ Z

< f

(a) < 2

f

(a) ∈ Z

Q

Z

辞書式順序

(X, ≺

), (Y, ≺

)

X × Y

≺

(x

, y

) ≺ (x

, y

) ⇔

 



(i) x

≺

x

,

または

(ii) x

= x

, y

≺

y

のように定義すると,容易にわかるように,

≺

X × Y

.

順序集合の列

X

, . . . , X

X

× X

× · · · × X

.

問

12.5 a < b

(a, b)

R

(a, b)

R

[a, b]

R

ではないことを示せ.

問

12.6

x, y

x ≤ y

y ≼ x

(1) ( R , ≼ )

(2) ( R , ≼ )

( R , ≤ )

. (3) ( N , ≼ )

( N , ≤ )

問

12.7 X, Y

,

X × Y

問

12.8 A = { 1, 2 } , N

.

,

A × N

N × A

12.3

順序集合に極大元があるための使いやすい十分条件を与えておこう

.

定 理

12.18 (ツォルンの補題)

X

X

.

すべての全順序部分集合が上界をもつような順序集合をツォルン集合と呼ぶ.

そうすると,ツォルンの補題

(定理 12.18)

以下では, (X,

≼ )

X

M

∅

X

, ∅ ∈ M

.

, M

.

, M

X

( M , ⊂ )

補 題

12.19 N

( M , ⊂ )

, ∪

N ∈ M

.

x, y ∈ ∪

N

x ∈ A, y ∈ B

A, B ∈ N

( N , ⊂ )

, A ⊂ B

B ⊂ A

.

x, y ∈ B

x, y ∈ A

x, y

X

A

B

, x, y

.

∪

N

X

補 題

12.20 A ∈ M

U(A) = { u ∈ X |

a ∈ A

a ≼ u }

とおく

(X

A

).

, U (A) ⊂ A

U (A)

X

X

証 明

A

X

,

U (A) ̸ = ∅

u ∈ U (A)

A

2)Max August Zorn (1906–1993,ドイツの数学者)が整列可能定理に代わる集合論の公理とし て提案して,代数におけるいくつかの応用を示した(1935). ツォルン自身は「補題」とは呼んでお らず, MP (maximum principle,極大原理)と称した.その論文で選択公理と整列可能定理の同値 性を予告したが,公表されなかったようである.

3)ここではHalmos [],松村[]にしたがって,集合と写像を用いた初等的な証明を紹介する. よ く知られた超限帰納法による証明は簡潔で直感的なのだが,そのためには整列集合の理論を準備す る必要がある.

12.3.

165

a ∈ A

a ≼ u

U(A) ⊂ A

u ∈ A

るから,

u = max A

u ≺ v

v ∈ X

v ∈ U (A)

であり,

U (A) ⊂ A

v ∈ A

u = max A

したがって

, u ≺ v

v ∈ X

, u

X

.

以下

, (X, ≼ )

.

導くことによって, ツォルンの補題

(定理 12.18)

まず, 補題

12.20

A ∈ M

U (A) ̸⊂ A

ら,

U(A) \ A ̸ = ∅

(AC2)

U (A) \ A

1

f (A)

A ∪ { f (A) }

X

,

g : M −→ M , g(A) = A ∪ { f (A) } , A ∈ M ,

が定義される. この写像

g

X

A

1

A

U (A) g(A)

A

図

12.2:

g : M −→ M

M

T

(i) ∅ ∈ T ,

(ii) A ∈ T ⇒ g(A) ∈ T

(iii) S ⊂ T

∪

S ∈ T .

M

T

T

(i)–(iii)

T

は最小のタワーである.

補 題

12.21 A ∈ T

T

.

,

B ∈ T

B ⊂ A

g(A) ⊂ B

証 明 そのような

A

U = { B ∈ T

| B ⊂ A

g(A) ⊂ B }

とおく. 証明のためには,

U = T

U ⊂ T

, U

, T

U = T

がわかる. そこで,

U

(i) ∅ ∈ T

∅ ⊂ A

∅ ∈ U

(ii) B ∈ U

B ⊂ A,

(iib) g(A) ⊂ B

このことから

g(B) ∈ U

B ∈ T

g(B) ∈ T

.

(iia) B ⊂ A

A

T

g(B)

も比較可能である

.

, g(B) ⊂ A

A ⊂ g(B)

.

g(B) ∈ U

B ⊂ A ⊂ g(B) = B ∪ { f (B) }

A = B

A = g(B)

A = B

g(A) = g(B),

g(A) ⊂ g(B )

g(B) ∈ U . A = g(B)

g(B) ⊂ A

g(B) ∈ U .

g(B) ∈ U

(iib) g(A) ⊂ B

.

, g(A) ⊂ B ⊂ g(B)

g(A) ⊂ g(B)

g(B) ∈ U

(iii) S ⊂ U

,

B = ∪

S = ∪

C∈S

C

とおく.

B ∈ U

U ⊂ T

S ⊂ T

T

,

B ∈ T

.

, S ⊂ U

,

C ∈ S

C ⊂ A

g(A) ⊂ C

C ∈ S

C ⊂ A

B ⊂ A

g(A) ⊂ C

C

∈ S

g(A) ⊂ C

⊂ B

B ⊂ A

g(A) ⊂ B

B ∈ U

補 題

12.22 T

M

証 明 簡単のため,

Z = { A ∈ T

| A

B ∈ T

}

12.3.

167

とおく. 定義から

Z ⊂ T

T

Z

Z = T

Z

(i) ∅ ∈ T

∅

B ∈ T

∅ ⊂ B

∅ ∈ Z

(ii) A ∈ Z ,

A ∈ T

T

補題

12.21

B ∈ T

B ⊂ A

g(A) ⊂ B

り立つ

.

, B ⊂ A ⊂ g(A)

, B ⊂ g(A)

.

g(A)

B ∈ T

g(A) ∈ Z

.

(iii) S ⊂ Z

∪

S ∈ Z

A = ∪

S = ∪

C∈S

C (12.1)

とおく

. A

B ∈ T

.

C

∈ S

B ⊂ C

B ⊂ C

⊂ A

C ∈ S

B ̸⊂ C

S ⊂ Z

Z

C

B ∈ T

と比較可能なので

C ⊂ B

.

, (12.1)

A ⊂ B

B ⊂ A

A ⊂ B

A

B ∈ T

.

ツォルンの補題

(定理 12.18)

T

12.22

,

T

.

,

(iii)

A

= ∪

T

(12.2)

は

A

∈ T

(ii)

g(A

) ∈ T

g(A

) ⊂ A

g(A

) = A

∪ { f (A

) }

f (A

) ∈ A

f (A

)

U (A

) \ A

X

, X

.

選択公理 ツォルンの補題

(定理 12.18)

(AC2)

,

.

.

定 理

12.23

証 明 ツォルンの補題を用いて選択公理

(AC2)

. Ω

∅ ̸∈ Ω

D ⊂ Ω

f : D −→ ∪

Ω

( D , f )

,

A ∈ D

f (A) ∈ A

Z

.

Z

A ∈ Ω

1

A ̸ = ∅

a ∈ A

f : { A } −→ ∪

Ω

f (A) = a

( { A } , f) ∈ Z

Z

( D

, f

) ≼ ( D

, f

)

D

⊂ D

A ∈ D

f

(A) = f

(A)

Z , ≼ )

.

( Z , ≼ )

Y ⊂ Z

, Ω

E = ∪

(D,f)∈Y

D (12.3)

とおいて

,

g : E −→ ∪

Ω

.

x ∈ E

( D , f) ∈ Y

x ∈ D

g(x) = f (x)

, x ∈ D

( D , f) ∈ Y

,

f (x)

g

( D

, f

), ( D

, f

) ∈ Y

x ∈ D

, x ∈ D

Y

D

⊂ D

D

⊂ D

.

f

(x) = f

(x)

,

g(x)

x ∈ D , ( D , f ) ∈ Y

E , g)

Z

, Y

.

, ( Z , ≼ )

. ( Z , ≼ )

( ˜ D , f ˜ ) ∈ Z

D ̸ = Ω

A

∈ Ω \ D ˜

A

a

∈ A

h(A) =

 



a

, A = A

, f ˜ (A), A ∈ D, ˜

h : ˜ D ∪ { A

} −→ ∪

Ω

D ∪ { A

} , h) ∈ Z

, ( ˜ D , f ˜ ) ≺ ( ˜ D ∪ { A

} , h) ∈ Z

.

( ˜ D , f ˜ ) ∈ Z

D = Ω

f

Ω