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.

  • 4
    I believe this is called a [Dedekind infinite set](http://en.wikipedia.org/wiki/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.2010-12-22
  • 0
    How do you define "infinite set"?2010-12-22
  • 0
    @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.2010-12-22
  • 0
    This reminds me of the following theorem: Every infinite subset of a countable set $A$ is countable.2010-12-22
  • 0
    @Adrián: According to the first section (http://en.wikipedia.org/wiki/Dedekind-infinite_set#Comparison_with_the_usual_definition_of_infinite_set), this *does* require the Axiom of Choice to prove. (sorry, how do you add links to comments?)2010-12-22
  • 0
    To do it *with* the axiom of choice, just well-order the entire set in the order type of some limit ordinal, and then delete the first element under the well ordering. You can then use the well ordering to construct a bijection from the original set to the proper subset by just sending each element in the original set to the next element in the well ordering. The cardinal number of the set is itself a limit ordinal, so you can use that for the limit ordinal in the well ordering.2010-12-22
  • 0
    @asmeurer You're right, it does say so. The part of the article that said that AC is not needed is [this](http://en.wikipedia.org/wiki/Dedekind-infinite_set#Dedekind-infinite_sets_in_ZF).2010-12-22
  • 0
    @asmeurer I learned how to put links in this [page](http://mathoverflow.net/editing-help). Look at the basic links section.2010-12-22
  • 0
    @ Adrián: Thanks. Of course, now it is too late to edit my comment...2010-12-22
  • 0
    @asmeurer Also [this](http://meta.stackexchange.com/questions/43019/how-do-comment-replies-work/43020#43020) should be useful to you, your last comment didn't reach me because of the space you left.2010-12-22
  • 0
    @Adrián: Oops. I never realized that those actually do pingbacks.2010-12-22
  • 0
    @Adrián: You pretty much gave the answer I was looking for, but you put it in a comment, so I can't mark it as "the answer."2010-12-27
  • 0
    @Carl: You kind of gave "the answer" in a comment too.2010-12-27
  • 0
    @asmeurer I'll add my comment 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
    *Any* infinite set has a proper infinite subset: just remove a point.2010-12-27
  • 0
    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.2010-12-27
  • 0
    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.2010-12-27
  • 0
    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.2010-12-27
  • 0
    (The definition of infinite that the OP is using is the standard one: Finite means of size as a natural number. Infinite is otherwise.)2010-12-27
  • 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 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.2010-12-22
  • 1
    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?2010-12-22
  • 0
    @asmeurer: You never said they have the same cardinality.2010-12-22
  • 0
    @Asaf: Thank you for your comment.2010-12-22
  • 2
    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.2010-12-22
  • 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
    á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.)2010-12-27
  • 0
    @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.2010-12-27
  • 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.2010-12-27