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.
Proof that if a set $S$ has a proper subset which is infinite, then $S$ must be infinite.
0
$\begingroup$
elementary-set-theory
-
7What is your definition of *infinite set*? The argument will depend on exactly what definition you’re using. – 2012-08-30
1 Answers
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.