Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
In your question doesn't " There exists ! " mean : "There does not exist"? Should the ! not be there? –  Adam Rubinson Nov 28 '12 at 13:44
    
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 –  fhyve Nov 29 '12 at 2:18
    
Ah right, thanks fhyve! I didn't know that! In that case everything seems correct. –  Adam Rubinson Nov 29 '12 at 9:19

2 Answers 2

up vote 2 down vote accepted

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'$.

share|improve this answer
    
Really? I was sure that the injectivity was needed to define the function as well... –  Asaf Karagila Nov 26 '12 at 8:04
    
@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. –  martini Nov 26 '12 at 8:08
    
I should probably wake up completely before making further remarks. :-) –  Asaf Karagila Nov 26 '12 at 8:09
    
@AsafKaragila Want some coffee? ;-). –  martini Nov 26 '12 at 8:12

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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