Answer to Question #300115 in Discrete Mathematics for Yaku

Question

Let O be the set of odd numbers and O’ = {1, 5, 9, 13, 17, ...} be its subset. Define

the bijections, f and g as:

f : O $\to$ O’, f(d) = 2d - 1, $\forall$ d $\in$ O.

g : $\Nu$ $\to$ O, g(n) = 2n + 1, $\forall$ n $\isin$ $\Nu$ .

Using only the concept of function composition, can there be a bijective map from $\Nu$

to O’? If so, compute it. If not, explain in details why not.

Answer 1

Given that the functions $f \text{~and~} g$ are bijections, defined as $f(d) = 2d - 1, \forall d \in O,$ $g(n) = 2n + 1, \forall n \in \N$. Here $O' = \{4x + 1 : x\in \N \cup \{0\}\} .$

But we see that, $g : \N \to O$ is not surjective since there is no preimage of 1 in $\N$.

For, $1= g(n)=2n+1 \implies n = 0$, but $0\notin \N$.

Hence there cannot be a bijective function from $\N \to O'$.

For $g$ must be bijective, it is must be defined as $g: \N \cup \{0\} \to O$.

Setting $g: \N \cup \{0\} \to O$ and using the fact "composition of two bijective functions is bijective", we have $h = f \circ g : \N \cup\{0\}\to O'$ is also a bijective function. The composition of functions is

$h(x) = (f \circ g)(x) = f(g(x)) = f(2x+1) = 2(2x+1)-1 = 4x+1,~\forall x \in \N \cup \{0\}.$