AFTD Auto-Formalizing Theoretical Domains

finite_family_injective_representatives_avoiding

theoremverified

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.

  1. 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.

    lines 6–9

      classical
      have hhall : ∀ s : Finset ι, s.card ≤ (s.biUnion fun i => A i \ B).card := by
        intro s
        by_cases hs : s.Nonempty
  2. 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)|.

    lines 10–17

    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
  3. 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.

    lines 18–19

    uses Finset.not_nonempty_iff_eq_empty.mp

        · have : s = ∅ := Finset.not_nonempty_iff_eq_empty.mp hs
          simp [this]
  4. 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.

    lines 20–22

    uses Finset.all_card_le_biUnion_card_iff_exists_injective, Finset.mem_sdiff.mp

      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)⟩
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.

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

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)⟩
See it in the graphDiscuss this resultChallenge it