College Mathematics Corner USA Math Olympiad

Mapping properties (TIFR 2014 problem 12)


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.


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.