オレの余剰次元

言いたいことも言えないこんな4次元じゃ

公開日
2022年5月13日
更新日
2022年5月21日

有限集合

対象
大学2.0年
前提知識
集合の基礎
写像

有限集合や,集合の元の個数について解説します.

空写像について

集合 に対し,写像 を形式的に考えることができます.その前に, との直積が であることの説明をします.

現代数学(集合論)では,順序対 で定義されます.これは, の元です.ここで, は集合 の冪集合のことです.

さて, に対する 全体は として定義されます.これを我々は普通, とも書きます. または のとき, は常に成り立たないので, です.

さて,集合 (空も認める)と, に対し, は成り立ちます.なぜならば,上の文は の略記で, は次に成り立ちません.つまり, 自体は常に成り立ちます( が成り立たないとき, は常に成り立つ).形式的な話ですが, は写像の定義に当てはまります.これを空写像といいます. ゆえに に限り, ともかけます.

ちなみに のとき, は写像の一条件 を満たしません.この文は の略記で, は常に不成立だからです.

命題

空写像

集合 に対し,写像 はただ一つ存在し, である.

命題

は全単射である.

の書き換えであることに注意してください.

証明

は常に成り立つので, は全射.

も常に成り立つので は単射.

切片の定義

集合の元の個数を定義するには,大まかに言って を定義し,集合 に対し全単射 が存在するとき, の要素の個数を とします.しかし, を使っているので,再帰性定理で正しく定義します.

定義

再帰性定理 II より,

を満たす写像 が存在する.切片という.

の定義より

などが成り立ちます.一般の に対する などとかくことにしましょう.ここで, とは, を満たす のことで, の前者のことです.

命題

未満の自然数全体を表すという主張です.

証明

とおく. で, だから,また, を満たす写像 は再帰性定理 II より, に限る.ゆえに

有限集合の定義

個数が等しいとは,一対一対応が存在することに他なりません.

定義

同数

集合 に対し全単射 が存在するとき,同数といい, とかく.

同数と同じ言葉に,等濃,対等,同等などがあります.英語では equinumerous というらしいので,同数がしっくりくると考え,これを採用しました.

補題

証明

条件よりある全単射 が存在.写像 で定義する. のとき, である. は全単射だから,合成 も全単射で の定義域を に制限した から への全単射だから

命題

証明

についての帰納法で, を示せばよい. で, と対等なのは に限るので,.すなわち のとき成り立つと仮定. ならば,ある全単射 が存在. とすると で矛盾.ゆえに だからある に対し .したがって だから,補題より .帰納法の仮定より だから, すなわち .よって のときも成立.

定義

有限集合と元の個数

集合 に対し,ある が存在し となるとき,有限集合という. である は一意的に定まり,これを 元の個数といい, とかく.有限集合でない集合を無限集合という.

例えば のとき,全単射 が存在します.各 とかくことにすれば と表せます.一般の に対し, のときは, などとかくことにします.

有限集合の性質

命題

加法性

のとき,

証明

とおくと,全単射 がそれぞれ存在. を以下で定義: が全単射であることを示す.単射性から. とする. の大小関係について以下の3通りが考えられる.

(1) のとき, は単射だから ,i.e.,

(2) のとき, だから

(3) のとき,(1) と同様にして

いずれの場合でも だから, は単射.

次に全射性を示す.任意に をとる. のとき, は全射だから,ある に対し .このとき, のとき, は全射だから,ある に対し .このとき, に注意すると,.以上より は全射.

が全単射であることが示されたので,

命題

有限集合の部分集合は有限集合である.

証明

に対し, となる集合 の部分集合が有限であることを帰納法で示せばよい. のとき, の部分集合は に限るので成立. のとき成り立つと仮定し, とする. の部分集合 を任意にとる. のとき, は有限集合. のとき, をとる. は, の部分集合で, だから帰納法の仮定より は有限集合.元の個数を とすると,.よって のときも成立.

命題

有限集合 に対し,

有限集合は,自身の真部分集合とは対等にならないということです.

証明

有限集合の部分集合は有限だから, は有限.条件より .ゆえに,.和の公式より だから,

有限集合 に対し,

命題

有限集合 に対し

証明

より .ゆえに である.

命題

は無限集合である.

証明

は全単射だから .真部分集合と同数になるので, は有限集合ではない.

補題

写像 の有限部分集合 に対し,

証明

とし, となる に対し が成り立つことを帰納法で示せばよい. のとき, より成立. のとき成り立つと仮定し, とする. をとると, だから, また, だから のときも成立.

定理

有限集合の基本定理

有限集合 に対し,以下が成り立つ.

  1. が単射ならば は全射.
  2. が全射ならば は単射.

この定理のネーミングの由来は足立恒雄氏『数 体系と歴史』によるもので,(2) の証明は (1) と同様だから読者が試みよ,といった旨のことが書かれていましたが,やたら苦労しました.(笑)

証明

(1) が単射だから,終集合を にした全射 が全単射になり が全射でないとすると, だから, 有限集合は真部分集合と対等にならないので .矛盾.

(2) が全射より,.ここで, が単射でないとすると,ある に対し で,.よって 一方,補題より だから矛盾.