We denote by $A$, $A′$, $B$, $B′$ the four sets.

We are given mapping $u:A′→A$, $v:B→B′$.

We denote by $F(A, B)$ the set maps $A→B$ ,$F(A′, B′)$ the set maps $A′→B′$.

Let $Φ : F(A, B) → F(A′, B′)$ be a mappig which makes $v◦f ◦ u ∈ F(A′, B′)$ correspond with for $f ∈ F(A, B)$.

Prove that we can't prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective." without Axiom of choice.

  • $\begingroup$ I'm confused. Are we to show the validity of your implication implies the axiom of choice? $\endgroup$ – Alvin Lepik Jul 15 '18 at 8:49
  • $\begingroup$ I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice. $\endgroup$ – Pacifica Jul 15 '18 at 8:57
  • $\begingroup$ So you want to show the undecidability of this implication in ZF, right? $\endgroup$ – joriki Jul 15 '18 at 9:28
  • $\begingroup$ @AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $f\mapsto v\circ f\circ u$ is not surjective $\endgroup$ – Max Jul 15 '18 at 9:28
  • $\begingroup$ Either that or a proof of AC from the implication $\endgroup$ – Max Jul 15 '18 at 9:29

Actually, the $u$ part is misleading, because $f\mapsto f\circ u$ is surjective if $u$ is injective, without the axiom of choice. The interesting part is about $v$ !

So we may as well take $u= id_{A'}$. And now the implication we have is "$v$ surjective implies $f\mapsto v\circ f$ surjective" and we want to see that this implies the axiom of choice.

Consider : $f\mapsto v\circ f$, $F(B', B)\to F(B',B')$.

If you take $id_{B'}\in F(B',B')$, the surjectivity of this map implies that $v$ has a section, i.e. there is a function $B'\to B$ that picks out an antecedent for each element of $B'$.

It's known that "every surjective function has a section" implies the axiom of choice, so there you go

  • $\begingroup$ Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice. $\endgroup$ – Pacifica Jul 15 '18 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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