AFTD Auto-Formalizing Theoretical Domains

exists_disjoint_colors_finset

theoremverified

For any list assignment L on a finite vertex set V with colors in ℕ and any natural number m, there exists an m-element subset Q ⊂ ℕ that is disjoint from the union of all lists L(v) over v ∈ V.

Statement

theorem exists_disjoint_colors_finset {V : Type*} [Fintype V] (L : V → Finset ℕ) (m : ℕ) :
    ∃ Q : Finset ℕ, Q.card = m ∧ Disjoint Q (Finset.biUnion Finset.univ L)
Source
arXiv:2611.03151 Lemma 9 proof, Step 1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any finite type $V$, any function $L : V \to \mathrm{Finset}(\mathbb{N})$, and any natural number $m$, there exists a finite set $Q \subseteq \mathbb{N}$ of cardinality $m$ that is disjoint from $\bigcup_{v \in V} L(v)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof constructs an explicit witness: because V is finite, the union S = ⋃_{v ∈ V} L(v) of all assigned color lists is a finite set of natural numbers, hence bounded above by its supremum sup(S). Choosing k = sup(S) + 1, the half-open interval Q = [k, k + m) contains m natural numbers, each strictly greater than every element of S. The cardinality |Q| = m follows by interval arithmetic, and disjointness holds because any element in Q is at least k > sup(S) while every element in S is at most sup(S).

  1. The half-open interval Q = [k, k + m), where k = sup(S) + 1 and S = ⋃_{v ∈ V} L(v), is chosen as the witness, reducing the goal to showing |Q| = m and Disjoint Q S.

    We define S as the union of all color lists L(v) across the finite vertex set V, and choose k to be one greater than the supremum of S (with respect to the identity). We then instantiate the existential witness with the interval Q = [k, k + m) of m consecutive integers starting at k, and split the conjunction into two subgoals: verifying the cardinality of Q and verifying its disjointness from S.

    lines 4–7

      let S := Finset.biUnion Finset.univ L
      let k := S.sup id + 1
      use Finset.Ico k (k + m)
      refine ⟨?_, ?_⟩
  2. The candidate set Q has cardinality m.

    By Nat.card_Ico, the number of elements in [k, k + m) is (k + m) - k. By Nat.add_sub_cancel_left, this simplifies to m.

    line 8

    uses Nat.card_Ico, Nat.add_sub_cancel_left

      · rw [Nat.card_Ico, Nat.add_sub_cancel_left]
  3. The candidate set Q is disjoint from S.

    By Finset.disjoint_left, it suffices to show that any element x ∈ Q does not belong to S. Suppose for contradiction that x ∈ Q and x ∈ S. By Finset.mem_Ico, x ∈ [k, k + m) implies k ≤ x. On the other hand, since x ∈ S, Finset.le_sup gives x ≤ sup(S). Recalling that k = sup(S) + 1, this implies sup(S) + 1 ≤ x ≤ sup(S), a contradiction resolved by linear integer arithmetic (omega).

    lines 9–14

    uses Finset.disjoint_left, Finset.mem_Ico, Finset.le_sup

      · rw [Finset.disjoint_left]
        intro x hx hxS
        rw [Finset.mem_Ico] at hx
        have hle : id x ≤ S.sup id := Finset.le_sup hxS
        dsimp at hle
        omega
Nat.card_Ico
The cardinality of the half-open interval of natural numbers [a, b) is b - a.
Nat.add_sub_cancel_left
For any natural numbers n and m, (n + m) - n = m.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.mem_Ico
An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Finset.le_sup
If an element belongs to a finite set, the value of a function at that element is at most the supremum of that function over the set.

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

/-- For any vertex-indexed collection of finite lists in ℕ on a finite vertex set, there exists an m-element set of colors disjoint from all lists. -/theorem exists_disjoint_colors_finset {V : Type*} [Fintype V] (L : V → Finset ℕ) (m : ℕ) :    ∃ Q : Finset ℕ, Q.card = m ∧ Disjoint Q (Finset.biUnion Finset.univ L) := by  let S := Finset.biUnion Finset.univ L  let k := S.sup id + 1  use Finset.Ico k (k + m)  refine ⟨?_, ?_⟩  · rw [Nat.card_Ico, Nat.add_sub_cancel_left]  · rw [Finset.disjoint_left]    intro x hx hxS    rw [Finset.mem_Ico] at hx    have hle : id x ≤ S.sup id := Finset.le_sup hxS    dsimp at hle    omega
See it in the graphDiscuss this resultChallenge it