I'm dealing with Exercise 2 of Bishop's Constructive Analysis, Chapter 2 :
- Construct a mapping $f$ from a set $A$ to a set $B$ such that $f$ is onto $B$, but there does not exist a mapping $g: B \rightarrow A$ with $f (g(b)) = b$ for all $b$ in $B$.
I don't know how to define $A$ in order to reach weak contradiction of choosing one member of the set $f^{-1}(b)$ for each $b$.
Such a set must be an undecidable set, like $\{x|(x=0\wedge p)\vee(x=1\wedge \neg p)\}$, where $p$ is NOT known to be true or not, like Goldbach conjecture. And existence of such a $g:B\rightarrow A$ must prove $p$ is true or not !
Another set $A$ can be, for example, $\mathbb{R}$ which doesn't have trichotomy or equality decidability.
Any help is appreciated.
#EDIT :
I think this map doesn't work, but it's not a bad try ($GC$ is Goldbach conjecture):
Let $A=\{x|(x=0\wedge GC)\vee(x=1\wedge \neg GC)\}$ and $B=\{2\}$. $A$ is nonempty but it's not nonvoid in the sense of Bishop's Book.
Define the function : $\left\{\begin{array}{ll} f:A\rightarrow B\\ f(x)\equiv2\end{array}\right.$.
Now, if there exists such a $g:B\rightarrow A$, then $g(2)$ is available !!! (not useful ?!)
I think i've find the counterexample :
Let $A=\{0,1\}$ and $B=\{a,b\}$, where $(a=b \longleftrightarrow GC)$. [I saw this idea in the proof of ($AC\rightarrow LEM$)]
Now define $\left\{ \begin{array}{} f:A\rightarrow B\\ f(0)=a \:,\:f(1)=b \end{array}\right.$
Clearly, $f$ is a surjection. If such a $g$ exists, then you can decide on equality of $g(a)$ and $g(b)$ as equality of members of $A$ is decidable !
Hence, $\left\{ \begin{array}{} g(a)=g(b) \rightarrow a=b\\ g(a)\neq g(b)\rightarrow a\neq b \end{array}\right.$. Therefore, you can decide on equality of $a$ and $b$ and so on Goldbach's conjecture
#Contradiction !