0
$\begingroup$

I have always found issues providing formal proofs for theorems. This time I'm stuck with this proof. I know my question might seem quite naive to most of you but please help me out with constructing a formal proof for the above theorem.

  • 7
    What is your definition of *infinite set*? The argument will depend on exactly what definition you’re using.2012-08-30

1 Answers 1

4

A set is finite if it is in bijection with $\bar{n} = \{0, 1, 2, ..., n - 1\}$ for some $n \in \mathbb{N}$.

A set is infinite if it is not finite.


Your statement is equivalent to its contrapositive statement : If $S$ is finite, then all its subsets are finite.

Suppose $S$ is finite. Then there exists a bijection $f : \bar{n} \rightarrow S$ for some $n \in \mathbb{N}$. Let $R$ be an subset of $S$. Define the function $g$ and $a_i$ by recursion

$g(0) = f(a_0)$ where $a_0$ is least such that $f(k) \in R$.

$g(i + 1) = f(a_{i + 1})$ where $a_{i + 1}$ is least natural number (if it exists) greater than $a_{i}$ such that $f(a_{i + 1}) \in R$

Hence $g : \bar{n'} \rightarrow R$ is a bijection for some $n' < n$. Thus $R$ is also finite.