A set is infinite iff there is a one-to-one correspondent with one of its proper subsets?

Maxwell Rosenlicht claims in "Introduction to analysis" that a set is infinite if and only if it may be placed into one-to-one correspondence with a proper subset of itself.

He says this is self-evident because a finite set cannot be placed into a one-to-one correspondence with a proper subset of itself (because it has fewer elements), and whilst this is reasonable - I cannot follow Rosenlicht in that "the above therefore follows obviously". Why must a set be infinite just because of some property of finite sets?

Solution 1:

In standard terminology, a "finite" set means one whose cardinality is a natural number, or in other words a set what is in bijective correspondence with $\{i\in\mathbb N\mid i<n\}$ for some $n\in \mathbb N$.

A set that is not in bijective correspondence with any proper subset of itself is called Dedekind-finite.

As you note, it is obvious that a finite set is also Dedekind-finite. But you're right that it is not obvious that every Dedekind-finite set is finite. In fact this is not necessarily true if we're working in a set theory without the Axiom of Choice.

If we do have the Axiom of Choice, however, we can prove easily that every set is either finite or contains a subset (not necessarily proper) that is in bijective correspondence with $\mathbb N$. In the latter case we can prove using the Hilbert's-Hotel construction that the set is not Dedekind-finite.

(Proof sketch. Let $A$ be a set and assume $A$ is not finite. Fix a choice function on the set of nonempty subsets of $A$. Construct by induction a function $f:\mathbb N\to A$ such that $f(n)$ is the chosen element of $A_n = A\setminus f(\{0,1,2,\ldots,n-1\})$. Because $A$ is not finite, $A_n$ is never empty. Then $f$ is a bijection between $\mathbb N$ and a subset of $A$.)

Solution 2:

This is a relatively subjective issue -- we're talking about what it means, exactly, for a set to be infinite.

That said, if you agree that a finite set is, by definition, a set that cannot be put into 1-1 correspondence with itself and a set that's not finite is infinite, you get

$$ \left(A \mbox{ finite} \iff A \mbox{ cannot be put into 1-1 correspondence with a proper subset}\right) \implies \left(\lnot(A \mbox{ finite}) \iff \lnot(A \mbox{ cannot be put into 1-1 correspondence with a proper subset})\right) \implies \left(A \mbox{ infinite} \iff A \mbox{ can be put into 1-1 correspondence with a proper subset}\right) $$

Solution 3:

I agree with you. The author gave a reason why a finite set cannot have a one-to-one correspondence with a proper subset of itself, but he did not give a reason why a set that does not have a one-to-one correspondence with a proper subset of itself must necessarily be finite. Therefore the only thing that he can logically assert is that if a set has a one-to-one correspondence with a proper subset of itself, it must be infinite. He gives no justification for the if-and-only-if relationship.

In other words, the author asserts that

$$(A \implies \lnot B) \implies (\lnot A \iff B)$$

Which is not sound. Having said that, the author's statement is true, despite the fact that his logic does not back it up.

Solution 4:

This is known as the Dedekind definition of a set being infinite. Here is more: http://en.wikipedia.org/wiki/Dedekind-infinite_set

As an exercise, you might try to show that this is equivalent to the definition stating that the set, or some subset of it, can be placed into a 1-1 correspondence with the positive integers.