Written with StackEdit. Which of the following can be true for a mapping $$ f : \Bbb Z \to \Bbb Q $$
A. It is bijective and increasing
B. It is onto and decreasing
C. It is bijective and satisfied $f(n) \ge 0$ if $n \le 0$
D. It has uncountable image

Here's my attempt at finding a mapping that satisfies C(Following Method to prove countability of $\Bbb Q$ from Stephen Abbot )

Define $A_n = \{ \frac ab : a,b\ge 0, \gcd(a,b) = 1,a+b=n,b \ne 0 \}$

$B_n = \{ \frac {-a}{b} : a,b > 0, \gcd(a,b) = 1, a+b = n \} $

Mapping the negative integers and 0 to the set $A_n \forall n \in \Bbb N$ and positive integers to the set $B_n \ \forall n \ \in \Bbb N$ in the same manner as Stephen Abbot, the mapping will be surjective because the sets $A_n$ and $B_n$ would certainly cover $\Bbb Q$ and would be injective because no two sets have any elements in common.

Correct Answer - C
Source - Tata Institute of Fundamental Research Graduate Studies 2014

Is my proof correct? In any case, I can't imagine such a method to be required in this problem so is there a more 'easy' mapping? Also, why can't we have a mapping as desired in A and B?

  • $\begingroup$ Your construction for (c) is fine and seems like the natural one. Answers (a) and (b) are impossible because if true, they would imply that $\mathbb Q$ can be linearly ordered. And (d) is impossible because $\mathbb Z$ is countable. $\endgroup$ – Bungo Dec 2 '16 at 19:50

A. False. Suppose $f\colon\mathbb{Z}\to\mathbb{Q}$ is bijective and increasing. Then $f(0)<f(1)$. Take $q\in\mathbb{Q}$ with $f(0)<q<f(1)$. Then $q=f(n)$: can you see the contradiction?

B. False. Same argument as before.

D. False. The image is a subset of $\mathbb{Q}$.

C. True. Your argument is good, but it can be better formalized.

Take your favorite bijection $g\colon\mathbb{N}\to\mathbb{Q}_{>0}$ (positive rationals). Now define $$ f(n)=\begin{cases} -g(n-1) & \text{if $n>0$}\\[4px] 0 & \text{if $n=0$}\\[4px] g(-n+1) & \text{if $n<0$} \end{cases} $$ (note: $\mathbb{N}=\{0,1,2,\dotsc\}$).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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