Cardinality of Complement

From ProofWiki
Jump to: navigation, search

Theorem

Let $T \subseteq S$ such that $\left|{S}\right| = n, \left|{T}\right| = m$.


Then:

$\left|{\complement_S \left({T}\right)}\right| = \left|{S \setminus T}\right| = n - m$

where:

$\complement_S \left({T}\right)$ 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 = \varnothing$.

Otherwise, $\left\{{T, S \setminus T}\right\}$ is a partition of $S$.

Let $\left|{S \setminus T}\right| = p$.

Then by the Fundamental Principle of Counting:

$m + p = n$

and the result follows.

$\blacksquare$


Sources