Prove or disprove: $f$ is an injection iff $\exists g \forall x\ g(f(x)) = x$ ($f$ and $g$ are total functions from D to D)

Question

Problem

Let $f:D \to D$ be a total function from some non-empty set $D$ to itself. $x$ and $y$ are variables ranging over $D$, and $g$ is a variable ranging over total functions from $D$ to $D$. Determine whether or not the proposition $\exists g \forall x\ g(f(x)) = x$ is equivalent to the proposition that $f$ is an injection.

Attempt

I claim that the proposition $\exists g \forall x\ g(f(x)) = x$ is equivalent to the proposition that $f$ is an injection.

Proof:

1. First, I show one direction of the equivalence: If $\exists g \forall x\ g(f(x)) = x$, then $f$ is injective.

   I will show it by contrapositive: If $f$ is not injective, then, for every $g$, there must be an $x$ such that $g(f(x)) \neq x$.

   Assume $f$ is not injective, and $g$ is any total function from $D$ to $D$.

   Since $f$ is not injective, there must be $x_0,x_1,y_0 \in D$ such that $x_0 \neq x_1$ and $f(x_0) = f(x_1) = y_0$. Then, we have that:

   $g(f(x_0)) = g(y_0)$ and $g(f(x_1)) = g(y_0)$.

   Note that, since $g$ is total, we know that $g(y_0)$ exists.

   From the above, $g(f(x_0)) = g(f(x_1))$.

   To show that this implies that there must be an $x$ such that $g(f(x)) \neq x$, there are two cases:

   • Case 1.1. If $x_0 \neq g(y_0)$, then $g(f(x_0)) = g(y_0) \neq x_0$. So, $x_0$ is an $x$ such that $g(f(x)) \neq x$.

   • Case 1.2. If $x_0 = g(y_0)$, then $g(f(x_1)) = g(y_0) = x_0$. However, since $x_0 \neq x_1$, this means that $g(f(x_1)) \neq x_1$. So, $x_1$ is an $x$ such that $g(f(x)) \neq x$.

   So, either way, there is an $x$ such that $g(f(x)) \neq x$.

2. Now, I show the other direction of the equivalence: If $f$ is injective, then $\exists g \forall x\ g(f(x)) = x$.

   Assume $f$ is total and injective. I will construct a $g$ such that $g$ is total and $\forall x\ g(f(x)) = x$.

   First, note that, since $f$ is total and injective, $f^{-1}$ is a surjective function, and $f^{-1}(x) = x$ for all $x$ in $f(D)$.

   So, for all $x$ where $f^{-1}(x)$ is defined, $g$ can be defined as $f^{-1}(x)$. However, $f^{-1}$ is not necessarily total, and $g$ needs to be total. To complete the definition of $g$, we need to define it for all $x \in D$ for which $f^{-1}(x)$ is not defined. For example, we can define $g(x) = x$ for all $x$ such that $f^{-1}(x)$ is not defined.

   So, $g$ can be constructed as:

   $g = \left\{\begin{matrix}f^{-1}(x) & \text{ if }f^{-1}(x)\text{ is defined}\\x & \text{ if }f^{-1}(x)\text{ is not defined}\end{matrix}\right.$

Is this correct? Thank you in advance.

Answer 1

Streamlined proof.

Assume for all x, g(f(x)) = x.
If f(x) = f(y), then x = g(f(x)) = g(f(y)) = y.
Thus f is an injection.

Assume f is an injection.
Define g:range f -> domain f.
If y in range f, then exists x with y = f(x).
Set g(y) = x.
Prove this is well defined using the fact that f is injective.
Show for all x, g(f(x)) = x.