3
$\begingroup$

If $f: A \rightarrow B$ is injective, $\exists ! f^{-1}:f(A)\rightarrow A$ such that $f^{-1}f(x) = x$

I know the proof of this is super simple, like 2 lines (+ some for uniqueness), but I can't figure how to logically work it out. For definition of injective function, I have $\forall x,y\in A, f(x)=f(y) \implies x=y$.

So we are trying to show that for all $y \in f(A),$ there exists a unique $x\in A$ with $f^{-1}(y) = x$. Could I change y to f(x) right there?

$\endgroup$
  • $\begingroup$ In your question doesn't " There exists ! " mean : "There does not exist"? Should the ! not be there? $\endgroup$ – Adam Rubinson Nov 28 '12 at 13:44
  • $\begingroup$ It means "there exists a unique". If it were "not", it would go before the existential quantifier, but that is CS notation anyways. To say "there does not exist" would be $\not \exists$ or $\neg \exists$. See en.wikipedia.org/wiki/Uniqueness_quantification $\endgroup$ – fhyve Nov 29 '12 at 2:18
  • $\begingroup$ Ah right, thanks fhyve! I didn't know that! In that case everything seems correct. $\endgroup$ – Adam Rubinson Nov 29 '12 at 9:19
2
$\begingroup$

Note that the injectivity is needed for uniqueness only: If you are given $y \in f(A)$, then by the definition of $f(A) = \{f(x)\mid x \in A\}$ there exists a $x \in A$ with $f(x) = y$.

For uniqueness use injectivity: If $f(x) = y$ and $f(x') = y$, then $f(x) = f(x')$, hence $x=x'$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Really? I was sure that the injectivity was needed to define the function as well... $\endgroup$ – Asaf Karagila Nov 26 '12 at 8:04
  • $\begingroup$ @AsafKaragila I was reffering to the OP last paragraph. It is written there "we are trying to show that for all $y∈f(A)$, there exists a unique $x \in A$ [...]". Of course for having defined a function by this, we need injectivity. $\endgroup$ – martini Nov 26 '12 at 8:08
  • $\begingroup$ I should probably wake up completely before making further remarks. :-) $\endgroup$ – Asaf Karagila Nov 26 '12 at 8:09
  • $\begingroup$ @AsafKaragila Want some coffee? ;-). $\endgroup$ – martini Nov 26 '12 at 8:12
3
$\begingroup$

We can use the following:

Lemma 1: A function $f : X \to Y$ is invertible if and only if it is one-to-one and onto.

Proof: Suppose that $f : X \to Y$ is invertible. Then, there exists a function $g : Y \to X$ such that $(f \circ g)(x) = (g \circ f)(x) = x$. To see that $f$ is onto, pick an element $y \in Y$. Then, $f(g(y)) = y$ so that $y$ is in the range of $f$. To see that $f$ is one-to-one, suppose that $f(x) = f(y)$. Then, $$g(f(x)) = g(f(y)) \implies x = y.$$

Now, suppose that $f$ is one-to-one and onto. We will show that $f$ is invertible. As $f$ is onto, we have that $\forall y \in Y, \exists x \in X$ such that $y = f(x)$. Since $f$ is injective, we have that $f(x) = f(y) \implies x = y, \forall x , y \in X$.

Let $g : Y \to X$ be defined by $g(y) = x$ if and only if $f(x) = y ~$ (why can we assume such a $g$ exists?). Then $g(f(x)) = g(y) = x$ and $f(g(y)) = f(x) = y$. Hence $g$ is an inverse of $f$. QED.

Lemma 2: The inverse of a function $f$ is unique if it exists.

Proof: Suppose that $f : X \to Y$ is invertible and it has two inverses $g, h : Y \to X$. Note that $\forall x \in X$, we have $f(g(x)) = x = f(h(x))$. Hence: $$ g(x) = g(f(g(x))) = g (f(h(x))) \implies g(x) = h(x). $$ Since $x$ was arbitrary, $g$ and $h$ must be identical as they have the same value for all $x \in X$. QED.

Finally, apply the above lemmas to the function $f\big|_A : A \to f(A)q$. Note that the function $f : A\to f(A)$ is bijective so long as it is injective. By definition, $$ f(A) = \left\{y \in B : f(x) = y ~~~\text{ for some }~~ ~x \in X\right\}, $$ so that $f\big|_A : A \to f(A)$ is surjective, and hence $f|_A$ is bijective.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.