Constructing a Bijection to Demonstrate Countably Infinite Set











up vote
0
down vote

favorite












I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.










share|cite|improve this question




























    up vote
    0
    down vote

    favorite












    I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.










    share|cite|improve this question


























      up vote
      0
      down vote

      favorite









      up vote
      0
      down vote

      favorite











      I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.










      share|cite|improve this question















      I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.







      elementary-set-theory cardinals






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Nov 22 at 3:41









      Andrés E. Caicedo

      64.6k8158246




      64.6k8158246










      asked Nov 22 at 2:40









      rcmpgrc

      174




      174






















          3 Answers
          3






          active

          oldest

          votes

















          up vote
          2
          down vote



          accepted










          The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.



          Exercise: check the various claims I've made in the previous paragraph!



          So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)






          share|cite|improve this answer




























            up vote
            0
            down vote













            It is not hard to construct explicitly an injective function $fcolon
            mathbf{Z}times mathbf{Q}tomathbf{N}$
            . For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.



            Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.






            share|cite|improve this answer




























              up vote
              0
              down vote













              If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.






              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%2f3008675%2fconstructing-a-bijection-to-demonstrate-countably-infinite-set%23new-answer', 'question_page');
                }
                );

                Post as a guest















                Required, but never shown

























                3 Answers
                3






                active

                oldest

                votes








                3 Answers
                3






                active

                oldest

                votes









                active

                oldest

                votes






                active

                oldest

                votes








                up vote
                2
                down vote



                accepted










                The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.



                Exercise: check the various claims I've made in the previous paragraph!



                So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)






                share|cite|improve this answer

























                  up vote
                  2
                  down vote



                  accepted










                  The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.



                  Exercise: check the various claims I've made in the previous paragraph!



                  So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)






                  share|cite|improve this answer























                    up vote
                    2
                    down vote



                    accepted







                    up vote
                    2
                    down vote



                    accepted






                    The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.



                    Exercise: check the various claims I've made in the previous paragraph!



                    So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)






                    share|cite|improve this answer












                    The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.



                    Exercise: check the various claims I've made in the previous paragraph!



                    So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Nov 22 at 2:55









                    Noah Schweber

                    119k10146278




                    119k10146278






















                        up vote
                        0
                        down vote













                        It is not hard to construct explicitly an injective function $fcolon
                        mathbf{Z}times mathbf{Q}tomathbf{N}$
                        . For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.



                        Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.






                        share|cite|improve this answer

























                          up vote
                          0
                          down vote













                          It is not hard to construct explicitly an injective function $fcolon
                          mathbf{Z}times mathbf{Q}tomathbf{N}$
                          . For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.



                          Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.






                          share|cite|improve this answer























                            up vote
                            0
                            down vote










                            up vote
                            0
                            down vote









                            It is not hard to construct explicitly an injective function $fcolon
                            mathbf{Z}times mathbf{Q}tomathbf{N}$
                            . For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.



                            Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.






                            share|cite|improve this answer












                            It is not hard to construct explicitly an injective function $fcolon
                            mathbf{Z}times mathbf{Q}tomathbf{N}$
                            . For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.



                            Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered Nov 22 at 3:11









                            P Vanchinathan

                            14.7k12036




                            14.7k12036






















                                up vote
                                0
                                down vote













                                If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.






                                share|cite|improve this answer

























                                  up vote
                                  0
                                  down vote













                                  If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.






                                  share|cite|improve this answer























                                    up vote
                                    0
                                    down vote










                                    up vote
                                    0
                                    down vote









                                    If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.






                                    share|cite|improve this answer












                                    If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.







                                    share|cite|improve this answer












                                    share|cite|improve this answer



                                    share|cite|improve this answer










                                    answered Nov 22 at 4:37









                                    Lee Mosher

                                    47.7k33681




                                    47.7k33681






























                                        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%2f3008675%2fconstructing-a-bijection-to-demonstrate-countably-infinite-set%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