1

I'm dealing with Exercise 2 of Bishop's Constructive Analysis, Chapter 2 :

  1. 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 ?!)

Andrés E. Caicedo
  • 79,201
Fardad Pouran
  • 2,178
  • 1
    You're overthinking this. If there's a choice to be made for some $b$, then you can't satisfy all the preimages. Your construction (you get to choose the map!) should be very simple and not involve the axiom of choice. (Also, I think you get to choose $A$ and $B$ since this would be true if $A$ were the empty set or a one-point set.) – aes Nov 23 '14 at 09:49
  • Indeed, the map $g$ must decide about some global property of $A$ which is undecidable ! – Fardad Pouran Nov 23 '14 at 11:51

1 Answers1

1

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 !

Fardad Pouran
  • 2,178