Bijections in Combinatorics (TOMATO Obj 168)

Bijection principle is a very useful tool for combinatorics. Here we pick up a problem that appeared in I.S.I.'s B.Stat-B.Math Entrance.

Part 1: The problem and the hints

Part 2

 Part 3

TIFR 2014 Problem 12 Solution - Mapping Properties


TIFR 2014 Problem 12 Solution is a part of TIFR entrance preparation series. The Tata Institute of Fundamental Research is India's premier institution for advanced research in Mathematics. The Institute runs a graduate programme leading to the award of Ph.D., Integrated M.Sc.-Ph.D. as well as M.Sc. degree in certain subjects.
The image is a front cover of a book named Introduction to Real Analysis by R.G. Bartle, D.R. Sherbert. This book is very useful for the preparation of TIFR Entrance.

Also Visit: College Mathematics Program of Cheenta

Problem:

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.

Chatuspathi

TIFR 2013 Problem 28 Solution -Bijective continuous non-homeomorphism


TIFR 2013 Problem 28 Solution is a part of TIFR entrance preparation series. The Tata Institute of Fundamental Research is India's premier institution for advanced research in Mathematics. The Institute runs a graduate programme leading to the award of Ph.D., Integrated M.Sc.-Ph.D. as well as M.Sc. degree in certain subjects.
The image is a front cover of a book named Introduction to Real Analysis by R.G. Bartle, D.R. Sherbert. This book is very useful for the preparation of TIFR Entrance.

Also Visit: College Mathematics Program of Cheenta

Problem:True/False?

Let \(f:X\to Y \) be a continuous map between metric spaces. If \(f\) is a bijection, then its inverse is also continuous.

Hint:

No need to go into weird spaces. Start with familiar spaces, find out counterexamples.

Discussion:

One way to search for counterexamples is finding spaces that can not be homeomorphic but surely has a one way continuous function. For example, start with a not-connected space and have its image connected. Then you can't go back, because connected sets will go to a connected set only (under continuous functions). Or similar thoughts can be made about compact sets.

To illustrate, I will give one such example.

Consider \( I=[0,1] \). And \(A=[-0.5, 0]\) \(B=(1,2]\). Translation by \(0.5\) takes \(A\) to \([0,0.5]\) and translating \(B\) by \(-0.5\) gives \((0.5,1]\). Therefore, we get \(I\) as the whole image of \(f\) where \(f(x)=x+0.5\), \(x\in A \) and \(f(x)=x-0.5\), \(x\in B\). This \(f\) is a continuous function from \(A \cup B \) to \(I\). This can be checked by sequence criteria, or pasting lemma as well. Note that for pasting lemma we need \(A\) and \(B\) be closed. But they truly are closed because here we are considering the space \(A \cup B \) as a subspace of \(\mathbb{R}\). That means, \(B\) can be written as a closed set in \(\mathbb{R}\) intersection the space \(A \cup B \).

Now that we know \(f\) is continuous, f is bijective is easy to check. And further, by our starting point, we know that inverse function can not be continuous since our domain space \(A \cup B \) is not connected (or compact) while I is.

Helpdesk