Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 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. –  Graduate Jul 27 at 19:29
    
It is legitimate. The Principle of Finite Choice can be proved without AC. –  Bryan Jul 27 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 at 19:31
1  
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 at 19:33

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
This is good, clarifying when the axiom of choice might enter into it. +1. –  MPW Jul 27 at 19:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.