Cardinality of Subset of Finite Set
Jump to navigation
Jump to search
Theorem
Let $A$ and $B$ be finite sets such that $A \subseteq B$.
Let
- $\card B = n$
where $\card {\, \cdot \,}$ denotes cardinality.
Then $\card A \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:
- $\card A < n$
$(2): \quad A = B$
In this case:
- $\card A = \card B$
and so:
- $\card A = n$
In both cases:
- $\card A \le n$
Hence the result.
$\blacksquare$
Also see
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Theorem $17.5$
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets