集合と写像

集合と写像

鳩の巣原理とよばれる数学原理は,n + 1 羽のが n 個の巣に戻ろうとすれば必ずある巣には 2 羽以上の鳩が戻らなければならないというものである.ディリクレ部屋割り論法あるいは引き出し論法ともよばれる.
  1. 集合
  2. 写像
  3. 同値関係
  4. 有限集合の基本定理

1. 集合

いろいろなものの集まりを集合といい,その集合を構成しているものをという.属する元が1つもない集合を空集合といい,φ という記号で表す.A を集合とするとき,a ∈ A は a が A の元であることを表す.

集合 B の元がすべて集合 A の元であるとき,B は A の部分集合であるといい,B ⊂ A で表す.集合 A と集合 B が等しいとは,A ⊂ B かつ B ⊂ A ということをいい,A = B で表す.また,B ⊂ A であって,A = B ではないとき,B は A の真部分集合であるという.

問題 集合 A, B, C について,A ⊂ B かつ B ⊂ C であれば,A ⊂ C であることを示せ.

集合 A と B の和集合合併集合ともいう)を A ∪ B で,共通部分共通集合ともいう)を A ∩ B で表す.

2. 写像

集合 A の各元に対して,集合 B の元がただ1つ対応する規則 f が定まっているとき,この対応を A から B への写像といい,f: A → B で表す.

2つの写像 f: A → B,g: A → B が等しいとは,A のすべての元 a について,f(a) = g(a)が成立することをいい,f = g で表す.

実数や複素数への写像については関数を用いるのが普通である.

例題 集合 A = {a, b, c, d} から集合 B = {0, 1} への写像を記述せよ.

解答 写像 f: A → B は,0 と 1 からなる4個の数字の列 f(a)f(b)f(c)f(d) で表される.そのような列は以下の 16 個である.

0000, 0001, 0010, 0010, 0011, 0100, 0101, 0111

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

写像 f: A→ B が与えられたとき,B の部分集合 { f(a) | a ∈ A } を f による A のといい,f(A) で表す.とくに,B = f(A), すなわち,B のすべての元が f の像になるとき,f は全射であるという.

また,写像 f が1対1写像,すなわち,f(a) = f(a') となるのは a = a' の場合に限るとき,f は単射であるという.全射であると同時に単射でもある写像を全単射写像という.

問題 次の問に答えよ.

  1. 集合 A = {a, b, c, d} から,集合 B = {1, 2} への全射写像の個数を求めよ.
  2. 集合 A = {a, b} から,集合 B = {1, 2, 3, 4} への単射写像の個数を求めよ.

写像 f: A → B と写像 g: B → C が与えられたとき,写像 a → g(f(a)) を f と g との合成写像といい,gοf で表す.

写像 f: A → B が全単射写像であれば,B の任意の元 b について f(a) = b となる元 a ∈ A がただ1つ存在する.したがって,写像 b → a が定義される.この写像を f の逆写像といい,f-1 で表す.

例題 集合 A から集合 B への写像 f: A → B と B から A への写像 g: B → A が存在して,gοf = idA および fοg = idB が成立すれば,f も g も全単射写像である.

問題 集合 A から集合 B への写像 f: A → B と集合 B から集合 C への写像 g: B → C が与えられている.このとき,

  1. 写像 g が単射であり,合成写像 gοf が全射であれば,f は全射写像であることを示せ.
  2. 写像 f が全射であり,合成写像 gοf が単射であれば,g は単射写像であることを示せ.

3. 同値関係

数学のあらゆる分野に同値関係が登場する.与えられた集合の同じような性質をもつ元を1つのまとまりとしてあつかうという考え方である.たとえば,毎日は曜日で区別され,整数には偶数と奇数があるという具合である.さらには,りんごの3個もみかんの3個も同じと考えるというのが数の起源であろう.

集合 A の2元について,関係があるかないかということが決められているとする.このとき,a が b に関係があるということを a 〜 b という記号で表す.A の任意の元 a, b, c に対して,次の3条件が満たされる関係を同値関係という.

  1. (反射律) a 〜 a
  2. (対称律) a 〜 b ⇒ b 〜 a
  3. (推移律) a 〜 b, b 〜 c ⇒ a 〜 c
以下,集合 A に定義された同値関係 〜 について議論する. 元 a と同値な元全体の集合を a の属する同値類といい,[a] で表す.すなわち, [a] = { b ∈ A | b 〜 a } である.

補題 2つの同値類 [a] と [b] については,

  1. [a] = [b]
  2. [a] ∩ [b] = 空集合
のいずれか一方が成立する. 集合 A の同値関係 〜 による異なる同値類全体の集合を A/〜 で表し,同値類集合という.

整数の集合において,整数 a, b の差 a - b が 3 の倍数のとき,a 〜 b と定義すると,同値関係になることは明らかである.各同値類は 3 で割った余りで定まるので,{Z/〜} = {[0], [1], [2]} である.

例題 集合 A から集合 B への全単射写像 f: A→ B が存在するとき,A と B は対等であるといい,A 〜 B と書くことにする.この対等という関係は同値関係である.

解答 恒等写像 idA: A → A は全単射写像であるので,A 〜 A である.次に,A 〜 B,すなわち,全単射写像 f: A → B が存在すれば,逆写像 f-1: B → A も全単射写像であるので,B 〜 A である.最後に,A 〜 B,B 〜 C を仮定する.このとき,全単射写像 f: A → B, g: B → C が存在する.合成写像 h = gοf: A→ C が全単射写像であることが以下のようにして証明できるので,A 〜 C が成立する.

まず,h の全射性を示す.そのため,c ∈ C を任意の元とすると,g が全射であるので,c = g(b) となる元 b ∈ B が存在する.また,f も全射であるので,元 a ∈ A が存在して,b = f(a) が成立する.このとき,c = h(a) となるので,h は全射である.次に,h の単射性を示す.そのため,h(a) = h(a') を仮定する.写像 g が単射であるので,f(a) = f(a') となり,f の単射性から a = a' がわかる.

問題 集合 A から集合 B への写像 f: A→ B が与えられているとする.集合 A の2元 a, b について,f(a) = f(b) のとき,a 〜 b と定義すれば,関係 〜 は同値関係になることを示せ.さらに,f が全射であれば,同値類集合 A/〜 と集合 B は対等であることを示せ.

4. 有限集合の基本定理

有限集合の元の個数は厳密には次のようにして定義される.

定義 集合 A の個数 |A| が n であるとは,A が自然数の集合 {1,2, ..., n} に対等であることをいう.

この定義が意味をもつためには,n ≠ m のとき,{1,2, ..., n} と {1,2, ..., m} が対等ではないことを確認する必要がある.これは疑いようのない事実であるが,数学的帰納法によって証明することができる.

補題(鳩の巣原理) m > n のとき,{1, ..., m} から {1, ..., n} への単射写像は存在しない.

問題 一辺が 40cm の立方体の金魚鉢に 9 匹の金魚を入れた.このとき,互いの距離が 20√3 cm 以下になるような 2 匹の金魚の組が必ず存在することを示せ.

問題 縦横 n × n の碁盤を考える.

  1. n + 1 個の碁石を並べれば,2個以上並ぶ行(横の線)と2個以上並ぶ列(縦の線)があることを示せ.
  2. 2n + 1 個の碁石を並べれば,3個以上並ぶ行(横の線)と3個以上並ぶ列(縦の線)があることを示せ.

補題 m < n のとき,{1, ..., m} から {1, ..., n} への全射写像は存在しない.

命題 {1, ..., m} と {1, ..., n} が対等である必要十分条件は m = n が成立することである.

問題 {1, ..., n} から自分自身への単射写像は同時に全単射写像であることを証明せよ.

問題 有限集合 A の任意の元 a0 をとり,A' = A \{a0} とおけば,|A'| = |A| - 1 であることを示せ.

以上の考察から有限集合に関する次の定理を示すことができる.

定理(有限集合の基本定理) A, B を有限集合とする.

  1. |A| = |B| ⇒ A と B は対等である.
  2. |A| ≦ |B| ⇒ A から B への単射写像が存在する.
  3. |A| ≧ |B| ⇒ A から B への全射写像が存在する.
  4. |A| = |B| のとき,A から B への単射写像は全単射写像である.

有限集合 A とその真部分集合 B が対等になることはない.

このことは無限集合については成立しない.たとえば,A を自然数の集合とし,B = {2, 3, 4, ...,} とすると全単射写像 j → j - 1 が存在するので,A と B は対等である.


トップへ
酒井文雄記(2000年4月)