Proof that If $f:X\to Y$ is surjective and $X$ is finite, then $Y$ is finite without AC I try to prove the following exercise without using the axiom of choice. On the second item, the proof that I found in the books, to define the function $g:Y\to X$, for every $y\in Y$, due to the surjective of $f$ they choose $x=g(y)\in X$ such that $f(x)=y$.
Let $f:X\to Y$, prove.


*

*If $Y$ is finite and $f$ injective, then $X$ is finite.

*If $X$ is finite and $f$ surjective, then $Y$ is finite.


Proof:


*

*Done.

*Let $X=\{x_1,\ldots,x_n\}$. Given any $y\in Y$, because $f$ is surjective, then exists $k\in I_n=\{1,\ldots,n\}$ such that $y=f(x_k)$. Consider the set
$$A_y:=\{i\in I_n:f(x_i)=y\}$$
Then $A_y\neq\emptyset$ because $k\in A$, so, by the Well-ordering principle, $A_y$ has a minimal element, let this element $i_y$, then $$f(x_{i_y})=y.$$ 
Define $g:Y\to X$ by $g(y):=x_{i_y}$. Im particular we get
$$f(g(y))=f(x_{i_y})=y,\quad \forall y\in Y.$$ 
Prove that $g$ is injective. Let $y,z\in Y$ such that $g(y)=g(z)$, then 
    $$g(y)=g(z)\Longrightarrow f(g(y))=f(g(z)) \Longrightarrow  y=z.$$
Therefore, $g$ is injective, then by the first item, $Y$ is finite.
Is it right?
 A: Yes, your proof is fine. Although it is in fact a bit complicated.
If you have proved that if $X$ is finite, then $\mathcal P(X)$ is finite, then you can just appeal to this, as $y\mapsto f^{-1}(y)$ is an injection from $Y$ into $\mathcal P(X)$.
A: Your proof is correct. The reason you do not need choice is because you have a well-order on $X$ (which exists without choice because $X$ is finite). So you can do essentially the same argument as at the top of your post, "...choose $x$ such that $f(x) = y$...", only now "choose" does not invoke choice because of the well-order on $X$.
In fact, your proof generalises to the following statement. If $X$ has a well-order and $f: X \to Y$ is surjective, then there is a section $g: Y \to X$ (i.e. injective $g$, s.t. $fg$ is the identity).
A: You do it very complicated. Suppose $|Y|=|X|+1$. Since it's surjective, if $y\in Y$, there is $x\in X$ s.t. $y=f(x)$. But then, $|X|$ element will have $|X|+1$ images, which is impossible (an element can not have several images). Therefore $|Y|\leq |X|$.
