# 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.

-
I believe this is called a Dedekind infinite set. The Wikipedia article should prove useful. In particular, take a look at the equivalent conditions in ZF, it also says that the Axiom of Choice is not required. – Adrián Barquero Dec 22 '10 at 21:39
How do you define "infinite set"? – Asaf Karagila Dec 22 '10 at 21:40
@Asaf: A set $A$ is finite if it is empty of if there is a bijection to the set $\{1, 2, \ldots n\}$ for some $n$. A set is infinite if it is not finite. – asmeurer Dec 22 '10 at 21:45
This reminds me of the following theorem: Every infinite subset of a countable set $A$ is countable. – PEV Dec 22 '10 at 21:49
@Adrián: According to the first section (en.wikipedia.org/wiki/…), this does require the Axiom of Choice to prove. (sorry, how do you add links to comments?) – asmeurer Dec 22 '10 at 21:50

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.

-
án : I am not sure what you mean by "this type of set". A set is infinite iff it has a proper infinite subset (For $a\in A$, $A\setminus\{a\}$ is infinite iff $A$ is). A set is Dedekind infinite iff there is a proper subset of $A$ in bijection with $A$. As you say, this is the same as saying that ${\mathbb N}$ injects into $A$, and this equivalence does not use choice. (And, under a small amount of choice, infinite is the same as Dedekind infinite.) – Andrés Caicedo Dec 27 '10 at 17:40
@Andres You're right. Writing "this type of set" does sound kind of funny and weird. I'll change a little bit the way I wrote it. Thanks. – Adrián Barquero Dec 27 '10 at 17:57
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. – asmeurer Dec 27 '10 at 20:37

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.

-
Any infinite set has a proper infinite subset: just remove a point. – Andrés Caicedo Dec 27 '10 at 19:03
Well yes, that's what this thread is all about, isn't it? The point is, how do you show that the resulting set is infinite. It seems to depend (modulo the Axiom of Choice) on which definition of infinite set you choose. – TonyK Dec 27 '10 at 19:18
Oh, no! If you remove a set and the resulting set has size $n$, the original set has size $n+1$. Done. So, removing a point from an infinite set should give you an infinite set. Similarly, if removing a point gives you an infinite set, then the original set is infinite. Else, it has size $n$ for some natural number $n$. Note $n>0$, and the set without a point has size $n-1$, also finite. There is no choice here. – Andrés Caicedo Dec 27 '10 at 19:43
The issue with Dedekind finite, etc, is that you cannot prove that there is a proper subset of the same size as the original set unless the original set is Dedekind infinite. But this is different than what is being asked. – Andrés Caicedo Dec 27 '10 at 19:44
(The definition of infinite that the OP is using is the standard one: Finite means of size as a natural number. Infinite is otherwise.) – Andrés Caicedo Dec 27 '10 at 19:45

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.

-
Jonas you will need a form of choice for the latter, you can construct models of ZF in which an infinite set has no countably infinite subset. – Asaf Karagila Dec 22 '10 at 21:42
Yes, I know that you can remove one point. But how do you then construct the bijection between the two sets to prove that they have the same cardinality? – asmeurer Dec 22 '10 at 21:43
@asmeurer: You never said they have the same cardinality. – Jonas Meyer Dec 22 '10 at 21:45
@Asaf: Thank you for your comment. – Jonas Meyer Dec 22 '10 at 21:45
asmeurer: in your question you only asked to construct a proper, infinite subset. If you remove one point from an infinite set, it will still be infinite (prove by contraposition: the union of one point to a finite set is still finite). If you want a proper subset of the same cardinality, then you need the axiom of choice to ensure this can always be done. – Carl Mummert Dec 22 '10 at 21:47