Inclusion–exclusion formula for elements with none of the properties

Builds on Cardinality of a finite set Inclusion–exclusion principle

Statement

Let $X$ be a finite set. Let $\mathcal{P} = \{p_1, \dots, p_m\}$ be a set of $m$ properties that each element of $X$ may or may not have.

For a subset $S \subseteq [m] = \{1, \dots, m\}$ , let $N(S)$ be the number of elements of $X$ that have every property $p_i$ with $i \in S$ . In particular $N(\varnothing) = |X|$ .

Then the number of elements of $X$ that have none of the properties in $\mathcal{P}$ is $\sum_{S \subseteq [m]} (-1)^{|S|} N(S).$

Remarks

This is the sieve form of the inclusion–exclusion principle. The sizes are cardinalities of finite sets.

Take $A_i$ to be the set of elements of $X$ with property $p_i$ . Then $N(S)$ is the size of the intersection of the $A_i$ for $i \in S$ , and the formula counts the complement of the union of the $A_i$ in $X$ .

Reading path

To understand this page from the ground up, read these 5 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

Cardinality of a finite set definition
Rule of sum statement
Inclusion–exclusion for two sets statement
Inclusion–exclusion principle statement
Inclusion–exclusion formula for elements with none of the properties statement

Tag	`XJPVHVVKD9`
URI	`m2://XJPVHVVKD9`
Kind	statement, theorem
Writing	W1 stated
MSC	05A05
Status	This copy of the site has no build data. Run `m2 status XJPVHVVKD9`.
Uses	Cardinality of a finite set, Inclusion–exclusion principle
Changed	4 November 2026

Inclusion–exclusion formula for elements with none of the properties

Statement

Remarks

Reading path

Further reading

What this page needs for W2

What links here