Can I pull out an arbitrary element from a set?

Suppose there is an onto function $f: \Bbb R \to \{0, 1\}$. I want to show that there is a function $g: \{0, 1\} \to \Bbb R$, such that $f(g(b)) = b$. I know that there are two element in the domain of $f$ (let's call them $a, b \in dom(f)$) such that $f(a) = 0$, $f(b) = 1$. We just create a function $g = \{(0, a), (1, b)\}$.

But what confuses me, is that we just took these elements $a, b$ arbitrary, like pulled them out of a hat. It would be more easier for me to understand if I took a longer way and was using the axioms directly (taking products, making separations) and finally showed that there is a set of functions and every function is what we need. How can I persuade myself that the former approach is legitimate?

-
You can do this by the principle of finite choice (which doesn't need the axiom of choice). Since $\Bbb R$ is partitioned into two sets $f^{-1}(0)$ and $f^{-1}(1)$. –  Bryan Jul 27 '14 at 19:28
@Bryan: Is it the axiom of choice? I can't use it. And, by the way, the question is not about how I can do this, but about how can I persuade myself that the first approach is legitimate. –  MossCross Jul 27 '14 at 19:29
It is legitimate. The Principle of Finite Choice can be proved without AC. –  Bryan Jul 27 '14 at 19:30
I'm pretty sure the ability to pull out an element arbitrarily is exactly what it means for something to be a non-empty set. –  Gina Jul 27 '14 at 19:31
The fact that $f$ is surjective ("onto") means precisely that $f^{-1}(0)$ and $f^{-1}(1)$ are nonempty, right? Which means there exist elements $a\in f^{-1}(0)$ and $b\in f^{-1}(1)$ as you said. There's nothing wrong with this. Maybe your uncertainty is due to the fact that, after all, there are lots of different functions $g$ that do this. You're just constructing one of them. –  MPW Jul 27 '14 at 19:33

1 Answer

Generally, in the context of first-order logic, you can "pull one arbitrary element" by what is called "existential instantiation" (not to confuse nights where you ponder the absurdity of human life).

So we can choose from a single non-empty set. By induction we can show that we can choose from finitely non-empty sets (this is not repeated instantiations, but rather something a bit more delicate here; but for starters you can think about it that way).

For your question, it is enough, since we only have two sets. So we have two sets which we can prove are non-empty, so we can instantiate two quantifiers and be done with it.

If you want to prove this for a more general setting, where the domain of $g$ is infinite, then you will usually need to appeal to the axiom of choice for that to be done.

-
This is good, clarifying when the axiom of choice might enter into it. +1. –  MPW Jul 27 '14 at 19:37