finite_family_injective_representatives_avoiding
For a finite indexed family of finite sets and a finite forbidden set, if every member contains at least as many elements as the number of indices plus the size of the forbidden set, there is an injective choice of representatives outside the forbidden set.
Statement
theorem finite_family_injective_representatives_avoiding {ι α : Type*} [Fintype ι] [DecidableEq α] (A : ι → Finset α) (B : Finset α) (hlarge : ∀ i, Fintype.card ι + B.card ≤ (A i).card) : ∃ f : ι → α, Function.Injective f ∧ ∀ i, f i ∈ A i ∧ f i ∉ B
- Source
- A direct consequence of the finite matching theorem, used in the triangle-packing representative kernel.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof applies Hall's Marriage Theorem to the family of sets A i \ B. To verify Hall's condition for an arbitrary index subset s ⊆ ι, the empty case is trivial, while for a nonempty s, choosing any element i ∈ s yields |s| ≤ |ι| ≤ |A i| - |B| ≤ |A i \ B| ≤ |⋃_{j ∈ s} (A j \ B)| by the cardinality assumption on A i. Hall's Marriage Theorem then produces an injective choice function f with f(i) ∈ A i \ B for all i, which means f selects an element from each A i avoiding B.
To establish the existence of the injective representatives, it suffices to verify Hall's marriage condition for the family i ↦ A i \ B.
We enable classical reasoning and formulate Hall's condition: for every finite subset of indices s, |s| ≤ |⋃_{i ∈ s} (A i \ B)|. We introduce an arbitrary subset s and split into cases based on whether s is nonempty.
classical have hhall : ∀ s : Finset ι, s.card ≤ (s.biUnion fun i => A i \ B).card := by intro s by_cases hs : s.Nonempty
Hall's condition holds when s is nonempty: |s| ≤ |⋃_{j ∈ s} (A j \ B)|.
Since s is nonempty, we pick an element i ∈ s. The single set A i \ B is contained in the union ⋃_{j ∈ s} (A j \ B), so its size is at most the size of the union. Furthermore, |s| is bounded above by the total number of indices |ι|. Because |A i| ≤ |A i \ B| + |B| and the theorem assumes |ι| + |B| ≤ |A i|, linear arithmetic over ℕ combines these four inequalities to conclude |s| ≤ |⋃_{j ∈ s} (A j \ B)|.
uses
Finset.subset_biUnion_of_mem,Finset.card_le_card,Finset.card_le_univ,Finset.card_le_card_sdiff_add_card· obtain ⟨i, hi⟩ := hs have hsub : A i \ B ⊆ s.biUnion (fun j => A j \ B) := Finset.subset_biUnion_of_mem (fun j : ι => A j \ B) hi have h₁ := Finset.card_le_card hsub have h₂ := Finset.card_le_univ s have h₃ := Finset.card_le_card_sdiff_add_card (s := A i) (t := B) have h₄ := hlarge i omega
Hall's condition holds when s is empty.
If s is not nonempty, then s = ∅. Both |∅| and the size of the empty union are 0, so the inequality 0 ≤ 0 holds trivially.
uses
Finset.not_nonempty_iff_eq_empty.mp· have : s = ∅ := Finset.not_nonempty_iff_eq_empty.mp hs simp [this]
There exists an injective function f : ι → α such that f(i) ∈ A i and f(i) ∉ B for every i.
Applying Hall's Marriage Theorem (Finset.all_card_le_biUnion_card_iff_exists_injective) to the verified condition yields an injective choice function f with f(i) ∈ A i \ B for all i. Unpacking the definition of set difference gives f(i) ∈ A i and f(i) ∉ B for every i.
uses
Finset.all_card_le_biUnion_card_iff_exists_injective,Finset.mem_sdiff.mpobtain ⟨f, hfinj, hf⟩ := (Finset.all_card_le_biUnion_card_iff_exists_injective (fun i => A i \ B)).mp hhall exact ⟨f, hfinj, fun i => Finset.mem_sdiff.mp (hf i)⟩
Finset.subset_biUnion_of_mem- If an element x belongs to an index set s, then u(x) is a subset of the union ⋃_{j ∈ s} u(j).
Finset.card_le_card- If a finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the whole type.
Finset.card_le_card_sdiff_add_card- For finite sets s and t, the cardinality of s is at most the cardinality of s \ t plus the cardinality of t.
Finset.not_nonempty_iff_eq_empty.mp- A finite set that is not nonempty is the empty set.
Finset.all_card_le_biUnion_card_iff_exists_injective- Hall's Marriage Theorem for finite sets: a family of finite sets t admits an injective system of distinct representatives if and only if every finite index subset s satisfies |s| ≤ |⋃_{i ∈ s} t(i)|.
Finset.mem_sdiff.mp- If an element belongs to the set difference s \ t, then it belongs to s and does not belong to t.
- The inequality in the nonempty case (line 17) is closed by the `omega` tactic, which handles Presburger arithmetic over ℕ to combine the four bounds: |s| ≤ |ι|, |ι| + |B| ≤ |A i|, |A i| ≤ |A i \ B| + |B|, and |A i \ B| ≤ |⋃_{j ∈ s} (A j \ B)|.
- The `classical` tactic at line 6 is a Lean formal detail that provides decidability instances for all propositions, allowing finite set operations without extra typeclass constraints.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem finite_family_injective_representatives_avoiding {ι α : Type*} [Fintype ι] [DecidableEq α] (A : ι → Finset α) (B : Finset α) (hlarge : ∀ i, Fintype.card ι + B.card ≤ (A i).card) : ∃ f : ι → α, Function.Injective f ∧ ∀ i, f i ∈ A i ∧ f i ∉ B := by classical have hhall : ∀ s : Finset ι, s.card ≤ (s.biUnion fun i => A i \ B).card := by intro s by_cases hs : s.Nonempty · obtain ⟨i, hi⟩ := hs have hsub : A i \ B ⊆ s.biUnion (fun j => A j \ B) := Finset.subset_biUnion_of_mem (fun j : ι => A j \ B) hi have h₁ := Finset.card_le_card hsub have h₂ := Finset.card_le_univ s have h₃ := Finset.card_le_card_sdiff_add_card (s := A i) (t := B) have h₄ := hlarge i omega · have : s = ∅ := Finset.not_nonempty_iff_eq_empty.mp hs simp [this] obtain ⟨f, hfinj, hf⟩ := (Finset.all_card_le_biUnion_card_iff_exists_injective (fun i => A i \ B)).mp hhall exact ⟨f, hfinj, fun i => Finset.mem_sdiff.mp (hf i)⟩