Let $f:ℝ→ℕ$ be onto. Does there exist a $g:ℕ→ℝ$ such that $f(g(b))=b$ for all $b∈ℕ$?

Question

I'm reading Classic Set Theory for Guided Independent Study, and they introduced ZF set theory (no axiom of choice still) and the construction of integers, real, rational and natural numbers. The books says that it's impossible to describe, finitely, a way of obtaining $g(b)$ for each $b∈ℕ$, but i can't see why. If i let $f(x)=x$ and $g(b)=b$ we would have $f(g(b))=g(b)=b$ why wouldn't this work?
Thank you!

badjohn · Accepted Answer

A complement to Asaf's answer.  Your problem here might be more about English than mathematics.  (I mean English as used in mathematics which takes some learning even for native English speakers.)
An analogy might help.  Suppose I claim that given a positive real number, I can calculate its square root.  I "prove" this ability by saying that the square root of $4$ is $2$.  Have I proved the ability that I claimed?
You have done the same.  You have found a $g$ for a specific $f$ but not proved your ability to do it for any $f$.

Asaf Karagila · Answer

No.
This is equivalent to the statement "Given any countable family of pairwise disjoint sets of real numbers, there is a choice function". Such thing, for example, would imply that every subset of the real numbers is finite or has a countably infinite subset.
This was shown to be unprovable from $sf ZF$ by Cohen, and is now one of the most important models of $sf ZF+lnot AC$, also known as "Cohen's first model".
There are other constructions that would make it even more explicit where and how a counterexample could consistently exist. But to truly appreciate that, you'd need to first understand set theory in general, forcing, and symmetric extensions.

Let $f:ℝ→ℕ$ be onto. Does there exist a $g:ℕ→ℝ$ such that $f(g(b))=b$ for all $b∈ℕ$?

2 Answers

Add your own answers!

Ask a Question