Categories

# Mapping properties (TIFR 2014 problem 12)

Question:

There exists a map $f:\mathbb{Z} \to \mathbb{Q}$ such that $f$

A. is bijective and increasing

B. is onto and decreasing

C. is bijective and satisfies $f(n)\ge 0$ if $n\le 0$

D. has uncountable image.

Discussion:

Option D is out of the question right away. Because the co-domain $\mathbb{Q}$ is countable, and the image set is a subset of the co-domain set, any subset of countable set is countable, so image set has to be countable.

Let’s assume $f$ is onto and decreasing. Then $…\ge f(-1) \ge f(0) \ge f(1) \ge f(2) \ge …$.

At this point, we don’t know for sure whether $f(0)=f(1)$ or not. But, for the map to be onto, we must have strict inequality somewhere in the above chain of inequalities.

Let’s say $f(a)>f(a+1)$. Then we ask what is the pre-image of the rational number $\frac{f(a)+f(a+1)}{2}$?

Let $f(n)=\frac{f(a)+f(a+1)}{2}$

Since, $f(n)=\frac{f(a)+f(a+1)}{2}>f(a)$ and $f$ is decreasing, $a>n$.

Also, since $f(n)=\frac{f(a)+f(a+1)}{2}<f(a+1)$ and $f$ is decreasing, $n>a+1$.

The two inequalities $a>n$ and $n>a+1$ together give a contradiction.

Therefore, option B is false.

What did we use here, only onto-ness and that f is decreasing. If instead our function $f$ was bijective and increasing then we will get a similar kind of contradiction:

Suppose $f$ is bijective and increasing. Then $f(0)<f(1)$ (One-to-one ness guarantees the strict inequality)

We have $\frac{f(0)+f(1)}{2}\in\mathbb{Q}$.

Therefore there exists $m\in\mathbb{Z}$ such that $f(m)= \frac{f(0)+f(1)}{2}$.

We then have $f(0)<f(m)<f(1)$ which means $0<m<1$, a contradiction because there is no natural number in between 0 and 1.

So option A is false.

We know that $\mathbb{Q}$ does have a bijection with $\mathbb{Z}$, in other words $\mathbb{Q}$ is countable.

Now, both the set $A=\{n\in \mathbb{Z}| n\le 0 \}$ and $B=\{q\in \mathbb{Q}| q\ge 0\}$ are countably infinite, therefore has a bijection between them. To see this, let $f_1:A\to \mathbb{Z}$ and $f_2:B\to \mathbb{Z}$ be bijections. Then $f_2^{-1}o f_1:A \to B$ is a bijection.

Similarly $C=\{n\in \mathbb{Z}| n> 0 \}$ has a bijection with $D=\{q\in \mathbb{Q}| q< 0\}$.

Now, we have $h:A\to B$ and $g:C\to D$ two bijections.

Then define $f(n)=h(n)$ for $n\in A$ and $f(n)=g(n)$ for $n\in C$ to get a bijection from $\mathbb{Z}$ to $\mathbb{Q}$. This is true because $A \cup B= \mathbb{Z}$ and $C \cup D= \mathbb{Q}$.

And this $f$ satisfies the condition of option C: $f$ is bijective and satisfies $f(n)\ge 0$ if $n\le 0$

Therefore, option C is true. ## By Ashani Dasgupta

Ph.D. in Mathematics from University of Wisconsin Milwaukee (USA)
Founder - Faculty at Cheenta