Subset of Finite Set is Finite

From ProofWiki
Jump to navigation Jump to search

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:

If $X$ is finite and $a \in X$, then $X \setminus \set a$ is also finite.

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

Retrieved from "https://proofwiki.org/w/index.php?title=Subset_of_Finite_Set_is_Finite&oldid=461900"