Complement principle

Builds on Cardinality of a finite set Rule of sum

Statement

Let $U$ be a finite set and let $A \subseteq U$ . Let $A^c = U \setminus A$ be the complement of $A$ in $U$ . Then $|A^c| = |U| - |A|$ .

Remarks

The rule follows from the rule of sum, because $U$ is the disjoint union of $A$ and $A^c$ . It is useful when the complement is easier to count. For example, the number of words of length $n$ over $\{0, 1\}$ that contain at least one $1$ is $2^n - 1$ .

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`03QC59M99B`
URI	`m2://03QC59M99B`
Kind	statement, proposition
Writing	W0 stub
MSC	05A05
Status	This copy of the site has no build data. Run `m2 status 03QC59M99B`.
Uses	Cardinality of a finite set, Rule of sum

Complement principle

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here