exists_disjoint_colors_finset
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).
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.
let S := Finset.biUnion Finset.univ L let k := S.sup id + 1 use Finset.Ico k (k + m) refine ⟨?_, ?_⟩
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.
uses
Nat.card_Ico,Nat.add_sub_cancel_left· rw [Nat.card_Ico, Nat.add_sub_cancel_left]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).
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
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.
/-- 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