(2016/05/10更新) (PDFファイル)

数理構造特論
June 8, 2016
Contents
1 集合
1.1 自然数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 写像
2.1
2.2
2.3
2.4
2.5
ウォームアップ
諸定義の復習 .
像 . . . . . . .
全射・単射 . .
写像の応用例 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
6
9
9
9
9
10
10
3 関係
13
3.1 諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 半順序関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 同値関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 論理
4.1
4.2
4.3
4.4
ウォームアップ . .
量化子 . . . . . . .
自由変数, 束縛変数
含意「ならば」⇒ .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 述語論理
5.1 ウォームアップ (何かのアニメで聞いた様な話 · · · ) .
5.2 諸定義 . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 トートロジー (恒真式) . . . . . . . . . . . . . . . .
5.4 述語論理 . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
17
17
17
18
.
.
.
.
21
21
21
21
22
6 帰納法
25
6.1 ウォームアップ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 整礎関係 : 「関係」の世界での帰納法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7 証明 (その 1)
29
7.1 証明技法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.2 ウォームアップ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.3 背理法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
8 証明 (その 2)
35
8.1 鳩ノ巣原理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.2 無限降下法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3
9 順序
9.1
9.2
9.3
9.4
前順序 . . . .
全順序 . . . .
半順序 . . . .
半順序の次元
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
39
39
40
41
10 束
43
10.1 モティベーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
10.2 諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
10.3 応用例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
11 群
11.1 ウォームアップ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2 諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.3 対称群 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
47
47
48
12 閉包
49
12.1 ウォームアップ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
12.2 Closure systemt と closure operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
13 位相空間
13.1 ウォームアップ .
13.2 閉集合と開集合 .
13.3 近傍 . . . . . . .
13.4 開集合系と近傍系
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
51
51
52
52
14 マトロイド
55
14.1 諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
15 マトロイドと貪欲法
59
15.1 貪欲法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1. 集合
1.1. 自然数
自然数の役割
• 何個あるかの個数を数えるときに使う.
• 何番目という順番を数えるときに使う.
自然数ならではの性質
性質 N 自然数の空でない任意の部分集合 A は最小値を持つ.
実際, 先ず 0 ∈ A を調べ, 次に 1 ∈ A を調べ, 次に 2 ∈ A を調べと, 順にチェックして行き 1 最初に A に
含まれていた自然数が最小値になる.
• 整数 Z は性質 N を持たない. 例えば A = {i : i ∈ Z, i < 0} は最小値を持たない.
• 有理数 Q は性質 N を持たない. 例えば A = { 21k : k ∈ N} は最小値を持たない.
• 0, 1, 2, 3, . . . と自然数と同じ要素使うが, 0, 2, 4, . . . , 1, 3, 5, . . . の順番を持つ集合 (つまり偶数同士ま
たは奇数同士なら通常の大小関係で, 奇数と偶数なら偶数の方が小さいと) を擬自然数と呼ぶこと
にする. 擬自然数は性質 N を満たす.
• 自然数や擬自然数の要素を人だと思い, 彼等が病院で診察待ちをしている (診察時間は各人 1 分と
する). 自然数の人達は自然数での順番で診察室に呼ばれ, 擬自然数の人達は擬自然数での順番で
診察室に呼ばれる. 自然数の人たちはいずれは必ず呼ばれるが, 擬自然数の奇数の人たちはいくら
待っても呼ばれることはない.
• それでも擬自然数はまだ「次の人を呼出す」という行為ができるだけ, まだましである. 実数 R は
呼び出しすらできない. なぜなら “次の方” が決められないから. 後者関数のある自然数とは大違
いである! 有理数 Q は順番を変えれば呼出し可能にできる.
後者関数:次の方
• 自然数では, ある数 (i) の次の数 (i + 1) というものがきちんと決まっている.
• 順序を持つある集合 Q が性質 N を満たすなら, (最大でない) ある要素の次の要素を決めることが
できる.
• a の次の数を suc(a) で表すことにする.
• 実際, 各要素 a ∈ Q に対し Aa = {x ∈ Q : a < x} とすると, (Q は性質 N を満たすので)Aa は最小
値をもつ. その最小値を suc(a) とすればよい.
• 集合が順序を持つとはどういうことか? これについては後の章で説明する.
任意の元 a ∈ N に対して, N↓ [a] = {x ∈ N : x < a}
1
そもそもこのようなチェックはできるのか? 属する/属さないの判断や (1 章参照), 無限回のチェックなどは許されている
のか?
5
ペアノの公理
• 公理的集合論では “空集合の存在” を土台にして理論が構築されている.
• よって, 空集合のみを足掛りにして, 自然数 (と実質同じもの) を定義することを考える. 詳しくは
後の章を通して説明する.
• {} = ∅ := 0, {0} = {∅} := 1, {0, 1} = {∅, {∅}} := 2, {0, 1, 2} = {∅, {∅}, {∅, {∅}}} := 3, · · · .
• 集合の包含関係を自然数の大小関係に対応付けている. 例えば, 2 < 3 と言う大小関係は {∅, {∅}} ⊂
{∅, {∅}, {∅, {∅}}} という包含関係と対応している 2 .
• 数学的帰納法の原理が含まれている.
1.2. 集合
講義の最初の段階では, 先ずは集合を次の 2 つのことが判定できるような「モノの集まり」と考える.
1. ある「モノ」が集合に入っているかどうか判定可能. (帰属関係 ∈)
2. 2 つの「モノ」を集合から取り出したとき, それらが等しいか否か判定可能. (同値関係 =)
集合の表記法
• 外延的記法とはある集合 A = {0, 2, 4, 6, 8} のように集合に族する要素（元）をすべて書き表すもの.
• 内包的記法とは, A = {2x | 0 ≤ x ≤ 4, x は整数 } のように集合の要素が満たす条件を記したもの.
集合の等しさ
• 2 つの集合が互いに等しいということを定義するために以下の外延性公理を仮定する.
∀A∀B[A = B ⇔ ∀x(x ∈ A ⇔ x ∈ B)]
• これはどんな集合 A, B を持ってきても, A = B ならば ∀x(x ∈ A ⇔ x ∈ B) が成り立ち, ∀x(x ∈
A ⇔ x ∈ B) が成り立つなら A = B であること意味している.
部分集合
定義 1.2.1. 「∀x, (x ∈ A ⇒ x ∈ B)」が成立つとき A は B の部分集合であるといい, A ⊆ B で表す.
• 集合 A と B が等しいしことを言うには, A ⊆ B と B ⊆ A の 2 つを示せばよい.
• 何故なら, 2 つが言える事で, 外延性の公理が言えるからである.
• 2 つの数 a, b が等しいこと, つまり a = b を示すには, a ≤ b と b ≤ a の 2 つを示せばよいことに類
似している.
• この類似は, ≤ と ⊆ の類似性 (節 3.2 参照) に関係している.
例 1.2.1. 「A は B の部分集合である」の否定「A ̸⊆ B 」を考える
2
• 定義より ¬(∀x, x ∈ A ⇒ x ∈ B) を考えればよい.
• これを書き換えると, ∃x s.t. ¬(x ∈ A ⇒ x ∈ B) となる.
• さらに書き換えると, ∃x s.t. ¬[¬(x ∈ A) ∨ (x ∈ B)] となる.
何故こう書き換えてよいかの詳細は, 4 章で説明する.
• さらに書き換えると, ド・モルガンの法則より ∃x s.t. (x ∈ A) ∧ (x ̸∈ B) となる.
これに関係して “順序数” という概念があるが, 本講義では扱わない.
空集合
• 「要素を 1 つも持たない集合が存在する」という考えをとるとき (つまり空集合の公理を仮定した
とき), その集合を空集合と呼び, 通常 ∅ で表す.
• つまり, 「∃A s.t. ∀x, x ∈
/ A」を仮定するとき, この A を通常は ∅ で表す, ということ.
• そのような A は何種類もあるかもしれない. つまり A1 ̸= A2 が共に空集合と呼べるかもしれない
のに, A1 を ∅ で表し, 同時に A2 を ∅ で表すと, 混乱しないのか？
• 異なる２つのものに, 同じ記号を割り当てることは危険である. (練習問題 2.3.3 参照)
• 実は, 後で示すとおり, 空集合は一意に決まる.
• ∀x, x ∈
/ ∅ は ∀x, ¬(x ∈ ∅) と書き換えてよい.
補題 1.2.1. 空集合 ∅ はすべての集合の部分集合である.
証明
• 背理法で示す. 先ず矛盾 ∅ ⊈ A を仮定する.
• このとき, 例 1.2.1 より, (x ∈ ∅) ∧ (x ̸∈ A) を満たす元 x が存在する.
• しかし
(
)
∃x s.t. x ∈ ∅ ⇔¬ ¬(∃x s.t. x ∈ ∅)
)
(
⇔¬ ∀x, ¬(x ∈ ∅)
となり, これは空集合の定義に反する．
• よって，任意の集合 A に対し ∅ ⊆ A が成り立つ．
□
補題 1.2.2. 空集合はただ 1 つ存在する.
証明
• A, B を共に空集合とする.
• 補題 1.2.1 を使うと,
– A が空集合より, A ⊆ B, つまり ∀x, x ∈ A ⇒ x ∈ B.
– B が空集合より, B ⊆ A, つまり ∀x, x ∈ B ⇒ x ∈ A.
• よって, ∀x(x ∈ A ⇔ x ∈ B) となり，外延性公理より A = B.
□
べき集合
定義 1.2.2. 集合 X のべき集合とは 2X := { 集合 A | A ⊆ X} のことである.
例 1.2.2.
• 2∅ = {∅} ̸= ∅. つまり:
– 2∅ は ∅ という集合だけからなり (i.e., 2∅ = {∅}),
– (∅ という集合を持つので)2∅ は空集合ではない, (i.e., 2∅ ̸= ∅).
{
}
• X = {a, {a}} のとき 2X は ∅, {a}, {{a}}, {a, {a}}
A = {a1 , a2 , . . . , an } と外延的に書け, 要素の個数が n 個とする. このとき 2 の要素数は 2 である.
A
n
順序対
我々が普段目にする順序対 (a, b) は, 集合論では (a, b) := {{a}, {a, b}} として定義される.
• a = b のときは {{a}, {a, b}} = {{a}, {a, a}} = {{a}, {a}} = {{a}} となり, うまくいっている.
• {a} ⊊ {a, b} より {a} と {a, b} が区別できるため, (a, b) = (a′ , b′ ) ⇔ (a = a′ ) ∧ (b = b′ ) がいえる.
直積
定義 1.2.3. 集合 X と Y に対し, 集合 {(x, y) | x ∈ X ∧ y ∈ Y } を直積と呼び, X と Y の X × Y で
表す.
練習問題 1.2.1. “X × A = X × B ならば A = B” は正しいか？
• 上の言っていることは, 2 つの実数 a, b に対し, “x × a = x × b ならば a = b” は正しいか？と構造的
に等しい. a ̸= b でも x = 0 なら x × a = x × b が成立つ.
• × の記号とも相性がよい. 0 = 0 × |A| = |∅ × A| = |∅|.
2. 写像
2.1. ウォームアップ
次のパズルについて考える.
• 箱に赤 (R), 黄色 (Y ), 緑 (G) の 3 色のボールが幾つか入っている. 箱の中からランダムにボールを
2 個取り出し, 次のルールに従い (必要なら) ボールを箱に追加する: 取り出した 2 個のボールが,
–
–
–
–
–
–
{R, R} ならば, 追加しない.
{Y, Y } ならば, G1 個と R2 個追加.
{G, G} ならば, Y 2 個と R4 個を追加.
{R, Y } ならば, R6 個を追加.
{R, G} ならば, Y 1 個と R2 個を追加.
{Y, G} ならば, Y 2 個と R1 個を追加.
• 箱の中にボールが 100 個入っている (R, Y , G の割合は分からない). ルールに従い 2 個取り出すと
いう操作を繰り返すが, この操作の繰返しはどこかで必ず止まるか?
2.2. 諸定義の復習
定義 2.2.1.
• 任意の元 x ∈ X に対して, Y の元 f (x) がただ 1 つ対応するとき, この対応 f を写像といい,
f : X → Y で表す．
• f : X → Y が単射とは, 「x1 , x2 ∈ X で x1 ̸= x2 」ならば, 「f (x1 ) ̸= f (x2 )」を満たすことで
ある
• g : X → Y が全射とは, 「任意の y ∈ Y に対して, 「g(x) = y 」を満たすような x ∈ X が存在
することである.
• 写像 f : X → Y と集合 A ⊆ X に対して，集合 {f (x) ∈ Y | x ∈ A} を f による A の像と呼
び, f (A) で表す. また, f (X) を f の値域という.
• B ⊆ Y に対して, 集合 {x ∈ X | f (x) ∈ B} を f による B の逆像と呼び, f −1 (B) で表す.
2.3. 像
練習問題 2.3.1. 写像 f : X → Y に対し, 集合 A, B を A ⊆ B なる集合とする. このとき, f (A) ⊆
f (B) を証明せよ.
練習問題 2.3.2. f (A ∪ B) = f (A) ∪ f (B) を証明せよ.
9
練習問題 2.3.3. 以下は “f (A ∩ B) = f (A) ∩ f (B)” を証明しようとしている. しかし誤りがある.
誤りを見つけよ. また修正するにはどうすればよいか考えよ.
• 先ず f (A ∩ B) ⊆ f (A) ∩ f (B) を示す.
–
–
–
–
y を f (A ∩ B) の任意の元とする. f (A ∩ B) の定義から, ∃x ∈ A ∩ B s.t. y = f (x).
A ∩ B ⊆ A より x ∈ A となる. よって f (x) = y ∈ f (A) が成立つ.
A ∩ B ⊆ B より x ∈ B となる. よって f (x) = y ∈ f (B) が成立つ.
よって y ∈ f (A) ∩ f (B) となるので f (A ∩ B) ⊆ f (A) ∩ f (B) が成立つ.
• 次に f (A) ∩ f (B) ⊆ f (A ∩ B) を示す.
– y を f (A) ∩ f (B) の任意の元とする. f (A) ∩ f (B) の定義から,
∗ ∃x ∈ A s.t. y = f (x) (y ∈ f (A) より) かつ
∗ ∃x ∈ B s.t. y = f (x) (y ∈ f (B) より)
が成り立つ.
– よって, x ∈ A かつ x ∈ B より, x ∈ A ∩ B が成立つ. 故に, f (x) = y ∈ f (A ∩ B) となる.
– したがって, f (A) ∩ f (B) ⊆ f (A ∩ B) が成立つ.
2.4. 全射・単射
練習問題 2.4.1. X を有限集合とし, f : X 7→ X を全単射とする. このとき f が恒等写像となるよ
うな整数 n が存在すること示せ. またこのことは X が無限集合では一般に成り立たないことも示せ.
n
2.5. 写像の応用例
• 2 つの (有限) 集合でどちらが要素数が多いかを知りたいだけなら, それらの要素数を知る必要は
ない.
• 2 つの集合の要素数はいくつかと聞かれているわけではない. どちらが多いかと聞かれている.
練習問題 2.5.1. n + 1 角形の三角形分割の仕方の個数と n 文字の 2 部分割の仕方の個数ではどちらが
(
)
多いか？例えば
n)= 5 文字の
2 部分割の一例として ABCDE → (AB)·(CDE) → (A·B)· (CD ·E) →
(
)
(A · B) · (C · D · E が考えられる.
解答
• 以下の図のような 1 対 1 の対応があるので, 同じになる. これはカタラン数としてよく知られて
いる.
• 以下の図は n = 4 での全ての対応 (5 パターン) を示している. 対応のさせ方は, 5 角形の赤い特別
な辺を通るように考え, 赤い矢印の先に進むとその先が 2 分されている. この 2 分が文字の分割方
法を表している.
A
D
B
C
(((AB)C)D)
A
D
B
C
((A(BC))D)
A
D
B
C
((AB)(CD))
A
D
B
C
(A((BC)D))
A
D
B
C
(A(B(CD)))
□
3. 関係
3.1. 諸定義
定義 3.1.1.
•
•
•
•
集合 A1 と A2 の (間の) 関係とは，直積 A1 × A2 の部分集合 R ⊆ A1 × A2 のことである.
順序対 (x, y) ∈ A1 × A2 が R に含まれるとき，xRy で表す.
逆に (x, y) ∈ A1 × A2 が R に含まれないとき，x̸ R y で表す.
A2 = A1 のとき, R を集合 A1 上の関係と呼ばれる. つまり, 集合 A 上の関係とは A × A の部
分集合 R ⊆ A × A のことである.
• A1 × A2 上ではなくより一般化し, A1 × A2 × . . . × An 上でも関係が定義できる. 特に A1 × A2
上の関係は, 二項関係と呼ばれる.
定義 3.1.2. R を S 上の関係とし, T ⊆ S とする.
• ある要素 x ∈ S が T の (R に関しての) 極小元とは,
– R が ∀z ∈ S, z̸ R z の場合 (< のような場合)
∗ (x ∈ T ) かつ (¬(∃y ∈ T, yRx)) が成立つときをいう. (cf. 4.7.1 節:[15])
∗ (x ∈ T ) かつ (∀y ∈ T, y̸ R x) が成立つときをいう. (cf. 2 章:[12], 定義 26:[22]))
– R が ∀z ∈ S, zRz の場合 (≤ のような場合)
∗ ∀y ∈ T, yRx ⇒ y = x. (cf. 定義 4.18:[18], 定義 4.4.4:[23])
– 同様に, ある要素 x ∈ S が T の (R に関しての) 極大元とは, x ∈ T かつ ∀y ∈ T, x̸ R y が
成立つときをいう.
• 極大元や極小元が存在しない場合がある.
(1, 3)
(3, 0)
等号が付かない場合
(2, 2)
(1, 2)
(0, 2)
(2, 1)
(1, 1)
(0, 1)
(2, 0) T
(1, 0)
(0, 0)
• ((0, 1) ∈ T ) かつ (¬(∃y ∈ T, y<(0, 1))) が成
立つ.
• ((0, 1) ∈ T ) かつ (∀y ∈ T, y̸<(0, 1)) が成立
つ.
等号が付く場合
• ∀y ∈ T, y≤(0, 1) ⇒ y = (0, 1)
13
定義 3.1.3. (推移閉包と反射閉包) R を集合 A 上の関係とする.
• R1 = ∪R, Rn = {(a, b) | a = x0 , b = xn , x0 Rx1 , x1 Rx2 , . . . , xn−1 Rxn } (n ≥ 2) とすると,
R+ = i=1,2,.. Ri を関係 R の推移閉包と呼ぶ.
• R0 = {(a, a) | a ∈ A}(反射的) とすると, R′ = R ∪ R0 を関係 R の反射閉包と呼ぶ.
∪
• R∗ = i=0,1,.. Ri は反射的推移閉包と呼ばれる.
3.2. 半順序関係
定義 3.2.1. 関係 ⪯ ⊆ A × A で，以下の三条件をみたすものを (反射的な) 半順序関係という．(半
順序関係を表すための R として ⪯ を使用している)
1. 任意の a ∈ A に対して a ⪯ a （反射律）
2. a ⪯ b かつ b ⪯ a ならば a = b（反対称律）
3. a ⪯ b かつ b ⪯ c ならば a ⪯ c （推移律）
反射律と反対称律を非反射律「∀a ∈ A, ¬(a ≺ a)」に置き変えて (⪯ ではなく ≺ に注意) 半順序関係
を考える場合もある. そのような場合は, (非反射的な) 半順序関係と呼ばれる.
1. 任意の a ∈ A に対して ¬(a ≺ a) （非反射律）
2. a ≺ b かつ b ≺ c ならば a ≺ c （推移律）
練習問題 3.2.1. N = {1, 2, 3, . . .} とする. a, b ∈ N に対して a が b の約数であることを a | b で表す
ものとする. a | b と a ≤ b は似ている.
1. a | b と b | a が成立つとき a と b にはどんな関係が成立つか?
2. a | b と b | c が成立つとき a と c にはどんな関係が成立つか?
解答
1.
2.
•
•
•
•
•
•
•
•
•
•
•
a | b より, ∃s ∈ N s.t. b = a · s.
b | a より, ∃t ∈ N s.t. a = b · t.
a = b · t = (a · s) · t = a · st.
よって a ∈ N(つまり a ̸= 0) より st = 1.
したがって, s, t ∈ N より s = t = 1, つまり a = b.
結局, 反対称律が言えたという事.
a | b より, ∃s ∈ N s.t. b = a · s.
b | c より, ∃t ∈ N s.t. c = b · t.
c = b · t = (a · s) · t = a · st.
st ∈ N より, ∃st ∈ N s.t. c = a · st といえるので, a | c がいえる.
結局, 推移律が言えたという事. 証明はして無いが, もちろん反射律も言える.
□
定義 3.2.2. S をある集合とし, A ⊆ 2S とする. A が S の分割 (partition) であるとは, 以下を満た
すときをいう:
1. ∀A1 , A2 ∈ A s.t. A1 ̸= A2 , A1 ∩ A2 = ∅,
∪
2. A∈A A = S.
定義 3.2.3. S をある集合とし, A, B を S の分割とする. A が B の細分 (refinement) であるとは,
∀A ∈ A, ∃B ∈ B s.t. A ⊆ B を満たすときをいう. A が B の細分のとき, A ⊑ B で表す.
練習問題 3.2.2. S をある集合とし, A, B, C を S の分割とする.
1. A ⊑ B と B ⊑ A が成立つとき, A と B にはどんな関係が成立つか?
2. A ⊑ B と B ⊑ C が成立つとき, B と C にはどんな関係が成立つか?
解答
1. A = B が成り立つ.
• 実際, 定義より A ∈ A ならば A ⊆ B なる B ∈ B が存在し, 同様に B に対しても B ⊆ A′ なる
A′ ∈ A が存在する.
• このとき A = A′ でなければならない. ∵ A ̸= A′ とすると, A ⊆ B ⊆ A′ より, A ∩ A′ ̸= ∅. 一
方 A は分割で A, A′ ∈ A(および今仮定している A ̸= A′ ) より A ∩ A′ = ∅ でなければならず,
矛盾.
2. A ⊑ C が成り立つ.
• 定義より A ∈ A ならば A ⊆ B なる B ∈ B が存在し, 同様に B に対しても B ⊆ C なる C ∈ C
が存在する.
• これは, A が C の細分であることを意味している.
□
3.3. 同値関係
定義 3.3.1. 関係 ∼ ⊆ A × A で，以下の三条件をみたすものを同値関係という．(同値関係を表す
ための R として ∼ を使用している)
1. 任意の a ∈ A に対して a ∼ a （反射律）
2. a ∼ b ならば b ∼ a （対称律）
3. a ∼ b かつ b ∼ c ならば a ∼ c （推移律）
練習問題 3.3.1.
• 100 の頭を持つ竜がいる.
• 騎士がその竜の首を切り落とすのだが, 4 パターンある. 切り落としたときに, 1 本でも頭が残っ
ていれば:
–
–
–
–
騎士は１５切り落とすが, その後すぐに２４の頭が生えてくる
騎士は１７切り落とすが, その後すぐに２の頭が生えてくる
騎士は２０切り落とすが, その後すぐに１４の頭が生えてくる
騎士は５切り落とすが, その後すぐに１７の頭が生えてくる
• つまり, 竜を倒すには, １５，１７，２０または５本の時に頭を切り落とせばよい.
• どのようにすれば, 竜を倒せるか？
解答
• どうやっても, 竜は倒せない.
• 竜の頭の数で同値類を作る：3 の倍数のときを赤で, 3 の倍数+1 のときを青で, 3 の倍数+2 のとき
を緑で表すことにする.
• 最初の状態は頭の数が 100 なので, 青である.
• そのような切り落とし方をしても, 3 の倍分しか頭の数は増減しないので, 状態は青のままである.
• 一方, 竜を倒せる直前の状態は,
–
–
–
–
15 = 3 · 5, つまり赤,
17 = 3 · 5 + 2, つまり緑,
20 = 3 · 6 + 2, つまり緑,
5 = 3 · 1 + 2, つまり緑
となっているので, つまり竜が倒せる状態にはできないということ.
□
練習問題 3.3.2. G = (V, E) を無向グラフとする. u, v ∈ V に対し, u と v を結ぶパスが G 内に存在
することを u ⇝ v で表すものとする. このとき, ⇝ は同値関係であることを証明せよ
解答
証明のスケッチを与える.
• 反射律：u から u への長さ 0 のパスが存在する.
• 対称律：u から v へのパス P が存在するならば, P を v から u へ辿ることで, それが u から v への
パスとなる.
• 推移律：u ⇝ v より u から u へのパス P1 が存在する. また, v ⇝ w より v から w へのパス P2 が存
在する. よって, u から w へのパス P1 · P2 が存在する.
□
4. 論理
4.1. ウォームアップ
次のパズルについて考える.
• 正直村と嘘つき村があり, どちらの村民も質問に対し YES(TRUE) か NO(FALSE) で答える.
• どちらの村民かは外見からは区別できない.
• 正直村の村民は必ず正しい答 (TRUE なら YES を, FALSE なら NO) を返し, 嘘つき村の村民は必
ず正しくない答 (TRUE なら NO を, FALSE なら YES) を返す.
• 正直村と嘘つき村の分岐点に, ある人が立っている. 正直村の道を知りたいあなたは, この人に 1 回
だけ質問できる. なんと質問すればよいか?
4.2. 量化子
• 否定の移動
– ¬(∀ xP (x)) ⇔ ∃x s.t. ¬P (x)
– ¬(∃x s.t. P (x)) ⇔ ∀x ¬P (x)
• 量化子の順序
– ∀ と ∃ の順番を入れ換えると意味が変わる.
∗ L(x, y) は, 「x は y を好いている」を意味するとする.
∗ ∀g, ∃b, [L(b, g)]: 各女子は、少なくとも 1 人の男性に好かれている.
∗ ∃b, ∀g, [L(b, g)]: すべての女子を好いている男性がいる.
– ∀ 同士または ∃ 同士の順番を入れ換えても意味は変わらない.
• 記号の略記
[
]
– ∀z ∈ Z, P (z) := ∀z, [(z ∈ Z) ⇒ P (z)] よって Z = ∅ のとき ∀z ∈ Z, P (z) は真.
– ∃z ∈ Z, P (z) := ∃z, (z ∈ Z) ∧ P (z) よって Z = ∅ のとき ∃z ∈ Z, P (z) は偽.
練習問題 4.2.1. 以下の意味を考えよ
どんな攻撃 A に対しても, 防御法 D が存在する.
4.3. 自由変数, 束縛変数
• ある変数 x を持つ式 f があり
∫ ∞ , 変数 x の値が決まらないと式 f の値が決まらない場合があるが, 決
まる場合もある. 例えば 0 f (x)dx の場合である. この例のような式の値に影響しない変数と,
f (x) = x + 2 のような式の値に影響する変数を区別したい.
• 論理式の世界でこのような区別をするときには, 以下の 2 つを区別することになる: 量化子のかか
る変数を束縛変数 (bound variable) といい, 量化子のかからない変数を自由変数 (free variable) と
いう.
17
• even(x): 自然数 x が偶数なら真, 奇数なら偽とする.
– x が具体的に分からないので even(x) は真か偽か分からない.
– 一方 “∀x ∈ N, even(x)” は偽である.
∫∞
∑
• もっと広い範囲で見れば, ∀, ∃ の量化子はかかっていないが, 10
i=1 i の i や, 0 f (x)dx の x も束縛
変数である. 変数 i や x の値は確かに変動するが, それらの動く範囲は確定しているので, それぞれ
の式の値は動かない, つまり確定できる. x + 2 の x は自由変数で, x 値が確定しない限り, その式
の値も確定できない. (cf. [26])
• 自由変数を全く含まない論理式は閉論理式 (closed formula) と呼ばれる.
4.4. 含意「ならば」⇒
• 一般に含意は理解しにくい面があるため, 少し説明する.
• ⇒ を真理値表で表すと以下となる：
P
0
0
1
1
Q
0
1
0
1
P ⇒ Q ¬P ∨ Q
1
1
1
1
0
0
1
1
• 上の真理値表から [P ⇒ Q] ⇔ [¬P ∨ Q] の等価性が成り立つ.
• 論理学での含意の理解する上で, P が成り立てば Q も成り立つ」と考えるより, むしろ「P が成り
立たないか, または Q が成り立つ」と考えた方が理解し易い.
例 4.4.1 (例 1.2.1). 「A は B の部分集合である」の否定 A ̸⊆ B を考える.
⇔
⇔
⇔
⇔
¬(∀x, x ∈ A ⇒ x ∈ B)
(否定を考えるので)
∃x s.t. ¬(x ∈ A ⇒ x ∈ B)
(否定の移動)
∃x s.t. ¬(¬(x ∈ A) ∨ (x ∈ B))
(含意の書き換え)
∃x s.t. (x ∈ A) ∧ ¬(x ∈ B)
(ド・モルガン)
∃x s.t. (x ∈ A) ∧ (x ̸∈ B)
(” 属さない” の省略形)
補題 4.4.1. [補題 1.2.1] 空集合 ∅ はすべての集合の部分集合である.
証明
[別証明]
• 集合 A が集合 B の部分集合であるという定義 1.2.1 「∀x, x ∈ A ⇒ x ∈ B 」を思い出そう.
• したがって, 「∀x, x ∈ ∅ ⇒ x ∈ B[ 」が真であることを言えばよい.
]
• 「∀x, x ∈ ∅ ⇒ x ∈ B 」は「∀x, (x ∈ ∅ が成り立たない) ∨ (x ∈ B が成り立つ) 」に書き換えら
れる.
[
]
• 「∀x, (x ∈ ∅ が成り立たない) ∨ (x ∈ B が成り立つ) 」は真である. 何故なら下線部が真になる
から.
□
例 4.4.2. [5 章:[28]]
• 「奇数の 2 乗は奇数である」は, ∀x[odd(x) ⇒ odd(x2 )] となる.
• ∀x[odd(x) ∧ odd(x2 )] では駄目.
• 例えば, x として偶数を取ると成り立たないから.
• 「2 乗すると奇数になるような奇数が存在する」は, ∃x s.t. odd(x) ∧ odd(x2 ) となる.
• ∃x s.t. odd(x) ⇒ odd(x2 ) では駄目.
• 含意の書き換えにより, ¬odd(x) ∨ odd(x2 ) と書き換えられる. このとき例えば, x として偶数
を取ると (¬odd(x) が) 成り立ってしまう.
例 4.4.3.
• [∃x, P (x)] ∨ [∃x, Q(x)] ⇔ ∃x, [P (x) ∨ Q(x)]
– 左辺 ⇒ 右辺を示す. 左辺から P を満たす x が存在するか, または Q を満たす x が存在す
る. そのような x を取ってくれば右辺が成り立つ.
– 左辺 ⇐ 右辺を示す. 右辺から P または Q を満たす x が存在する. そのような x を取って
くれば左辺が成り立つ.
• [∃x, P (x)] ∧ [∃x, Q(x)] ⇐ ∃x, [P (x) ∧ Q(x)]
– 左辺 ⇐ 右辺を示す. 右辺から P も Q も満たす x が存在する. そのような x を取ってくれ
ば左辺が成り立つ.
– 左辺 ⇒ 右辺の反例を示す. x を自然数 N から取るとして, P を偶数なら真, Q を奇数なら
真とする. このとき, 左辺は成り立つが右辺は成り立たない.
5. 述語論理
5.1. ウォームアップ (何かのアニメで聞いた様な話 · · · )
•
•
•
•
•
好きな自然数を頭の中で思い浮かべる.
それを 2 倍する
そこから 6 を引く
それを 2 で割る
それから最初に思い浮かべた数を引く
その結果は · · ·
5.2. 諸定義
• 命題: 真偽が確定してる文
例: 「4 は偶数である」という文
大事な点：“真でなければ偽”(またはその逆) が言える事.
• 命題変数: 命題を値としてとる変数
例: P , P として「4 は偶数である」の命題を代入する.
• 論理結合子: 論理積 ∧, 論理和 ∨, 含意 ⇒, 否定 ¬
例:
–
–
–
–
P に「3 は偶数」を代入する.
Q に「4 は偶数」を代入する.
すると, P , Q がともに真となる.
P が偽, Q が真となるので, 「P ⇒ Q」は真となる.
• 論理式: 以下のように再帰的に定義される.
1. 命題変数は論理式である.
2. A, B がともに論理式ならば, (A ∩ B), (A ∪ B), (A ⇒ B), (¬A), はいずれも論理式である.
⇒
∧
B
⇒
∨
A
B
A
B
Figure 5.1: 論理式 ψ:(A ∨ B) ∧ (A ⇒ B) ⇒ B を木を使った表現.
5.3. トートロジー (恒真式)
トートロジー (恒真式): 命題変数の値に関係なく常に真となる論理式のこと. (ウォームアップの, 思い
浮かべた数に関係なく常に 1 となるのと似ている)
21
例:
•
•
•
•
•
兄 A と弟 B の (実の) 兄弟がいる. 兄弟のうち少なくとも一方は 18 歳未満である.
当たり前だが, もし兄 A が 18 歳未満なら弟 B も 18 歳未満である.
命題 A:“兄 A は 18 歳未満である”, 命題 B:“弟 B は 18 歳未満である” とする.
このとき次の論理式 ψ を考える: ψ:(A ∨ B) ∧ (A ⇒ B) ⇒ B
ψ の意味するところは, “(兄弟のうち少なくとも一方は 18 歳未満) かつ (兄 A が 18 歳未満なら弟
B も 18 歳未満) ならば (弟 B は 18 歳未満)” である.
• 命題 A, B の真偽に関係なく, ψ は常に真となる, つまり ψ はトートロジー. 以下の真理値表で確認
できる.
A
0
0
1
1
B (A ∨ B) (A ⇒ B) (A ∨ B) ∧ (A ⇒ B)
0
0
1
0
1
1
1
1
0
1
0
0
1
1
1
1
ψ
1
1
1
1
5.4. 述語論理
• 命題 (真偽が確定してる文) の主語 (対象) と述語 (性質, 関係) を分離することで, 命題間の論理的
な関係が議論できるようになる. [cf. 4.1 節 [27], [25]]
例: 文: 4 は (主語) 偶数である (性質).
– 命題論理ではこの文を分解せず 1 つの文として捉える.
∗ 命題変数 P に「4 は偶数である」という文を代入する, という考えになる.
∗ P に代入する命題 (文) が決まれば, 命題変数 P の真偽も決まる.
– 一方, 述語論理では, 主語と述語に分解して考える.
∗ x を自然数を値としてとる変数とし, F (x) を x が偶数ならば真, そうでなければ偽をとる
関数を考える, という考え方.
∗ x に代入する主語 (対象, ここでは自然数) が決まれば, F (x) の真偽も決まる. ここに, 主
語と述語に分離されている意味がある.
• 述語論理を構成する部品
– 関数記号: Dn → D
関係を表す.
– 述語記号: Dn → {T, F}
性質 (または関係) を表す.
– ここで n はアリティと呼ばれる引数の個数を表す数.
∗ NextZ(x) は x + 1 を意味する関数記号.
例:
∗ IsNextZ(x, y) は y = x + 1 のとき真で, それ以外は偽を表す述語記号.
– 項:
∗ 固体変数 (x:自然数を値にとる) や固体定数 (4 という特定の自然数) は項である.
∗ f を n 変数の関数記号で, t1 , . . . , tn が項ならば, f (t1 , . . . , tn ) も項である.
– 量化子 (quantifier): ∀(全称量化子) や ∃(存在量化子) のこと.
– 原子論理式: P (t1 , . . . , tn ) のこと. ここで, ti は項, P はアリティn の述語記号.
• 論理式の帰納的定義
1. 原子論理式は論理式である.
2. P, Q が論理式であるとき, ¬P, P ∧ Q, P ∨ Q, P ⇒ Q は論理式である.
3. P が論理式で, x が個体変数であるとき, ∀xP (x), ∃xP (x) は論理式である.
例 5.4.1. 「x は偶数である」を述語論理で表すと：∃y,
(
(
Z(y) ∧ E W (y), x
))
• Z(x): x が整数なら真, そうで無いなら偽となる, アリティ1 の述語記号
• W (x): Z 7→ Z で, 2x を値として返すアリティ1 の関数記号
• E(x, y): Z2 7→ Z で, x = y が整数なら真, そうで無いなら偽となる, アリティ1 の述語記号
帰納的定義より論理式
z
}|
z
帰納的定義より論理式
}|
述語記号, つまり原子論理式
}|
{
( z }| {
( z }| { 固体変数
z}|{ ) )
∃y,
Z(y) ∧ E W (y), x
述語記号なので
原子論理式
z
{
{
関数記号
例 5.4.2. グラフ G = (V, E) に対し, 3 彩色可能問題は以下のように表現できる.
∃R∃B∃Y s.t.
[
]
∀v (R(v) ∧ ¬B(v) ∧ ¬Y (v)) ∨ (¬R(v) ∧ B(v) ∧ ¬Y (v)) ∨ (¬R(v) ∧ ¬B(v) ∧ Y (v)
∧
[
]
∀u, v E(u, v) ⇒ ¬ (R(u) ∧ R(v)) ∨ (B(u) ∧ B(v)) ∨ (Y (u) ∧ Y (v))
例 5.4.3. 以下の論理式は自然数の性質「空でない任意の部分集合 A は最小値を持つ」を表している.
[(
)
(
)]
∀A ⊆ N ∃x s.t. x ∈ A ⇒ ∃y ∈ A s.t. ∀z[z ∈ A ⇒ y ≤ z]
例 5.4.4.
(∃y ∀x P (x, y)) ⇒ (∀x ∃y P (x, y))
は真となる. 実際,
• ⇒ の左辺が真であれば, y として左辺を満たすある y ′ が存在することになり,
• ⇒ の右辺の y として y ′ を取れば右辺が成り立つ.
6. 帰納法
6.1. ウォームアップ
練習問題 6.1.1. 赤と青のボールが幾つかある. 「n 個のボールを 1 列に並べたとき, それらすべて
のボールの色は等しい」という命題を P (n) で表す.
以下は P (n) がすべての n に対して成り立つことを証明しようとしている. どこに誤りがあるか？
• P (1) は明らかに成り立つ (1 個しかないので)
• 帰納法の仮定としてボールの個数が n のとき P (n) 成り立つとして, P (n + 1) が成り立つことを以
下に示す.
–
–
–
–
ボールを左から右に n + 1 個並べる.
左から n 個のボールは仮定よりすべて等しい.
右から n 個のボールは仮定よりすべて等しい.
よって全体で色は等しい.
練習問題 6.1.2. 命題 P に対する数学的帰納法は, 以下の 2 つを示すことでなされる:
1. P (1) が成り立つ事,
2. 任意の自然数 k に対して, P (k) ⇒ P (k + 1) が成り立つ事.
このとき, P (i) の i は自然数であることが多いが, 自然数を考えなければいけないのであろうか？
卵が先か鶏が先か? 次のような堂々巡り (無限降下) を避けるために, 帰納法では, 初期段階にあたる “
礎 (いしずえ)” が必要になる.
• 卵があれば, それを産んだ鶏がいる.
• どの鶏も, 最初は卵だった.
6.2. 整礎関係 : 「関係」の世界での帰納法
無限降下列と整礎
• <R を X 上の二項関係とする. x1 >R x2 >R x3 >R · · · なる無限列を無限降下列と呼ぶ.
• 次の定義は無限降下列と深く関係する.
定義 6.2.1. X 上の二項関係 <R が「空で無い任意の (X の) 部分集合 Y に対して, Y は極小元
を持つ」という性質を満たすとき, 整礎 (well-founded) であるという.
25
• 整礎を論理式で表わすと以下のようになる. (最後は y = z と成り得るので z ̸≤ y ではなく z ̸< y と
なる).
[(
)
(
)]
∀Y ⊆ X Y ̸= ∅ ⇒ ∃y ∈ Y s.t. ∀z[z ∈ Y ⇒ z ̸< y]
• 以下は “空でない任意の部分集合 A は最小値を持つ” という自然数の性質を表している. N は全順
序なので, z ̸< y ならば y ≤ z となる.
[(
)
(
)]
∀A ⊆ N A ̸= ∅ ⇒ ∃y ∈ A s.t. ∀z[z ∈ A ⇒ y ≤ z]
定理 6.2.1. [cf. 定理 2.47:[21]] X 上の二項関係 <R が整礎であること, <R が X で無限降下列を持た
ないことは同値である.
証明
ある無限降下列 x1 >R x2 >R x3 >R · · · が存在したとする. このとき, Y := {x1 , x2 , x3 , . . .} は
(<R に関して) 最小元を持たない. よって <R は整礎ではない. 逆に <R は整礎ではないと仮定すると, 最
小元を持たず空でないある Y ⊆ X が存在する. 以下を繰り返すことで無限列が作れる.
•
•
•
•
Y は空でないのである元 a1 が存在する.
Y からある元 a1 をとると a1 は最小元ではないので, a2 <R a1 なる a2 が存在する.
Y からある元 a2 をとると a2 は最小元ではないので, a3 <R a2 なる a3 が存在する.
一般に, Y からある元 ai をとると ai は最小元ではないので, ai+1 <R ai なる ai+1 が存在する.
□
• 上述の証明のように, ある要素 ai に依存して次の要素 ai+1 を選ぶ操作を無限回繰り返すという証
明を受け入れてよいものかは疑問の余地がある. 実際, “従属選択公理 (axiom of dependent choices
(DC))” と呼ばれる公理を予め仮定することで, このような証明を許すという場面がある. (e.g.
(1.1.2):[17], 2.4.7:[13], 2.1 節:[6])
• (DC) は “選択公理 (axiom of choice (AC))” よりも弱いことが知られている. (e.g. Theorem 5.26:[10],
P135:[9])
自然数 N の世界
• 数学的帰納法は以下のように表現できる.
[
∧
ϕ(0)
|{z}
初期段階
[
]]
∀k ∈ N ϕ(k) ⇒ ϕ(k + 1)
|
{z
}
⇒
帰納段階
∀k ∈ N, ϕ(k) .
|
{z
}
(IPN )
全てで成立
• これは次のようにも表現できる (表現は異なるが本質的に等しい).
[
∀k ∈ N
(
)
∀m ∈ N m < k ⇒ ϕ(m)
|
{z
}
k−1
]
⇒ ϕ(k) ⇒ ∀k ∈ N, ϕ(k).
(CIPN )
だけでなく k−2,...,0 全てで成立
• 上式には初期段階である
ϕ(0) が明示的には表れないが
, k = 0 のとき m < k(= 0) が偽になるため,
(
)
(
)
m < 0 ⇒ ϕ(m) が真になり, m < 0 ⇒ ϕ(m) ⇒ ϕ(0) を満たすには, ϕ(0) が成り立つ必要がある.
自然数 N の世界から構造・集合の世界へ
• 数学的帰納法は自然数 N に関する論法であるが, 【N のように適切な順序付けされている集合であ
れば】, N 以外の集合に対しても数学的帰納法を考えることができる.
• これについて考えるために, (IPN ) での “N” を “ある関係 <R で順序付けられたある集合 X” に一般
化した, 次の定義が必要となる.
定義 6.2.2. [cf. 8.2.3 節:[14]] 以下を数学的帰納法の原理a と呼ぶ.
∀x ∈ X
a
[(
]
)
∀y ∈ X(y <R x ⇒ ϕ(y)) ⇒ ϕ(x) ⇒ ∀x ∈ X, ϕ(x)
(CIP)
complete induction principle と呼ばれている.
• 先に【N のように適切な順序付けされている集合であれば】と述べたが, 次の補題は, 整礎な二項
関係であればその上で数学的帰納法が展開できることを示している.
補題 6.2.2. [cf. Lemma 1.3:[11], Lemma 2.1.2:[8]] X 上の二項関係 <R が整礎であれば (CIP)
が成り立つ.
証明
– 背理法で証明する. (CIP) の仮定の部分である
((
)
)
∀x ∈ X ∀y ∈ X (y <R x ⇒ ϕ(y)) ⇒ ϕ(x)
(6.1)
[
]
は成り立つが, ¬ ∀x ∈ X, ϕ(x) と (矛盾を仮定) する.
]
[
]
[
– ¬ ∀x ∈ X, ϕ(x) を書き換えると, ∃x ∈ X s.t. ¬ϕ(x) と書ける. つまり, Y = {x ∈ X :
¬ϕ(x)} とすると, Y は空集合ではない. よって, (X, <R ) が整礎であるから, Y は極小元を
持つ.
– Y のある極小元を ŷ とすると, 極小元の定義 (定義 3.1.2 参照) より, (ŷ ∈ Y ) かつ
∀y ∈ Y, y ̸<R ŷ
≡∀y ∈ X, y ∈ Y ⇒ y ̸<R ŷ
≡∀y ∈ X, y <R ŷ ⇒ y ̸∈ Y
(対偶)
ここで x ̸<R x に注意 (x ̸< x のようなこと. 整礎の議論では x ≥ x ≥ x ≥ · · · のような無限降
下列を嫌うので, ≤R ではなく <R で議論する.)
– 整理すると,
ŷ ∈ Y
(6.2)
かつ
∀y ∈ X, (y <R ŷ ⇒ y ̸∈ Y )
(6.3)
成り立つ.
– Y = {x ∈ X : ¬ϕ(x)} に注意すれば, (6.2), (6.3) は, それぞれ次のように書き換えてよい.
¬ϕ(ŷ)
(6.4)
∀y ∈ X, (y <R ŷ ⇒ ϕ(y))
(6.5)
かつ
が成り立つ.
– (6.1) が成り立つので
, (6.1) の x として極小元 ŷ を取ると
(ŷ ∈ Y ⊆ X よりそうできる),
((
)
)
∀x ∈ X
∀y ∈ X (y <R x ⇒ ϕ(y)) ⇒ ϕ(x) · · · (6.1)
((
)
)
ŷ ∈ X
∀y ∈ X (y <R ŷ ⇒ ϕ(y)) ⇒ ϕ(ŷ)
|{z}
|
{z
}
(∗)
(6.5)
が成り立つ.
– ということは, (6.5) が成り立つので (∗) も成り立つ, ということである. しかし (∗) は (6.4) に
矛盾.
□
問題 6.2.1. T を 2 分木とする. n(T ) を T の頂点数, h(T ) を T の高さとする. T に対し, n(T ) ≤
2h(T )+1 − 1 が成り立つことを示せ.
証明
構造的帰納法による証明
初期段階:
• 根に対して成り立つ: 実際, n(T ) = 1 で h(T ) = 0. よって, n(T ) = 1 ≤ 20+1 − 1 = 1.
帰納段階:
• 帰納法の仮定として, 高さが k 以下の 2 分木すべてに対し, n(T1 ) ≤ 2h(T1 )+1 −1 と n(T2 ) ≤ 2h(T2 )+1 −1
が成り立つとする.
• よって,
n(T ) = 1 + n(T1 ) + n(T2 )
≤ 1 + (2h(T1 )+1 − 1) + (2h(T2 )+1 − 1)
≤ 2 · max(2h(T1 )+1 , 2h(T2 )+1 ) − 1
= 2 · 2max(h(T1 ),h(T2 ))+1 − 1
= 2 · 2h(T ) − 1
= 2h(T )+1 − 1
□
7. 証明 (その 1)
7.1. 証明技法
正当性を示す場合
• 背理法
• 帰納法
• 対偶法
解の存在を示す場合
• 構成法
– 方程式を解いたり, 計算して, 実際に解や値を見つけ出す
– 解や値を見つけ出すアルゴリズムとその正当性を示す
– 判例を見つける
• 非構成法
– 鳩ノ巣原理
– 無限降下法
– 確率的手法
7.2. ウォームアップ
√
2 が無理数の (背理法の) 証明について考察する.
整理されていない証明
√
定理 2 は無理数である.
証明
√
√
2 が有理数であると (矛盾を) 仮定する. すると, 2 = m
と書ける正の整数 m, n が存在する.
n
ここで
m と n は互いに素であるとできる. (そうでなければそれぞれを最大公約数で割ればよい)
√
m
2 = n より, 2n2 = m2 と書け, よって m2 は偶数である.
自然数 m が奇数ならば, その二乗 m2 は奇数なので, 対偶をとると m は偶数となる.
よって m = 2ℓ と書ける正の整数 ℓ が存在する. よって m2 = 4ℓ2 となり, 2n2 = (m2 =)4ℓ2 となり,
n2 = 2ℓ2 となり, n2 は偶数となる. よって (先と同様の議論より)n は偶数となる.
• m と n の両方とも偶数となるが, これは互いに素であることに矛盾.
•
•
•
•
•
□
29
やや整理された証明
補題 i を自然数とする. i2 が偶数なら i も偶数である.
証明
i = 2k + 1 が奇数なら i2 = (2k + 1)2 = 4k 2 + 4k + 1 = 4(k 2 + k) + 1 も奇数である. 対偶をと
ると, i2 が偶数なら i も偶数である.
□
√
定理 2 は無理数である.
√
√
証明
背理法で証明する. 2 が有理数であると (矛盾を) 仮定する. すると, 2 = m
と書ける正の整
n
数 m, n が存在する. ここで m と n は互いに素であると考えてよい. (そうでなければそれぞれを最大公
約数で割ればよい)
このとき, m と n はともに偶数であることを以下に示す. これが示せれば, m と n は互いに素である
ことに矛盾し, 背理法が完了する.
√
√
より
m
=
1. 先ず m が偶数であることを示す. 2 = m
2n とでき, これを二乗すると m2 = 2n2 と
n
2
なり, m が偶数となる. よって補題より m も偶数となる.
2. 次に n が偶数であることを示す. 今示した通り m は偶数より, m = 2ℓ と書ける正の整数 ℓ が存在
する. よって m2 = 4ℓ2 となり, 2n2 = (m2 =)4ℓ2 となり, n2 = 2ℓ2 となり, n2 は偶数となる. よって
補題より n も偶数となる.
□
一般化した証明 (もっと一般化できるが…)
「偶数である」を「2 で割り切れる」と解釈すると, より一般的なことが見えてくる.
補題 i を自然数とし, x を素数とする. このとき, i2 が x で割り切れるなら i も x で割り切れる.
証明
この対偶を示す, つまり i が x で割り切れないならば i2 も x で割り切れないことを示す. i が
x で割り切れないとすると, i = xk + y (1 ≤ y ≤ x − 1) なる k と y が存在する. i2 は (xk + y)2 =
x2 k 2 + 2xyk + y 2 = x(xk 2 + 2yk) + y 2 と変形できる. i2 が x で割り切れないことを示せばよい.
それを示すには, y 2 = qx とできないことを示せばよい. これを背理法で示す. もし y 2 = qx とできた
とすると, (素因数分解を考えれば x が素数なので) q ≥ x でなければならず, そうなると y 2 ≥ x2 , つまり
y ≥ x となり矛盾.
□
定理 x を素数とする.
√
x は無理数である.
√
√
証明
背理法で証明する. x が有理数であると (矛盾を) 仮定する. すると, x = m
と書ける正の整
n
数 m, n が存在する. ここで m と n は互いに素であると考えてよい. (そうでなければそれぞれを最大公
約数で割ればよい)
このとき, m と n はともに x で割り切れることを以下に示す. これが示せれば, m と n は互いに素で
あることに矛盾し, 背理法が完了する.
√
√
1. 先ず m が x で割り切れることを示す. x = m
より m = xn とでき, これを二乗すると m2 = xn2
n
となり, m2 が x で割り切れることになる. よって補題より m も x で割り切れる.
2. 次に n が x で割り切れることを示す. 今示した通り m は x で割り切れることより, m = xℓ と書け
る正の整数 ℓ が存在する. よって m2 = x2 ℓ2 となり, xn2 = (m2 =)x2 ℓ2 となり, n2 = xℓ2 となり, n2
は x で割り切れることになる. よって補題より n も x で割り切れる.
□
7.3. 背理法
• ¬(P ⇒ Q) ⇔ (P ∧ ¬Q) より, もし (P ∧ ¬Q) が成り立たないと仮定すると, ¬(¬(P ∧ ¬Q)) が成り
立つことになる.
• 排中律 (が使えればそれ) より二重否定が消せるので, P ⇒ Q が成り立つといえる.
練習問題 7.3.1. 素数が無限に存在する証明に間違いがある. どこが間違いか？
証明
•
•
•
•
今少なくとも k 個の素数 p1 , p2 . . . . , pk が存在すると仮定する.
このとき, q = (p1 × p2 × . . . × pk ) + 1 を考える.
この q は pi 達では割り切れない. よって q は (pi 達とは異なる) 素数である.
「k 個はある」という保証から「k + 1 個はある」という保証が得られたので, これを繰り返すこと
により, 素数をいくらでも多く見つけることができる.
• よって, 素数は無限個存在する.
□
(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30031 = 59 × 509
練習問題 7.3.2. 次の, 素数が無限に存在する証明は正しいか?
証明
• 素数の個数が有限個しか存在しないと仮定する. この素数全体からなる有限集合を P = {p1 , p2 . . . . , pk }
で表すことにする.
• このとき, q = (p1 × p2 × . . . × pk ) + 1 を考える.
• この q は pi 達では割り切れない. よって q は (pi 達とは異なる) 素数である.
• q ̸∈ P より, P が素数全体からなる集合であることに矛盾. よって, 素数は無限個存在する.
□
練習問題 7.3.3. 演習問題 7.3.1 と 7.3.2 の証明の違いは何か？
• q が素数であることを言うには, q 未満のすべての素数で q が割り切れないことをチェックしなけ
ればならない.
• 演習問題 7.3.1 の証明では, すべてではなく限られた素数のみで割り切れないことをチェックした
に過ぎない.
• 一方演習問題 7.3.2 では, “q は q より小さい数 r (i.e. r ≤ q) では割り切れない” ことが成り立って
いる. 何故ならもし r で割り切れたとすると:
– 先ず大事な点は, ある自然数 r が素数であれば, P はすべての素数を含んでいるので, r ∈ P が
必ず成り立つ.
– r が素数の場合, r ∈ P より, r = pi と書けるが, q の作り方から q は r = pi では割り切れない.
– r が素数でない場合, r はある素数 pi ∈ P を約数に持つので, q は pi でも割り切れる. しかし
それは q の作り方からあり得ない.
• 演習問題 7.3.1 の証明で, q が素数で無い場合は, p1 , p2 . . . . , pk 以外の約数が存在することになる.
その場合は, その約数の中に p1 , p2 . . . . , pk 以外の素数を見出すことができる.
定理 7.3.1. 素数は無限に存在する.
証明
(Theorem 5.6:[8]])
• 与えられた任意の自然 n に対し, p > n なる素数 p が存在することを示せば十分である.
• m := n! + 1 とする. もし m が素数であれば主張が成立.
• もし m が素数でなければ, m は幾つかの素数によって素因数分解できる. この素因数分解に出てき
た素数の集合を P (m) で表わすことにする.
• 任意の p ∈ P (m) に対し, p > n が成り立つことを示す.
– もしそうでないと仮定すると, 2 ≤ p ≤ n となる. よって p は 1 × 2 × . . . × p × . . . × n = n! の
約数である.
– また p は m の素因数分解に現れる素数なので, 当然 m = n! + 1 の約数である.
– つまり p は n! + 1 − n! = 1 の約数である. しかしこれは 2 ≤ p に矛盾.
□
他の簡潔な証明としては [20] もある.
練習問題 7.3.4.
• とある不思議な国があり, その国ではすべての道路が一方通行になっている.
• さらに, 各町と町はすべて一方通行の道路で結ばれている.
• このとき, 以下を満たすある町 (もしかしたらこの不思議な国の首都かもしれない) が存在する
ことを示せ.
• すなわち, その町以外の別のどんな町からもから, 高々1 つの町を経由するだけで, その町に行
ける.
C
a
a
m=3
e
b
d
c
e
b
d
c
Figure 7.1: パズル 4.5(問題)
解答
• 他の町から自分の町に入ってくる道路の本数が一番多い国に着目する（そのような町が複数ある
場合は, その中からどれか適当に 1 つ選ぶ. どれを選ぶかは重要ではない）
• すなわち, 「入ってくる道路の本数 (値, ことがら)」に着目し, その最大値に着目して考えるという
こと.
• 選んだ町を C で, また C に入ってくる道の本数を m で, また C に直接行ける町の集合を S で表す.
• S 以外の国で, C でない国がある場合と無い場合の 2 つの場合に分けて考える.
【S 以外の町で, C でない国が無い場合】この場合・
・
・
【S 以外の町で, C でない国が有る場合】そのような町のどれか 1 つについて考える. そのよう
な町を X で表す. このとき, X は少なくとも S のどこか 1 つの町に道が出ているはずである.
何故か？ → もしそうでないとすると何に矛盾するか？
• したがって, C が所望の町である.
□
C
a
C
m=3
S
S
e
b
d
c
Figure 7.2: パズル 4.5(解法)
8. 証明 (その 2)
8.1. 鳩ノ巣原理
√
練習問題 8.1.1. 1 辺が 2 の正方形の内部に, どの 2 点も距離が 1 以上離れているようには, 5 つの
点を置けないことを示せ. 点は正方形の境界線上には置けない.
練習問題 8.1.2. S を 1 から 1000 までの自然数から 501 個とってきてできた任意の集合とする. この
とき, a | b (a は b の約数) であるような, a, b ∈ S が存在することを示せ.
∀S ⊂ {1, 2, 3, . . . , 1000} s.t. |S| = 501, ∃a, b ∈ S s.t. a | b.
解答
• “∀a, b ∈ S, ¬(a | b)” が成り立つ S が存在すると仮定する · · · (♯).
(
) (
)
∃S ⊂ {1, 2, 3, . . . , 1000} s.t. |S| = 501 ∧ ∀a, b ∈ S, ¬(a | b) .
• S≤500 = {c ∈ S | c ≤ 500}, S>500 = {c ∈ S | c > 500} とする.
• 各元 e ∈ S≤500 に対し, 2e, 4e, 8e, 16e, . . . の中で初めて 500 を超える (つまり 501 以上になる) もの
を e′ で表す. このとき,
– 必ずそのような e′ は存在し, e′ ∈ {501, 502, . . . , 1000} となる (つまり 1000 は超えない).
– e ∈ S に対して e′ ∈ {501, 502, . . . , 1000} を割当てる関数を f で表すことにする.
– f は単射である. 何故なら, もし a, b ∈ S かつ a < b(つまり a ̸= b) で, k = f (a) = f (b) とする
k
と, a, b ∈ { k2 , k4 , 16
, . . .} となるが, だとすると, a = 2ki , b = 2kj となる i, j(i > j) が存在する. つ
i−j
まり, b = k·22i = a · 2i−j となり, a が b の約数となり, (♯) に矛盾.
• x = |S≤500 | とすると, |S≤500 | + |S>500 | = 501 より, |S>500 | = 501 − x となる · · · (*).
• 以下に注意すると, |S>500 | ≤ 500 − x となり, (*) と矛盾.
– f が単射より
, |{f (e) | e ∈ S≤500 }| = x,
(
)
– S>500 ⊆ {501, 502, . . . , 1000}\{f (e) | e ∈ S≤500 } ,
– {f (e) | e ∈ S≤500 } ⊂ {501, 502, . . . , 1000}.
□
別解
• 鳩ノ巣原理で証明する. 反例となる S が存在したと仮定する. 501 から 1000 まででラベル付けされ
ている 500 個の箱を用意する.
• 各 e ∈ S に対し, “e が i ∈ {501, 502, . . . , 1000} の約数” となるようなどこかの i でラベル付けされ
た箱に (e を) 入れることを考える.
35
• 各 e ∈ S に対し, 必ず e はどこかの箱の中に入ることを, (推移性を考え) 場合分けで示す.
–
–
–
–
–
–
–
–
–
–
e ∈ {501, 502, . . . , 1000} の場合, e の値でラベル付けされている箱に入れる.
e ∈ {251, 252, . . . , 500} の場合, e を 2e が入る箱に入れる.
e ∈ {126, 127, . . . , 250} の場合, e を 2e が入る箱に入れる.
e ∈ {63, 64, . . . , 125} の場合, e を 2e が入る箱に入れる.
e ∈ {32, 33, . . . , 62} の場合, e を 2e が入る箱に入れる.
e ∈ {16, 17, . . . , 31} の場合, e を 2e が入る箱に入れる.
e ∈ {8, 9, . . . , 15} の場合, e を 2e が入る箱に入れる.
e ∈ {4, 5, 6, 7} の場合, e を 2e が入る箱に入れる.
e ∈ {2, 3} の場合, e を 2e が入る箱に入れる.
S は 1,2 を含めない.
• 箱は 500 個しかなく, S は 501 個の要素を持つ. したがって, 2 個以上の要素を持つ箱が存在し, そ
れらは約数・倍数の関係になっている.
問題 8.1.1. T = {e1 , . . . , en } とする. S = {S1 , S2 , . . . , S2n−1 +1 } とする. ここで, 各 1 ≤ i ≤ 2n−1 + 1
に対し, Si ⊆ T . このとき, Si ⊂ Sj なる Si , Sj が存在することを, 鳩ノ巣原理を使って示せ. ヒント：
箱のラベルとして, e1 を除いた集合を考えよ.
8.2. 無限降下法
練習問題 8.2.1. 以下の, 「1 は最も小さな正の実数 ?」の証明のどこに誤りがあるか？
1. 最も小さな正の実数を M とおく. M は正の実数なので M ̸= 0 (0 は正の実数でも負の実数で
もない).
2. このとき, N = M × M は正の実数. したがって, M ≤ N が成り立つ (何故なら, M は最も小
N
さな正の実数より). つまり, M
≥ 1 (M ̸= 0 なので M で割ることができる).
M ×M
N
3. よって, M = M = M ≥ 1 を得る.
4. 上記より, 最も小さな正の実数 M は 1 以上で, さらに実際 1 は正の実数である. したがって, 1
は最も小さな正の実数である.
練習問題 8.2.2.
√
2 が無理数であることの証明.
証明
•
•
•
•
•
•
√
2 の平方根が有理数であると仮定すると, 2 つの自然数 p, q を用いて 2 = pq と表せる.
そのような p, q に対し, q の値が最小となるような p, q を考える (つまり既約分数を考える)
よって 2q 2 = p2 とでき, これより p は偶数であることがわかる.
したがてある整数 k が存在し p = 2k とできる.
2
よって q 2 = p2 = 2k 2 を得る. よって q も偶数である.
√
q = 2ℓ で表すと, 2 = pq = 2k
= kℓ とか書け, q の最小性に矛盾.
2ℓ
□
練習問題 8.2.3. 平面な基盤上に「＋端子」, 「‐端子」がそれぞれ n 個ある. これら 2n 個の端子か
ら, どの 3 個の端子を選び出しても一直線上にないとするとき, ショートしない（端子どうしを結ん
だ線が交差しない）ような配線 (端子のペアリング) が存在することを示せ. (数学オリンピックから
の引用)
証明
• (交差してもよいすると) 配線の仕方は高々n! 個しか存在しない.
• そのような配線の仕方の中で, 長さの総和が最小となる配線が仕方が存在する.
• そのような配線の仕方では, 交差することが無い. 何故なら, もし交差していたら, 交差をほどいた
配線の仕方の方が総和が短くなることが, 三角不等式から示せる. しかしこれは最小性に矛盾.
□
9. 順序
本章では, 数値上の大小関係を拡張した概念を説明する. ポイントは 2 つあり, 1 つは “比較不能なペアの
存在を許した拡張” ともう 1 つは “数値の比較から集合の比較への拡張” である.
9.1. 前順序
定義 9.1.1. ある集合 S に対し, S 上のある二項関係 ⪯ga前順序であるとは, 以下の 2 つを満たすと
きをいう.
推移律
反射律
a ⪯ b かつ b ⪯ c ならば a ⪯ c
任意の a ∈ A に対して a ⪯ a
定義 9.1.2. [e.g. 定義 (1.1.10):[2], 定義 2.6:[1]] R を S 上の前順序とし, T ⊆ S とする.
• ある要素 x ∈ S の (R に関しての) 上方位集合 (upper contour set, upper section, final segment)
とは, {y ∈ S : xRy} をいい, [x, →) で表わす.
• ある要素 x ∈ S の (R に関しての) 下方位集合 (lower contour set, lower section, initial segment)
とは, {y ∈ S : yRx} をいい, (←, x] で表わす.
9.2. 全順序
定義 9.2.1. 集合 S 上の関係 ⪯ が以下の三条件をみたすとき, (S, ⪯) を全順序構造という.
反対称律 a ⪯ b かつ b ⪯ a ならば a = b;
推移律 a ⪯ b かつ b ⪯ c ならば a ⪯ c;
完全律 a ⪯ b または b ⪯ a の何れかが必ず成り立つ
定義 9.2.2. 集合 S 上の整列関係 (well-order) とは, S 上の全順序関係 ⪯ で, S の空でない任意の部
分集合が必ず ⪯ に関する最小元をもつものをいう.
• 整列関係は, 整礎関係の関係を全順序に制限したもの. (両者の関係については, 例えば 2.2 節:[16],
系 5.1:[7] を参照)
• 例:
– 自然数全体の集合で, 順序が 0, 1, 2, 3, . . . 1
1
ペアノの公理, 数学的帰納法, 最小値の原理などが関係しているが, ここでは素朴に整列順序関係が成り立つと考えるこ
とにする.
39
– 自然数全体の集合で, 順序が 0, 2, 4, 6, . . . , 1, 3, 5, . . .
0 = (0, 0), 2 = (0, 1), 4 = (0, 2), 6 = (0, 3), . . . , 2k = (0, k), . . .,
1 = (1, 0), 3 = (1, 1), 5 = (1, 2), 7 = (1, 3), . . . , 2k + 1 = (1, k), . . .,
と考え, 辞書式順序を考えたもの.
• 反例:
– 整数全体の集合で通常の順序 . . . , −2, −1, 0, 1, 2, . . .
– 集合 { k1 | k は 0 でない自然数 } で通常の順序 . . . , 31 , 12 , 11
9.3. 半順序
定義 9.3.1. 集合 S 上の関係 ⪯ が以下の三条件をみたすとき, ⪯ を半順序関係 , また (S, ⪯) を
半順序構造という.
反対称律 a ⪯ b かつ b ⪯ a ならば a = b
推移律
a ⪯ b かつ b ⪯ c ならば a ⪯ c
反射律
任意の a ∈ A に対して a ⪯ a
定義 9.3.2. P = (S, ⪯) を半順序構造とし, X を S の部分集合とする.
• b ∈ S が X の上界(下界) とは, ∀x ∈ X, x ⪯ b(∀x ∈ X, b ⪯ x) を満たすときをいう. b は X に
属さなくてもよい.
• b が X の最大元(最小元) とは, b ∈ X で ∀x ∈ X, x ⪯ b(∀x ∈ X, b ⪯ x) を満たすときをいう. 条
件にあるように, b は X に属さなくてはならない.
• b が X の極大元(極小元) とは, b ∈ X で [∀x ∈ X, x ⪯ b ⇒ x = b]([∀x ∈ X, b ⪯ x ⇒ x = b]) を
満たすときをいう.
• b ∈ S が X の上限(下限) とは, X の上界の最小元 (X の下界の最大元). つまり, X の任意の上
界 b′ に対して, b ⪯ b′ (b′ ⪯ b) が成り立つときをいう. X の上限 (下限) を sup X(inf X) で表す.
• 上界, 上限√
, 最大元や極大元が存在しない場合もある
. 例えば, 有理数 (Q, ≤) で A = {a ∈ Q : a2 < 2}
√
の上界は 2 以上の有理数の集合だが, 2 ̸∈ Q であるため上界, すなわち上界の最小元が存在しな
い. 最大元や上界は存在するのであれば一意に決まる.
• 半順序構造 P = (R, ≤) に対し, Q(⊂ R) を考える, ここで R, Q はそれぞれ実数, 有理数の集合を意
√
味する. 上の例の A は最大元を持たないが上限は持つ:max A は存在しないが sup A = 2.
• X = S のときの最大元, 最小元, 極大元, 極小元を, それぞれ P の最大元, 最小元, 極大元, 極小元と
呼ぶ.
例 9.3.1. 各区間 Ii = [ℓi , ri ] に対し, Ii ⩽ Ij iﬀ ℓi ≤ ℓj かつ ri ≤ rj とすると ⩽ は半順序関係をなす.
問題 9.3.1.
• PS = (2A , ⊆) を半順序構造とする, ここで A は有限集合とし, ⊆ は包含関係で定義された半順
序関係とする. このとき PS の最大元と最小元はそれぞれ何になるか?
• PI = (I , ⩽) を半順序構造とする, ここで I は区間の有限集合とし, ⩽ は区間で定義された半
順序関係とする. このとき PI は必ず最小元を持つといえるか?
9.4. 半順序の次元
この節では, 集合 S(S に特に意味はない) 上の半順序関係について考える. 話の簡単化のために, S を空
でない有限集合とする.
定義 9.4.1.
• P = (S, ≤P ) を半順序構造とし, L = (S, ≤L ) を全順序構造とする.
• L が P の linear extension とは, x ≤P y ⇒ x ≤L y (x ≤L y ⇒ x ≤P y とは限らない)
• P の linear extension は複数存在し得る. P の linear extension 全体からなる集合を E (P) で表す.
命題 9.4.1. 空でない半順序構造 P = (S, ≤P ) に対し, E (P) ̸= ∅.
証明
• V = S, E = {(u, v) | u ≤ v} なる有向グラフ G = (V, E) を考える. このとき, G は DAG(有向閉路
を持たないグラフ) であることに注意. G の頂点で入次数が 0 の頂点からなる集合を S(G) で表す.
• 以下の操作を頂点がなくなるまで繰り返す:
1. S(G) を適当な順序で並べる.
2. G から S(G) を削除したグラフをあらたに G とする.
• 出来上がった頂点の順序は P の linear extension である.
□
命題 9.4.2. 空でない半順序構造 P = (S, ≤P ) に対し,
∩
L∈E (P)
= P.
証明
• P において比較不能な x と y に対し, x ≤ y を満たす P の linear extension が存在することをいえ
ば, 命題が証明できる. (x, y の対称性より, y ≤ x を満たす P の linear extension の存在も同時に言
えるから)
• したがって, 命題 9.4.1 より, 半順序関係 P に x ≤ y を加えた関係 P’ も半順序になることを示せば
よい.
• 関係 P’ で問題となるのは, 推移律のみである (他の 2 つの律は明らかに成り立つ)
1. x ≤ y かつ y ≤ z だが z ≤ x の場合この場合, P では y ≤ z かつ z ≤ x であるので, y ≤ x となり, あり得ない.
2. x ≤ y かつ z ≤ x だが y ≤ z の場合この場合, P では z ≤ x かつ y ≤ z であるので, y ≤ x となり, あり得ない.
よって, 推移律も成り立つので P’ も半順序関係である.
□
定義 9.4.2.
• L = {(S, ≤1L ), . . . , (S, ≤dL )} を S 上の全順序構造の集合とする.
• このとき, x ≤P y ⇔ ∀1 ≤ i ≤ d, x ≤iL y で定義される半順序関係 ≤P を L が生成する半順序
と呼び, GP (L ) で表す.
• GP は S 上の全順序構造の集合に S 上の半順序構造を割当てる写像である.
• 命題 9.4.2 より, GP (E (P)) = P が成り立つので, GP は全射である.
定義 9.4.3.
• P = (S, ≤P ) を半順序構造とし, L = {(S, ≤1L ), . . . , (S, ≤dL )} を S 上の全順序構造の集合とする.
• L が P の realizer とは, GP (L ) = P が成り立つときをいう.
• このとき, ∀1 ≤ i ≤ d, (S, ≤iL ) ∈ E (P) に注意. linear extension の個数 d を realizer のサイズと
呼ぶ.
• GP が全射より, 任意の半順序関係に対し realizer が存在する.
定義 9.4.4.
• 半順序構造 P = (S, ≤P ) の次元とは, P の realizer で最小のサイズのもののそのサイズを指す.
10. 束
10.1. モティベーション
• 自然数 N 上の通常の大小関係 ≤ は整礎関係である. つまり N の空でない任意の部分集合が必ず最
小元をもつ, という性質が成り立つ.
• これより, N の任意の部分集合 X に対し, X の上界が空でないなら, X の上界は必ず最小元をもつ,
が成り立つ.
• この上界が最小元を持つという性質を, (N, ≤) からより一般の (S, ⪯) へ拡張することを考える. 最
小元だけでなく, 最大元についても考慮する.
• この拡張を考えることで, 意見バラバラに見える (集合, 関係) 等を統一的に扱うことが可能となる.
また, 順序関係を代数的に扱うことも可能となる.
10.2. 諸定義
定義 10.2.1. 束の定義の仕方は 2 つある.
半順序集合としての定義:
• 半順序集合 (S, ⪯) が束とは, 任意の x, y ∈ S に対し, {x, y} の (⪯ に関する) 下限 inf{x, y} と
上限 sup{x, y} が存在するときをいう.
代数的定義:
• 集合 S に, 二つの二項演算 ∧, ∨ が定義され, それが次の法則に従うとき, 三つ組み (S, ∧, ∨) は
束であると言い, ∧ と ∨ をそれぞれ, 交わり (meet) と結び (join) とよぶ. ただし, 巾等律は
他の三法則から導かれるので除いてもよい.
巾等律
交換律
結合律
吸収律
x∧x=x∨x=x
x ∧ y = y ∧ x, x ∨ y = y ∨ x
(x ∧ y) ∧ z = x ∧ (y ∧ z), (x ∨ y) ∨ z = x ∨ (y ∨ z)
(x ∧ y) ∨ x = x, (x ∨ y) ∧ x = x
• 下限が交わりに, 上限が結びに対応する.
• a ⪯ b ⇔ a = a ∧ b と定めることで, 半順序集合としての定義と代数的定義が一致する.
• また, a ⪯ b ⇔ b = a ∨ b が導ける.
補題 10.2.1. 束は以下のように定義しても良い. 半順序集合 (S, ⪯) が束とは, 任意の有限部分集合
X ⊆ S に対し, X の (⪯ に関する) 下限 inf X と上限 sup X が存在するときをいう. (もともとの定
義は |X| = 2 の場合に当たる).
43
10.3. 応用例
例 10.3.1.
• N を自然数の集合とし, ≤ を通常の大小関係とする. 自然数 x, y ∈ N に対し,
– 結びとして max(x, y),
– 交わりとして min(x, y) とすれば (N, ≤) は束となる.
• 自然数 N \ {0} 上の整除関係 (半順序) “|” と,
{
}
– 結びとして最小公倍数 lcm (例えば 12 ∧ 18 = min {12,
24,
36,
·
·
·
}
∩
{18,
36,
·
·
·
}
{
}= 36),
– 交わりとして最大公約数 gcd (例えば 12 ∨ 18 = max {1, 2, 3, 4, 6} ∩ {1, 2, 3, 6, 9} = 6),
とすれば (N \ {0}, |) は束となる.
– この場合, (任意の数の約数である)1 が最小元で, 最大元は存在しない.
– 0 に含める場合は (任意の数の倍数である)0 が最大元とできる. 実際, 任意の y ∈ N に対し
y ≤ 0. ∵ y = 0 のとき 0 ≤ 0 が成り立つ. y ̸= 0 のとき y は 0 の約数 a .
• 集合 X に対し, (⊆, 2X ) と, 結びとして和集合, 交わりとして積集合. この場合, ∅ が最小元で,
X が最大元.
• 集合 S = {s1 , . . . , sn } に対し, S を S の分割全体からなる集合とし, A, B ∈ S に対し, A が B
の細分であるとき A ⊑ B となる半順序とする. このとき, (⊑, S ) は束となる.
– A ⊔ B を以下を満たす C でサイズ |C| が最大のものとする.
[
] [
]
∀A ∈ A, ∃C ∈ C s.t. A ⊆ C ∧ ∀B ∈ B, ∃C ∈ C s.t. B ⊆ C .
[
] [
∪
∪
′
これは, C =∪{C | ∃A∪
⊆ A, ]B ′ ⊆ B s.t. C = A∈A′ = B∈B′ ∧ ̸ ∃A′′ ⊆ A′ , B ′′ ⊆
B ′ s.t. C = A∈A′′ = B∈B′′ } と言い換える事ができる.
– A ⊓ B を以下を満たす C でサイズ |C| が最小のものとする.
[
] [
]
∀C ∈ C, ∃A ∈ A s.t. C ⊆ A ∧ ∃B ∈ B s.t. C ⊆ B .
これは, C = {C | C ̸= ∅, C = A ∩ B, A ∈ A, B ∈ B} と言い換える事ができる.
– A と B の結びとして A ⊔ B.
– A と B の交わりとして
A⊓
{
} B.
– この場合, {s1 }, . . . , {sn } が最小元で, {S} が最大元.
a
x = qy, y ̸= 0 が成り立つとき, y は x の約数という. よって, ∀y ∈ N \ {0},
0=0y
x=qy
より,
y は 0 の約数
y は x の約数
補題 10.3.1. 任意の x, y ∈ N に対し, x ≤ y かつ u ≤ v ならば min(x, u) ≤ min(y, v) が成り立つ.
補題 10.3.2. x, y, u, v を 1 以上の整数とする. このとき,「x | y かつ u | v ならば gcd(x, u) | gcd(y, v)」
が成り立つ.
証明
•
•
•
•
min{x ,u } min{x ,u }
min{x ,u }
1 1
2 2
k k
gcd(x, u) = p1
p2
. . . pk
と書ける.
min{y1 ,v1 } min{y2 ,v2 }
min{yk ,vk }
gcd(y, v) = p1
p2
. . . pk
と書ける.
x | y より, xi ≤ yi . また, u | v より, ui ≤ vi . よって, min{xi , ui } ≤ min{yi , vi }
したがって, gcd(x, u) | gcd(y, v).
□
補題 10.3.3. X, Y, U, V をある有限集合の部分集合とする. このとき, 「X ⊆ Y かつ U ⊆ V ならば
X ∩ U ⊆ Y ∩ V 」が成り立つ.
証明
• ∀e ∈ X ∩ U に対し, e ∈ X ⊆ Y かつ e ∈ U ⊆ V より e ∈ Y ∩ V .
□
補題 10.3.4. X , Y, U, V をある有限集合の分割とする. このとき, 「X ⊑ Y かつ U ⊑ V ならば
X ⊓ U ⊑ Y ⊓ V 」が成り立つ.
証明
• 任意の S ∈ X ⊓ U について考える. S ∈ X ⊓ U より,
∃X ∈ X , U ∈ U s.t. S = X ∩ U.
• X に対し, ∃Y ∈ Y s.t. X ⊆ Y . 同様に U に対し, ∃V ∈ V s.t. U ⊆ V .
• したがって, 上記 S, Y, V (, X, U ) に対して,
S = X ∩ U ⊆ Y ∩ V ∈ Y ⊓ V.
• よって, X ⊓ U ⊑ Y ⊓ V.
□
練習問題 10.3.1. 補題 10.3.1, 10.3.2, 10.3.3, 10.3.4 の証明を統一できないか?
定理 10.3.5. 束 (⪯, S) に対し, 「x ⪯ y かつ u ⪯ v ならば x ∧ u ⪯ y ∧ v 」が成り立つ.
証明
• x ⪯ y より x = x ∧ y. . . . (♭)
• 同様に, u ⪯ v より u = u ∧ v. . . . (♯)
• よって,
(x ∧ u) ∧ (y ∧ v) =
=
=
=
=
(
)
x ∧ u ∧ (y ∧ v)
結合律より
(
)
x ∧ (y ∧ v) ∧ u
交換律より
(
)
x ∧ y ∧ (v ∧ u)
結合律より
(x ∧ y) ∧ (v ∧ u)
結合律より
x∧u
(♭), (♯) より
• したがって, (x ∧ u) ⪯ (y ∧ v) がいえる.
□
系 10.3.6. 補題 10.3.1, 10.3.2, 10.3.3, 10.3.4 が成り立つ.
11. 群
11.1. ウォームアップ
問題 11.1.1. 以下の操作について考える.
• 箱の中に赤, 青, 緑の 3 色のボールが幾つか入っている. ボールを 2 個取り出し 1 つ追加すると
いう以下のルールでボールを減らして行く.
–
–
–
–
–
–
取り出したボールが赤 2 個なら赤ボールを追加.
取り出したボールが青 2 個なら緑ボールを追加.
取り出したボールが緑 2 個なら青ボールを追加.
取り出したボールが赤と青なら青ボールを追加.
取り出したボールが赤と緑なら緑ボールを追加.
取り出したボールが青と緑なら赤ボールを追加.
• ボールの選び方にかかわらず最後に残るボールは, (最初の箱の状態のみに依存して) 一意に決
まるか?
11.2. 諸定義
群論の面白い点は, 操作を要素としている点である.
巡回置換
• 巡回置換の例 (1 → 5 → 2 → 1), (3 → 4 → 3) の巡回は次のように表される.
(
) (
)
1 2 3 4 5
1 2 5 3 4
=
5 1 4 3 2
5 1 2 4 3
• 恒等置換:
(
ι:
1 2 ···
1 2 ···
n
n
)
• 互換 (i1 i2 ): i1 と i2 だけを入換える.
(
(i1 i2 ) :
1 ···
1 ···
i1 · · ·
i2 · · ·
i2 · · ·
i1 · · ·
n
n
)
• 上記を一般化し, (i1 i2 · · · ik ): i1 → i2 → i3 → · · · → ik → i1 と入換える.
(
)
1 · · · i1 · · · i2 · · · ik · · · n
(i1 i2 · · · ik ) :
1 · · · ik · · · i1 · · · ik−1 · · · n
• 巡回置換は、互換の積で表現できる.
47
– 巡回置換をサイクル毎に分解する.
– 各サイクルは以下のようにで分解できる. (k1 k2 k3 · · · kn ) = (k1 kn ) · · · (k1 k3 )(k1 k2 )
• どの置換も互換の積として表すことができ, その表し方は一意には決まらない. しかしどのような
表し方でもその互換の個数の偶奇は一意に定まる. 互換の個数が偶数のとき偶置換といい, 互換の
個数が奇数のとき奇置換という.
定義 11.2.1. 集合 G と G に閉じた演算 ◦(G × G 7→ G) が, 群とは, 以下を満たすときを言う.
1.
2.
3.
4.
演算 ◦ は結合則が成り立つ.
a ◦ (b ◦ c) = (a ◦ b) ◦ c.
演算 ◦ には単位元 e が存在する.
∃e s.t. ∀a ∈ G, a ◦ e = e ◦ a = a.
G の任意の元 a に対して逆元 a−1 が存在する.
∀a ∈ G, ∃a−1 s.t. a ◦ a−1 = a−1 ◦ a = e.
群の元の個数を位数と呼ぶ.
11.3. 対称群
• σi と下記のような演算からなる群は (n = 4 次の)対称群と呼ばれ, Sn で表される. Sn の位数は n!
になる (n 個の要素を並べる組み合わせ分).
)
) (
)(
(
1 2 3 4
1 2 3 4
1 2 3 4
=
σ1 σ2 =
4 1 2 3
2 4 1 3
2 4 3 1
• 一般に可換とは限らない.
σ2 σ1 =
(
1 2 3 4
2 4 1 3
)(
1 2 3 4
2 4 3 1
)
(
=
1 2 3 4
4 3 1 2
)
• 実際, 群の定義を満たす.
1. 演算に閉じていることは, すべての置換を考慮しているので, 2 つの置換 σi σj を組合わせたも
のはそれ自体ある置換 σk である.
2. 結合側が成り立つ (紐のイメージで考えればほとんど自明).
3. 何もしない, つまり動かさないという置換が単位元となる.
4. 元に戻す置換は必ず存在する.
• 置換という操作が群の要素になっている点が面白い.
15 パズルへの応用
• 15 パズルの 1 回のスライドは, (空白 (16) とその隣接するマスでの) 互換に対応する. したがって,
初期状態から何回かスライド操作を行い, 別の状態 T を得るという過程は, 何回か互換を行うとい
う過程に等しく, その意味では状態 T は巡回置換と考えられる.
• 初期状態 S から 14 のマスと 15 のマスのみを入換えた状態を S ′ で表す. 状態 S ′ は 14 と 15 を入換
える互換だけで得られるので, 奇置換である.
• 初期状態 S から状態を S ′ に変形できたと仮定すると, 空白 (16) が右下にある状態は必ず偶置換に
対応する. これは, 盤面を市松模様に塗ると, 空白 (16) が白又は黒のマス目に移動するのは (白の
場合) 偶数または (黒の場合) 奇数回スライドした状態に対応することを考えれば明らかである.
• 状態 S ′ は偶置換でもあり奇置換でもあることになり矛盾.
12. 閉包
12.1. ウォームアップ
無限の積と有限の積
• Ai := (− 1i , 1i ) とする. 各 i = 1, 2, . . . に対し, Ai は開集合である.
(
)
n
∩
1 1
• 任意の自然数 n に対し,
Ai = − ,
は開集合である .
n
n
i=1
∞
∩
• 一方
Ai = {0} は開集合ではない.
i=1
12.2. Closure systemt と closure operator
定義 12.2.1. [e.g. 1.2.1 節, 定義 1:[24], 4.4 節:[19], 定義 2.1.3:[3]] ある集合 S に対し, ある部分族
C ⊆ 2S が closure system とは, 次を満たすときをいう.
(cs1) S ∈ C ,
(cs2) ∀(∅ ̸=)D ⊆ C ,
∩
A∈D
A ∈ C.
定義 12.2.2. 以下の 3 つの性質を満たす関数 f : 2S 7→ 2S を closure operator と呼ぶ.
(co1) A ⊆ f (A),
(co2) A ⊆ B ⇒ f (A) ⊆ f (B),
(co3) f (f (A)) = f (A).
f (A) を (C での)A の閉包と呼ぶ.
Closure system と closure operator の関係を以下で見てゆく (e.g. 定理 2.1.6:[3]).
Closure system から closure operator を構成する
• C をある台集合 S のある closure system とする.
(
• 各 A ⊆ S に対し, 関数 f を次のように定義する: f (A) :=
• C は closure system であるので, 各 A ⊆ S に対し, f (A) =
∩
)
R .
(A⊆R,R∈C
∩
A⊆R,R∈C
49
)
R
は C に属する.
• f (A) は {R | A ⊆ R, R ∈ C } の中の最小の元である, つまり,
f (A) ∈ {R | A ⊆ R, R ∈ C }
∧
∀R ∈ {R | A ⊆ R, R ∈ C },
f (A) ⊆ R.
このとき, f は closure operator となる:
(co1) A ⊆ f (A) が成り立つ, 何故なら,
(
)
∩
• R ∈ {R | A ⊆ R, R ∈ C } ならば A ⊆ R より, A ⊆
R
= f (A).
A⊆R,R∈C
(co2) A ⊆ B ならば f (A) ⊆ f (B) である. 証明は確認問題で.
(
)
(co3) f (A) = f f (A) が成り立つ. 何故なら,


∩
(
)
• f (A) ∈ C より, f f (A) = 
R = f (A) ∩ R1 ∩ R2 ∩ . . . = f (A), ここで f (A) ⊆
f (A)⊆R,R∈C
Ri に注意.
Closure operator から closure system を構成する
• f : S 7→ S をある台集合 S 上のある closure operator とする.
• 集合族 F を次のように定義しする.
F := {f (A) | A ⊆ S}
このとき F は closure system となる:
(cs1) f (S) = S, 何故なら, S ⊆ f (S) かつ (f : S 7→ S より)f (S) ⊆ S. したがっては S = f (S) ∈ F .
∩
(cs2) 任意の E ⊆ F に対し, M := R∈E R ∈ F を示せばよい.
∩
• 各 A ∈ E に対し, M ⊆ A. 何故なら, M = R∈E R = A ∩ R1 ∩ R2 . . . ⊆ A, ここで Ri ∈ E .
• したがって, 各 A ∈ E に対し, f (M ) ⊆ f (A) = A.
• また, f (M ) ⊆ M が成り立つ:
∩
∩
∩
A⊆
A⊆
A = M.
f (M ) =
M ⊆A,A∈F
M ⊆A,A∈E
A∈E
• 一方, M ⊆ f (M ) が成り立つので, f (M ) = M となるが, これは M = f (M ) ∈ F を意味する.
13. 位相空間
13.1. ウォームアップ
領地問題 [ジョルダンの閉曲線定理]
• ある惑星に A と B の住人が二人だけいる. A と B とで惑星を二分し, それぞれの領地を決めよう
とている.
• 惑星には何も障害物が無いとする. A が棒を使って地面緯線を引いてとてつもなく大きな輪を地面
に描いたとする. その輪の内側を A の領土とし, 外側を B の領土とすることにした.
• 果たしてこの方法で本当に領土は二分できるのか? この方法では領土を二分できないような場合
は存在しないのか?
13.2. 閉集合と開集合
定義 13.2.1. (S, C ) が位相空間とは, C が集合 S 上の closure system で, 以下を満たすときをいう:
• ∅ ∈ C,
• ∀A, B ∈ C , A ∪ B ∈ C .a
a
有限回の和で閉じているということ
定義 13.2.1 は以下の閉集合で定義される位相空間に他ならない.
定義 13.2.2. 集合 S 上の集合族 C に対し, (S, C ) が閉集合系による位相空間とは, 以下を満たすと
きをいう:
(ct1) ∅, S ∈ C ,
(ct2) ∀A, B ∈ C , A ∪ B ∈ C ,
∩
(ct3) ∀(∅ ̸=)D ⊆ C , A∈D A ∈ C .
C は閉集合系と呼ばれる.
O := {A | A ∈ C } とすると, ド・モルガンの法則より, 開集合系による位相空間も定義できる. すな
わち, 集合 S 上の集合族 O が, 以下を満たすときをいう:
(ot1) ∅, S ∈ O,
(ot2) ∀A, B ∈ O, A ∩ B ∈ O,
∪
(ot3) ∀(∅ ̸=)D ⊆ O, A∈D A ∈ O.
は開集合系と呼ばれる.
51
13.3. 近傍
定義 13.3.1. x ∈ S に対し, B(x) ⊆ 2S が x の近傍系とは, 以下を満たすときをいう:
(nh0) B(x) ̸= ∅,
(nh1) ∀B ∈ B(x), x ∈ B,
(nh2) [A ∈ B(x)] ∧ [A ⊆ B] ⇒ B ∈ B(x),
(nh3) A, B ∈ B(x) ⇒ A ∩ B ∈ B(x),
(nh4) B ∈ B(x) ⇒ ∃A ⊆ B s.t. [x ∈ A ∈ B(x)] ∧ [∀y ∈ A, B ∈ B(y)].
• 最後の条件 (nh4) は, x の近傍は x に十分近い y の近傍でもあることを意味している.
13.4. 開集合系と近傍系
近傍系から開集合系へ
定理 13.4.1. 各 x ∈ S に対し, x の近傍系 B(x) が存在すると仮定する. このとき,
A ∈ O ⇔ ∀x ∈ A[∃V ∈ B(x) s.t. V ⊆ A]
(COS)
で開集合系 O を定義すると, (S, O) は位相空間となる.
証明
(ot1) 上条件式の A を ∅ とすれば, 前提条件が成り立たないので, 以下が成り立つ:
∀x ∈ ∅[∃V ∈ B(x) s.t. V ⊆ ∅]
≡
x ∈ S, x ∈ ∅ ⇒ ∃V ∈ B(x) s.t. V ⊆ ∅].
上条件式の A を S とすれば, (nh0) より次が成り立つ: ∀x ∈ S[∃V ∈ B(x) s.t. V ⊆ S].
(ot2) A, B ∈ O のとき, (条件式の A を (A∩B) に置き換えた) ∀x ∈ (A∩B)[∃V ∈ B(x) s.t. V ⊆ (A∩B)]
を示せばよい.
• x ∈ (A ∩ B) より, x ∈ VA ⊆ A, x ∈ VB ⊆ B なる VA , VB ∈ B(x) が存在する.
• よって, (nh3) より x ∈ (VA ∩ VB ) ∈ B(x) が言えて, さらに, (VA ∩ VB ) ⊆ A ∩ B も成り立つ.
• したがって, 条件式 (COS) の V として (VA ∩ VB ) が取れる.
∪
(ot3) (∅ ̸=)D ⊆ O に対し, AD := A∈D A と表したとき, ∀x ∈ AD [∃V ∈ B(x) s.t. V ⊆ AD ] を示せば
よい.
• x ∈ AD より, x ∈ Ax ∈ D が存在する. よって, D ⊆ O より, x ∈ Ax ∈ O とできる.
• よって, 条件式 (COS) より, ∃VAx ∈ B(x) s.t. VAx ⊆ Ax さらに, VAx ⊆ Ax ⊆ AD も成り立つ.
• したがって, 条件式の V として VAx が存在する.
□
開集合系から近傍系へ
定理 13.4.2. (S, O) を開集合系による位相空間とする. 各 x ∈ S に対し,
X ∈ B(x) ⇔ ∃B ∈ O s.t. x ∈ B ⊆ X.
(CNB)
とすると, B(x) は S の近傍系である.
証明
(nh0) B(x) ̸= ∅ を示す. (ot1) より, S ∈ O. よって, S ∈ O s.t. x ∈ S ⊆ S. つまり, 条件式 (CNB) の B
として S が取れるということ. よって空集合ではない.
(nh1) ∀X ∈ B(x), x ∈ X を示す. B(x) の定義より明らか.
(nh2) [X ∈ B(x)] ∧ [X ⊆ Y ] ⇒ Y ∈ B(x) を示す.
• X ∈ B(x) より, ∃B ∈ O s.t. x ∈ B ⊆ X.
• よって明らかに, ∃B ∈ O s.t. x ∈ B ⊆ X ⊆ Y となり, Y ∈ B(x).
(nh3) X, Y ∈ B(x) ⇒ X ∩ Y ∈ B(x) を示す.
確認問題で.
(nh4) Y ∈ B(x) ⇒ ∃X ⊆ Y s.t. [x ∈ X ∈ B(x)] ∧ [∀y ∈ X, Y ∈ B(y)] を示す.
• Y ∈ B(x) より, ∃B ∈ O s.t. x ∈ B ⊆ Y が成り立つ. このとき, 条件式 (CNB) の X として B
が取れることを以下に示す:
• 先ず, B ∈ B(x) が成り立つ. 実際, 条件式 (CNB) の B として B 自身を取れば, 右辺が成り立
つ. よって, [x ∈ B ∈ B(x)] が成り立つ.
• 次に, [∀y ∈ B, Y ∈ B(y)] を示す. そのためには, ∃B ∈ O s.t. y ∈B ⊆ Y を示せばよいが, こ
れは B と y の取り方から明らかに成り立つ.
□
14. マトロイド
14.1. 諸定義
定義 14.1.1. 有限集合 E とその部分集合族 I が以下の遺伝的性質 (I1) を満たすとき, M = (E, I)
を部分集合システム(subset system) と呼ぶ.
(I1) I ⊆ J ∈ I ⇒ I ∈ I.
例 14.1.1.
• 頂点に重みを持つグラフ G に対し, 最大独立点集合を求める問題.
• 辺に重みを持つグラフ G に対し, 最大マッチングを求める問題.
• ジョブに重みを持つジョブの集合に対し, 独立で重みの和が最大となるジョブ集合を求める問題.
定義 14.1.2. 部分集合システム∑
M = (E, I) に対する最適化問題とは
, E = {e1 , . . . , en } の各要素 ei
∑
が重さ w(ei ) を持ち, I ∈ I s.t.
ei ∈I w(ei ) = maxJ∈I
ei ∈J w(ei ) を求める問題である.
定義 14.1.3. 部分集合システム M = (E, I) が以下の交換特性 (exchange property)(I2) を満たすと
き, マトロイド(matroid) と呼ぶ．
(I2) I, J ∈ I, |I| < |J| ⇒ ∃j ∈ J\I s.t. I ∪ {j} ∈ I.
マトロイド M = (E, I) において，
• E を M の台集合(ground set)，I を独立集合族という．
• 独立集合族 I の元 I ∈ I は，M の独立集合(independent set) と呼ばれる．
• 逆に独立でない集合は従属集合と呼ばれる. 極小な従属集合をサーキットと呼ぶ. サーキッ
ト全体からなる集合をサーキット族と呼び, CM (または単に C) で表す.
• 極大な独立集合を基と呼ぶ. 基全体からなる集合を基族と呼び, BM (または単に B) で表す.
• ここでは詳しくは触れないが,
– マトロイドは基族やサーキット族を使っても定義できる.
– ランク (階数) 関数というものがあり, 劣モジュラ関数と関係している.
• closure operator f に以下の条件 (Steinitz-MacLane exchange property) を加えたものとマトロイ
ドは同値となる (cf. 定理 5:[4], [5])
x ̸∈ f (A), x ∈ f (A ∪ {y}) ⇒ y ∈ f (A ∪ {x})
55
例 14.1.2.
線形マトロイド (Linear matroid)
• (ある体 F 上の) 行列 M について考える. E を, M の列ベクトル全体からなる集合とする.
I を, 一次独立な列ベクトルの集合全体からなる族とする.


a b c d e f
 1 0 0 1 0 1 


 0 1 0 1 1 0 
0 0 1 0 1 1
• 上の行列の例では例えば独立な列ベクトルの集合として J = {a, e, f }, I = {b, d} をとる
と, I ∪ {e}(または I ∪ {f }) も独立な列ベクトルの集合となる.
• {a, b, c, d} は従属集合であるが, サーキットではない. 実際, {a, b, d} ⊂ {a, b, c, d} は従属
集合である. 一方 {a, b, d} はサーキットである.
例 14.1.3.
閉路マトロイド (Cycle matroid)
• 無向グラフ G について考える. E を, G の辺集合とする. I を, 閉路を含まない辺集合 (つ
まり森) 全体からなる族とする.
c
6
1
7
a
d
2 5
4
3
b
Figure 14.1: 閉路マトロイドの例
• 上のグラフの例では例えば独立集合として J = {1, 2, 3}, I = {4, 5} をとると, I ∪ {1}(ま
たは I ∪ {2}, I ∪ {3}) も独立集合となる.
• {2, 3, 5, 6} は従属集合であるが, サーキットではない. 実際, {5, 6} ⊂ {2, 3, 5, 6} は従属集
合である. 一方 {2, 3, 5} はサーキットである. また {7} もサーキットになる.
例 14.1.4.
横断マトロイド (Transversal matroid)
• 2 部グラフ G = (U, V ; E) について考える. F ⊆ E に対し F の端点からなる集合を V (F )
で表す. I を {U ∩ V (M ) | M ⊆ E はあるマッチング } とする.
Figure 14.2: 横断マトロイドの例
• 上のマッチングの例では例えば独立集合として J = {a, b, c, d}, I = {e, f, g} をとると,
I ∪ {a}(または I ∪ {b}, I ∪ {d}) も独立集合となる.
• {c, d, e, f, g} は要素数 5 なので当然) 従属集合であるが, サーキットではない. 実際,
{c, e, f, g} ⊂ {c, d, e, f, g} は従属集合でサーキットである.
練習問題 14.1.1. 例 14.1.2 の線形マトロイドで, (I2) が成り立つことを例を通してみてみる. J =
{d, e, f }, I = {a, b} をとると,
(I2) I, J ∈ I, |I| < |J| ⇒ ∃j ∈ J\I s.t. I ∪ {j} ∈ I
の j として取れる J の要素は何か?

a
 1

 0
0
b
0
1
0
c
0
0
1
d
1
1
0
e
0
1
1

f
1 

0 
1
【答え】e と f
定理 14.1.1. I, J ∈ B ならば |I| = |J|.
証明
• I, J ∈ B とする.
• |I| < |J| とすると, 交換特性より ∃j ∈ J\I s.t. I ∪ {j} ∈ I.
• しかしこれは I の極大性に矛盾.
□
例 14.1.5. 例 14.1.2 の線形マトロイドで考えると, 基はいわゆる基底のことで, よってどの基底もそ
のランクは変わらない. 例 14.1.3 の閉路マトロイドで考えると, 基はいわゆる全域木のことで, よっ
てどの全域木もその辺の本数は変わらない.
練習問題 14.1.2. 例 14.1.3 の閉路マトロイドで, (I2) が成り立つことを例を通してみてみる. J =
{1, 2, 5}, I = {3, 6} をとると,
(I2) I, J ∈ I, |I| < |J| ⇒ ∃j ∈ J\I s.t. I ∪ {j} ∈ I
の j として取れる J の要素は何か?
c
6
1
7
a
d
2 5
4
3
b
Figure 14.3: 例 14.1.3:閉路マトロイドの例でのグラフ
【答え】1
15. マトロイドと貪欲法
15.1. 貪欲法
• M = (E, I) をマトロイドとする.
• ここで E = {e1 , e2 , . . . , en } を台集合とし, 要素 ei の重みを wi で表す.
• 便宜上, w(f1 ) ≥ w(f2 ) ≥ . . . ≥ w(fn ) を仮定する (つまり重みの大きい順にあらかじめソートされ
ている).
貪欲アルゴリズム
Input: マトロイド M = (E = {e1 , . . . , en }, I), w(e1 ) ≥ · · · ≥ w(en )
Output: 基 Bn ∈ I s.t. w(Bn ) = maxB∈B w(B)
B0 := ∅;
/* E の要素は予め重さの降順にソートされている
for i := 1 to n do
if Bi−1 ∪ {ei } ∈ I then
Bi := Bi−1 ∪ {ei }
else
Bi := Bi−1
*/
return Bn
定理 15.1.1. M = (E, I) を部分集合システムとし, A を部分集合システムに対する貪欲アルゴリズ
ムとする. このとき, 任意の重み付け w : ei → wi に対し A が最適解を出力するための必要十分条件
は, M がマトロイドであることである.
A が最適解を出力する ⇐ M はマトロイド
• Bopt = {eo1 , . . . , eor } (w(eo1 ) ≥ · · · ≥ w(eor )) を最適解とし, BA = {ea1 , . . . , ea′r } (w(ea1 ) ≥ · · · ≥
w(ear )) を A の出力解とする.
• このとき, BA は基となる. ∵ BA が基でないとすると,
–
–
–
–
–
先ず BA は独立なので, r′ ≤ r に注意. さらに, BA が基でないので r′ < r が言える.
よって (I2) が使え, (I2) より, ∃eak ∈ E\B s.t. B ∪ {eak } ∈ I.
一方, eak ∈ E\B, つまり eak ̸∈ B より, ∀i(1 ≤ i ≤ n), eak ̸∈ Bi に注意. 特に eak ̸∈ Bak に注意.
したがって, A は ak 回目のループで, Bak −1 ∪ {eak } ̸∈ I と判断しているはず.
しかし, (I1) より Bak −1 ∪ {eak } ⊆ B ∪ {eak } ∈ I に矛盾.
したがって, Bopt と BA が基なので, r = r′ である.
• 各 j ∈ {1, 2, . . . , r} に対し, w(eaj ) ≥ w(eoj ) が成り立つことを背理法で示す.
• w(eak ) < w(eok ) なる k が存在すると (矛盾を) 仮定する. そのような k で最小のものについて考え
る. また X = {ea1 , . . . , eak−1 }, Y = {eo1 , . . . , eok } と表す.
• X, Y ∈ I, |Y | = |X| + 1 より (I2) が使えて,
∃eoi ∈ Y \X s.t. X ∪ {eoi } ∈ I
59
つまり,
{ea1 , . . . , eak−1 } ∪ {eoi } ∈ I
· · · (♭)
• さらに, w(eoi ) が降順より w(eoi ) ≥ w(eok ), また仮定より w(eok ) > w(eak ) である. 故に, w(eoi ) ≥
w(eok ) > w(eak ) となり oi < ak でなければならない. つまり, eoi は eak より先に A で判定されてい
るはずである.
• よって Boi −1 ⊆Boi ⊆ Bak −1 = {ea1 , . . . , eak−1 } ∈ I より 1 , (♭) に注意すると,
Boi −1 ∪ {eoi } ⊆ {ea1 , . . . , eak−1 } ∪ {eoi } ∈ I
· · · (♯)
• よって, oi (< ak ) 回目のループで A は eoi を採用しなければならないはずである. しかし eoi ∈ Y \X
つまり eoi ̸∈ X より, A は eoi を採用していない, よって矛盾.
∑
∑
• したがって, rj=1 w(eaj ) ≥ rj=1 w(eoj ) が言え, BA が最適解であることが言えた.
A が最適解を出力する ⇒ M はマトロイド
• (I2) を満たさないと仮定する. この場合, 以下を同時に満たす X, Y ∈ I が存在する:
– |X| = |Y | + 1 · · · (♭)
– 各 e ∈ X\Y に対し, Y ∪ {e} ̸∈ I · · · (♯)
• (♭) より, |X\Y | = |X| − |X ∩ Y | = (|Y | + 1) − |X ∩ Y | = |Y \X| + 1 · · · (†)
• Y \X ̸= ∅ である. · · · (‡)
∵ Y \X = ∅ とすると Y ⊂ X となり, |X| = |Y | + 1 よりある要素 e ∈ X ∈ I が存在し X\Y = {e}
とできる. しかしこれは, Y ∪ {e} = X ∈ I となり (♯) に矛盾.
1+2ϵ
1
• (†) と (‡) より, 0 < (1 + 2ϵ)|Y \X| < |X\Y | を満たす 0 < ϵ < 1 が存在する. つまり |X\Y
< |Y \X|
.
|
この ϵ を使って, 各要素の重みを以下のように定義する:


2
if ei ∈ X ∩ Y


 1
if ei ∈ Y \X
|Y \X|
w(ei ) =
1+2ϵ
if ei ∈ X\Y

|X\Y |


ϵ

if ei ∈ E\(X ∪ Y ) ̸= ∅.
|X\Y ||E\(X∪Y )|
• 貪欲アルゴリズムは最初に X ∩ Y の要素から選ぶ. それらを選びきると次に, Y \X の要素から選
ぶ (この時点で Y を選びきったことになる).
• さらに続けたとき, (♯) より X\Y の要素が選ばれることは無い.
1 + 2ϵ
ϵ
ϵ
• 明らかに,
≥
≥
.
|X\Y |
|X\Y |
|X\Y ||E\(X ∪ Y )|
• よって Y を選びきった後は, (もし採用できる要素があれば)E\(X ∪ Y ) の要素が選ばれる. 貪欲ア
ルゴリズムの出力を BG で表すと,
∑
|E\(X ∪ Y )|ϵ
|Y \X|
+
w(e) ≤ 2|X ∩ Y | +
|Y \X| |X\Y ||E\(X ∪ Y )|
e∈B
G
≤ 2|X ∩ Y | + 1 + ϵ.
• 一方 X の重さは,
∑
w(e) = 2|X ∩ Y | + |X\Y |
e∈X
1 + 2ϵ
|X\Y |
= 2|X ∩ Y | + 1 + 2ϵ
となり, さらに X ∈ I より, 最適値は 2|X ∩ Y | + 1 + 2ϵ 以上となり, 「A が最適解を出力する」と
いう大元の仮定に矛盾.
1
最後の等式は, ak − 1 回目ではまだ {ea1 , . . . , eak−1 } で, 次の ak 回目で初めて {ea1 , . . . , eak } となるから
Bibliography
[1] Salvador Barberà, Peter Hammond, and Christian Seidl. Handbook of Utility Theory: Volume 1:
Principles. Springer Science & Business Media, 1998.
[2] Douglas S Bridges and Ghanshyam B Mehta. Representations of Preferences Orderings, volume
422. Springer Science & Business Media, 2013.
[3] Klaus Denecke and Shelly L Wismath. Universal algebra and applications in theoretical computer
science. CRC Press, 2002.
[4] Brenda L Dietrich. Matroids and antimatroids?a survey. Discrete Mathematics, 78(3):223–237,
1989.
[5] Ulrich Faigle. Exchange properties of combinatorial closure spaces. Discrete applied mathematics,
15(2):249–260, 1986.
[6] Thomas Forster. Logic, induction and sets, volume 56. Cambridge University Press, 2003.
[7] J. Gallier. Discrete Mathematics. Universitext.
[8] Jean H Gallier. Logic for computer science: foundations of automatic theorem proving. Courier
Dover Publications, 2015.
[9] Lorenz J Halbeisen. Combinatorial Set Theory: with a gentle introduction to forcing. Springer
Science & Business Media, 2011.
[10] Alan G Hamilton. Numbers, sets and axioms: the apparatus of mathematics. Cambridge University
Press, 1982.
[11] David Harel, Dexter Kozen, and Jerzy Tiuryn. Dynamic logic. MIT press, 2000.
[12] Thomas Jech. Set theory. Springer Science & Business Media, 2013.
[13] Thomas J Jech. The axiom of choice. Courier Corporation, 2008.
[14] Steven G Krantz. Handbook of logic and proof techniques for computer science. Springer Science
& Business Media, 2002.
[15] David Makinson. Sets, logic and maths for computing. Springer Science & Business Media, 2012.
[16] Francisco Miraglia. An introduction to partially ordered structures and sheaves. Polimetrica sas,
2006.
[17] Gregory H Moore. Zermelo’s axiom of choice: Its origins, development, and influence. Courier
Corporation, 2012.
[18] Charles C Pinter. A Book of Set Theory. Courier Corporation, 2014.
61
[19] Sergiu Rudeanu. Sets and ordered structures. Bentham Science Publishers, 2012.
[20] Filip Saidak. A new proof of euclid’s theorem. The American Mathematical Monthly, 113(10):937,
2006.
[21] Dan Simovici and Chabane Djeraba. Mathematical Tools for Data Mining: Set Theory, Partial
Orders, Combinatorics. Springer Science & Business Media, 2014.
[22] Patrick Suppes. Axiomatic Set Theory. Courier Corporation, 2012.
[23] Daniel J Velleman. How to prove it: a structured approach. Cambridge University Press, 2006.
[24] Wolfgang Wechler. Universal algebra for computer scientists, volume 25. Springer Science &
Business Media, 2012.
[25] 伊藤誠 (翻訳) アッケルマン (著). 記号論理学の基礎. 大阪教育図書, 1960.
[26] 萩谷昌己. 岩波講座応用数学 [基礎 11] 論理と計算. 岩波書店, 1993.
[27] 本橋信義. 今度こそわかる論理数理論理学はなぜわかりにくいのか. 講談社, 2014.
[28] 戸次大介. 数理論理学. 東京大学出版会, 2012.

Download Report