# 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$

From Injection to Image is Bijection:

- $\N_{< m} \sim X$

By definition of the cardinality of $X$:

- $\size X = m$

$\blacksquare$