Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is $\mathbb{Q^+}$ countably infinite? I am trying to construct a bijection $\mathbb{Z^+}\rightarrow \mathbb{Q^+}$, i think it is obvious to find a injection from $\mathbb{Z^+}\rightarrow \mathbb{Q^+}$, but i cannot prove for that injection, there exist a surjection between $\mathbb{Q}$ and $\mathbb{Z}$. Is there any way to prove it ?

Edited: What about is there a bijection between $\mathbb{Z^+}\times \mathbb{Z^+}\rightarrow \mathbb{Q^+}$

share|improve this question
1  
Have you ever seen Cantor's zig-zag argument which shows that one can 'list' all the rational numbers? You can apply it only for elements of $\mathbb{Q}^{+}$, to see that it is countably infinite. –  Rankeya Mar 17 '12 at 2:51
    
See here. –  Alex Becker Mar 17 '12 at 2:55
    
About the question i edited, as we know $4\over 2$ = $2\over 1$, it seems that it is not easy to construct the bijection right? –  Mathematics Mar 17 '12 at 3:02
    
@Mathematics: if you have a list that contains each fraction at least once, you can get one that contains each fraction exactly once simply by looking at the sublist consisting of all elements that don't repeat an earlier one. –  Henning Makholm Mar 17 '12 at 3:26
    
$$\color{red}{(1,1)},\\ \color{green}{(1,2), (2,1)}, \\\color{blue}{(1,3), (2,2), (3,1)},\\ \cdots$$ and so on $\aleph_0$ times. –  user2468 Mar 17 '12 at 5:00
add comment

2 Answers

up vote 2 down vote accepted

There may be other ways to prove a bijection between a denumerable set and $\mathbb{Q}^+$, but I too ascribe to the diagonalization method. Since I'm suspecting this may be homework I'm not going to write out a full solution.

Consider a table where in row $i$ and column $j$, we place the rational number $\frac{j}{i}$; then every rational number appears in the table. Define a function $f: \mathbb{N} \rightarrow \mathbb{Q}^+$, and show that it is bijective. We can achieve this by traversing our table diagonally in the order, $$\frac{1}{1},\frac{2}{1},\frac{1}{2},\frac{3}{1},\frac{2}{2},\frac{1}{3},\frac{4}{1},...$$ I'm not going to draw out the table, but it is clear if you work it out from yourself how to go from here by skipping any number that you have already encountered in your list (in order to ensure $f$ is one-to-one). So, since every element of $\mathbb{Q}^+$ is encountered eventually, $f$ is onto and thus bijective. Therefore, $\mathbb{Q}^+$ is denumerable.

share|improve this answer
    
is there a bijection btw $Z^+\times Z^+$? –  Mathematics Mar 17 '12 at 5:34
add comment

See the Cantor-Bernstein-Schroeder theorem which says you just have to inject each set into the other. It turns that into a bijection. Now take $\frac ab \to 2^a3^b$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.