Existing in Mathlib · Combinatorics
Inclusion–Exclusion Principle
To count a finite union exactly, add the sizes of the individual sets, subtract the sizes of all pairwise intersections, add the triple intersections, and continue alternating over every nonempty chosen subfamily.
- finite unions
- finite intersections
- alternating sums
- powersets
- cardinality
- indicator functions
Exact theorem
Exact Mathlib statement
theorem Finset.inclusion_exclusion_card_biUnion {ι α : Type*} [DecidableEq α]
(s : Finset ι) (S : ι → Finset α) :
#(s.biUnion S) = ∑ t : s.powerset.filter (·.Nonempty),
(-1 : ℤ) ^ (#t.1 + 1) * #(t.1.inf' (mem_filter.1 t.2).2 S)The theorem at a glance
Inclusion–exclusion at a glance
A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.
Inclusion–exclusion at a glance
Detailed visual description
The poster gives the exact three-set inclusion–exclusion identity as a readable representative of the general finite-family theorem. Seven patterned tokens occupy the seven nonempty Venn regions, while adjacent singleton, pair, and triple region shapes encode the add-subtract-add parity. Its route summary identifies the indicator expansion, parity by subfamily size, and specialization of the general sum identity at f = 1.
Statement structure
Statement and scope
Read the exact Mathlib declaration
This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.
Seven regions through alternating corrections
Detailed visual description
Three overlapping blue, green, and gold enclosures form exactly seven nonempty regions, each carrying one texture: dots, horizontal stripes, vertical dashes, diagonal hatch, waves, grid, or concentric rings. A central lattice has three singleton nodes, three pair nodes, and one triple node. All six containing incidences are present: each singleton connects to exactly its two pair nodes, and every pair connects by a dashed arrow to the triple. A braided three-color strand and outer flows lead to one final enclosure containing the same seven textures exactly once. No empty-subfamily node or operator glyph appears.
Why it matters
A mathematical landmark
Inclusion–exclusion is one of the central counting principles of combinatorics. Mathlib's selected theorem exposes its full finite-family structure directly: the powerset of the index set organizes every nonempty intersection, and the parity of subfamily size controls the exact correction.
ProofAtlas record
What has been checked
Mathlib is the source of the theorem; the local Lean replay and page review are separate.
Claim boundary
No new theorem is claimed
This page indexes Mathlib's finite-cardinality inclusion–exclusion theorem for a finite index Finset s and a family S : ι → Finset α. It sums the cardinalities of the intersections indexed by every nonempty subfamily t of s with sign (-1)^(|t|+1) to recover #(s.biUnion S). It is not the nearby theorem for weighted sums, complements, measures, integrals, infinite families, or truncated Bonferroni bounds.
- The selected declaration concerns the cardinality of a finite union of finite sets; it does not state the nearby weighted-sum or complement variants.
- The theorem sums over every nonempty subfamily, so the alternating correction does not stop after pairwise or triple intersections in a larger family.
- The selected declaration does not assert a measure, integral, probability, infinite-family, or truncated Bonferroni formula.
- The three-set diagrams are finite representatives of the general Finset-indexed statement, not a restriction of the theorem to exactly three sets.
- ProofAtlas is indexing an existing Mathlib theorem, and generated explanations and visuals are not proof evidence.
Source and local evidence
Where the theorem comes from
- Existing declaration
Finset.inclusion_exclusion_card_biUnionin mathlib- Relationship
- The checked artifact is the upstream declaration itself
- Local Lean evidence
artifact.library.mathlib.inclusion-exclusion-principle.v001