Let X be an infinite set.
Is it possible to show the existence of a countably infinite subset of X without using the Axiom of Choice?



Is it possible to show that an infinite set has a countable (infinite) subset, without using the Axiom of Choice?
Short answer: No.


By countably infinite subset you mean, I guess, that there is a 1-1 map from the natural numbers into the set. 


If ZF is consistent, then it is consistent to have an amorphous set, i.e., an infinite set whose subsets are all finite or have a finite complement. If you have an embedding of the natural numbers into a set, the image of the even numbers is infinite and has an infinite complement.
So the set cannot be amorphous.


