edited by
3,124 views
15 votes
15 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)
edited by

4 Answers

38 votes
38 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)$

$h(a,b)=h(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.

$\text{LHS} = \text{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).

edited by
4 votes
4 votes

To prove h is one-one we need to basically prove that h cant be same for any two binary pairs i pick,

thus, more formally For h being one-one. h(a,b)=h(c,d) => (a,b)=(c,d)

So we will prove the contrapositive of it i.e. (a,b) != (c,d) => h(a,b) !=h(c,d)


Now lets pick h(a,b)=(2a+1)2^b -1 and h(c,d)=(2c+1)2^d -1

For comparing the above i ignore ‘-1’ coz any ways its just the gap within them! (even if you dont ignore not much of an issue coz if those two numbers turn out to be same then one doing a ‘-1’ still they would be same and if they were initially different then doing a ‘-1’ wont change the gap between them)

So lets analyse this h function in binary..as it would be easier to prove i feel.

h(a,b)=(2a+1)*2^b  [ignore -1]

which basically means take the binary equivalent of a => left shif by 1 bit (indicated by 2*a) =>and then add 1 to it (means make it odd or equivalently saying make its LSB bit as 1)=> and then left shift the whole previous setting of bits by ‘b’ bits to left (indicated by a multiplication of 2^b)

So my claim is after doing all this ill get

a number in which ‘b’ lsb bits are zero and then b+1 st bit is guaranteed to be 1

Now remember this rule ..i just formulated we will use it to prove for two different binary pairs h cant be same.

so lets pick up c,d=> h(c,d)=(2c+1)2^d

NOW,

Okay so lets begin the comparison, 

For 2 binary pairs to differ atleast one of the element of the tuple should be different,

Case 1: For (a,b) and (c,d) assume a=c but b!=d

This case is easy,

by the above interpretation its clear that the ‘b’ in (a,b) represents a ‘b’ bit left shift after which b+1 st bit is guranteed to be 1 (..as 2a+1 is defintely “odd”)

So if b!=d that means they differ by atleast 1.

So say b<d (as they differ so either would be smaller than the other)

thus doing a left shift by ‘b’ (say b=3) bits makes b+1 st bit as 1 (=> 3rd bit =0 and 4th bit in binary is 1)

and doing a left shift by ‘d’ (say d=4) bits makes d+1 st bit as 1 (=>4th bit =0 and 5th bit in binary is 1)

Thus as per the highlighted part in this case we can conclude here itself that h(a,b) and h(c,d) can’t be same.

Now also due to this it even doesnt matter what ‘a’ and ‘c’ actually was now they might be same or might be different doesnt matter, we actually proved just on the basis of ‘b’ and ‘d’ that they differ altogether.

Case 2: For (a,b) and (c,d) assume a!=c and b!=d

I think i need not to prove this, as if you follow till here then its clear that if ‘b’ and ‘d’ differ then (a,b) and (c,d) never be same irrespective of whatever ‘a’(=>more precisely 2a+1) and ‘c’(more precisely 2c+1)  are…

Case 3: For (a,b) and (c,d) assume a!=c and b=d

This is the last case by which they can differ !

Now again its also easy to prove why they differ here too!

as ‘b’ and ‘d’ are same thus both have b+1 st bit as 1 (or can also be called as d+1 st bit)

and then post that we have binary of ‘a’ and ‘c’  (more precisely binary of 2a+1 and 2c+1 ), as we know they arent same => so is there binary wont be same

hence even in this case if the two tuples are different then h cannot evaluate as same proved.

THUS USING THE CONTRAPOSITIVE STATEMENT ITS CLEAR TO SAY THAT IF h EVALUATES SAME FOR TWO BINARY PAIRS THEN THOSE BINARY PAIRS HAVE TO BE SAME !

Thus we got an injection here!


 

Now proving that this function is ONTO is not a big deal,

So lets do some ‘setting’,

let b=0 for h(a,b)

we get,

h(a,0) = (2a+1)*2^b – 1 = (2a+1) – 1 = 2a 

enumerating over a as {0,1,2,3...} generated whole of the “EVEN NUMBER SPACE”

ITS EASY TILL HERE..

NOW COMES THE INTERESTING CASE ..To prove “h” also “SPANS” whole of the ODD number space! ,

Lets say it doesnt SPAN whole of the ODD number space (for any setting of a and b)

then definitely there should exists atleast one odd number who cant be expressed as (2a+1)2^b-1

so,

(2a+1)*2^b – 1 != k  (let k be that odd number)

(2a+1)*2^b != k+1 ==> NOW bcoz k is ODD , k+1 is definitely EVEN

THUS,

(2a+1) !=  (k + 1) / 2^b

Now as we know k+1 is EVEN = > (since k is chosen to be ODD)

THINK OF ‘k+1’ LIKE A BAG whose NET WORTH IS EVEN so DEFINITELY IT SHOULD CONTAIN SOME NUMBER OF 2’s IN IT STUFFED !

Let that ‘ some number of 2’s ’ be ‘m’

SO k+1 contains 2^m as a factor inside it.

Now as we divide it by 2^b, lets ‘raise’ b to m so that 2^b=2^m

and Now perform the division of k+1/2^b=k+1/2^m 

So this would remove off all 2’s in k+1 (or in a way throw out all 2’s from the bag named k+1)

Thus,

what we would eventually left off would be a PURE ODD NUMBER, lets call it as ‘an_odd’

Thus we obtain,

(2a+1) != an_odd

Now RHS is an ODD number (we did its ‘setting' just now!)

and its easy to see that why LHS is ODD (more precisely 2a+1 is basically the way how odd numbers are defined ..more simply...on division by 2 giving a remainder of 1=>2(a)+1)

But we started off by claiming that LHS != RHS

which seems to be a false claim!

Thus LHS has to be equal to RHS thus,

WE PROVED THAT THERE CANNOT BE ANY ODD NUMBER, WHO CAN POSSIBLY BE DEPRIVED OF NOT BEING ABLE TO EXPRESSED BY THE GIVEN DEFINITION OF h(a,b).

Thus we proved that h is ALSO ONTO

SO,

h being ONE-ONE + ONTO => h is BIJECTIVE.

edited by
0 votes
0 votes
for every  value of (a,b) there exist value in co-domain set which makes it an onto  function here
0 votes
0 votes

h:N×N→N

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

lets start with

(0,0)= 0

(0,1)=1

(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 

Related questions