Prove that for any injective $f: A \to B$ and bijective $g: B \to C$ a function $h$ can be defined so that $h(g(f(x))) = x$ for all $x \in A$

Question

I've struggled for a few hours with a convincing enough proof of the following.

Let

$A = \{\textrm{red}, \textrm{green}, \textrm{blue}\}$

$B = \{1, 2, 3, 4\}$

$C = \{\textrm{cat}, \textrm{dog}, \textrm{rabbit}, \textrm{turtle}\}$

$f: A \to B$ an injective function and $g: B \to C$ a bijective function.

Prove that for any choices of $f$ and $g$ a function $h: C \to A$ can be defined so that $h(g(f(x))) = x$ for all $x \in A$.

I initially went down some paths involving showing that various compositions of $f$, $g$, and $h$ are injective or surjective and as such can serve as inverses etc. But then I realised that $h$ can never be bijective since $A$ and $C$ have a different number of elements and I went back to square one.

This is my current proof:

Since $f$ is injective and $D_f = A$ then $V_f$ will always consist of three distinct elements in $B$ regardless of how $f$ is defined. Since also $g$ is injective, $V_g$ will always consist of three distinct elements in $C$ regardless of how $g$ is defined. (We're really saying that $g \circ f$ is injective since by definition $g(f(x)) = g(f(y)) \implies f(x) = f(y) \implies x = y$.) Since $D_h$ is larger than $A$ we can always define $h$ so that $V_h = A$, in other words that it is surjective, and so that each $y \in C$ is the image of the respective $x \in A$. We then have a function $h: C \in A$ that satisfies that $h(g(f(x))) = x$ for all $x \in A$. Note that it's not required for $g$ to be surjective or $h$ to be injective to always be able to define $h$ accordingly. In fact, $h$ can never be injective since $A$ and $C$ have a different number of elements.

What do you think? Am I completely off the track here? Although this is maybe the least stringent proof I have produced so far, it is to myself the most convincing one, unless I've missed some fatal flaw in the logic.

Any suggestions or comments are much appreciated.

Answer 1

The essence of your argument is sound, good job!

Of course, giving a single example or even privileging a single example in a proof is not a good form, so your proof shouldn't be stating that $A$ has three members in it. The proof works perfectly well even if $A$, $B$, and $C$ are infinite sets. You also don't want to refer to the fact that $A$ and $C$ don't have the same number of elements, because there's nothing in the statement of the proof to suggest that $f$ can't be surjective.

Answer 2

It suffices to require that $A \neq \emptyset$ and both $f:A \to B$ and $g:B \to C$ are injective, with neither one required to be bijective.

Since $f$ and $g$ are injective, so is their composition $g \circ f:A \to C$. Also, any injection with nonempty domain has a left inverse (send elements of the image to their unique preimages and other elements of the codomain to some random element of the domain, which exists since the domain is assumed to be nonempty). In particular, $g \circ f$ has a left inverse $h:C \to A$ for which $\forall a \in A \ h(g(f(a)))=a$ (since $A$ is nonempty).

Similarly, if $f:A \to B$ and $g:B \to C$ are surjective functions, then the composition $g \circ f:A \to C$ is also surjective, and has a right inverse $h:C \to A$ for which $\forall c \in C \ g(f(h(c)))=c$ (assuming the axiom of choice).

Answer 3

Since, as you say, $g \circ f$ is injective, we can set $$ h(x) = \begin{cases} (g \circ f)^{-1}(x) & (g\circ f)^{-1}(\{x\}) \neq \emptyset \\ a & (g\circ f)^{-1}(\{x\}) = \emptyset \end{cases} $$ where $(g\circ f)^{-1}(x)$ is the unique element in $(g\circ f)^{-1}(\{x\})$, and $a$ is some fixed element of $A$.

Take $x \in A$, and set $y = (g \circ f)(x)$. Then $(g \circ f)^{-1}(y) = x$. Hence $$h(g(f(x))) = h((g\circ f) (x)) = h(y) = (g \circ f)^{-1}(y) = x$$

Because of how I defined $h$, we should probably consider the case where $A = \emptyset$. In this case, the only function $h : C \to A$ is the empty function, and $h(g(f(x))) = x$ is trivially true for all $x \in A$ (since there are no $x \in A$!).