1

My question is: can this be proven without using the almighty Axiom of Choice?

Here's the idea of my proof using the axiom:

We need an injective function from $B$ in $A$.

Let $e$ be the choice function, $e: P(A) \rightarrow A$.

It's easy to see that $g = e \circ f^{-1}$ is injective.

Guillermo Mosse
  • 1,457
  • Why is $f^{-1}$ injective? – YoTengoUnLCD Jan 18 '16 at 16:35
  • 1
    HINT: Search the site. – Asaf Karagila Jan 18 '16 at 17:47
  • @YoTengoUnLCD, $f^{-1}$ is not necessarily injective, but $e \circ f^{-1}$ is. – Guillermo Mosse Jan 18 '16 at 19:01
  • Why? if $f^{-1}(a)=f^{-1}(b)$ with $a\neq b$, then $e\circ f^{-1}(a)=e\circ f^{-1}(b)$ and we get that $e\circ f^{-1}$ is not injective. – YoTengoUnLCD Jan 18 '16 at 19:23
  • If $e \circ f^{-1}(a)=e \circ f^{-1}(b)$ then, as $e$ is a choice function ($e(X) \in X$), $e \circ f^{-1}(a) \in f^{-1}(a) \cap f^{-1}(b)$. Preimages of elements are mutually disjoint, so we can conclude than $f^{-1}(a) = f^{-1}(b)$, and $a=b$. Something more: if you wanted to prove me false, you should have given me a real counterexample. As you can see, what you said didn't work because the first part was false, as it can never happen. – Guillermo Mosse Jan 19 '16 at 13:13

1 Answers1

4

What you've written requires the axiom of choice, as you say. However, there is a way around it: define a specific $e$!

HINT: You know that $A$ is countable - this means there is a bijection between $A$ and $\mathbb{N}$ (or $A$ is finite, but that case is trivial), so we might as well assume $A=\mathbb{N}$. Now, to each element $b$ of $B$ we associate the set $$X_b=\{a: f(a)=b\};$$ by assumption $X_b$ is nonempty for each $b$.

Do you know a nicely definable way to pick out an element from a nonempty set of natural numbers?

Exercise: generalize this to show that if $A$ is well-orderable, and $f:A\rightarrow B$ is surjective, then $B$ is well-orderable.

Noah Schweber
  • 245,398