Infinite Set Equivalent to Proper Subset

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof 1

Let $T$ be an infinite set.

By Infinite Set has Countably Infinite Subset, it is possible to construct a countably infinite subset of $T$.

Let $S = \left\{{a_1, a_2, a_3, \ldots}\right\}$ be such a countably infinite subset of $T$.

Create a Partition of $S$ into:

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

Let a bijection be established between $S$ and $S_1$, by letting $a_n \leftrightarrow a_{2n-1}$.

This is extended 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 a bijection has been demonstrated between $T$ and one of its proper subsets $T \setminus S_2$.

That is, 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 No Bijection between Finite Set and Proper Subset that $T$ must be infinite.

$\blacksquare$


Proof 2

Let $S$ be a set.


Suppose $S$ is finite.

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


Suppose $S$ is infinite.

From Infinite Set has Countably Infinite 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 + 1}\right) & : \exists n \in \N: x = v \left({n}\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$


Proof 3

Let $X$ be a set which has a proper subset $Y$ such that:

$\card X = \card Y$

where $\card X$ denotes the cardinality of $X$.

Then:

$\exists \alpha \in \complement_X \paren Y$

and

$Y \subsetneqq Y \cup \set \alpha \subseteq X$

The inclusion mappings:

$i_Y: Y \to X: \forall y \in Y: i \paren y = y$
$i_{Y \cup \set \alpha}: Y \cup \set \alpha \to X: \forall y \in Y: i \paren y = y$

give:

$\card X = \card Y \le \card Y + \mathbf 1 \le \card X $

from which:

$\card X = \card Y + \mathbf 1 = \card X + \mathbf 1$

So by definition $X$ is infinite.

$\Box$


Now suppose $X$ is infinite.

That is:

$\card X = \card X + \mathbf 1$

Let $\alpha$ be any object such that $\alpha \notin X$.

Then there is a bijection $f: X \cup \set \alpha \to X$.

Let $f_{\restriction X}$ be the restriction of $f$ to $X$.

Then from Injection to Image is Bijection:

$\image {f_{\restriction X} } = X \setminus \set {f \paren \alpha}$

which is a proper subset of $X$ which is equivalent to $X$.

$\blacksquare$


Also see


Sources