Infinite Set Equivalent to Proper Subset

Theorem

A set is infinite if and only if it is equivalent to one of its proper subsets.

Proof

Proof 1

Let $S = \left\{{a_1, a_2, a_3, \ldots}\right\}$ be a countably infinite subset of an infinite set $T$. Such a subset can always be constructed by Infinite Set has Countable Subset.

Partition $S$ into $S_1 = \left\{{a_1, a_3, a_5, \ldots}\right\}, S_2 = \left\{{a_2, a_4, a_6, \ldots}\right\}$.

We can establish a bijection between $S$ and $S_1$, by letting $a_n \leftrightarrow a_{2n-1}$.

We can extend this to a bijection between $S \cup \left({T \setminus S}\right) = T$ and $S_1 \cup \left({T \setminus S}\right) = T \setminus S_2$ by assigning each element in $T \setminus S$ to itself.

So we have demonstrated a bijection between $T$ and one of its proper subsets $T \setminus S_2$, which shows that if $T$ is infinite, it is equivalent to one of its proper subsets.

Now, let $T_0\subsetneq T$ be a proper subset of $T$, and $f:T\to T_0$ be a bijection.

It follows from Subset of Finite Set No Bijection that $T$ must be infinite.

$\blacksquare$

Proof 2

Let $S$ be a set.

Suppose $S$ is finite.

From Subset of Finite Set No Bijection we have that $S$ can not be equivalent to one of its proper subsets.

Suppose $S$ is infinite.

From Infinite Set has Countable Subset, we can construct $v: \N \to S$ such that $v$ is an injection.

We now construct the mapping $h: S \to S$ as follows.

$h \left({x}\right) = \begin{cases} v \left({n}\right) & : x \in \operatorname{Im} \left({v}\right) \\ x & : x \notin \operatorname{Im} \left({v}\right) \end{cases}$

It is clear that $h$ is an injection.

But we have that $v \left({0}\right) \notin \operatorname{Im} \left({h}\right)$ and so $\operatorname{Im} \left({h}\right) \subsetneq S$.

The result follows from Injection to Image is Bijection.

$\blacksquare$

Comment

This results was used by Richard Dedekind as the definition of infinity itself.

Sources

• W.E. Deskins: Abstract Algebra (1964): Exercise $1.3: 14$
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.7$: Example $56$