pptxファイル

前回の（後半の）ポイント
𝑋から𝑌への部分写像、写像（関数）、全射、単射、全単射
 部分写像: 𝑋から𝑌への多対1対応
 写像: 𝑋にもれの無い多対1対応
𝑓: 𝑋 → 𝑌
 全射: 𝑌にもれの無い写像
 単射: 1対1対応の写像
 全単射: 全射かつ単射 𝑋, 𝑌 が有限集合ならば 𝑋 = |𝑌|
逆写像
 𝑓: 𝑋 → 𝑌が単射ならば、𝑓 −1 : 𝑌 → 𝑋 は逆部分写像
𝑓: 𝑋 → 𝑌が全単射ならば、𝑓 −1 : 𝑌 → 𝑋 は逆写像（全単射）
写像の合成
 (部分）写像の行列表現
𝑎𝑏𝑐𝑑
𝑓=
31 ∙3
𝑎𝑐𝑏𝑑
=
3 ∙13
 写像の合成
𝑎𝑏𝑐
𝑔∙𝑓 =
011
1234
𝑏𝑎𝑐𝑎
=
1234
1 010
写像の合成
𝑋
𝑌
𝑌
𝑍
𝑔
𝑓
𝑔∙𝑓
合成写像の結合性
𝑔 ∙ 𝑓ℎ ∙ 𝑔 ∙ 𝑓 ℎ ∙ 𝑔
𝑓
𝑔
ℎ
写像合成の非可換性
𝑓
𝑔
𝑔∙𝑓
異
な
る
𝑔
𝑓
𝑓∙𝑔
合成写像の逆写像
𝑓
𝑔
𝑔∙𝑓
(𝑔 ∙ 𝑓)−1
一
致
す
る
𝑔−1
𝑓 −1
𝑓 −1 ∙ 𝑔−1
置換
 置換の行列表現
1 2 3 4 5
4 1 5 2 3
集合として同じ
同じ置換
2 4 5 1 3
1 2 3 4 5
置換の積
𝑓 =
1 2 3 4 5
4 1 3 5 2
𝑔∙𝑓 =
𝑔 =
1 2 3 4 5
5 4 1 3 2
1 2 3 4 5
1 2 3 4 5
5 4 1 3 2
4 1 3 5 2
=
1 2 3 4 5
3 5 1 2 4
巡回置換
省略
 巡回置換
1 2 3 4 5
4 1 3 2 5
＝( 1 4 2 )
＝
1 4 2 3 5
4 2 1 3 5
＝
1 4 2
4 2 1
置換の分解
1 2 3 4 5
＝
1 4 2
・
＝
3 5
5 3
＝(1 4 2)(3 5)
5 3
4 2 1
4 1 5 2 3
3 5
・
1 4 2
4 2 1
＝(3 5)(1 4 2)
演習10
(1)
1 2 3 4 5
＝(1 4) (2 3 5) ＝(2 3 5) (1 4)
4 3 5 1 2
(2)
1 2 3 4 5 6 7
5 6 4 1 3 7 2
(3)
1 2 3 4 5 6 7 8
7 2 5 8 6 3 1 4
演習11
(1) 1 12 3 4
1 1
3 4
1 2
2 3 4 1
3 4 1
1 2 3 4
4
2 3 4 1
＝
＝
1 4
1 3
1 2
2 1
4 1
3 1
2 1
4 2 3
3
1 4
3 2
3 4
1 4
2 3 4
4 1
2 3
4 3
4 1
＝
＝
有限集合Pの要素への番号付け
N|𝑃| = {𝑘 | 𝑘 ∈ N, 1 ≤ 𝑘 ≤ |𝑃|}
×
・
・
×
・
・
・
×
1
2
.
.
.
|𝑃|
𝑃
N|𝑃| から𝑃への全単射
自然数の集合と偶数の集合(p.4)
偶数の集合𝐸 = 2, 4, 6, …
とすると、
𝐸 は自然数全体の集合 N の真部分集合
𝐸 = 2, 4, 6, …
1番目の偶数 2番目の偶数
3番目の偶数
N から𝐸 への全単射 𝑓 𝑖 = 2 × 𝑖 が存在する
𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓
N = 𝐸
自然数の集合と整数の集合
整数の集合Z = … , −2, −1, 0, 1, 2, …
N は Z の真部分集合
とすると
Z = … , −2, −1, 0, 1, 2, …
3番目 1番目 2番目
N からZへの全単射
𝑛
2
𝑓 𝑛 =
𝑛−1
−
2
N = Z
4番目
𝑛が偶数
𝑛が奇数
N の２次の直積
N2
(1, 4) (2, 4) (3, 4) (4, 4) (5, 4)
(1, 3) (2, 3) (3, 3) (4, 3) (5, 3)
(1, 2) (2, 2) (3, 2) (4, 2) (5, 2)
(1, 1) (2, 1) (3, 1) (4, 1) (5, 1)
自然数の２次の直積
N2
7
4
8
2
5
9
1
3
6
10
N の冪集合(p.5)
N とその冪集合は対等でない
i.e. |N |＜|P(N)|
背理法による証明
仮定：番号付け可能とする
• N の1番目の部分集合𝑁1 , N の2番目の部分集合𝑁2 ，
… , N の 𝑘番目の部分集合𝑁𝑘 , …
という番号付けが存在し
• どんなN の部分集合も、いずれかの𝑁𝑖 と一致する
以下のようなN の部分集合𝐾を考える
𝐾 = {𝑘 ∣ 𝑘 ∉ 𝑁𝑘 }
𝑘 ∈ 𝐾 ⇔ 𝑘 ∉ 𝑁𝑘
矛盾
𝐾はいかなる𝑁𝑖 とも一致しない
仮定が間違っていた（番号付け可能でない）
対角線論法
N 1 がN1を
1が
𝑁1
×
○
2を
2 含む含まない
3
4 ……… k ………
×
×
○ ……… ○ ……….
𝑁2
○
×
○
×
○ ……… ○ ……….
𝑁3
○
×
○
×
○ ……… ○ ……….
K
1
𝑁4
○
×
×
×
× ……… ○ ……….
.
.
.
𝑁𝑘
○
×
○
○ ……… ×
○ ……….
.
. KはN
の部分集合だが，いずれの𝑁𝑖 とも一致しない
Nの部分集合の数え上げ

Download Report