基礎数理 室田 基本演習 問題 第１部：集合 vers. 2009-09-07
問題S1. S={1,2, . . . , n}の各要素の重みを表す実数w1, . . . , wnが与えられているとする．S の部分集合Aに対して，h(A) =∑
i∈Awi と定義される集合関数hがモジュラ等式 h(A) +h(B) =h(A∪B) +h(A∩B) を満たすことを示せ．
問題S2. S ={1,2, . . . , n}の各要素の重みを表す実数w1, . . . , wnが与えられているとする．S の部分集合Aに対して，f(A) = maxi∈Awi と定義される集合関数f が劣モジュラ 不等式f(A) +f(B)≥f(A∪B) +f(A∩B) を満たすことを示せ．
問題S3. 整数a, bに対してa−bが6の倍数のときにa∼bと定めることにより２項関係∼ を定義する．これが同値関係であることを証明せよ．
問題S4. 集合S = {(a, b) |a ∈Z, b ∈Z\ {0}} の上に２項関係∼を「(a, b) ∼ (a0, b0) ⇐⇒
ab0=a0b」で定義する．この２項関係∼が同値関係であることを証明せよ．
問題S5. 行列の集合の上に，「A∼B ⇐⇒ ある正則行列Pが存在してP−1AP =B」によっ て２項関係∼を定義する．
（１）この２項関係∼が同値関係であることを示せ．
（２）通常の行列の加算（和）を用いて，同値類の間に加算を定義しようとしても 上手くできないこと(well-definedでないこと) を説明せよ．
問題S6. 擬順序関係¹が与えられたとき，2項関係∼を「a∼b ⇐⇒ a¹bかつb¹a」に よって定義する．
（１）∼は同値関係になることを示せ．
（２）その同値類C1, C2, . . .の代表元をa1, a2, . . .とすると，同値類の間の2項関係
≤を「Ci ≤ Cj ⇐⇒ ai ∈ Ci, aj ∈ Cjに対しai ¹ aj」によって定義できること
（well-definedであること）を示せ．
（３）上で定義した2項関係≤は順序関係であることを示せ．
問題S7. 右図のグラフの強連結成分分解を求めよ．
q1 q2
q3 q 4
5q
q 6
1 6 1 PPPqPP
BB BBB N
6
-
?
問題S8. 劣モジュラ集合関数ρ(X)の最小値を与えるXの全体をLとすると，Lは分配束を成 すことを示せ．ただし，ρが劣モジュラであるとは，任意のX, Y に対して，ρ(X) + ρ(Y)≥ρ(X∪Y) +ρ(X∩Y) が成り立つことをいう．
問題S9. S = {a, b, c}上の同値関係，全順序，半順序，擬順序をすべて列挙せよ．ただし，
a, b, cの置換で入れ替わるものは同じとみなす．
問題S10. S ={a, b, c}上の部分集合からなる分配束で∅とSを含むものをすべて列挙せよ．た
だし，a, b, cの置換で入れ替わるものは同じとみなす．
以上
1
