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?






elementary-set-theory







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?






elementary-set-theory







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?






elementary-set-theory







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




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

                      Quarter-circle Tiles

                      Image
                      up vote 0 down vote favorite I have $99$ identical square tiles, each with a quarter-circle drawn on it like this: [asy] size(1.5cm); draw(Arc((2,0),1,90,180),red+1); draw((0,0)--(2,0)--(2,2)--(0,2)--(0,0)); [/asy] When I arrange the tiles in a $9times 11$ rectangular grid, each with a random orientation, what is the expected value of the number of full circles I form? I think this problem has to do with finding the chance any given 2x2 square has a circle, but I can't find it. expected-value share | cite | improve this question asked Nov 20 at 15:03 6minecraftninja 1 2
                      Read more

                      build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

                      Image
                      0 I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $epsilon$ -transition from the start state to the actual finite states of the given automaton. The start state of the given automaton will be my accepting(finite) state of my new one. All transitions will be reversed of course to recognize the reversed word. But how do I have to change the stack of the pushdown automaton? That's tricky. formal-languages automata context-free-grammar share | cite | improve this question edited Nov 29 '18 at 14:20 joee
                      Read more

                      Mont Emei

                      Image
                      Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog
                      Read more