• 締切済み
  • すぐに回答を!

2つの可算無限集合においてその直積は可算無限集合である

2つの可算無限集合においてその直積は可算無限集合であるということ{f(i,j)=1/2(i+j-1)(i+j-2)+j}を数列、または格子を使って証明するにはどうしたらよいか教えてください。

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

  • 回答数2
  • 閲覧数1129
  • ありがとう数2

みんなの回答

  • 回答No.2

格子を使って説明する方法はたとえば「無限と連続」遠山啓著の分数が,可算無限個である証明で出てきます. m/n(n,mは自然数)という分数の場合, 横軸にmを縦軸にnを配置します. 任意の分数j/kは横軸j縦軸kの交点という格子点で 表せます.あとは,この格子点をたとえば 1/1 1/2 2/1 1/3 2/3 3/3 ・・・1/n 2/n ・・・ n-1/n ・・・ のようにたどると,自然数と全単射が作れるので(但し,1/2=2/4=3/6・・・のように同じ数のときは飛ばすようにする必要がある.)この分数と自然数の濃度は同じといえます. 直積の場合も同じ(分数の時のように飛ばして数えることがないので分かりやすいと思います.)考えで,全単射を作れます. ∀(n,m)∈N×N(記号がなかったのでかけるで代用) に対して, k∈Nを k(n,m)=n+Σ(j=1 to m-1)j とすれば,全単射となります.

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

質問者からのお礼

ありがとうございます。参考になりました。このやり方で考えてみます。

関連するQ&A

  • 有理数集合の濃度は非可算?!

    有理数集合の濃度は非可算?! 有理数集合Qの濃度は可算ですが、以下のように考えたところQ(の部分集合)が非可算無限集合になってしまいました。 どこが誤りかご教授願います。 正の有理数は素数のベキを用いて 2^α×3^β×…(α,β,…∈Z) で一意的に表される。 素数の個数は可算無限個なので Q+とZの可算無限個の直積が一対一対応する。 このときZも可算無限集合なので、可算無限集合の可算無限直積で非可算無限集合になる。 よってQ+は非可算無限集合である。

  • 可算無限集合と非可算無限集合の違いが分かりません。

    例えば、こういう問題のときそれぞれ可算無限集合と非可算無限集合のうちどっちですか? (1)0≦x≦1を満たす実数x (2)任意の自然数N (3)任意の実数R 回答よろしくお願いします。

  • 可算無限集合について。

    aを任意の有理数としたとき、0<a<1を満たすaの集合って可算無限集合ですか?

  • 回答No.1

可算無限集合であることを証明するためには、(i,j)と1,2,3,....の間に一対一の対応があることを証明すればいいのです。 そして、この問題では、ご親切に、具体的にf(i,j)=1/2(i+j-1)(i+j-2)+jという対応を与えてくれています。つまり、この関数自身が、(i,j)と1,2,3,....の間の一対一対応になっているのです。 それを証明しましょう。 まず、(i+j-1)か(i+j-2)のどちらかが偶数になるので、f(i,j)は自然数です。ここで、f(i,j)=f(k,l)かつ、i≠k,j≠lと仮定して、矛盾を導くのが一番簡単なやり方です。 つまり、f(i,j)が自然数で、値が重ならないことを示してやればいいのです。 背理法使わなくても出来ます。 f(i,j)<f(i+1,j)<f(i,j+1)<f(i+1,j+1) という関係が成り立つ(i,j)→Zへの写像fを作れば帰納的に証明できます。実際にこの関数fはそうなっています。 f(i,j+1)<f(i+1,j+1) f(i,j)<f(i+1,j) は、ほとんど自明ですね。 f(i+1,j)-1=f(i,j+1)は、すぐにわかります。よって、 f(i+1,j)<f(i,j+1) です。 以上より、 f(i,j)<f(i+1,j)<f(i,j+1)<f(i+1,j+1) が成立。また、 f(1,1)=1<f(2,1)=2<f(1,2)=3<f(2,2)=5 より、帰納法を用いて証明できた。 となります。

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

質問者からのお礼

ありがとうございます☆すっきりしてて分かりやすいないようでした。自分なりにもう一度考えてみます。

関連するQ&A

  • 直積集合 N*Z の可算集合

    可算集合の証明の問題です。 (1)数え方の規則:N→N*Z を与えなさい。 (2)13番目の要素は?(1,1,1)(-2,1,4)は何番目の要素? N^2のときとは違って困ってます。よろしくお願いします。

  • 無限集合に関することです。

    無限集合に関することです。 自然数全体を可算無限個の互いに交わらない集合A1,A2,A3・・・(どのAkも可算無限集合)の和として表わされることを示したいのですがどうすれば良いですか? 可算無限集合は自然数全体の集合との間に1対1対応の関係がある集合のことなのに、自然数全体を互いに交わらない集合で示せるのでしょうか?

  • 有限集合を無限に直積した集合の濃度は?

    有限集合Aがあったとして、A×A×A×・・・と加算無限回直積させたら濃度はどうなりますか? 直感では加算無限個になると思うのですが、証明する方法が思いつかないので教えてください もし言葉や記号に間違いがあったら教えてください、補足します

  • 可算であることの証明

    可算についてなのですが、次の2つがどうしても証明出来ません。 1.可算集合の無限部分集合は可算である 2.有理数a,bを端点とする開区間(a,b)全体の集合は可算である 一応濃度、可算集合については一通り勉強したのですが…。 言っている事はなんとなくわかるのですが、自分でいざ問題を解いてみる(証明してみる)と何をどう書いてよいのやらまったくのお手上げです。 きちんと理解できていないのが原因だと思うのですが、いろいろな本を読み漁ってもこの”集合論”という分野、いまいちピンときません。 どうか回答のほどよろしくお願いします。

  • 直積集合の証明問題

    A×B、C×Dは直積集合をして、 (A×BがC×Dの部分集合) ⇔ (AはCの部分集合、かつBはDの部分集合) という証明問題を解きたいのですが、あまりに当たり前なことなので、 逆に何から手をつけて解いていけばいいのか全く分かりません。 どなたか、証明の仕方がわかる方がいましたら、証明の方針だけでも教えて欲しいです。 よろしくお願いします。

  • 可算無限集合のベキ乗が可算無限でないことを対角線論法で証明する。

    http://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%B3%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AE%E5%AF%BE%E8%A7%92%E7%B7%9A%E8%AB%96%E6%B3%95 をみているのですが、 わかりません。 証明 背理法による。全単射 ψ: X → 2^X が存在したとしよう。X の部分集合 A を だいたい可算無限の意味がよくわかりません。 お願いします。

  • 位相 可算集合

    Xを非可算集合とし、AをXの可算な部分集合とする。このとき、XとX-Aが対等であるときを証明せよ。 この問題の解答と経過を教えてください!! おねがいします!!

  • 「直積集合の全集合」とは?

    別の方の質問 http://oshiete1.goo.ne.jp/qa4877672.html を見ていて気になった点についてです。 「集合族の空集合と全集合」とは何でしょうか? 通常、「空集合」や「全集合」は、何らかの集合の ベキ集合族に対して定義される概念かと思います。 一般の集合族に対する「全集合」とは、どのように 定義されるのでしょう? 「集合族Φの全集合」と言ったら、Φ自身のことでしょうか、 それとも、Φの最大元のことでしょうか? ご存知の方、解説よろしくお願いします。 先の http://oshiete1.goo.ne.jp/qa4877672.html の例で言えば、 ΨとΩの集合族としての直積は、質問氏の書いている Ψ×Ω = { (A,B) ; A∈Ψ, B∈Ω } ですが、これは、 ベキ集合族ではないし、σ集合族でもありません。 Y と Z の空間としての直積に付随するσ集合族 という意味で 言っているのだとすれば、「直積」は、このΨ×Ωではなく、 Ψ×Ωの任意個の元の和集合全体が成す集合族 になるハズです。 その際、「全集合」が Y×Z であることは違いありませんが… また、A×0 = 0×B = 0 と考えるなら、この式の「×」を 0 と B の集合としての直積と解釈したことになります。 Ψ×Ω = { A×B ; A∈Ψ, B∈Ω } と表記するのならば、 右辺内の A×B は、A と B の対 (A,B) という意図で 標準的でない書き方をしてしまったものと解釈すべきで、 A と B の集合としての直積ではありえません。 その場合、0×B は、Ψ×Ωの元で Y成分が 0、Z成分が B の ものであって、空集合ではありません。

  • 直積集合について質問です

    直積集合について質問です。 直積集合を定義することによってどのような利点が生まれるのですか? また集合Aと集合Bの直積集合において、集合Aの部分集合fを要素と考えて集合Bの要素と部分集合fを組にすることは可能ですか?

  • 可算無限個とは・・・

    可算無限個とは、どういうことなんですか? 数学辞典をもっていないので、困っています。 知ってる方がいらっしゃったら、教えてください!