集合論

花木章秀

目次

3 写像
3.1 写像
3.2 合成写像
3.3 制限写像
3.4 全射
3.5 単射
3.6 全単射
3.7 二項演算
3.8 その他
3.9 演習問題

写像

3.1 写像

A , B を集合とする。 A の各元に対して B の元が一つ定まっているとする。このときこの対応を A から B への写像という。 f が A から B への写像であることを
f : A → B
と表す。このとき A を定義域、 B を値域という。写像 f によって a ∈ A に対応する B の元を f (a ) と表し、これを a の f による像という。どのように定まる写像なのかを明示したい場合には
f : A → B (a ↦→ f(a))
などと書く。
例3.1.1. 通常は f : A → B と書けば f が写像であることを意味するが、以下の例では簡単のため写像ではないものに対しても同様の記号を用いる。
  1. f : ℕ → ℕ を f(a) = a + 1 で定めれば、これは写像である。
  2. f : ℕ → ℕ を f(a) = a - 1 で定めると、これは写像ではない。なぜならば 1 ∈ ℕ に対して f(1) = 1 - 1 = 0 ⁄∈ ℕ であり、 1 の f による像が定まらない からである。
  3. f : ℝ → ℝ を f (a ) は a の平方根とすると、これは写像ではない。まず正の数 について平方根は 2 つあり、このどちらを対応させるのかが定かでない。また負 の数については平方根は ℝ に存在しないので対応が決まらない。
  4. f : ℝ >0 → ℝ を f (a ) は a の正の平方根とする (すなわち √ --f(a) = a ) と、こ れは写像である。またこのとき値域を ℝ >0 としても、これは写像である。
  5. f : ℚ → ℕ を f (a) は a の分母として定めると、これは写像ではない。なぜな らば有理数の書き方は一意的でなく、分母の定義が曖昧だからである。これを「分 母が正である既約分数に表したときの分母」とすれば、これは一意的に定まるので 写像になる。ただし「整数に対しては分母を 1 とする」などの注意も書き加えた 方がよいだろう。
  6. P (x ) を実数係数多項式とする。このとき f : ℝ → ℝ を f(a) = P (a) で定めれ ば、これは写像である。通常はこの写像 f と多項式 P に同じ記号を用いる。
  7. f : ℝ → ℝ , f (x) = 1∕(x2 - 1) は x = ｱ1 で値が定まらないので写像ではな い。 f : ℝ → ℝ , 2f(x) = 1∕(x + 1) は写像である。

この例を見れば分かるように写像 f : A → B が定まるためには次のことが必要である。

  1. 任意の a ∈ A に対して f(a) が定まる。ただし a ∈ A の記述の仕方が一意的で ない場合には、どのような記述に対しても同じ元が対応しなければならない。
  2. (1) で定まった f(a) は B の元である。
f がこの条件を満たすとき f が定まる、または f は矛盾なく定義される(well-defined) という。

二つの写像 f : A → B と g : A → B が等しいとは、任意の a ∈ A に対して f (a ) = g(a) となることとする。

例3.1.2. A を空でない任意の集合とする。 f : A → A を、任意の a ∈ A に対して f (a ) = a とすれば f は写像である。これを A の恒等写像といい id A と書く。 ( A が空のときも恒等写像は定義できるが、その意味は分かりにくいだろう。)
例3.1.3. A を集合、 B を空でない任意の集合とする。 b ∈ B を一つ固定する。 f : A → B を、任意の a ∈ A に対して f (a ) = b とすれば f は写像である。これを定値写像という。
例3.1.4. A = {1,2,3} , B = {a,b} と す る。 f : A → B を f (1 ) = a , f(2) = a , f(3) = b で定めればこれは写像である。写像 f : A → B を決めるには f(1),f(2),f (3 ) を任意に定めればよいので A から B への写像は全部で 8 個あることが分かる。

より一般に A = {1, 2,⋅⋅⋅ ,m } , B = {1,2,⋅⋅⋅ ,n} とするとき A から B への写像は nm 個ある。 ( A から B への写像全体の集合を Map (A,B ) , または BA などと書いたりする。)

問3.1.5. A = {1,2} , B = {1,2,3} とするとき A から B への写像をすべて書け。
問3.1.6. A = {1,2} とする。 A から ℝ への写像、 ℝ から A への写像をそれぞれ一つ、具体的に構成せよ。

3.2 合成写像

f : A → B , g : B → C をそれぞれ写像とする。このとき a ∈ A を f で移して、続けて g で移すという操作が考えられる。このように考えると A から C への新しい写像が得られる。これを f と g の合成写像といい g ∘ f と書く。
g ∘ f : A → C (a ↦→ g(f (a )))
PIC
Figure3.1: g ∘ f

はじめに f で移しているのに g ∘ f と書くのは、その像が g(f(a)) となっているからである。 (場合によっては写像の合成を逆の順序で書くこともあるが、この講義ではこの順序で統一する。) このとき f の値域と g の定義域が一致していることが重要で、そうでないときには合成写像は考えられない。 (実際には f の値域が g の定義域に含まれていればよいが、正確には後で説明する。)

例3.2.1. 写像の定義域と値域が一致しているときには、同じ写像の合成を考えることができる。 f : A → A に対して f 0 = idA , f n+1 = f ∘ f n ( n ≥ 1 ) として f n ( n ∈ {0 } ∪ ℕ ) を定義することができる。このとき f m+n = fm ∘ fn が成り立つ。
例3.2.2. f : ℝ → ℝ を f (x ) = x2 + 1 で定める。このとき f2(x) = f(x2 + 1) = (x2 + 1)2 + 1 = x4 + 2x2 + 2 である。

3.3 制限写像

写像 f : A → B を考える。また C ⊂ A とする。 c ∈ C は A の元でもあるので f (c) ∈ B が定まる。このようにして写像 C → B が定義される。これを f の C への制限、または制限写像といい f|C と書く。

これと似たこととして f : A → B に対して、すべての像 f(a) が B の部分集合 C に含まれるならば、自然に ′f : A → C ( ′f (a) = f(a) ) が定義できる。 ( ′f は同じ記号 f を用いて表されることも多い。)

3.4 全射

写像 f : A → B を考える。 C ⊂ A に対して
f (C) := {f(c) | c ∈ C}
とおいて、これを f による C の像という。定義から明らかなように f(C ) は B の部分集合である。
PIC
Figure3.2: f(C )

ここで注意するのは C は A の部分集合であって A の元ではないので、今までの意味では f(C ) は定義されない。この場合の f (C ) とは新しく定義した記号であり、通常の意味での写像の像ではない。

注意. 正 確 に は 以 下 の よ う に 考 え る。 f に対して ^f : P (A ) → P (B ) を ^f (C) := {f(c) | c ∈ C} で定めると、これは写像である。 A^ = {S ∈ P (A ) | |S | = 1} とおくと、 ^A は自然に A と同じものと考えることができる。同様に ^B = {T ∈ P (B ) | |T | = 1} とおくと、 ^B は自然に B と同じものと考えることができる。このように考えれば、制限写像 ^f|A は f と同じものと考えられる。この意味で ^f を f と書けば、上で説明したような記号となる。
例3.4.1. 写像 f : ℝ → ℝ を f(x) = x2 で定める。 a,b ∈ ℝ に対して (a,b) = {r ∈ R | a < r < b} , (a,b] = {r ∈ R | a < r ≤ b} , [a,b) = {r ∈ R | a ≤ r < b} , [a,b] = {r ∈ R | a ≤ r ≤ b} を、それぞれ開区間、半開区間、半開区間、閉区間という。このとき
f ([1,2)) = [1,4 ) f ((- 1,2)) = [0,4 ]f ((- ∞, 1 ]) = [1,∞ ) f (ℝ) = [0,∞ )
などとなる。

特に C = A としたとき f(A) を単に f の像といい Im f とも書く。

PIC
Figure3.3: Im f

Im f = B が成り立つとき f を全射という。すなわち f : A → B が全射であるとは

ということである。 f が全射であることを f : A ↠ B などと書くこともある。
例3.4.2.
  1. f : ℤ → ℤ ( a ↦→ a + 1 ) は全射である。なぜならば、任意の b ∈ ℤ に対して b - 1 ∈ ℤ であり f (b - 1) = (b - 1) + 1 = b が成り立つからである。
  2. f : ℕ → ℕ ( a ↦→ a + 1 ) は全射ではない。なぜならば、 1 ∈ ℤ に対して f(a) = a + 1 = 1 となる a ∈ ℕ が存在しないからである (そのような a は 0 であるが 0 ⁄∈ ℕ である)。
命題3.4.3. f : A → B , g : B → C を考える。 f , g がともに全射であるならば g ∘ f : A → C は全射である。

証明. f (A ) = B , f (B) = C であるから g ∘ f (A ) = g(f(A )) = g(B) = C である。 _

命題3.4.4. f : A → B , g : B → C を考える。このとき合成写像 g ∘ f : A → C の像について Im (g ∘ f) ⊂ Im g が成り立つ。特に g ∘ f : A → C が全射であれば g は全射である。

証明. c ∈ Im (g ∘ f ) とする。このとき、ある a ∈ A があって g (f (a)) = c である。 f (a ) ∈ B であるから c ∈ Im g である。よってはじめの主張を得る。

g が全射でなければ Im g ⊊ C であり Im (g ∘ f) ⊂ Im g ⊊ C となるから g ∘ f は全射ではない。 _

命題3.4.5. 写像 f : A → B に対して、「任意の集合 C と二つの写像 g : B → C , h : B → C について、 g ∘ f = h ∘ f ならば g = h である」という条件を考える。この条件が満たされることと f が全射であることは同値である。

証明. f が全射であるとし、 g ∘ f = h ∘ f とする。 b ∈ B を任意にとる。 f は全射なので、ある a ∈ A があって f(a) = b である。このとき

g(b) = g(f(a)) = g ∘ f (a) = h ∘ f (a ) = h (f(a)) = h(b)
となるので g = h である。

f が全射でないとする。 b0 ∈ B で b0 ⁄∈ f(A ) なるものが存在する。 C = {x, y} ( x ⁄= y ) とおき、任意の b ∈ B に対して g(b) = x で g : B → C を定め、

{ x if b ⁄= b0h (b) = y if b = b 0
で h : B → C を定める。このとき b0 ⁄∈ f(A ) としているので、任意の a ∈ A に対して g ∘ f (a ) = x = h ∘ f (a ) となる。すなわち g ∘ f = h ∘ f であるが g ⁄= h なので、 f は命題の条件を満たさない。 _

3.5 単射

写像 f : A → B を考える。 b ∈ B に対して
f -1(b) := {a ∈ A | f(a) = b}
とおいて、これを f による b の逆像という。これも単なる記号であり f- 1 は写像ではない。 (正確には f -1 : B → P (A) である。)
PIC
Figure3.4: f-1(b)

C ⊂ B に対しても

f-1(C ) := {a ∈ A | f(a ) ∈ C }
とおいて、これを f による C の逆像という。 (この場合、正確には - 1f : P(B ) → P (A ) である。)
⋃f-1(C ) = f- 1(b) b∈C
が成り立つことは明らかであろう。
PIC
Figure3.5: f-1(C )
例3.5.1. 写像 f : ℝ → ℝ を f (x) = x2 で定める。このとき
f -1(1) = {- 1,1} -1 f (- 1) = ϕ f-1([1,4)) = (- 2,- 1] ∪ [1,2) - 1f ([- 4,- 1)) = ϕ f-1((- 4,1)) = (- 1,1) f-1((- ∞, 1]) = [- 1,1] -1 f (ℝ ) = ℝ
などとなる。
問3.5.2. f : A → B を写像とし C ⊂ B とする。 - 1f(f (C)) ⊂ C であることを示せ。また f (f-1(C )) = C とはならない例を示せ。
問3.5.3. 写像 f : A → B を考える。 b,b′ ∈ B , b ⁄= b′ であるとき -1 - 1 ′f (b) ∩ f (b ) = ϕ であることを示せ。

任意の b ∈ B に対して f-1(b) が高々一つの元しか含まないとき、 f を単射という。言い換えると

ということである。 f が単射であることを f : A ↣ B などと書くこともある。
例3.5.4.
  1. f : ℤ → ℤ ( a ↦→ a2 ) は単射ではない。なぜならば 1 ⁄= - 1 であるが 12 = (- 1)2 が成り立つからである。
  2. f : ℕ → ℕ ( 2a ↦→ a ) は単射である。なぜならば ′a ⁄= a ならば 2 ′2a ⁄= (a ) が 成り立つからである。
命題3.5.5. f : A → B , g : B → C を考える。 f , g がともに単射であるならば g ∘ f : A → C は単射である。

証明. c,c′ ∈ C に対して g ∘ f(c) = g ∘ f (c′) とする。 g(f (c)) = g(f (c′)) で g が単射なので f (c) = f (c′) である。また f が単射なので c = c′ である。よって g ∘ f は単射である。 _

命題3.5.6. f : A → B , g : B → C を考える。合成写像 g ∘ f : A → C が単射であれば f は単射である。

証明. ′a,a ∈ A とし ′f(a ) = f (a) とする。このとき ′ ′g ∘ f (a) = g(f(a)) = g(f(a )) = g ∘ f(a ) である。 g ∘ f が単射であるから a = a′ である。よって f は単射である。 _

命題3.5.7. 写像 f : A → B に対して、「任意の集合 C と二つの写像 g : C → A , h : C → A について、 f ∘ g = f ∘ h ならば g = h である」という条件を考える。この条件が満たされることと f が単射であることは同値である。

証明. f が 単 射 で あ る と し、 f ∘ g = f ∘ h と する。 c ∈ C に対して f(g(c)) = f ∘ g (c) = f ∘ h(c) = f(h(c)) である。 f が単射なので g(c) = h(c) となり g = h となる。

f が単射でないとする。 a,a′ ∈ A , a ⁄= a′ で f(a) = f(a′) となるものがある。 C = {c} とおいて g(c) = a , ′h(c) = a として g : C → A , h : C → A を定める。このとき g ⁄= h であるが f(g(c)) = f(a) = f (a ′) = f(h (c)) となり f ∘ g = f ∘ h が成り立つ。よって命題の条件はみたされない。 _

例3.5.8. A ⊂ B であるとき f : A → B を f (a ) = a で定めることができる。これを A の B への埋め込み、または包含写像という。埋め込は明らかに単射である。
例3.5.9. f : A → B とする。 B ⊂ C なる C に対して ′f : A → C を ′f (a) = f (a ) ∈ C で定めることができる。これは正確には次のように解釈される。 ι : B → C を埋め込みとし、合成写像 f ∘ ι : A → C を考えるのである。
例3.5.10. 合成写像のところで f : A → B , g : C → D で B ⊂ C ならば、合成写像を考えることができると書いた。これは正確には次のように解釈される。すなわち ι : B → C を埋め込みとし、合成写像 g ∘ ι ∘ f : A → D を考えるのである。

3.6 全単射

f : A → B が全単射であるとは、 f が全射かつ単射であることとする。言い換えると ということである。このとき「任意の b ∈ B に対して f (a) = b となる a ∈ A が存在する」ことから全射、「唯一つ存在する」ということから単射であることが分かる。この言い換えから全単射 f : A → B に対しては、 b ∈ B に対して f (a) = b となる a ∈ A を対応させることによって写像 g : B → A が定まる。この写像 g を f の逆写像といって -1f で表す。逆像の定義でも -1f という記号を用いたが、そのときは -1f は単なる記号であった。しかしここでは -1f は写像であるので注意が必要である。
例3.6.1. A を集合とする。恒等写像 idA : A → A ( a ↦→ a ) は明らかに全単射である。 (idA)-1 = idA であることは明らかだろう。恒等写像は A ⊂ A と見たときの埋め込みに等しい。
命題3.6.2. 全単射 f : A → B とその逆写像 f -1 : B → A について次が成り立つ。
-1 -1f ∘ f = idA, f ∘ f = idB
命題3.6.3. f : A → B が全単射であるための必要十分条件は、ある g : B → A があって g ∘ f , f ∘ g が共に全単射となることである。

証明. f : A → B が全単射であれば g として -1f をとれば命題 3.6.2 より f -1 ∘ f = idA , f ∘ f -1 = idB は共に全単射である。

g : B → A に対して g ∘ f , f ∘ g が共に全単射であるとする。このとき g ∘ f が全射であるから命題 3.4.4 より f は全射であり、 f ∘ g が単射であるから命題 3.5.6 より f は単射である。 _

定理3.6.4. |A| = |B| < ∞ とする。このとき写像 f : A → B について、次は同値である。
  1. f は単射。
  2. f は全射。
  3. f は全単射。

証明のために簡単な補題を用意しよう。補題の証明は定義から明らかである。

補題3.6.5. f : A → B が全射であるための必要十分条件は、任意の b ∈ B に対して -1|f (b)| ≥ 1 となることである。また、単射であるための必要十分条件は、任意の b ∈ B に対して |f-1(b)| ≤ 1 となることである。

定理 3.6.4 の証明. (3) = ⇒ (1), (3) = ⇒ (2) は明らか。 (1) =⇒ (2),(2) =⇒ (1) を示せばよい。 -1 ∑ -1A = f (B) = b∈B f (b) であり、 ′b ⁄= b ならば f -1(b) ∩ f- 1(b′) = ϕ なので ∑|A| = b∈B |f-1(b)| であることに注意しておく。

f を単射とする。

∑|A | = |f- 1(b)| ≤ |B| = |A| b∈B
より任意の b ∈ B に対して |f -1(b)| = 1 である。よって f は全射である。

f を全射とする。

∑|B | ≤ |f -1(b)| = |A| = |B| b∈B
より任意の b ∈ B に対して -1|f (b)| = 1 である。よって f は単射である。 _
例3.6.6. |A| = ∞ のときは f : A → A が全射、または単射であっても全単射とは限らない。例えば f : ℤ → ℤ , f (a ) = 2a は単射であるが全射ではない。また f : ℕ → ℕ , f (1) = 1 , f(a) = a - 1 ( a > 1 ) とすれば、これは全射ではあるが単射ではない。
例3.6.7. f : A → B を単射とする。 ′f : A → Im f を ′f (a) = f (a ) で定義することができる。このとき ′f は全単射である。

3.7 二項演算

整数の足し算とは何だろうか。これは写像を用いて説明される。すなわち、それは写像 f : ℤ × ℤ → ℤ に他ならない。 f(a,b) を a + b という記号を用いて表しているだけである。

このように、ある集合 A に対して、写像 f : A × A → A が与えられるとき、それを A の二項演算という。二項演算の像は適当な記号、ここでは仮に △ とする、を用いて f (a,b) = a△b のように表される。二項演算 (a, b) ↦→ a△b に対して

交換法則:
a △b = b△a
結合法則:
(a△b )△c = a△ (b△c )
などが考えられるが、二項演算がこれらを満たしている必要はない。
例3.7.1. 実数の減法は交換法則も結合法則も満たさない二項演算である。また実数の除法は 0 で割ることができないので、二項演算ではない。

3.8 その他

命題3.8.1. 集合 A , B に対し Map (A, B ) で A から B への写像全体の集合を表す。 f : A → B が与えられたとき *f : Map (B,C ) → Map (A, C) を *f (φ ) = φ ∘ f で定義する。
PIC
Figure3.6: *f (φ) = φ ∘ f

このとき次が成り立つ。

  1. f が単射ならば f* は全射である。
  2. f が全射ならば *f は単射である。

証明. (1) f を単射とする。このとき全単射 g : A → Im f が得られる。任意の a ∈ A に対して g (a ) = f(a) である。

ψ ∈ Map (A, C ) を任意にとる。 c ∈ C を一つ固定しておく ( C が空集合でないことは仮定している)。 φ ∈ Map (B, C ) を b ∈ Im f に対しては φ (b) = ψ(g-1(b)) で定め、 b ⁄∈ Im f に対しては φ (b) = c と定める。このとき、任意の a ∈ A に対して

f *(φ)(a) = φ(f(a )) = φ (g(a)) = ψ(g-1(g(a))) = ψ (a )
となる。よって f*(φ) = ψ であり、 f* は全射である。

(2) f を全射とする。 f *(φ ) = f*(φ′) とする。このとき、任意の a ∈ A に対して ′φ (f(a)) = φ (f(a)) である。 f が全射なので ′φ = φ となり *f は単射である。 _

命題3.8.2. f : B → C とする。 f* : Map (A,B ) → Map (A, C) を f*(ψ ) = f ∘ ψ で定義する。
PIC
Figure3.7: f*(ψ) = f ∘ ψ

このとき次が成り立つ。

  1. f が単射ならば f* は単射である。
  2. f が全射ならば f* は全射である。

証明. (1) f を単射とする。 f*(ψ ) = f*(ψ ′) とすれば、任意の a ∈ A に対して f(ψ (a)) = f (ψ′(a)) であるが、 f が単射なので ψ (a) = ψ′(a) である。よって ′ψ = ψ であり f* は単射である。

(2) f を全射とする。任意の ψ : A → C に対して φ : A → B を以下のように定める。 a ∈ ψ -1(c) ( c ∈ C ) ならば φ (a ) ∈ f -1(c) となるようにする。 f が全射だから、これは可能である。また ⋃A = c∈C f -1(c) なので、これで任意の a ∈ A の行き先が定まる (実はここで後で説明する選択公理を使っている)。このようにすれば f*(φ ) = ψ であり f* は全射である。 _

問3.8.3. A = {1,2,⋅⋅⋅ ,m } , B = {1,2,⋅⋅⋅ ,n} とする。 A から B への単射の個数を求めよ。

3.9 演習問題

  1. 写像 f : ℝ → ℝ で |f-1(0)| = 3 となるものを一つ構成せよ。
  2. A, B は集合 X の部分集合、 P, Q は集合 Y の部分集合とする。写像 f : X → Y に対して次を示せ。
    1. f(A ∪ B ) = f(A ) ∪ f (B )
    2. f(A ∩ B ) ⊂ f(A ) ∩ f (B ) (等しくならない例も作れ)
    3. f(A - B ) ⊃ f (A ) - f(B ) (等しくならない例も作れ)
    4. f-1(P ∩ Q ) = f- 1(P ) ∩ f-1(Q )
    5. -1 - 1 -1f (P ∪ Q ) = f (P ) ∪ f (Q )
    6. f-1(P - Q) = f -1(P) - f- 1(Q)
  3. f : A → B , g : B → C とする。 f が全単射であるとき、 g が単射であることと g ∘ f が単射であることは同値である。また g が全射であることと g ∘ f が全射である ことは同値である。以上のことを示せ。
  4. f : A → B , g : B → C とする。 g が全単射であるとき、 f が単射であることと g ∘ f が単射であることは同値である。また f が全射であることと g ∘ f が全射である ことは同値である。以上のことを示せ。
  5. f : A → B , g : B → C , h : C → A に対して h ∘ g ∘ f , g ∘ f ∘ h , f ∘ h ∘ g のう ち二つが全射で、残りの一つが単射であるとすると、 f,g,h はすべて全単射であることを 示せ。また、二つが単射で、残りの一つが全射であるとしても、 f,g,h はすべて全単射で あることを示せ。