Prove $f: A \rightarrow B$ is strictly injective, $\implies$ $f^{-1}$ is a function and dom $ f^{-1} \subset B$

Question

The question I have about this proof is that, do I need to choose a specific function $f:A\rightarrow B$ that is not injective but surjective? Will I lose generality if I do?

For instance, I was thinking of choosing $A = \mathbb{N_3}$ and $B=\mathbb{Z}$ and $f:\mathbb{N_3}\rightarrow\mathbb{Z}$ as $f(x) = -x$.

$f = \{(1,-1),(2,-2),(3,-3)\}$

You can see thusly that $f$ is injective, but of course it only maps to a finite number of elements of a countably infinite set so it's not surjective.

$f^{-1} = \{(-1,1),(-2,2),(-3,3)\}$

We can see of course that the dom $f^{-1} = \{-1,-2,-3\} \subset \mathbb{Z}$.

Have I lost generality using this specific example? Is there a way to generalize the proof that I'm missing?

---

UPDATE:

Here is a more general proof I have formulated.

Show $f:A\rightarrow B$ injective, not surjective $\implies f^{-1}$ is a function and dom $f^{-1} \subset B$.

---

Assume $f$ is injective $\iff f(x_1) = f(x_2) \implies x_1 = x_2$.

Let $x\in A$ and $f(x)=y\in B$.

$f = \{(x_1,y_1), (x_2,y_2), ... \}$

$f^{-1} = \{(y_1,x_1), (y_2, x_2), ... \}$

$\forall y\in B, \exists! x\in A$ s.t. $(y,x) \in f^{-1}$, so $f^{-1}$ is a function.

Choose an arbitrary $y \in$ dom $f^{-1}$.

We know $f(x) = y \in B, \forall x \in A$.

$y \in$ dom $f^{-1} \land y \in B \implies$ dom $f^{-1} \subseteq B$.

Now we seek to prove dom $f^{-1} \subset B$.

Suppose for the sake of contradiction that dom $f^{-1} = B$.

$f$ is not surjective, so $\exists y \in B$ such that $\forall x \in A, f(x) \neq y$.

But $f^{-1}(y) = x$, where $f^{-1}:$ dom $f^{-1} \rightarrow A$.

It follows that $\exists y \in B$ such that $y \notin$ dom $f^{-1}$.

$\implies$ dom $f^{-1} \neq B$

dom $f^{-1} \neq B \land$ dom $f^{-1} \subseteq B \implies$ dom $f^{-1} \subset B$.

Answer 1

First you need to show that $f^{-1}:f(A)\to A$ is a function. It takes elements from the image of $f$, and sends them back to $A$. What would make $f^{-1}$ a function? It must map each element of its domain to one element in its range. So in other words you need to show that if $z,w\in f(A)$ such that $z=w$, then $f^{-1}(z)=f^{-1}(w)$. Hint: The fact that $f$ is injective will help you here.

To show that $dom(f^{-1})\subsetneq B$, pick an element $x\in dom(f^{-1})$ and show that $x\in B$. Then show that there exists some element $y\in B$ such that $y\notin dom f^{-1}$.

---

Here are my comments on your current attempt. Your text will be in boxes.

Let $x\in A$ and $f(x)=y\in B$.
$f = \{(x_1,y_1), (x_2,y_2), ... \}$
$f^{-1} = \{(y_1,x_1), (y_2, x_2), ... \}$

This notation works only if $A$ is countable. It would be better represented by $f=\{(x,y)|\, x \in A, \, y=f(x) \}$.

$\forall y\in B, \exists! x\in A$ s.t. $(y,x) \in f^{-1}$, so $f^{-1}$ is a function.

This is true, but you should clarify why $x$ is unique. This is where the fact that $f$ is injective is important.

Choose an arbitrary $y \in$ dom $f^{-1}$.
We know $f(x) = y \in B, \forall x \in A$.
$y \in$ dom $f^{-1} \land y \in B \implies$ dom $f^{-1} \subseteq B$.

The quantifier $\forall$ is incorrect. It should be "for some" $x\in A$ since $y$ is fixed! This means that there exists an $x\in A$ such that $f(x)=y$. Hence $y$ is in the image of $f$, which means $y\in B$. Since the choice $y\in dom(f^{-1})$ was arbitrary, we have dom $f^{-1} \subseteq B$.

Now we seek to prove dom $f^{-1} \subset B$.
(Suppose for the sake of contradiction that dom $f^{-1} = B$.)
$f$ is not surjective, so $\exists y \in B$ such that $\forall x \in A, f(x) \neq y$.
(But $f^{-1}(y) = x$, where $f^{-1}:$ dom $f^{-1} \rightarrow A$.)
It follows that $\exists y \in B$ such that $y \notin$ dom $f^{-1}$.
$\implies$ dom $f^{-1} \neq B$

The two bolded lines with parentheses are not necessary.

---

Ok, with those fixes everything should be good!

Answer 2

Wheter or not the given $f:\>A\to B$ is surjective is completely irrelevant. In any case we have the range $f(A)\subset B$, and it is this range that might qualify as domain of $f^{-1}$. An example: We study the function $\exp:\>{\mathbb R}\to{\mathbb R}$ with range ${\mathbb R}_{>0}$. The question then is whether there is an inverse function $\exp^\leftarrow:\>{\mathbb R}_{>0}\to{\mathbb R}$.

For any point $y\in f(A)$ the full inverse image $$f^{-1}\bigl(\{y\}\bigr):=\{x\in A\>|\>f(x)=y\}$$ is a nonempty subset of $A$. If $f$ is injective then this set is a singleton, i.e., contains exactly one element. Unpacking this element we then obtain the inverse function $$f^{^-1}:\quad f(A)\to A,\qquad y\mapsto{\rm the}\bigl(f^{^-1}\bigl(\{y\}\bigr)\bigr)$$ we are interested in.