In Lang "Real and Functional analysis" is demonstrated that given a countable set $A$ and a function $f: A \rightarrow B$ which is surjective on $B$, then $B$ is finite or countable.
Proof: Consider $y \in B$ then there exists a non void set $F_y= \{x \in A | f(x)=y \}$, consider one element of the set , say $x_y \in F_y$. Now the assosiation $y \rightarrow x_y$ is injective from $B \rightarrow A$ (the proof of injectivity is easy) then, for the definiton of countability we have that also $B$ is countable.
My questions are:
-
It seems to me that this proof uses the axiom of choice to choose the elements in the family $F_y$, is this correct?
-
If yes, there are proof of the same "theorem" without the AOC?
-
I've heard of a theorem which says that if there exist a pair of injection $i_1,i_2, \ \ i_1:A \rightarrow B \ \ i_2:B \rightarrow A$ then there is a bijection $ f:A \rightarrow B$. And that this theorem can be demonstrated without AOC, is this true? There is a similar theorem for surjective functions?
Best Answer
(1,2) As written, the proof certainly seems to appeal to the axiom of choice for choosing each of the $x_y$s. But this is not necessary and easily eliminated: since you know that $A$ is countable, you can choose a bijection $A\leftrightarrow \mathbb N$ once and for all, and then for every $y$ let $x_y$ be the element in $F_y$ that has the smallest index.
(3) Yes, this is the Cantor-Schröder-Bernstein theorem, and it does not depend on the axiom of choice. The corresponding theorem for surjections does require AC.