I'm having trouble proving the following:
1) Prove that a function f is one-one if and only if ∀xy∈A,x≠y→f(x)≠f(y).
I was told to do this by the contrapositive, so I show that f(x)=f(y) → x=y. However, how do I do this? Can I make an example?
2) Assume f:A→B is a correspondence (or bijection), i.e., f is one-one and onto. Show that f has a unique inverse (which we'll denote by f^(−1)), and that ∀x∈B,f(f^(−1)(x))=x, i.e., that f is f^(−1)'s inverse.
I'm unsure how to approach this one.
Best Answer
For the first part, prove the theorem directly from the definition of an injective function: a function is injective if (and only if, though the latter phrase is often left out in definitions) $f(x)=f(y)$ implies $x=y$.
But $f(x)=f(y)$ implies $x=y$ if and only if $x \not = y$ implies $f(x) \not = f(y).$ This is the application of contrapositive to the definition of one-to-one (injective) functions.
For the second part, you must first show that $f(x)$ has an inverse, then show that this inverse is unique. Since $f(x)$ is injective onto its range, $f(x)=f(y)$ implies $x=y.$
Designate a function $f^{-1}$ on the range element $f(x)$ in such a way that $f^{-1}(f(x))=x.$ We must show the function is well-defined, that is, there is no more than just $x$ as the answer. But $f(x)=f(y)$ if and only if $x=y,$ so $f^{-1}(f(x))=f^{-1}(f(y))=x.$ Hence $f^{-1}$ is well-defined. Similarly, $f^{-1}(f(x))=f^{-1}f(y))$ implies $x=y,$ from the definition of inverse, but from the one-to-one property of $f,$ we have $f(x)=f(y)$ so that $f^{-1}$ is itself also a one-to-one function. Finally, $f(x)$ maps onto all the range, so that $f^{-1}(x)$ maps onto all the domain, showing $f^{-1}$ is a bijection.
Now suppose $f(f^{-1})(x)=y.$ Then applying $f^{-1}$ to both sides gets $f^{-1}(y)=f^{-1}(x)$ which means $y=x$ since $f^{-1}$ is one-to-one. Hence $f(f^{-1})(x)=x.$
For uniqueness, suppose $f^{-1}(f(x))=x=g(f(x))$ for all $x.$ Then $f^{-1}(f(x))-g(f(x))=0$ for all $x,$ meaning $f^{-1}$ and $g$ are the same function. So the inverse must be unique.