Spivak's Calculus: Chapter 3 Problem 24b 24b) Suppose that $f$ is a function such that every number $b$ can be written $b = f(a)$ for some real number $a$. Prove that there is a function $g$ such that $f \circ g = I$
I think I do understand this question and how to solve it, but I'm struggling to find a way to express my solution in a mathematically rigorous way, particularly when $f$ is not injective. Here's my idea:
First of all, if $f$ is injective, then it's trivial.
Let $g(x) = a$, where $x = f(a)$ for any $a \in \text{domain}(f)$
Since $f$ is injective, by definition there is only one value of $a$ that satisfies $x = f(a)$ for each $x$, which means $g$ is well defined. And $\text{domain}(g) = \text{image}(f)$ (by definition of $g$), which from the supposition in the question is $\mathbb{R}$. Also, $\text{domain}(f) = \text{image}(g)$, since $f$ and $g$ are injective (but that fact is not important). So $f(g(x))$ is defined for all $x ∈ \mathbb{R}$. Finally, $f(g(x))$ = $f(a)$, where $x = f(a)$ for $x ∈ \mathbb{R} \to f(g(x)) = I(x)$.
But now if $f$ is not injective, it gets more complicated. If I keep my original definition of $g$, being "$g(x) = a$, where $x = f(a)$ for any $a \in \text{domain}(f)$", then that doesn't work because $g$ is no longer a function. Because since $f$ is not injective, there exists atleast 2 numbers $z$ and $w$ such that $z \neq w$ but $f(z) = f(w)$, which means there exists $x$ such that: $g(x) = z = w$.
I think the idea is to simply redefine $g$ to simply "choose" either $z$ or $w$, and assign it to $x$. For example it could choose the smaller of the two. The only difference this would make is now $\text{domain}(f) \subset \text{image}(g)$, instead of $\text{domain}(f) = \text{image}(g)$. But since that fact wasn't important before, the conclusion in the question still holds.
Here's my question. How do I explicitly write down a definition of $g$ that "chooses" the smaller of $z$ or $w$? Furthermore, recall there exists at least 2 numbers z and w. There could be arbitrarily more numbers such that $f(z) = f(w) = f(m) = f(n)$ and so on. And that's just one of the arbitrary branches the common values $f$ could take. There could be a different set of numbers $f(z_2)  = f(w_2) = f(m_2)$ and so on, that are not equal to $f(z)$, etc.
This is starting to get very messy. How can I express $g$ mathematically?
 A: The fallacy you noticed is real, well done for spotting it! What you are asked to show is basically the axiom of choice for the real numbers. It is an axiom because you can’t prove (the general version) from the other axioms of set theory, even though it seems kind of sensible.
So you have two options:

*

*You can gloss over the fact that your definition has this problem and basically say: “Well, just choose any of the options, nothing strange to see here.”

*You can invoke the axiom of choice. It says (straight from the Wikipedia article): For any indexed family $(S_i)_{i\in I}$ of non-empty sets (where $I$ is some indexing set) there is a family $(x_i)_{i\in I}$ such that $x_i \in S_i$ for every $i\in I$. I leave it to you to figure out how to get to Spivak’s claim. (Actually, my favorite formulation of the axiom of choice is basically what you have to prove, but not restricted to numbers.)

A: Suppose there exists an explicit choice function $C :\mathcal P(\mathbb R) \rightarrow \mathbb{R}$.
Let $A \subset \mathbb{R}$. By definition, $C(A) = r$ for some $r \in \mathbb{R}$.
Note that if $A \subset \mathbb{R}$, then clearly: $\{~~A \setminus C(A)~~\}$ $\subset \mathbb{R}$.
Now define a function $A_n : \mathcal P(\mathbb R) \to \mathcal P(\mathbb R)$ recursively as follows:
$A_1(A)$ = $A$
$A_2(A)$ = $A_1(~~A_1 \setminus \{C(A_1)\}~~)$
$A_3(A)$ = $A_2(~~A_2 \setminus \{C(A_2)\}~~)$
etc. etc.
Formally:

*

*$A_1(A)$ = $A$


*If $A = \emptyset$, Then: $A_n(\emptyset) = \emptyset$


*If $A \neq \emptyset$, Then:
$A_n(A)$ = $A_{n-1}(~~A_{n-1} \setminus C(A_{n-1}~~)$ $~~~~\forall n \in \mathbb{N}, n > 1$
Basically what I'm doing is applying the choice function $C$ to $A$ to choose a specific real number $r_1$ in $A$, then defining $A_2$ to be the set {$A$ missing $r_1$}, then applying $C$ to $A_2$ to choose a different real number $r_2$ in $A$, then defining $A_3$ to be the set {$A$ missing ($r_1$ and $r_2$)}, etc. etc.
Ok now define another function $Z:A \rightarrow \mathbb{N}$ using the original choice function $C$ and the new $A_n$ function like so:
$Z(r)= \{n, ~where ~r=C(A_n)$
This function $Z$ is very special. Every element $r \in A$ corresponds to a unique value of $Z(r)$. In otherwords, $Z$ is capable of mapping every element of a subset of real numbers to a unique natural number $n$.
I feel like Cantor will have something to say about this...
A: If $f$ is a non-injective function, $f$ can be written as $f = \{(x_1,f_1), (x_2,f_2)\cdots \} + \{(x_{1+i},f_i),(x_{2+i},f_i)\cdots \} + \{((x_{1+2i},f_{2i}),(x_{2+2i},f_{2i})\cdots \} + \cdots$ where $(x_{a+bi} = x_{c+di}) \implies (a+bi = c+di)$ and $(f_{a+bi} = f_{c+di}) \implies (a+bi = c+di)$.
Define $\hat f = \{(x_1,f_1), (x_2,f_2)\cdots \}$
Define $A_n = \{(x_{1+ni},f_{ni}),(x_{2+ni},f_{ni}) \cdots \}$
$\therefore f= \hat f + \sum_{p=1}^Z A_p$, where $Z \in \mathbb{N}$ or $Z = \infty$
Now using AoC: Construct a new set $\hat A$ which contains exactly one ordered pair $(x_{a+ni},f_{ni})$ from each $A_n$.
Define $f_{\text{injective}} = \hat f + \hat A$
Finally define $g(x) = a$, where $(a,x) \in f_{\text{injective}}$
