論理と集合要約 NO.8

写像は始集合と終集合をコミにして考える必要があるのでした。合コンのメンツが大事なように、 X と Y にどのぐらいの元があるのかが重要です。このことをうまく用いて、写像は始集合と終集合との元の多さを比べるのにも使われます。

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

第 8 回目の主題 : 写像

◎全射、単射、全単射。

定義 8.1 (再). 写像 f : X → Y が (1) ∀y ∈ Y ∃x ∈ X (f(x) = y) を満たすとき、 f は全射であるという。

(2) ∀x_{1}, x_{2} ∈ X(x_{1} ≠ x_{2} ⟹ f(x_{1}) ≠ f(x_{2})) を満たすとき、 f は単射であるという。

(3) 全射かつ単射であるとき、 f は全単射であるという。

全射、単射、全単射の判定には、 X, Y としてどのようなものを考えているかが大変重要な意味を持つ。

定理 8.2. f : X → Y が全単射ならば、つぎのような性質を満たす写像 f^{−1} : Y → X がただひとつ存在する。

y = f(x) ⇔ x = f^{−1}(y)

この f^{−1} のことを f の逆写像とよぶ。

問題 8.1. f : ℝ ∋ x ↦ 2x + 1 ∈ ℝ の逆写像を求めよ。

◎「ホテルヒルベルト」

一般に、 X から Y への単射が存在することは、 X の元のほうが Y の元よりも「少ない」ことを意味すると考えられる。 X の各々の元を「人」、 Y の各々の元を「ホテルの部屋」に例えると、単射の存在は一人ひとりが別々の部屋に入れることを意味するからである。同様に、 X から Y への全射が存在することは、 X の元のほうが Y の元よりも「多い」と考えられる。

ただし、無限集合においては、「多い」「少ない」の感覚は有限集合とは少し異なる。

問題 8.2. つぎのことをそれぞれ示しなさい。 (1) ℤ_{>0} から ℤ_{>0} \ {1} への全単射が存在する。

(2) ℤ から 2ℤ への全単射が存在する。

(3) ℤ から ℤ_{>0} への単射が存在する。

(4) ℤ_{>0}^{2} から ℤ への単射が存在する。

(5) ℤ^{2} から ℤ への単射が存在する。

(6) 任意の整数 n にたいして、 ℤ^{n} から ℤ への単射が存在する。

(7) ℚ から ℤ への単射が存在する。

集合の元 A の「個数」を #A と書こう。実は、「個数」は無限集合に対しても定義されて、さらに、単に「無限である」というよりも細かな尺度を導入することができる。そこで、そのような意味合いを込めて「濃度」という言葉を使うのが普通である。その定義は以下の通り。

定義 8.3. 集合 A に対して、 A の濃度と呼ばれる記号 #A を定める。濃度の間の等号は、次のような意味で使う。

#A = #B ⇔ (A から B への全単射が存在する。 )

この定義もちょっと間に合わせ的である。 (あとで「同値関係」という概念を導入することによりすこしマシにできる。 )

定義 8.4. 集合 A から B への単射が存在するとき、 #A ≤ #B と書くことにする。

この定義は A, B のとり方によらず、 A, B の濃度のみで決まっている。

定理 8.5. 集合 A, B, C に対して、

(#A ≤ #B and #B ≤ #C) ⟹ #A ≤ #C

がなりたつ。

論理と集合要約 NO.8

つぎの定理は基本的で、その証明は面白いが、少し難しいので web に置いておくことにする。興味がある人は

http://www.math.kochi-u.ac.jp/docky/kogi/ からたどるとよい。

定理 8.6 (ベルンシュタイン).

(#A ≤ #B and #B ≤ #A) ⟹ #A = #B

がなりたつ。

濃度の言葉 (とベルンシュタインの定理) を用いると、次のことが分かる

#ℤ = #(ℤ_{>0}) = #ℤ^{2} = #ℤ^{3} = #ℚ = #ℚ^{2} = #ℚ^{3}