Subset of Finite Set is Finite

Theorem

Let $X$ be a finite set.

If $Y$ is a subset of $X$, then $Y$ is also finite.

Proof

From the definition, $X$ is finite iff $\exists n \in \N$ such that there exists a bijection:

$f: X \leftrightarrow \N_n$

where $\N_n$ is the set of all elements of $\N$ less than $n$, that is:

$\N_n = \left\{{0, 1, 2, \ldots, n-1}\right\}$

The case in which $X$ is empty is trivial.

We begin proving the following particular case:

If $X$ is finite and $a \in X$, then $X \setminus \left\{{a}\right\}$ is also finite.

From Bijection between Specific Elements there exists a bijection $f: \N_n \to X$, which satisfies $f \left({n}\right) = a$.

Next we prove the general case by induction.

Basis for the Induction

If $n = 1$ then $X \setminus \left\{{a}\right\} = \varnothing$ is finite.

If $n > 1$, the restriction of $f$ to $\left\{ k\in\N:k\leq n-1\right\}$ yields a bijection into $X \setminus \left\{ a\right\}$, hence $X\setminus\left\{ a\right\}$ is finite and has $n-1$ elements.

So, we have that if $n=1$, then its subsets ($\varnothing$ and $X$) are finite.

This is the basis for the induction.

Induction Hypothesis

Now we need to show that, if our Theorem is valid for sets with $n$ elements, it is also true for sets with $n+1$ elements.

This is our induction hypothesis.

Induction Step

This is our induction step:

Let $X$ have $n+1$ elements, and let $Y \subseteq X$.

If $Y = X$, there is nothing to prove.

Otherwise, $\exists a \in X \setminus Y$.

This means that $Y$ is acually a subset of $X \setminus \left\{{a}\right\}$.

Since $X \setminus \left\{{a}\right\}$ has $n$ elements, it follows that $Y$ is finite.

$\blacksquare$

Note

It is possible to define $\N_n = \left\{{1, 2, 3, \ldots, n}\right\}$, in which case the proof is the same.

Sources

• Elon Lages Lima: Análise Real 1 (1989): $\text{Chapter 1}, \S 2$