情報数学 I-A 講義のポイント No - 東京理科大学

情報数学 I-A ^{講義のポイント} No.9

講義 (No.9) の内容 中間試験範囲の復習

集合（Set）

A, B 集合を表す記号

a∈A, b /∈B 集合の要素を表す記号

∅≡ { }空集合

包含関係 B⊂A^def⇔ ∀x∈B⇒x∈A

真部分集合 B$A^def⇔ ∀x∈B⇒x∈A かつ ∃x0∈A s.t. x0∈/B 等号A=B^def⇔ A⊂B かつ B⊂A (∀x∈B⇔x∈A)

和集合A∪B≡ {x; x∈A または x∈B}

共通集合A∩B≡ {x; x∈A かつ x∈B}

差集合A\B ≡ {x; x∈A かつ x /∈B}

補集合A^c≡X\A={x∈X; x /∈A}

対称差A△B ≡(A\B)∪(B\A)添え字の集合J の各要素αに J ∋α 7→ Xα を対応させて作られる集合

集合族A ≡ {X_α; α∈J}

和集合 ∪

α∈J

X_α 共通集合 ∩

α∈J

Xα

例１)J ={1,3,5}のとき，

集合族 A ≡ {X₁, X₃, X₅} 和集合 ∪

α∈J

Xα=X1∪X3∪X5

共通集合 ∩

α∈J

X_α=X₁∩X₃∩X₅

例２)J=N(自然数の全体)のとき，

集合族A ≡ {X1, X2, X3,· · · } 和集合 ∪

α∈J

Xα=

∪∞ k=1

Xk =X1∪X2∪X3∪ · · ·

共通集合 ∩

α∈J

X_α= ∩^∞

k=1

X_k=X₁∩X₂∩X₃∩ · · ·

定理 1 (1.1) 1. 交換律 A∪B=B∪A, A∩B =B∩A;

2. 結合律 (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C) ; 3. 分配律 (A∪B)∩C= (A∩C)∪(B∩C), (A∩B)∪C= (A∪C)∩

(B∪C) ;

4. 双補律 A∩A^c=∅, A∪A^c=X, (A^c)^c=A, X^c=∅;

5. ド・モルガン (A∪B)^c=A^c∩B^c, (A∩B)^c =A^c∪B^c, (∪

α∈J

A_α )_c

= ∩

α∈J

A^c_α, (∩

α∈J

A_α )_c

= ∪

α∈J

A^c_α;

直積集合

X×Y ≡ {(x, y) ; x∈X, y∈Y} 添え字の集合J の各要素αに

J∋α 7→ Xα を対応させて作られる集合 集合族A ≡ {X_α; α∈J}

直積集合∏

α∈J

X_α

例１)J ={1,3,5}のとき，

集合族 A ≡ {X₁, X₃, X₅} 直積集合 ∏

α∈J

X_α=X₁×X₃×X₅

例２)J =N(自然数の全体)のとき，

集合族A ≡ {X₁, X₂, X₃,· · · } 直積集合 ∏

α∈J

X_α=∏^∞

k=1

X_k=X₁×X₂×X₃× · · · 実数Rの部分集合

閉区間[a, b]≡ {x∈R; a5x5b}=線分ab 開区間(a, b)≡ {x∈R; a < x < b}

半開区間(a, b]≡ {x∈R; a < x5b}

半開区間[a, b)≡ {x∈R; a5x < b}

例３)J=N(自然数の全体)のとき，

集合族A ≡ {A1, A2, A3,· · · } ただし，An≡(₁

n,3−¹_n)

(n= 1,2,3,· · ·) 和集合 ∪

α∈J

A_α= ∪^∞

k=1

A_k = (0,3),共通集合 ∩

α∈J

A_α= ∩^∞

k=1

A_k = (1,2)

写像(mapping) f :X →Y

集合Xの各元xに集合Y の1つの元yを対応させる規則f のことをXか らY への写像という。

domf を写像f の定義域，ranf ≡ {f(x) ; x∈domf}を写像fの値 域という。

とくに，domf =Xのとき，写像fの値域は，f(X)≡ {f(x) ; x∈X}

で表される。

(1)A⊂Xに対して，f(A)≡ {f(x) ; x∈A}を，Aのfによる像という。

(2) B⊂Y に対して，f⁻¹(B)≡ {x∈X; f(x)∈B}を，Bのf による 原像という。

写像の種類

(1) 単射(1対1，one-to-one, injection)

(*)∀y∈ranf に対して，∃1x∈X s.t. y=f(x)

(**)∀x, x^′∈domf に対して，x̸=x^′ ⇒ f(x)̸=f(x^′) (2)全射(上への，onto, surjection)

(*)ranf =Y

(**)∀y∈Y に対して，∃x∈X s.t. y=f(x) (3)全単射(上への1対1，one-to-one onto, bijection) (*)全射かつ単射

補題 2 (1) f :X →Y

A⊂B ⇒ f(A)⊂f(B)

補題 3 (2) J=N(自然数の全体)のとき，集合族A ≡ {A1, A2, A3,· · · },集 合族B ≡ {B1, B2, B3,· · · }

A_α⊂B_α (∀α∈J) ⇒ ∪

α∈J

A_α⊂ ∪

α∈J

B_α

補題 4 (3) J =N(自然数の全体)のとき，集合族A ≡ {A1, A2, A3,· · · },集 合族B ≡ {B₁, B₂, B₃,· · · }

Aα⊂Bα (∀α∈J) ⇒ ∩

α∈J

Aα⊂ ∩

α∈J

Bα

定理5 (1.2) A={A_α⊂X; α∈J}, B={B_β ⊂Y; β ∈K}, f:X→ Y に対して次が成立する。

(1) f (∪

α∈J

Aα

)

= ∪

α∈J

f(Aα), f (∩

α∈J

Aα

)

⊂ ∩

α∈J

f(Aα) ;

(3) f⁻¹



∪

β∈K

Bβ



= ∪

β∈K

f⁻¹(Bβ), f⁻¹



∩

β∈K

Bβ



= ∩

β∈K

f⁻¹(sBβ)

A₁, A₂⊂X, B₁, B₂⊂Y, f :X →Y に対して次が成立する。

(4) B1⊃B2 のとき，f⁻¹(B1\B2) =f⁻¹(B1)\f⁻¹(B2) ; (5) A₁⊂f⁻¹(f(A₁)), f(

f⁻¹(B₁))

=B₁∩f(X), f(

A₁∩f⁻¹(B₁))

= f(A1)∩B1

１）直積集合とべき集合

添え字の集合J の各要素αにJ ∋α 7→ xα ∈Xα を対応させる写 像f（すなわち，f(α) =x_α (∀α∈J)）の全体を ∏

α∈J

X_αとかき，集合族 A ≡ {X_α; α∈J}の直積集合という。このf は，直積集合の要素

∏

α∈J

x_α または (x_α)_α∈J

で表せる（すなわち，同一視できる）。xαをf のα−座標という。直積集 合 ∏

α∈J

X_α に対して，X_α =X (∀α∈J) のとき，∏

α∈J

X_α を X^J

と表し，X を底とし，Jを指標とするべき集合（あるいは配置集合）とい う。とくに，X を２元集合とし，J =Aとすると，2^Aは，Aのすべての部 分集合からなる集合族と考えることができる。さらに，より一般に，B^Aは，

B^A≡ {f | f :A→B への写像の全体}

１）X上の関係R⊂X×X ≡ {(x, y) | x∈X, y∈X} RはX×X の部分集合

２）X上の同値関係R

i) 反射律 ∀x∈X に対して，(x, x)∈R ii) 対称律(x, y)∈R ⇒ (y, x)∈R

iii)推移律(x, y)∈R，(y, z)∈R ⇒ (x, z)∈R

上記のi)ii)iii)を満たす関係Rを同値関係という。

３）X 上の同値関係Rの例 ４）X上の関係Rの逆関係R⁻¹

R⁻¹≡ {(y, x) | (x, y)∈R}

５）X上の同値関係Rの同値類

[x]≡ {y∈X | (x, y)∈R}

[x]の要素xを代表元という。

６）X上の同値関係Rの同値類[x]の性質

定理 6 1. ∀x∈X に対して，x∈[x] よって，[x]̸=∅

2. (x, y)∈R ⇔ [x] = [y]

3. (x, y)∈/R ⇔ [x]∩[y] =∅ ７）X上の同値関係Rによる商集合

X/R≡ {[x] | x∈X} X = ∪

x∈X

[x]

８）X上の同値関係Rによる商集合XRの性質 1. ∀x∈X に対して，[x]̸=∅

2. [x]̸= [y] ⇔ [x]∩[y] =∅ 3. X = ∪

x∈X

[x]

上記の１.〜３.を満たすものを類別という。

９）Xの直和分割A ≡ {A_i⊂X; i∈J} A_i̸=∅ (∀i∈J) A_i∩A_k =∅ (i̸=k)

X =∪

i∈J

Ai

１０）X上の同値関係RとXの直和分割Aの関係について 定理 7 Xの直和分割Aに対して，X上の関係Rを

(x, y)∈R ^def⇔ ∃i∈J s.t. x, y∈Ai

で定めると，Rは，X上の同値関係である。

定理 8 X=Rを実数の全体とし，

(x, y)∈R ^def⇔ x−y∈Z

で定められたX上の関係RはX上の同値関係である。さらに，任意に固定 した実数pに対して，写像f_p: [p, p+ 1)→X/Rを

fp(x) = [x]∈X/R (∀x∈[p, p+ 1)) で定めると，f_pは，全単射である。

証明. (i)反射的： 任意のx∈Xに対して，x−x= 0∈Z ⇒ (x, x)∈R (ii) 対称的： (x, y)∈ R ⇒ x−y ∈Z ⇒ −(x−y) =y−x∈ Z ⇒ (y, x)∈R

(iii) 推移的： (x, y) ∈ R かつ (y, z) ∈ R ⇒ x−y ∈ Z かつ y−z∈Z

⇒ (x−y) + (y−z) =x−z∈Z ⇒ (x, z)∈R よって，RはX上の同値関係である。

全射性： 任意の[y]∈X/Rに対して，

∃x=y− ⌊y⌋+p∈[p, p+ 1) s.t. fp(x) = [x] = [y]∈X/R ここで，⌊y⌋は，ガウス記号（yを超えない最大整数）を表す。

単射性： 任意のx, y ∈ [p, p+ 1) かつ x ̸= y ⇒ f_p(x) = [x] ̸=

[y] =fp(y)

よって，f_pは，全単射である。