# Infinite Set Equivalent to Proper Subset/Proof 3

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

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$

## Sources

- 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 8$: Theorem $8.10$