I am required to prove this statement if it is true, or disprove it if it isn't. The function that I am working with is as follows: $p: \mathbb{N} × \mathbb{N} \to \mathbb{N}, p(a, b) = \frac{ab(b+1)}{2}$.

I am suspicious that this function is not injective, but I can't seem to find a counter-example, so I tried negating the definition of an injective function, that is $\forall x_1,y_1, x_2, y_2 \in \mathbb{N} × \mathbb{N}, p(x_1, y_1) = p(x_2, y_2) \Rightarrow (x_1, y_1) \ne (x_2, y_2)$ to prove the negation is true, which would imply the original statement is false. However, I am not sure if that is right.

What I did so far is, I simply supposed that $p(x_1, y_1) = p(x_2, y_2)$, so I got $\frac{x_1y_1(y_1+1)}{2} = \frac{x_2y_2(y_2+1)}{2}$ $\Leftrightarrow x_1y_1(y_1+1) = x_2y_2(y_2+1)$. But once I got here, I don't really know what to do next.


1 Answer 1


You have not properly negated the definition of an injective function. Remember when you negate the universal symbolic quantifier, it becomes existential. Further, you have not properly negated the implication.

Once you properly negate the definition, you will see that to prove a function is not injective, you just need an example of a pair of distinct inputs that map to the same output:

$p(a_1,3)=6a_1$, and $p(a_2,4)=10a_2$. To prove the function is not injective it suffices to find $a_1, a_2 \in \mathbb{N}$ such that $6a_1=10a_2$.

Hint: Consider the LCM of $6$ and $10$.

  • $\begingroup$ Would $a_1 = \frac{30}{6} = 5, a_2 = \frac{30}{10} = 3$ $\endgroup$
    – user743879
    Mar 11, 2020 at 20:20
  • $\begingroup$ Yes with this choice of $a_1$ and $a_2$, one sees $p(5,3)=p(3,4)$, but $(5,3)\neq(3,4)$. $\endgroup$
    – gfppoy
    Mar 11, 2020 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy