Cardinality of Complement
Jump to navigation
Jump to search
Theorem
Let $T \subseteq S$ such that $\card S = n, \card T = m$.
Then:
- $\card {\relcomp S T} = \card {S \setminus T} = n - m$
where:
- $\relcomp S T$ denotes the complement of $T$ relative to $S$
- $S \setminus T$ denotes the difference between $S$ and $T$.
Proof
The result is obvious for $S = T$ or $T = \O$.
Otherwise, $\set {T, S \setminus T}$ is a partition of $S$.
Let $\card {S \setminus T} = p$.
Then by the Fundamental Principle of Counting:
- $m + p = n$
and the result follows.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.2$