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.
Accepted Atlas resultNot recorded for the preferred artifact
These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.
Formal orientation
Statement map
This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.
The theorem at a glance
Hall's Marriage Theorem at a glance
A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.
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. Generated explanation only; the exact HTML statement and pinned source are authoritative.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.
A system of distinct representatives appears as one selected edge at every left and right endpoint. Generated explanation only; the exact HTML statement and pinned source are authoritative.Detailed visual description
Two columns contain exactly six vertices each. Six thick horizontal gold edges pair the rows one to one, while faint diagonal candidate edges and nested cobalt contours suggest the surrounding family of choices and neighborhood conditions.
Complementary intuition
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.
The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.
Authoritative formal type
Exact Mathlib statement
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
Selected evidence declaration text
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
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.
Because each object of hallMatchingsFunctor is nonempty and finite, nonempty_sections_of_finite_inverse_system supplies a section u together with compatibility hu. This coherence, rather than an arbitrary independent choice on each finite set, is the bridge to one global function.
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.
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.
