◀ ▲ ▶Branches / Set-theory / Proof

Proof

(related to Theorem: Distinction Between Finite and Infinite Sets Using Subsets)

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

Finite case "$\Rightarrow$"

• 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 functionn $f:X\to S.$

Infinite case "$\Rightarrow$"

• 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.

Infinite case "$\Leftarrow$"

• 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.

Finite case "$\Leftarrow$"

• 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.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Flachsmeyer, Jürgen: "Kombinatorik", VEB Deutscher Verlag der Wissenschaften, 1972, 3rd Edition