# Proof that if a set $S$ has a proper subset which is infinite, then $S$ must be infinite.

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.

-
What is your definition of infinite set? The argument will depend on exactly what definition you’re using. –  Brian M. Scott Aug 30 '12 at 5:16

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.

-