5
$\begingroup$

Let $A$ and $B$ be sets. If there exists a surjection $f : A \to B$ then there exists an injection $g : B \to A$.

Proof: given $b \in B$ select an element $a \in f^{-1}(b)$. Denote this element by $g(b)$. Then $g(b) \in f^{-1}(b)$ so that $f(g(b)) = b$. Consequently $g(b_1) = g(b_2)$ implies $f(g(b_1)) = f(g(b_2))$ so that $b_1 = b_2$. We conclude $g$ is an injection. QED

Is the axiom of choice required to make this argument rigorous?

$\endgroup$

marked as duplicate by Andrés E. Caicedo, Zach L., Sujaan Kunalan, user87543, TZakrevskiy Dec 13 '13 at 9:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ See also here. $\endgroup$ – Andrés E. Caicedo Dec 13 '13 at 2:11
  • 2
    $\begingroup$ Without choice, we can have surjections without injections. We can in fact have an equivalence relation on $\mathbb R$ such that there are more equivalence classes than reals. $\endgroup$ – Andrés E. Caicedo Dec 13 '13 at 2:12
  • $\begingroup$ @AndresCaicedo that last statement is surprising. Do you have a link or a citation? $\endgroup$ – Umberto P. Dec 13 '13 at 2:15
  • 3
    $\begingroup$ Yes. See for example here. $\endgroup$ – Andrés E. Caicedo Dec 13 '13 at 2:20
  • $\begingroup$ Just to be explicit: As shown in the links, it is an open problem whether your statement is equivalent to the (full) axiom of choice. It certainly needs at least some amount of choice to be proved. $\endgroup$ – Andrés E. Caicedo Dec 13 '13 at 17:13
4
$\begingroup$

I don't have a proof that the existence of any injection depends on the axiom of choice, but the existence of a right inverse is equivalent to AC, as follows. Let $X$ be a set not containing $\emptyset$ and consider the set $Y = \{(z, A)\ |\ z\in A \in X\}$. Define $f:Y\rightarrow X$ by $f((z,A)) = A$. If $g$ is a right inverse of $f$, then $g^*(A)$ given by the the first element of the ordered pair $g(A)$ is a choice function.

$\endgroup$
0
$\begingroup$

It is. In fact, I believe it can be show that the universal truth of this theorem is equivalent to the axiom of choice.

$\endgroup$
  • $\begingroup$ In fact, this is equivalent to the axiom of choice. $\endgroup$ – ncmathsadist Dec 13 '13 at 1:45
  • 1
    $\begingroup$ This is a nontrivial affair. See this: math.uwo.ca/~srankin/courses/4123/2011/zorns_lemma.pdf $\endgroup$ – ncmathsadist Dec 13 '13 at 1:50
  • 1
    $\begingroup$ @ncmathsadist I'm well aware that Zorn's Lemma is equivalent to the axiom of choice, but I don't see how that's relevant to this discussion. Your link to planetmath just reiterates the fact that "every surjection splits" is equivalent to the axiom of choice, which I commented on above, and which is the content of the accepted answer. In Asaf's answer here math.stackexchange.com/a/192486/7062, he says that it's still open whether "surjection $X\rightarrow Y$ implies injection $Y\rightarrow X$" implies the axiom of choice, which is what you claim. $\endgroup$ – Alex Kruckman Dec 13 '13 at 2:44
  • 1
    $\begingroup$ I don't understand, are you saying that you have a proof that the partition principle implies the axiom if choice?? All the linked proofs do not contain such proof. $\endgroup$ – Asaf Karagila Dec 13 '13 at 10:14
  • 1
    $\begingroup$ By the way, the problem whether or not the partition principle implies the axiom of choice is the oldest open problem of set theory. I am not aware of any progress made towards it in the last twenty years. So if you have a proof, I would love to see that. $\endgroup$ – Asaf Karagila Dec 13 '13 at 10:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.