The Gateway to Computer Science Excellence
+2 votes

Consider the function $h: N \times N \rightarrow N$ so that $h(a,b) = (2a +1)2^b - 1$, where $N=\{0,1,2,3,\dots\}$ is the set of natural numbers.

  1. Prove that the function $h$ is an injection (one-one).
  2. Prove that it is also a Surjection (onto)
in Set Theory & Algebra by Veteran (52.2k points)
edited by | 520 views
can any body proof the onto part


any idea..


@Verma Ashish

I think proving one-one is very easy directly from the definition.

Let's prove its surjective.

$\underline{\mathbf{Proof \;for\; Surjection\; (onto):}}$

$3$ steps followed in induction:

  1. Prove for $\mathbf {n = 1}$
  2. Assume its true for $\mathbf{k+1}$
  3. Then, prove it for $\mathbf{n}$

Let us prove first that any positive number can be written in the form $\mathbf{2^a(2b+1)}$, where $\mathbf{a, b \in non-negative\ integers}$

It is true for $\mathbf{n = 1} \text{(Substitute a = 0, b = 0)}$

Now, let's suppose its true of all $\mathbf {k < n}$,

$\therefore$ we need to prove that its true for $\mathbf n$.

When $\mathbf {n \in odd}$, let $\mathbf{2b+1}$. Then we can assume $\mathbf{a = 0}$

when $\mathbf{ n \in Even, \;\text{let} \;n = 2m}$

Then by using induction conjecture, there should exist natural numbers $\mathbf {a_1}$ and $\mathbf b$ so that $\mathbf{m = 2^{a_1}(2b+1)}$

Then $\mathbf{n = 2^a(2b+1)}$, where $\mathrm {a = a_1+1}$

Hence, proved.

Thanks, @jeet

I proved one-one by basic definition..(in answer)

3 Answers

+4 votes

The given function is $h(a,b)=(2a+1)2^b-1$

$h:N\times N\to N$


(i) injection:-

$h$ will be one-to-one if, $h(a,b)=h(c,d)\implies (a,b)=(c,d)$


$\Rightarrow (2a+1)2^b-1=(2c+1)2^d-1$

$\Rightarrow \frac{2a+1}{2c+1}=2^{d-b}$

If $d\neq b$ then RHS will always be even, but LHS is (odd/odd) which is odd.

$LHS = RHS \text{ only if }d=b,$

$\Rightarrow \frac{(2a+1)}{(2c+1)}=1$

$\Rightarrow (2a+1)=(2c+1)\Rightarrow a=c$

$\implies (a,b)=(c,d),\; hence\; h$ is one-one.

(ii) Surjection:-

For $h$ to be onto, there should not be any non-negative integer which can't be generated by the function. i.e. all the elements of co-domain should be mapped by some element of domain set.

Now look at the function it is $(2a+1)2^b-1$

If $b=0, (2a+1)2^b-1=2a \implies$ all non-negative even numbers generated.

If $b\neq 0,(2a+1)2^b-1\implies$ all non-negative odd numbers generated.

So all the numbers of co-domain (i.e. $N$) are mapped by some $(a,b)$ pair. Hence h is onto (surjective).

by Boss (13.1k points)
Nice answer.

For the below part, I understand the outcome would be odd always. Though how can it be concluded that all the odd numbers would be generated? 

If $b≠0,(2a+1)2^b−1$ ⟹ all non-negative odd numbers generated.

Any odd number can be written in $(2a+1)2^b-1$ form.

Ex:-(i) 35,  $(2a+1)2^b-1=35$

$\implies (2a+1)2^b=36\implies 9\times 2^2(a=4,b=2)$

(ii) $87=(2a+1)2^b-1$

$\implies (2a+1)2^b=88\implies 11\times 2^3(a=5,b=3)$
In general,


$(2a+1)2^b=even(\geq 2)$

And this even number can be represented as $odd\times 2^x$, uniquely.
These are two examples, it doesn't prove the statement that every odd number can be generated by $(2a+1)2^b−1$
Yup this makes sense!
Yes.. 2 examples can't prove it..

I have also given general idea in 2nd comment..
JEET's comment also makes sense that if every positive integer can be generated by $\mathbf{n = 2^a(2b+1)}$,then every non negative integer will be generated by $\mathbf{n = 2^a(2b+1)-1}$
0 votes
for every  value of (a,b) there exist value in co-domain set which makes it an onto  function here
by Loyal (5.7k points)
which makes co-domain = range here hence onto
Actually we need to prove it is a bijection or not, right?

@Kaluti is there any proof for this?


for every value of (a,b) there exist value in co-domain set 

This statement neither implies one - one nor onto..

0 votes


function  h(a,b)=(2a+1)2b−1h(a,b)=(2a+1)2b−1, 

lets start with

(0,0)= 0


(0,2)=3 ... we can see every time function output is unique 

(1,0)=2 ... output unique .. so every function is one to one

 and every co-domain image in domain so function also onto 

by Active (1.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,382 answers
105,323 users