I read somewhere that a set is infinite if and only if it has a proper infinite subset. I also remember seeing someones name attached to this theorem on Wikipedia once, but I can't even find that now. I haven't been able to find a proof of this theorem, nor been able to generate one myself.
I can prove that if a set has a proper infinite subset then it is itself infinite by proving the contrapositive that if a set is finite then it does not have any proper infinite subsets (this is a simple contradiction proof).
But I can't figure out how to, given an arbitrary infinite set, construct a proper infinite subset. Does this require the Axiom of Choice? I can't really figure out how to do it with that either. A proof or reference to a proof would be much appreciated.