幾何学序論１

(1)

幾何学序論１ K.Ichihara

集合の対等と濃度

有限集合とは無限集合とは

可算集合と非可算集合

濃度の比較

冪集合の濃度

幾何学序論１

市原一裕

2014

^年

6

^月

9

^日（月）

2

^限

(2)

濃度の比較

冪集合の濃度

小テスト

1. 次の空欄にあてはまる語句を答えなさい．

I f は【】 ⇔ ∀y∈Y, ](f⁻¹(y))≥1

I f は【】 ⇔ ∀y∈Y, ](f⁻¹(y))≤1

I f は【】 ⇔ ∀y∈Y, ](f⁻¹(y)) = 1

2. f (x) = x

²

で定義される写像 f : R → R ^が全射でないことを示しなさい．

3. f (x) = x

³

で定義される写像 f : R → R ^が

単射であることを示しなさい．

(3)

濃度の比較

冪集合の濃度

有限集合とは

直感的な定義：含まれる元の個数が有限個の集合のこと．

つまり・・・

全ての元に（有限個の）番号が付けられる集合

⇒

その「番号」に対して，元たちと全単射がつくれる！

定義

2.8.1

【有限集合（

finite set

）】

集合

X

が有限集合であるとは，ある

n ∈

N^{に対して，}

全単射

f

:

{

1,2,3,

· · · , n } → X

が存在すること．

この

n

^を

X

^{に含まれる元の個数} ^といい，

]X

^{であらわす．}

注意

2.8.1

本当は先にNの定義をしないといけない．．．が，ここでは，

(4)

濃度の比較

冪集合の濃度

要素の個数と全単射

定理

2.8.1

２つの有限集合

X

と

Y

に対して，

1. ^単射

f

:

X → Y

^{が存在する}

⇔ ]X ≤ ]Y

2. 全射

f

:

X → Y

が存在する

⇔ ]X ≥ ]Y

3. 全単射

f

:

X → Y

が存在する

⇔ ]X

=

]Y

注意

2.8.2 (1)

の

⇒

^の対偶

「

]X > ]Y ⇒

^単射

f

:

X → Y

が存在しない」

は 鳩の巣原理 とよばれ有名（

1834

^{年，ディリクレ）．}

(5)

濃度の比較

冪集合の濃度

集合の対等

定義

2.8.2

【集合の対等（濃度が等しい）】

２つの集合

X

^と

Y

が対等である（濃度が等しい）とは，

全単射

f

:

X → Y

^{が存在すること．}^（

X ∼ Y

^とかく）

注意

2.8.3

ここでは「集合の濃度」とはなにか，という定義はしない．あくまで「濃度が等しい」ことの定義だけ．

定理

2.8.2

２つの有限集合

X

と

Y

が対等である

⇔ ]X

=

]Y

(6)

濃度の比較

冪集合の濃度

全射・単射と合成写像

無限集合についても，集合が対等である（濃度が等しい）

ことの定義は，有限集合のときと同じ，

つまり全単射が存在することと定義しよう．

定義

2.7.1

【無限集合（

infinite set

）】

集合

X

が無限集合であるとは，

X

とは異なる

X

の部分集合（つまり，

X

の真部分集合）で，

X

と対等な集合が存在すること．

例

2.8.1

N^{は無限集合．}

注意

2.8.5

鳩の巣原理より，有限集合は無限集合ではない．

(7)

濃度の比較

冪集合の濃度

可算集合と非可算集合

定義

2.9.1

【可算集合（

countable set

）】

集合

X

が可算集合であるとは，

X

^とN^{が対等である}

（つまり，全単射

X →

N^{が存在する）こと．}

可算集合でない集合を非可算集合（

uncontable set

）という．

例

2.9.1

Rは非可算集合（証明は対角線論法による）

(8)

濃度の比較

冪集合の濃度

濃度の大小

定義

2.10.1

【濃度の大小】

集合

X

と

Y

に対して，単射

f

:

X → Y

が存在するとき，

Y

^の濃度は

X

の濃度以上であるといい，

]X ≤ ]Y

^とかく．

定理

2.10.2

集合

X

^と

Y

^{に対して，}

]X ≤ ]Y

^かつ

]Y ≤ ]X

^のとき，

X

と

Y

は対等である，つまり，濃度は等しい

（つまり，全単射

f

:

X → Y

が存在する）

この定理は次の定理からわかる．

定理

2.10.2

，ベルンシュタインの定理（

1897

）

２つの集合

X

^と

Y

^{に対して，}

２つの単射

f

:

X → Y

と

g

:

Y → X

が存在するとき，

実は，全単射

h

:

X → Y

が存在する．

(9)

濃度の比較

冪集合の濃度

冪集合の濃度

次の定理によって，いくらでも濃度の大きな無限集合が存在することがわかる．

定理

2.7.1

任意の集合

X

に対して，

]X ≤ ]2

^X である．

幾何学序論１

幾何学序論１

2014

6

9

2

1. 次の空欄にあてはまる語句を答えなさい．

2. f (x) = x

で定義される写像 f : R → R が 全射でないことを示しなさい．

3. f (x) = x

で定義される写像 f : R → R が

単射であることを示しなさい．

⇒

2.8.1

finite set

X

n ∈

f

{

· · · , n } → X

n

X

]X

2.8.1

2.8.1

X

Y

f

X → Y

⇔ ]X ≤ ]Y

f

X → Y

⇔ ]X ≥ ]Y

f

X → Y

⇔ ]X

]Y

2.8.2 (1)

⇒

]X > ]Y ⇒

f

X → Y

1834

2.8.2

X

Y

f

X → Y

X ∼ Y

2.8.3

2.8.2

X

Y

⇔ ]X

]Y

2.7.1

infinite set

X

X

X

X

X

2.8.1

2.8.5

2.9.1

countable set

X

X

X →

uncontable set

2.9.1

2.10.1

X

Y

f

X → Y

Y

X

]X ≤ ]Y

2.10.2

で定義される写像 f : R → R ^が全射でないことを示しなさい．

で定義される写像 f : R → R ^が