3

For a function $f : N \times N \rightarrow N$, such as $f(x,y)=2^{x-1}(2y-1)$ how would you go about proving the function is injective?

While I understand how to go about proving a function is injective for a function with one variable, generalizing beyond one variable has stumped me.

sbauer322
  • 33
  • 1
  • 5

1 Answers1

6

The technique is identical to the one variable case: Suppose that $f(x, y) = f(x', y')$ and show that $x = x'$, $y = y'$. In this case, we'd get

$$2^{x - 1} (2y - 1) = 2^{x' - 1}(2y' - 1)$$

Without loss of generality, $x \ge x'$, and so upon rearrangement we find that

$$2^{x - x'}(2y - 1) = 2y' - 1$$

Now if $x > x'$, the left side is even, while the right side is....

Can you take it from here?

  • I understand up until "Now if x>x′, the left side is even, while the right side is...." How would you go about getting to x=x' and y=y'? I am missing the importance of the left and right being odd or even. – sbauer322 Dec 01 '13 at 19:42
  • @ACP The left side is even, but the right side is odd. Is this possible? –  Dec 01 '13 at 19:44
  • @Bongers I would hope it is not possible, so as x cannot be greater than x' it must be equal to x'... Thanks! – sbauer322 Dec 01 '13 at 19:49
  • For $f(x,y)$ to be injective, it can't have the same value for two different pairs of arguments, no? Then how come $f(x,1/2) = 0 \forall x$? Doesn't that breaks its injectivity? – urquiza Oct 28 '14 at 20:21
  • 1
    @urquiza: $\frac{1}{2} \not \in N;$ and therefore the arguments $(x,\frac{1}{2});$ are not in the domain of $f$. Admittedly the original question should have written $\mathbb{N}$ instead of $N,;$ but for real values odd/even makes no sense. – gammatester Oct 29 '14 at 12:50