$\aleph_1\leq A$ for an uncountable set $A$ So we have to prove (axiom of choice is given) that $\aleph_1$ which is the next aleph after $\aleph_0=\omega$ satisfies $$\aleph_1\leq A$$ given that $A$ is uncountable.
Here was my reasoning. The axiom of choice is equivalent to saying that any two cardinalities are comparable. Thus, assume that $A<\aleph_1$, by definition of the alephs, we must have that $|A|=\omega$ which means that $A$ is equinumerous with the naturals, the definition of countable. Hence, by contrapositive we are done.
Is this argument right? The professor said on the midterm we need to use transfinite recursion, but I dont see how. 

The fact any two cardinalities are comparable is probably one of the consequences of Choice that you're supposed not to use.
It looks more like the expected solution is to use transfinite induction up to $\omega_1$ to explicitly construct an injection $\omega_1\to A$.
With details depending on the exact formulation of AC and transfinite recursion you're using, it would look something like:


*

*Fix a choice function $\chi: \mathscr P(A)\setminus\{\varnothing\}\to A$.

*Define by transfinite recursion a function $f:\omega_1\to A$:
$$ f(\alpha) = \chi(A\setminus\{f(\beta)\mid \beta\in\alpha\})$$

*Every $\alpha<\omega_1$ is at most countable, so $\{f(\beta)\mid\beta\in\alpha\}$ is at most countable, so $A\setminus\{f(\beta)\mid \beta\in\alpha\}$ must be nonempty, and the definition makes sense.

*$f$ is an injection, because if $\beta<\alpha<\omega_1$ then $f(\alpha)$ has explicitly been constructed to differ from $f(\beta)$.

