Let p 01 Times N rightarrow Z defined by rho n m n2nm m Pr

Let p: {0,1} Times N rightarrow Z defined by rho (n, m) = n-2nm + m. Prove or provide a counterexamples for the following statements. rho is surjective. rho is injective.

Solution

The function f : {0,1} ×N Z given by p(n,m) = n-2mn+m is surjective. To see this, suppose that we have an arbitrary element of the codomain n Z. Then p(n, 0) = n 0 = n, so the element (n, 0) {0,1} ×N× Z is an element of the domain mapping to n in the codomain. Thus p is surjective. On the other hand, p is not injective. For example, note that p(3, 1) = p(1,3) even though (3, 1) != (1,3) [not equal to].