前回の（後半の）ポイント 𝑋から𝑌への部分写像、写像（関数）、全射、単射、全単射 部分写像: 𝑋から𝑌への多対1対応 写像: 𝑋にもれの無い多対1対応 全射: 𝑌にもれの無い写像 単射: 1対1対応の写像 全単射: 全射かつ単射 𝑋,𝑌 が有限集合ならば 𝑋 =|𝑌| 𝑓:𝑋→𝑌 逆写像 𝑓:𝑋→𝑌が単射ならば、 𝑓 −1 :𝑌→𝑋 は逆部分写像 𝑓:𝑋→𝑌が全単射ならば、 𝑓 −1 :𝑌→𝑋 は逆写像（全単射）
写像の合成 (部分）写像の行列表現 写像の合成 𝑓= 𝑎 𝑏 𝑐 𝑑 3 1 ∙3 = 𝑎 𝑐 𝑏 𝑑 3 ∙1 3 𝑓= 𝑎 𝑏 𝑐 𝑑 3 1 ∙3 = 𝑎 𝑐 𝑏 𝑑 3 ∙1 3 写像の合成 𝑔∙𝑓= 𝑎 𝑏 𝑐 0 1 1 1 2 3 4 𝑏 𝑎 𝑐 𝑎 = 1 2 3 4 1 1
写像の合成 𝑋 𝑌 𝑌 𝑍 𝑓 𝑔 𝑔∙𝑓
合成写像の結合性 𝑓 𝑔 ℎ ℎ∙𝑔∙𝑓 𝑔∙𝑓 ℎ∙𝑔
写像合成の非可換性 𝑔∙𝑓 𝑓 𝑔 異なる 𝑓 𝑔 𝑓∙𝑔
合成写像の逆写像 𝑓 𝑔 𝑔∙𝑓 (𝑔∙𝑓) −1 一致する 𝑔 −1 𝑓 −1 𝑓 −1 ∙ 𝑔 −1
置換 置換の行列表現 1 4 集合として同じ 2 1 3 5 4 2 5 3 同じ置換 1 4 2 3 5
置換の積 1 4 2 1 3 4 5 5 2 1 5 2 4 3 1 4 3 5 2 𝑓 = 𝑔 = 1 5 2 4 3 1 4 3 5 2 1 4 2 1 3 4 5 5 2 1 3 2 5 3 1 4 2 5 4 𝑔∙𝑓 = =
巡回置換 巡回置換 省略 1 4 2 1 3 4 2 5 1 4 4 2 2 1 3 5 1 4 2 ＝ ＝ ＝( 1 4 2 )
置換の分解 1 4 2 1 3 5 4 2 5 3 1 4 2 3 5 ・ ＝ ＝(1 4 2)(3 5) 1 4 2 3 5 ・ ＝ ＝(3 5)(1 4 2)
演習10 (1) 1 4 2 3 3 5 4 1 5 2 ＝(1 4) (2 3 5) ＝(2 3 5) (1 4) (2) 1 5 2 6 3 4 4 1 5 3 6 7 7 2 (3) 1 7 2 3 5 4 8 5 6 6 3 7 1 8 4
演習11 (1) 1 2 1 1 2 3 3 4 4 1 1 3 4 1 3 1 1 2 1 4 1 3 1 2 ＝ ＝ 2 4 1 2 3 3 4 4 1 4 1 4 2 3 3 3 4 1 4 3 2 3 4 1 4 ＝ ＝ 2
有限集合Pの要素への番号付け N |𝑃| ={𝑘 | 𝑘 ∈N, 1≤𝑘≤|𝑃|} 𝑃 × 1 ・ 2 . |𝑃|
自然数の集合と偶数の集合(p.4) 偶数の集合𝐸= 2, 4, 6, … とすると、 𝐸 は自然数全体の集合 N の真部分集合 偶数の集合𝐸= 2, 4, 6, … とすると、 𝐸 は自然数全体の集合 N の真部分集合 𝐸= 2, 4, 6, … 1番目の偶数 2番目の偶数 3番目の偶数 N から𝐸 への全単射 𝑓 𝑖 =2×𝑖 が存在する 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 N = 𝐸
自然数の集合と整数の集合 整数の集合Z= …, −2, −1, 0, 1, 2, … とすると N は Z の真部分集合 3番目 1番目 2番目 4番目 N からZへの全単射 𝑓 𝑛 = 𝑛 2 𝑛が偶数 − 𝑛−1 2 𝑛が奇数 N = Z
N の２次の直積 N 2 (1, 1) (2, 1) (3, 1) (4, 1) (5, 1) (1, 2) (2, 2) (3, 2) (4, 2) (5, 2) (1, 3) (2, 3) (3, 3) (4, 3) (5, 3) (1, 4) (2, 4) (3, 4) (4, 4) (5, 4)
自然数の２次の直積 N 2 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 が 2を N 1 が 1を 含まない 含む 1 2 3 4 ……… k ……… K 𝑁 1 ○ × × ○ ……… ○ ………. ○ ○ × ○ ……… ○ ………. × × × × ……… ○ ………. ○ × ○ ○ ……… ○ ………. K 𝑁 1 × 𝑁 2 × 𝑁 3 ○ 𝑁 4 ○ . 𝑁 𝑘 × . KはN の部分集合だが，いずれの𝑁𝑖 とも一致しない Nの部分集合の数え上げ