Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.