Lawvere - Conceptual Mathematics - Criterion for decomposition of a map into two pieces

Question

This is a problem from Lawvere's Conceptual Mathematics in a section talking about when we can find solutions to 'choice'/lifting diagrams.

I have maps: $h\colon A \to C$, $g\colon B \to C$ with the property:

For all $a \in A$, there is a $b \in B$ such that $h(a) = g(b)$.

I want to show there exists a function $f$ such that $h = g \circ f$.

I would define $f(a) = b$ where $b$ is an element guaranteed by our mapping property. Potentially, there are multiple such elements $b$, in which case we would fix a $b_0 \in \{b | h(a) = g(b)\}$.

To show that $f$ is well defined we must show:

1. $f$ is defined for all elements on the domain.
2. $f$ only maps to elements in the codomain.
3. If $a$ and $a'$ are elements in $A$ such that $a = a'$ then $f(a) = f(a')$.

1) and 2) are true by definition of $f$ since every element $a$ is mapped to an $h(a)$ and we are only assigning $f(a)$ to values in $B$.

For 3), I think the argument goes like this:

Let $a, a' \in A$ be such that $a = a'$. Since h is a well defined function, $h(a) = h(a')$, and by our assumed property there exists at least one $b \in B$ such that $g(b) = h(a)$. If there is only one such $b$ then $g(b) = h(a) = h(a') \implies f(a) = f(a') = b$. If there is more than one such $b$, we have fixed $b_0$ in our definition of $f$ so $f(a) = f(a') = b_0$ where $b_0 \in \{b | h(a) = g(b)\}$.

Does my argument for 3) look OK? I always get a little confused trying to prove these well-definedness of functions...

Thank you

Answer 1

Quick remark before addressing your proof. The "one-valuedness" property of functions is not $a=a^\prime\implies fa=fa^\prime$. This implication always holds since the equality $a=a^\prime$ means $a,a^\prime$ are completely interchangeable. "One-valuedness" means that $fa$ is a single element of the target/codomain.

I think your proof is fine, but there is an important subtlety. You are choosing for every $a\in A$ an element $b\in B$ satisfying $g(b)=h(a)$. Note that when $A$ is infinite, it is not "physically evident" that one can make an infinity of choices. The assertion this is possible is known as the axiom of choice. It plays an important role in many branches of math.

---

The following uses the notion of "fiber" (inverse image of a point). Forgive me if it is not familiar to you.

The following conditions are reformulations of each other.

• there exists $b\in B$ such that $gb=ha$.
• the fiber of $g$ over $ha\in C$ is non-empty $g^{-1}(ha)\neq \emptyset$.

Your proof suggests to choose an element from each fiber $g^{-1}(ha)$ for $a\in A$. A pleasant related formulation of the axiom of choice is the following: "every surjection (epimorphism of sets) has a section."