Cardinality of Subset of Finite Set

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $\left\lvert{B}\right\rvert = n$.


Then $\left\lvert{A}\right\rvert \le n$.


Proof

Let $A \subseteq B$.


There are two cases:


$(1): \quad A \ne B$

In this case:

$A \subsetneqq B$

and from Cardinality of Proper Subset of Finite Set:

$\left\lvert{A}\right\rvert < n$


$(2): \quad A = B$

In this case:

$\left\lvert{A}\right\rvert = \left\lvert{B}\right\rvert$

and so:

$\left\lvert{A}\right\rvert = n$


In both cases:

$\left\lvert{A}\right\rvert \le n$

Hence the result.

$\blacksquare$


Also see


Sources