# Without axiom of choice

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.

• I'm confused. Are we to show the validity of your implication implies the axiom of choice? – Alvin Lepik Jul 15 '18 at 8:49
• 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. – Pacifica Jul 15 '18 at 8:57
• So you want to show the undecidability of this implication in ZF, right? – joriki Jul 15 '18 at 9:28
• @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 – Max Jul 15 '18 at 9:28
• Either that or a proof of AC from the implication – 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'$.
• 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. – Pacifica Jul 15 '18 at 13:57