「集合Xが有限集合⇒∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射」

質問

有限集合の定義は
「Aが無限集合⇔　A⊃∃B:真部分集合 such that Map(A,B)∋∃f:全単射」
の否定
「Aが有限集合⇔　A⊃∀B:真部分集合 に対しても Map(A,B)∋f:全単射　は存在しない」
ですよね。
これから
「集合Xが有限集合⇒∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射」
がどうやって導き出せるのでしょうか?

回答No.5

gururinbus

No.1です。

“有限集合”の定義の「数える」や「有限個」は、日常で使うような常識的な意味として使っています。だから、(2)も一応、言っといた方がよいかなぁと思ったんです。

matsui888さんが書いたように

Xは“有限集合”⇔∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射

と定義すれば、(2)は不要です。

回答No.4

mis_take

「A⊃∀B:真部分集合 に対しても Map(A,B)∋f:全単射　は存在しない」
は
「∀Ｂ⊆Ａ（Ｂ≠Ａ → ￢∃ｆ∈Map(Ａ,Ｂ) ｆは単射）」
「∀Ｂ⊆Ａ（∃ｆ∈Map(Ａ,Ｂ) ｆは単射 → Ｂ＝Ａ）」
と同じです。

Ａ≠空 とする。

ａ_0,…,ａ_n,… を次のように定義する。
ａ_0＝Ａの元
ａ_{n+1}＝Ａ＼{ａ_0,…,ａ_n} の元（Ａ＼{ａ_0,…,ａ_n}≠空 のとき）
ａ_{n+1}＝ａ_0 （Ａ＼{ａ_0,…,ａ_n}＝空 のとき）

ｆ∈Map(Ａ,Ａ)を次のように定義する。
ｆ(ａ_k)＝ａ_{k+1}
ｆ(ｘ)＝ｘ （∀ｋ(ｘ≠ａ_k) のとき）

Ｂ＝{ｆ(ｘ)｜ｘ∈Ａ} とする。

Ａが有限でも無限でも，ｆ∈Map(Ａ,Ｂ) は(全)単射である。
Ａが有限 ⇔ Ｂ＝Ａ

注：Ａが有限のとき，ｆの定義が，あるｎについて ｆ(ａ_n)＝ａ_{n+1}＝ａ_0 で終わる。

回答No.3

gururinbus

ごめんなさいNo.2の回答の集合Aは集合Xにかえる必要があります。

回答No.2

gururinbus

No.1です。
(1)で、Xが有限集合「A⊃∀B:真部分集合 に対しても Map(A,B)∋f:全単射　は存在しない」⇒Xは“有限集合”「集合Xの元の個数を数えてその数が有限個」　を導き、

(2)で、Xが“有限集合”「集合Xの元の個数を数えてその数が有限個」⇒∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射　　を導いたので

(1)、(2)より
Xが有限集合「A⊃∀B:真部分集合 に対しても Map(A,B)∋f:全単射　は存在しない」⇒∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射

が導けたと思うのですが。

お礼

ご回答有難うございます。

やっと意味が分かりました。
所で、「集合Xの元の個数を数えてその数が有限個の場合」の部分('数える'と'有限個'の定義)はどのように定義されているのでしょうか?
つまり、“有限集合”の定義を記号と数式で表すとどのように書けるのでしょうか?

恐らく、
Xは“有限集合”⇔∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射
が“有限集合”の定義だと推測します。
すると(2)は不要なのではないかと疑問に思ったのですが…

回答No.1

gururinbus

ちょっと紛らわしくなるので、次のように約束しておきます。

「集合Xの元の個数を数えてその数が有限個の場合、Xは“有限集合”と呼ぶことにする。そうでない場合、Xは“無限集合”と呼ぶことにする。空集合は元の個数が0個として“有限集合”として約束します。」

これから、無限集合、有限集合、“有限集合”、“無限集合”という言葉を区別して用います。

方針としては
(1)Xが有限集合⇒Xは“有限集合”　をまず示し、
(2)Xが“有限集合”⇒⇒∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射　を示します。

(1)背理法で示す。仮にXが有限集合であるにも関わらず、Xが“有限集合”でない。すなわちXが“無限集合”であると仮定する。
Xが空集合でないのでXの元が存在する。これをa1と記すことにする。次に、X＼{a1}が“無限集合”であることに注意します。(なぜなら、X＼{a1}が“有限集合”だとすると、Xも“有限集合”となってしまうから)
次にX＼{a1}の元をa2と記すことにする。すると、X＼{a1,a2}も“無限集合”。
以下、この操作を繰り返すと任意の自然数nに対し、X＼{a1,a2,…an}が“無限集合”であることがわかります。(正確には帰納法で示す。)
一般にX＼{a1,a2,…an}の元をan+1と書いてやれば、
{a1,a2,…an,…}⊂Xがわかります。(ここでa1,a2,…の元の指定に対し選択公理が使われています。)
写像fを次のように定義します。
f:X→X＼{a1} , X∋x≠aiならf(x)=x , X∋x=aiなら、f(ai)=ai+1　(i=1,2,…)
すると、fは全単射であることがわかります。(証明は、はしょります。)
よって、XとXの真部分集合X＼{a1}の間に全単射があるので、Xは無限集合となります。これは、Xが有限集合であることに矛盾。よって、Xは“有限集合”。

(2)Xが“有限集合”とする。元の個数が有限個なので、Xの元をa1,a2,…と記していき、
X={a1,a2,…,an}とする。(元の個数が有限個なのでこのように書ける。)

写像gをg(ai)=iと定義すれば明らかに全単射となる。
したがって、∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射は成立。

お礼

ご回答有難うございます。

> ちょっと紛らわしくなるので、次のように約束しておきます。
「Aが有限集合⇔　A⊃∀B:真部分集合 に対しても Map(A,B)∋f:全単射　は存在しない」
という定義から導き出す事は出来ないのでしょうか?