Stating that a function is injective using quantifiers

465 Views Asked by At

Using quantifiers, we have to state that a function f is injective meaning that for a unique element in the domain, there will be a unique image associated with that specific element and no two pre images can share a same image. So my answer for this would be:

$$\forall a\forall b(f(a)=f(b)\leftrightarrow a=b)$$

This answer seems correct to me as $f(a)$ can only be equal to $f(b)$ when a=b.

But the answer given is: $$\forall a\forall b(f(a)=f(b)\rightarrow a=b)$$

I don't understand this answer.For all $a$ and for all $b$ if $f(a)=f(b)$ then $a=b$ , i get that part but in the case $f(a)\not=f(b)$ then $a=b$ or $a\not=b$, but we need to ensure that $a\not=b$ and in this statement both options are possible. Please explain.

1

There are 1 best solutions below

0
On BEST ANSWER

The formula $$\forall a\forall b\Big(f(a)=f(b)\rightarrow a=b\Big)$$ states that the function $f$ is injective: meaning that, for any two elements of its domain, if $f(a)=f(b)$, then you actually have that the elements you started with are one and the same, $a=b$.

But your formula is not actually wrong! It just has a redundant part, that is, $$\forall a \forall b\Big(f(a)=f(b)\leftarrow a=b\Big):$$ what is a function? A function $f:X\rightarrow Y$ is a relation on $X\times Y$ (that is, a subset of $X\times Y$) such that, if both $(a,y_{1})$ and $(a, y_{2})$ are in this relation, then $y_{1}=y_{2}$. But we usually write, to mean that $(x,y)$ is in a function $f$, $f(x)=y$, so this means that a function is a relation satisfying, for any $a$ and $b$ in its domain, that $$a=b\quad\text{implies}\quad f(a)=f(b),$$ what is exactly the redundant part of your formula. The extra implication you wrote down is already built in in the definition of function, and is therefore not necessary, although not wrong as well.