Cardinality of Subset of Finite Set

Theorem

Let $A$ and $B$ be finite sets such that $A \subseteq B$.

Let $\left|{B}\right| = n$.

Then $\left|{A}\right| \le n$.

If $A \subsetneq B$ ($A$ is a proper subset of $B$, i.e. $A \subseteq B$ and $A \ne B$), then $\left|{A}\right| < n$.

Proof

The proof proceeds by induction on $n$, the cardinality of $B$.

Basis for the Induction

The case $n = 0$ is verified as follows:

Suppose $\left|{B}\right| = 0$. From Cardinality of Empty Set, $B = \varnothing$.

There are no sets $A$ such that $A \subsetneq \varnothing$.

Therefore, for $n = 0$, the theorem is an example of vacuous truth.

This is the basis for the induction.

Induction Hypothesis

Fix $n \in \N$ with $n \ge 0$.

Assume that the statement holds for all sets $B$ with $\left|{B}\right| = n$.

This is our induction hypothesis.

Induction Step

This is our induction step:

Suppose we have any set $B$ such that $\left|{B}\right| = n + 1$.

Let $A = B$. Then $\left|{A}\right| = n + 1$, hence the theorem is verified.

Next, let $A \subsetneq B$. From the definition of $\subsetneq$, we have:

$\exists b \in B: b \notin A$

Therefore, $A \subseteq B \setminus \left\{{b}\right\}$.

From Cardinality Less One, $\left|{B - \left\{{b}\right\}}\right| = n$.

Therefore, we can apply the induction hypothesis.

It follows that $\left|{A}\right| \le n < n + 1$, as asserted.

We conclude the theorem holds for $B$.

As $B$ was arbitrary, we conclude it holds for any set with cardinality $n + 1$.

The result follows by the Principle of Mathematical Induction.

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 13$: Arithmetic
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.7$: Example $56$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 17$: Theorem $17.5$