- By hypothesis, $X$ is a non-empty set with a proper subset $S\subset X.$

- Let $X$ be finite.
- By subsets of finite sets, $S$ is finite with $|S| \le |X|.$
- Since $S$ is a proper subset, we have even $|S| \neq |X|.$
- Therefore, $|S| < |X|.$
- By characterization of finite sets (no. $3$), there is no injective function $f:X\to S.$

- Assume, $X$ is infinite.
- Choose $x_1\in X,$ $x_2\in X\setminus\{x_1\},$ $x_3\in X\setminus\{x_1,x_2\},$ etc.
- Since $X$ is infinite, we can continue this process for all indices $i\in\mathbb N$ be mapping $f:\mathbb N\to X,$ $f(i):=x_i.$
- By construction, this is an injective function $f:\mathbb N\to X.$
- Now, define the function $g:X\to S$ ($S$ being a proper subset of $X$) as follows:

$$g(x):=\begin{cases}x&\text{if }x\in X\setminus \{x_i\mid i\in\mathbb N\}\\x_{i+1}&\text{if }x=x_i\end{cases}$$ - By construction, the function $g$ is injective as well.

- By contraposition to finite case $”\Rightarrow”,$ if there
*is*an injective function $f:X\to S,$ then $X$ is not finite, therefore $X$ is infinite.

- By contraposition to the infinite case $”\Rightarrow”,$ if there
*is no*injective function $g:X\to S,$ then $X$ is not infinite, therefore $X$ is finite.

q.e.d

| | | | created: 2019-09-07 16:19:09 | modified: 2019-09-07 16:26:19 | by: *bookofproofs* | references: [8297]

(none)

[8297] **Flachsmeyer, Jürgen**: “Kombinatorik”, VEB Deutscher Verlag der Wissenschaften, 1972, Dritte Auflage