Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to...











up vote
0
down vote

favorite













Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.




It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?



This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?










share|cite|improve this question




















  • 1




    "It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
    – Arthur
    Nov 22 at 8:07






  • 1




    @Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
    – 5xum
    Nov 22 at 8:34










  • " Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
    – Hagen von Eitzen
    Nov 22 at 8:35






  • 1




    Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
    – Asaf Karagila
    Nov 22 at 12:40








  • 1




    (Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
    – Asaf Karagila
    Nov 22 at 12:43















up vote
0
down vote

favorite













Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.




It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?



This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?










share|cite|improve this question




















  • 1




    "It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
    – Arthur
    Nov 22 at 8:07






  • 1




    @Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
    – 5xum
    Nov 22 at 8:34










  • " Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
    – Hagen von Eitzen
    Nov 22 at 8:35






  • 1




    Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
    – Asaf Karagila
    Nov 22 at 12:40








  • 1




    (Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
    – Asaf Karagila
    Nov 22 at 12:43













up vote
0
down vote

favorite









up vote
0
down vote

favorite












Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.




It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?



This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?










share|cite|improve this question
















Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.




It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?



This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?







elementary-set-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 22 at 12:39









Asaf Karagila

301k32422753




301k32422753










asked Nov 22 at 8:05









Gummy bears

1,87311430




1,87311430








  • 1




    "It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
    – Arthur
    Nov 22 at 8:07






  • 1




    @Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
    – 5xum
    Nov 22 at 8:34










  • " Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
    – Hagen von Eitzen
    Nov 22 at 8:35






  • 1




    Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
    – Asaf Karagila
    Nov 22 at 12:40








  • 1




    (Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
    – Asaf Karagila
    Nov 22 at 12:43














  • 1




    "It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
    – Arthur
    Nov 22 at 8:07






  • 1




    @Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
    – 5xum
    Nov 22 at 8:34










  • " Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
    – Hagen von Eitzen
    Nov 22 at 8:35






  • 1




    Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
    – Asaf Karagila
    Nov 22 at 12:40








  • 1




    (Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
    – Asaf Karagila
    Nov 22 at 12:43








1




1




"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07




"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07




1




1




@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34




@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34












" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35




" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35




1




1




Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila
Nov 22 at 12:40






Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila
Nov 22 at 12:40






1




1




(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila
Nov 22 at 12:43




(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila
Nov 22 at 12:43










2 Answers
2






active

oldest

votes

















up vote
0
down vote













Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.






share|cite|improve this answer




























    up vote
    0
    down vote













    Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.



    Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.






    share|cite|improve this answer























      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008864%2fprove-that-set-mathbbz%25c3%2597-mathbbq-is-countably-in%25ef%25ac%2581nite-by-constructing-a-b%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      0
      down vote













      Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
      i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.






      share|cite|improve this answer

























        up vote
        0
        down vote













        Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
        i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.






        share|cite|improve this answer























          up vote
          0
          down vote










          up vote
          0
          down vote









          Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
          i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.






          share|cite|improve this answer












          Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
          i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Nov 22 at 8:15









          Yadati Kiran

          1,352418




          1,352418






















              up vote
              0
              down vote













              Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.



              Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.






              share|cite|improve this answer



























                up vote
                0
                down vote













                Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.



                Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.






                share|cite|improve this answer

























                  up vote
                  0
                  down vote










                  up vote
                  0
                  down vote









                  Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.



                  Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.






                  share|cite|improve this answer














                  Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.



                  Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Nov 22 at 12:52









                  user26857

                  39.2k123882




                  39.2k123882










                  answered Nov 22 at 8:26









                  M. Santos

                  564




                  564






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008864%2fprove-that-set-mathbbz%25c3%2597-mathbbq-is-countably-in%25ef%25ac%2581nite-by-constructing-a-b%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Ellipse (mathématiques)

                      Quarter-circle Tiles

                      Mont Emei