5
$\begingroup$

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.

  • 0
    @asmeurer I'll add my commen$t$ as an answer then.2010-12-27

3 Answers 3

0

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.

  • 0
    I agree that there'$s$ no choice here, Andres! The point of my Answer was that no choice is required, *even if we use the Dedekind definition of infinite set*. Now go back to sleep.2010-12-27
8

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.

  • 0
    @Jonas & Carl: Yes, I just realized that. Maybe that is why I had such a hard time proving it.2010-12-22
3

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.

  • 0
    So just to be clear on things, choice is not required to prove that it has an infinite subset, but it is required to prove that it has an infinite subset of the same cardinality.2019-01-21