# Finite Set Contains Subset of Smaller Cardinality

## Theorem

Let $S$ be a finite sets.

Let

$\size S = n$

where $\size {\, \cdot \,}$ denotes cardinality.

Let $0 \le m \le n$.

Then there exists a subset $X \subseteq S$ such that:

$\size X = m$

## Proof

### Case 1

Let $m = n$.

Then $X = S$ is a subset $X \subseteq S$ such that:

$\size X = m$

$\Box$

### Case 2

Let $m = 0$.

Then $X = \O$ is a subset $X \subseteq S$ such that:

$\size X = m$

$\Box$

### Case 3

Let $0 < m < n$.

By definition of the cardinality of a finite set:

$S \sim \N_{< n}$

where:

$\sim$ denotes set equivalence
$\N_{<n}$ is the set of all natural numbers less than $n$

Consider the set of all natural numbers less than $m$, $\N_{< m}$.

 $\ds k$ $\in$ $\ds \N_{< m}$ $\ds \leadstoandfrom \ \$ $\ds k$ $<$ $\ds m$ Definition of set of all natural numbers less than $m$ $\ds \leadsto \ \$ $\ds k$ $<$ $\ds n$ As $m < n$ and the ordering on the natural numbers is transitive $\ds \leadstoandfrom \ \$ $\ds k$ $\in$ $\ds \N_{< n}$ Definition of set of all natural numbers less than $n$

By the definition of a subset:

$\N_{< m} \subseteq \N_{< n}$

Let $i : \N_{< m} \to \N_{< n}$ be the inclusion mapping.

Let $f : \N_{< n} \to S$ be a bijection between $\N_{< n}$ and $S$.

From Composite of Injections is Injection, the composite $f \circ i : \N_{< m} \to S$ is an injection.

Let $X = \Img {f \circ i}$ be the image of $f \circ i$.

By definition of the image of a mapping:

$X \subseteq S$
$\N_{< m} \sim X$

By definition of the cardinality of $X$:

$\size X = m$

$\blacksquare$