Proof that a set is infinite if and only if it has an infinite proper subset 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.  
 A: It doesn't require the axiom of choice.  Remove one point.
If you want a countably infinite subset of every infinite set, I think you need to use (or at least the usual proof uses) the axiom of countable choice.
However, maybe you are thinking of the condition of being Dedekind infinite, as mentioned in Adrián Barquero's comment.  There you want not just an infinite proper subset, but a proper subset that is in bijection with the whole set.  This can be proved using the existence of a countably infinite subset, so again uses countable choice.
A: Note: I'm adding my original comment as an answer at the OP's suggestion.
I believe that this notion of infinite set is called a Dedekind infinite set. The Wikipedia article states some equivalent conditions under the section Dedekind infinite sets in ZF where it says explicitly that the Axiom of Choice is not required to prove their equivalence. In particular, one of the equivalent conditions for $A$ to be Dedekind infinite is that $A$ has a countably infinite subset.
A: Surely a Dedekind infinite set trivially has an infinite proper subset: its image under the bijective function that is required for it to be Dedekind infinite.
A: Suppose $S$ is infinite. Let $S_{1} \in S$.
Consider the set $S\backslash\{S_1\}$. Clearly it is a proper subset of S.
Suppose, we can find a bijective map $f:\{1,2,...,n\}\rightarrow S\backslash\{S_1\}$.
Now, suppose $\tilde f:\{1,2,...,n,n+1\}\rightarrow S$
such that $\tilde f(k) = f(k), \hspace{1cm} k=1,2,...,n$
and, $\tilde f(n+1) = S_1$
$\implies \tilde f$ is bijective - which is impossible as $S$ is infinite.
Hence, $S\backslash\{S_1\}$ is infinite.
