# Subset of Finite Set is Finite

## Contents

## 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 if and only if $\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 = \set {0, 1, 2, \ldots, n - 1}$

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

We begin proving the following particular case:

From Bijection between Specific Elements there exists a bijection $f: \N_n \to X$, which satisfies $\map f n = a$.

Next we prove the general case by induction.

### Basis for the Induction

If $n = 1$ then $X \setminus \set a = \O$ is finite.

If $n > 1$, the restriction of $f$ to $\set {k \in \N: k \le n - 1}$ yields a bijection into $X \setminus \set a$.

Hence $X \setminus \set a$ is finite and has $n - 1$ elements.

So, we have that if $n = 1$, then its subsets ($\O$ 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 actually a subset of $X \setminus \set a$.

Since $X \setminus \set a$ has $n$ elements, it follows that $Y$ is finite.

$\blacksquare$

## Also see

## Sources

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 10.24$ - 1989: Elon Lages Lima:
*AnĂ¡lise Real 1*: $\S 1.2$ - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 6$: Finite Sets: Corollary $6.6$ - 2010: Raymond M. Smullyan and Melvin Fitting:
*Set Theory and the Continuum Problem*(revised ed.) ... (previous) ... (next): Chapter $3$: The Natural Numbers: $\S 6$ Finite Sets: Exercise $6.1 \ (2)$