(1) f が 全射 ⇔ f∗ が 全射 (⇒を示すのに 選出公理が 必要) (2) f が 単射 ⇔ f∗ が 単射
(3) f が 全射 ⇔ f∗ が 単射 (4) f が 単射 ⇔ f∗ が 全射
ヒント (1) ⇒: h ∈ YA に 対し て, f◦g = hとな るよ うな g ∈ XA は, ∀a ∈ A, g(a)∈f−1(h(a))を 満たす.
⇐: y ∈Y に 対し て,cy∈YAを cy(a) =yとなる定値写像とすれば, 条件が 適用で きる. (cy の存在に A=∅が 必要)
(2)⇒: g=g′ ∈XAとすれば,∃a0∈A,g(a0)=g′(a0).
⇐: x=x′ ∈X に 対し て,cx, cx′ ∈XAをそれぞれ cx(a) =x,cx′(a) =x′ となる定 値写像とすれば,条件が 適用できる.
(3)⇒: h=h′ ∈WY とすれば,∃y0∈Y, h(y0)=h′(y0).
⇐: (背理法)f が 全射でなければ, ∃y0∈Y \f(X). W が 異な る2 元を 持つことを 用いて,h(y0)=h′(y0)でh(y) =h′(y) (y=y0)となるh, h′∈WY を作り,f∗が 単 射であることに 矛盾を 出す.
(4) ⇒: g ∈WX に 対し て, h◦f =g とな るよ うな h∈ WY は, y =f(x)∈ Y ⇒ h(y) =h(f(x)) =g(x)でなければ ならない.
⇐: x0=x1∈X に 対し て,W が 異なる2 元を 持つことを用いて,g(x0)=g(x1)と なるg∈WX を 作り, f∗が 全射であることを 適用.
2 つの 元 x, y ∈ X に 対し て, x y または x yが 成立するとき, x と yは 比較 可能[comparable]であるというが, 任意の 2つの元x, y ∈X が 常に比較可能なと き,すなわち, つぎ の条件を満たすとき, 順序を全順序[total order] または 線形 順序[linear order]という:
(O4) ∀x, y ∈X,xy or xy — 比較可能律[comparability law]
集合N,Z, Q, Rにおけ る通常の大小関係は 全順序であるが,元を 2つ以上持つ 集合 X の巾集合 P(X)におけ る包含関係 ⊂は 順序であるが 全順序ではない.
集合X 上の順序 に対し て,X 上の 2 項関係 <をつぎ のように 定義する: x < y ⇔
def xy, x=y
2 項関係<は あるいは と表わす場合もある.19 この2 項関係<はつぎ の 2 条件を満たす:
(O∗1) ∀x, y ∈X, (x < y ⇒x=y) — 非反射律[irreflexive law]
(O∗2) ∀x, y, z∈X, (x < y, y < z ⇒x < z) — 推移律[transitive law]
(O∗1)は 定義より明らか. (O∗2)は,x < y,y < zならば, (O3)よりxz であるが, x=zとすれば,x < y,y < xなので, (O2)よりx=y となり矛盾するので, x < z.
上の 2 条件 (O∗1), (O∗2)を 満たす 2 項関係 < を X に おけ る狭義の順序[order in the strict sense] という. 逆に, 集合 X 上に 狭義の順序 <が 与えられたとき, 2 項 関係 をつぎ のように定義する：
xy ⇔
def x < y または x=y
このとき, 2 項関係 は条件 (O1), (O2), (O3)を満たし, X 上の順序となる. 演習 4.4 集合X 上の狭義の順序 <によって定義され る 2項関係 が 順序に なること,すなわち条件 (O1), (O2), (O3) を満たすことを確かめよ.
ヒント (O∗1), (O∗2)から x < yと y < xは 両立し ない.
集合 X 上の全順序 が 定義する狭義の順序 <は, 以下の条件を満たす: (O∗3) ∀x, y ∈X,x=y orx < y or x > y — 三分律[trichotomy]
この条件を 満たす狭義の順序 < を狭義の全順序であるい う. 明らかに, 狭義の全 順序が 定義する順序は 全順序である.
注意: 条件(O∗3)において,x=y,x < y,x > yのうち唯一つだけが 成立する.
19集合の間の包含関係 ⊂に 対し ては,あるいはと 書く.
集合 X 上の順序(または 狭義の順序) (または <) に 関し て, x y (または x < y)の否定はx y (または x < y) と書く. また, x y, x < y, x y, x < y は,それぞれ y x, y > x, y x, y > x とも書く. 条件 (O∗3) は 以下の条件と同 値である:
∀x∈X, x< x
注意: 全順序集合においては,xy の否定は x > y となるが, 一般の場合には, x, y ∈X が 比較不可能なときもxyとなるので, xy の否定は必ずし もx > y とはならない.
順序が 与えられている集合X を順序集合[ordered set]というが, 単なる集合 X ではなく,順序という“構造”を持っていることを示すため, 集合と順序の組 (X,)で 表す. ど んな 順序 が 与えられているのか 明確な 場合には, 単に X を 順序集合と呼ぶことが 多い. 全順序 が 与えられている集合を全順序集合[totally ordered set] または線形順序集合[linearly ordered set]という. 集合N,Z, Q,Rは 通常の大小関係により全順序集合となる. また, 集合 X の巾集合 P(X)は 包含関 係 ⊂により順序集合となるが, X が 元を 2 つ以上持つ場合には,P(X)は全順序 集合ではない.
すでに 見たように, 集合 X 上に 狭義の順序 <が 与えられれば, 順序 が 定義 され,X は順序集合となるので,順序集合は狭義の順序が 与えられた集合であると い うこともできる. 狭義の全順序は 全順序を定義するので,全順序集合は 狭義の全 順序が 与えられた集合である.
順序集合X = (X,) の部分集合 Aに 対し て,つぎ の条件を満たす a∈Aを A の最大元[maximum] (または 最小元[minimum])とい う:
∀x∈A, ax (または ax)
A の最大元(最小元)は存在すれば 一意的に 決まるので, maxA (または minA)と 表す. また, つぎ の条件を満たす a∈Aを A の極大元[maximal element] (または 極小元[minimal element])という:
∀x∈A, a< x (または a> x)
演習 4.5 Aの最大元(または最小元)は存在すれば,それは A の極大元(または 極小元)であり, 一意的に 決まることを示せ. また, 全順序集合においては,極大元 (または 極小元)は 最大元(または 最小元)になることも示せ.
演習 4.6 A の極大元(または 極小元)が 存在するが 一意的でない例を与えよ.
順序集合 X = (X,) の部分集合 A に 対し て, つぎ の条件を 満たす b ∈ X を
(X におけ る) Aの上界[upper bound] (または, 下界[lower bound])という:
∀x∈A, b x (または bx)
もし Aの上界(または下界)bが Aの元であれば,それは Aの最大元(または最小 元)とな る. X におけ る A の上界(または 下界)が 存在するとき, Aは (X におい て)上に 有界[upper bounded] (または, 下に 有界[lower bounded]) であるといい, 上にも下にも有界であるとき,有界[bounded]であるという. Aが 上に有界(または 下に有界)であるとき, Aの最小上界[least upper bound](または最大下界[greatest lower bound]), すなわち, 上界の最小元(または 下界の最大元)を 上限[supremum]
(または 下限[infimum])といい, 存在すれば やは り一意的に 決まるので, supA (ま たは infA) と表す. 定義より, c∈X が c= supA (または c= infA)であること を示すには,つぎ の 2つの条件を確かめれば よい:
(i)∀x∈A, cx (または cx)
(ii) b∈X, (∀x∈A, bx (または b x)) ⇒ cb (または cb) 演習 4.7 全順序集合においては, (ii) はつぎ と同値であることを示せ: (ii’) ∀x < c (または ∀x > c), ∃a∈A such that x < a (または a < x)
演習 4.8 順序集合 X において,A ⊂B ⊂X とする. 共に最大元が 存在すると き, maxA maxB となること, 共に 上限が 存在するとき, supAsupB となる ことを示せ. 最小元と下限に 関し てはど んなことが いえ るか?
演習 4.9 集合X の巾集合 P(X) を包含関係⊂による順序集合と考えたとき, {A, B} ⊂P(X)の上限 sup{A, B}と下限 inf{A, B}はそれぞれ 何になるか.
順序集合X の順序を部分集合Y に制限すれば, Y 上の順序 Y が 得られ る. すなわち,
∀x, y ∈Y, xY y⇔
defxy
このとき, Y = (Y,Y) を X の部分順序集合[orderd subset] とい う. 全順序集合 の部分順序集合は 全順序集合である.
A⊂Y ⊂X の場合,A の上限と下限は X で考えるのか Y で考えるのかが 問題 となるので,つぎ のように 書いて区別する:
supX A, supY A, infXA, infY A
演習 4.10 順序集合 X において,A ⊂Y ⊂X とする.
(1) Aの上限に関して, supXAと supY Aが 共に存在すれば, supXAsupY Aが 成立することを示せ. また, 一般に =は 成立し ないが, その例を与えよ. 下限 に 関し て, 対応することを示し, =が 成立し ない例も与えよ.
(2) supX Aは 存在するが supY Aが 存在し ない例を与えよ. 下限に 関する同様な 例も与えよ.
(3) supY A は 存在するが supXAが 存在し ない例を与えよ. 下限に 関する同様な 例も与えよ.
演習 4.11 自然数の集合 N において, m ∈ Nが n ∈N で 割り切れ るとい う関 係 n|m は N 上の順序となることを 示せ. この順序に 関し て,n > 1が N\ {1} の 極小元となるためには, nが 素数となることが 必要十分であることを示せ.
演習 4.12 上記の順序集合 N= (N,|)におけ る{n, m} ⊂N の上限 sup{n, m} と下限 inf{n, m}はそれぞれ 何を意味するか?