Suppose each index i is assigned a finite set t i. One can choose an element f i from every t i with no two indices choosing the same element exactly when, for every finite collection of indices, the union of their assigned sets has at least as many elements as that collection.
matchings
finite sets
injective choice
systems of representatives
Exact theorem
Exact Mathlib statement
theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α : Type v} [DecidableEq α] (t : ι → Finset α) : (∀ s : Finset ι, s.card ≤ (s.biUnion t).card) ↔ ∃ f : ι → α, Function.Injective f ∧ ∀ x : ι, f x ∈ t x
The theorem at a glance
Hall's Marriage Theorem at a glance
A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.
Hall's Marriage Theorem at a glance
Loading full-resolution image…
Every finite-subfamily union condition is shown equivalent to a total injective representative function, without implying surjectivity onto the target type.Open original image in a new tab
Every finite-subfamily union condition is shown equivalent to a total injective representative function, without implying surjectivity onto the target type. Explanatory diagram.Detailed visual description
The left side selects a finite subfamily of indexed Finsets, forms its union, and compares the two cardinalities. The right side highlights one distinct allowed representative per index while many elements of alpha remain unused. A lower strip names all five scope ingredients before an injective-not-onto footer.
Statement structure
From hypotheses to conclusion
This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.
Hall matching schematic
Loading full-resolution image…
Five indexed sets receive distinct representatives; two available right-side values remain unused.Open original image in a new tab
Five indexed sets receive distinct representatives; two available right-side values remain unused. Explanatory scientific diagram.Detailed visual description
Five emerald vertices on the left each send one luminous gold edge to a different ivory vertex on the right. Seven ivory vertices are available in total, and two remain unmatched; thin candidate edges and cobalt neighborhood contours show the wider choice system without implying surjectivity.
Why it matters
A mathematical landmark
Hall's theorem characterizes when a perfect system of distinct representatives exists. It is a cornerstone of matching theory and finite combinatorics; Mathlib's selected statement allows an arbitrary index type while testing every finite subfamily.
Proof architecture
From finite matchings to one global choice
5 curated stages
Mathlib's arbitrary-index Hall theorem builds finite local matching spaces, organizes their restrictions into an inverse system, uses compactness to select a coherent section, extracts a global injective representative function, and proves the converse by cardinality comparison.
These source-anchored stages explain the retained Mathlib proof route. They are generated explanations, not proof evidence or an extracted Lean proof-term dependency graph.
Every finite subfamily has a finite, nonempty space of injective representative choices.
Nonempty (hallMatchingsOn t ι') ∧ Finite (hallMatchingsOn t ι')
For a finite index set ι', hallMatchingsOn stores functions into α that are injective and choose inside each assigned finite set. The Hall inequality feeds the finite theorem to prove nonemptiness, while encoding a matching into the finite union proves that this local matching space is finite.
A matching on a larger finite subfamily restricts to the same choices on every smaller one.
hallMatchingsOn t ι'' → hallMatchingsOn t ι'
hallMatchingsOn.restrict precomposes a larger local matching with the subset inclusion and retains injectivity and membership. hallMatchingsFunctor uses exactly these restriction maps, reversing inclusions through the opposite category.
The figure shows the compactness stage of Mathlib’s arbitrary-index Finset form of Hall’s marriage theorem. Several nested finite-subfamily matching cards appear in two compatible towers. Every restriction arrow points upward from a larger finite subfamily to a smaller one, aligned choices agree across the two towers, and dashed paths feed the coherent local family into one representative function. The lowest cards continue the inverse system without identifying any finite subfamily with the arbitrary index type.
04
Read off the global injective choice
Read off the global injective choice
Loading full-resolution image…
Singleton values form the global choice, while pairwise coherence forces those choices to be injective.Open original image in a new tab
Singleton values form the global choice, while pairwise coherence forces those choices to be injective.
∃ f, Function.Injective f ∧ ∀ i, f i ∈ t i
The function takes i from the coherent matching on the singleton containing i. For i and i', hu compares both singleton choices with the matching on their pair, whose injectivity proves equality of values can only come from equality of indices. The singleton matching also proves f i belongs to t i.
05
Recover the Hall inequalities
Recover the Hall inequalities
Loading full-resolution image…
Any injective representative choice sends each finite subfamily into its allowed union, so cardinalities satisfy Hall's condition.Open original image in a new tab
Any injective representative choice sends each finite subfamily into its allowed union, so cardinalities satisfy Hall's condition.
(∀ s, #s ≤ #(s.biUnion t)) ↔ ∃ f, Function.Injective f ∧ ∀ i, f i ∈ t i
Injectivity rewrites the size of s as the size of s.image f. Membership of every representative places that image inside s.biUnion t, and card_le_card gives the desired inequality. This closes the reverse implication and therefore the exact equivalence.
Accepted Atlas resultNot recorded for the preferred artifact
Mathlib is the source of the theorem; the local Lean replay and page review are separate.
Claim boundary
No new theorem is claimed
This is Mathlib's indexed-Finset equivalence. It concerns finite member sets t i, checks every finite subfamily s, and concludes the existence of an injective representative function; the page does not substitute a different graph-theoretic formulation.
Proof Atlas did not originate Hall's theorem or Mathlib's declaration.
The selected declaration includes an arbitrary index type and a finite-subfamily condition.
The explanatory matching diagram is not a proof of the equivalence.
