• 締切済み
  • 暇なときにでも

「集合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:全単射」 がどうやって導き出せるのでしょうか?

共感・応援の気持ちを伝えよう!

  • 回答数5
  • 閲覧数433
  • ありがとう数4

みんなの回答

  • 回答No.5

No.1です。 “有限集合”の定義の「数える」や「有限個」は、日常で使うような常識的な意味として使っています。だから、(2)も一応、言っといた方がよいかなぁと思ったんです。 matsui888さんが書いたように Xは“有限集合”⇔∃n∈N such that Map(X,{1,2,…n})∋∃f:全単射 と定義すれば、(2)は不要です。

共感・感謝の気持ちを伝えよう!

関連するQ&A

  • 「有限集合の部分集合は有限集合」の証明

    有限集合Xの部分集合Aは有限集合であることの証明がわかりません。 X;集合とします X⊇A とします。 とあるテキストによると,Aが有限集合であるとは, __∀F∈P(P(X))[F;A上帰納的 ⇒ A∈F] との事です。 ここで,Xの冪集合の冪集合P(P(X))∋FがA上帰納的であるとは, __φ∈F∧∀C∈F∀x∈A[C∪{x}∈F] であると事,とされています。 この定義に従って, _X;有限集合 ⇒ A;有限集合 を証明したいのですが,証明がさっぱり分かりません。 是非とも証明を御教え下さい。宜しくお願い致します。

  • 有限集合の定義って? {1,2,…}は有限集合?

    無限の公理は ∃A;[(φ∈A)∧((¬(x∈A))∨(x∪{x}∈A))] というものなので 集合Aが無限集合の定義は「(φ∈A)∧(¬(x∈A)∨(x∪{x}∈A)」ですよね。 すると、有限集合の定義は無限集合ではないもの 即ち Aが有限集合であるとは「¬[(φ∈A)∧(¬(x∈A)∨(x∪{x}∈A)]」 と言う風に書けると思います。 ¬[(φ∈A)∧(¬(x∈A)∨(x∪{x}∈A)]は ¬(φ∈A) ∨ ¬(¬(x∈A)∨(x∪{x}∈A))と書け、 ¬(φ∈A) ∨ ((x∈A)∧¬(x∪{x}∈A)) したがって、 (Aはφを含まない) ∨ (x∈A)∧(Aはx∪{x}を含まない) となってしまい、自然数全体の集合から0を差し引いたN\{0}という集合 {φ∪{φ},(φ∪{φ})∪{φ∪{φ}},…}は有限集合となってしまいますよね。 (∵この集合はφを含んでいないので) でもこれを有限集合とは到底思えませんよね。 一体何処から間違っているのでしょうか?

  • 自身への写像が全単射となることの証明

    (1) 写像f:A→Aとする。Aが有限集合であるとき、写像fが単射ならばfは全単射である事を示せ。 (2) Aが無限集合であるとき、fは全単射か。そうであれば証明せよ。そうでないなら反例を示せ。 上の問題の(1)は以下のように考えました。 f(A) は A の部分集合。 f(A)≠A と仮定すると、A とその真部分集合との間に全単射が存在したことになる。これは、無限集合の定義であるため、有限集合は全単射である。 このような証明で十分なのでしょうか?また、上のように考えたのでAが無限集合であるときはfは全単射ではないと思うのですが、反例が思いつきません。 わかる人がいれば教えてください。よろしくお願いします。

  • 回答No.4

「A⊃∀B:真部分集合 に対しても Map(A,B)∋f:全単射 は存在しない」 は 「∀B⊆A(B≠A → ¬∃f∈Map(A,B) fは単射)」 「∀B⊆A(∃f∈Map(A,B) fは単射 → B=A)」 と同じです。 A≠空 とする。 a_0,…,a_n,… を次のように定義する。 a_0=Aの元 a_{n+1}=A\{a_0,…,a_n} の元(A\{a_0,…,a_n}≠空 のとき) a_{n+1}=a_0 (A\{a_0,…,a_n}=空 のとき) f∈Map(A,A)を次のように定義する。 f(a_k)=a_{k+1} f(x)=x (∀k(x≠a_k) のとき) B={f(x)|x∈A} とする。 Aが有限でも無限でも,f∈Map(A,B) は(全)単射である。 Aが有限 ⇔ B=A 注:Aが有限のとき,fの定義が,あるnについて f(a_n)=a_{n+1}=a_0 で終わる。

共感・感謝の気持ちを伝えよう!

  • 回答No.3

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

共感・感謝の気持ちを伝えよう!

  • 回答No.2

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

ちょっと紛らわしくなるので、次のように約束しておきます。 「集合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:全単射 は存在しない」 という定義から導き出す事は出来ないのでしょうか?

関連するQ&A

  • 集合は有限集合と無限集合だけですか?

    有限集合の元の数を考えるとき、 「いかなる有限集合よりも元の数が多い有限集合は存在しない」------(A) ことがわかります。一番大きな基数の有限集合が存在しないと言い換えても良いですね。 ところがここに無限集合の概念を導入すると 「いかなる基数の有限集合よりも大きい集合として無限集合がある」---(A’) ここで「大きい」とは二つの集合の元を対応させて行くと、「大きい」方の元が余ることを言います。 ここでは、“超有限集合”=無限集合という関係が成り立ちます。 さて、公理的集合論の公理により、無限集合Rから常にPower(R)が作れるので、 「いかなる無限集合よりも濃度の数が多い無限集合は存在しない」------(B) が成立しました。 一番大きな濃度の無限集合が存在しないと言い換えても良いですね。 ここで、有限、無限に続く第三の概念として、“超無限集合”=寿限無集合(仮名)という概念を導入します。 すると、(A)に対して(A’)が成り立ったように、(B)に対して(B’)が成り立ちます。 「いかなる濃度の無限集合よりも大きい集合として寿限無集合がある」---(B’) 質問1:このような寿限無集合はZFC公理系で無矛盾に定義できますか? 質問2:集合の種類は有限と無限の二種類でしたが、第三の概念を導入すると、無限集合では成り立たないが寿限無集合の世界だけで成り立つ定理も発見できると思うのですが、このような概念の拡張をした数学者はいましたか? 質問3:有限と無限以外に第三の概念を導入することが無意味であると立証できますか?

  • 無限集合の定義で

    ∃f:全単射 such that f:A→B (但し、BはAの真部分集合) の時、Aを無限集合と言うのがデデキントの無限集合の定義だと思いますが 非可算集合の時にも(例えば実数体)このような全単射写像はするのでしょうか?

  • 集合の問題お願いします

    Aが有限集合ならば、その真部分集合への単射は存在しない。 これを数学的帰納法で証明せよ。

  • 組み合わせの全体と部分集合の全体は等しいか?

    「組み合わせの全体」と「有限集合の部分集合の全体」は等しいと感じますが,この事に関する「証明」または「定理」は存在するでしょうか? ご存じの方,教えて下さい. 以下が質問の内容の詳細です. 正の整数を,1, 2, 3, ....., n-1, n とします.この n個の正の整数の組み合せ(重複は許さない)の総数 N は, N=Σ[r=1→n] n!/(r!(n-r)!)= =n!/(1!(n-1)!) + n!/(2!(n-2)!) + n!/(3!(n-3)!) +・・・+ n!/((n-1)!(n-(n-1))!) + n!/(n!(n-n)!) =(2^n)-1 ですから, N=(2^n)-1 です. そして,組み合せの全体そのものは, (1),(2),・・・,(n-1),(n), (1,2),(1,3),・・・, (2,3),(2,4),・・・, (1,2,3),(1,2,4),・・・, (2,3,4),(2,3,5),・・・, (1,2,3,4),(1,2,3,5),・・・, (2,3,4,5),(2,3,4,6),・・・, ・・・・・, (1,2,3,4,・・・,n-1,n) となります. 次に,有限集合を S = {1, 2, 3, ....., n-1, n} とします. n は正の整数です.S の部分集合(真部分集合でない,かつ,空集合は除く)の全体は, {1},{2},・・・,{n-1},{n}, {1,2},{1,3},・・・, {2,3},{2,4},・・・, {1,2,3},{1,2,4},・・・, {2,3,4},{2,3,5},・・・, {1,2,3,4},{1,2,3,5},・・・, {2,3,4,5},{2,3,4,6},・・・, ・・・・・, {1,2,3,4,・・・,n-1,n} となります. これらの S の部分集合の全体は,集合の元の構成が組み合せの全体と等しいですか? 分かる方,教えて下さい.お願いします.

  • "無理数全体の集合から実数全体への全単射が存在する"の証明の説明をお願いします。

    次の問題の解答で分からないところがあるので説明をしてもらいたいです。 問: 無理数全体の集合からRへの全単射が存在することを証明せよ 解: R-Q から R への全単射の存在を示せばよい R-Q は無限集合であるから、可算部分集合 A が存在する ここで Q は可算集合なので、A∪Q は可算集合 よって全単射 f: A→A∪Q が存在するので 関数 g:R-Q →Rを     g(x)= { x (x∈R-A)         〔 f(x) (x∈A) と定義すると g は全単射である ■ 最後のところで、なぜgを上のように定義すると全単射になるのかがわかりません。 よろしくおねがいします。

  • 「集合Sの真部分集合S'からSへ全単射写像が存在する時、Sを無限集合という」を使ってのR:無限の証明は?

    無限集合の定義は 「集合Sの真部分集合S'からSへ全単射写像が存在する時、Sを無限集合という」 だと思います。 NやQやZは無限集合であることはわかりますが、 R(実数の集合)が無限集合であることは上の定義から導く事は可能なのでしょうか? N⊂Rで 「無限集合を含む集合は無限集合である」 という命題からRは無限集合と導く他ないのでしょうか?

  • 位相空間の本で

    読んでいてあまりわからない所が2点ありまして、 1.XにXのすべての部分集合を開集合とする位相を入れると、   Xの部分集合Cがコンパクト ⇔ Cが有限集合 という部分と、 2.Xをコンパクトハウスドルフ空間、Yをハウスドルフ空間とするとき、   写像f:X→Yが全単射連続なら逆像f-1:Y→Xも連続になる という部分に疑問が残りました。 1.については、コンパクト⇒閉集合であることや、Cが有限集合なら有限個の開被覆で覆えるからコンパクトである、ということが使える(?)のではじめの「XにXのすべての部分集合を開集合とする位相を入れる」部分が必要ないのではないかとも思うのですが・・・ 2.については、Xがコンパクトハウスドルフ空間ならその部分集合Cもコンパクトでその写像はやっぱりコンパクトで・・・その逆像もコンパクトで・・・・? どこから連続の議論に持っていけばよいのかが分かりませんでした。 「証明は読者に委ねよう」というお得意の言い回しで飛ばされてしまっていて、なんだか消化不良のままです>< ご返答よろしくお願い致します。

  • 可算無限についてお願いします

    集合Xが有限集合の時、 ∪{Xの、要素数kの部分集合を全て集めた集合}  (k=0,1,2…|X|) は、Xのべき集合(2^X)と同じものですよね。 でも集合Xが有限集合ではなく、自然数の集合Nであった場合、 ∪{Nの、要素数kの部分集合を全て集めた集合}  (k=0,1,2…) は可算無限であり、Nのべき集合(2^N)は非可算無限だと聞きましたが、 その違いはいったいなぜ起こるのですか? ※ 集合Y(≠∅ )に対し f:Y→2^Y となる全射が存在しないので、X=Nとすることで2^Nが非可算である事は理解しています。

  • 有限集合からなる位相空間における写像の連続性

    ある位相空間Xから別の位相空間Yへの写像fが連続であるとは、Yの任意の開集合Oの逆像f^-1(O)が開集合であると定義されていると思いますが、この定義に従うと、有限集合に位相を入れた位相空間Xからの別の位相空間Yへの写像は、位相空間Xの集合が全部開集合となり、必ず連続になるのでしょうか。

  • σ-集合体について

    σ-集合体について (1)Ωは無限集合であるとする。 A={A⊂Ω:AまたはA^cが有限集合か空集合} この集合族Aは集合体であるがσ-集合体ではないことを示せ。 (2)Ωが有限集合のとき、その部分集合族Aが集合体ならばσ-集合体せあることを示せ。 (3)A,FはΩの部分集合族でA⊂Fとする。また、 A'={A⊂Ω:A^c?A} とする。Fが集合体であればA'⊂Fであることを示せ。 (4) (3)によってA'⊂σ(A)が示されるが、さらにσ(A')=σ(A)を示せ。 この問題が分かりません。 定義や定理は理解できるのですが、活用できません。 解答お願いします。