682 viewsDiscrete maths

Consider the function h:N×Nso that h(a,b)=(2a+1)2^b1, where N={0,1,2,3,… }is the set of natural numbers.

Prove that the function h is an injection (one-one) and that it is also a Surjection (onto)

Anonymous 0 Comments

h(a,b) = h(c,d) then (a,b) = (c,d) –>one-one function definition

(2a+1)2b-1 = (2c+1)2d-1

(2a+1)2b= (2c+1)2d——(1)

(2a+1)/(2c+1)= 2b/2d

check parity of LHS and RHS

LHS = odd/odd = always odd

RHS = 2b-d = always even except b-d =0

If LHS = RHS then b-d = 0 then b=d

substitute b=d in eq(1)

(2a+1)2b= (2c+1)2d

2a+1 = 2c+1  So a=c

Proving that it is Surjection

we have to prove that every element of co-domain is mapped to some element of domain. That means every natural number {0,1,2,3…} should be produced by (2a+1)2b-1 for some a,b ∈ {0,1,2,3…}

then (2a+1)2b should produce {1,2,3……}

case1: Odd natural numbers {1,3,5,….}

when b=0

(2a+1)2b will become 2a+1

so every odd number can be produced

Case2: Even numbers

even numbers can be divided into two ways with respect to their prime factorization.

  1. which contains only 2 as their prime factor                                            we can write it as 2b and can be covered with (2a+1)2b where a=0
  2. which contains some other prime factors                                                     lets say it 2b X p1Xp2Xp3X…..Pk ( where pi is other prime numbers)    which is 2b X (odd number) = which is in (2a+1)2b  form, So can be produced. So finally every natural number can be covered by above function.
WP2Social Auto Publish Powered By : XYZScripts.com