finite_three_weighted_sets_half_cover_implies_pair_cover
If a positive total of three nonnegative integer weights gives every point at least half the weight of the sets containing it, two of those sets cover every point.
Statement
theorem finite_three_weighted_sets_half_cover_implies_pair_cover {α : Type*} [DecidableEq α] (A B C : Finset α) (x y z : ℕ) (hpos : 0 < x + y + z) (hcover : ∀ v : α, x + y + z ≤ 2 * ((if v ∈ A then x else 0) + (if v ∈ B then y else 0) + (if v ∈ C then z else 0))) : (∀ v, v ∈ A ∨ v ∈ B) ∨ (∀ v, v ∈ A ∨ v ∈ C) ∨ (∀ v, v ∈ B ∨ v ∈ C)
- Source
- Elementary support observation in OP-337, motivated by https://arxiv.org/abs/2610.23487.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof is by contradiction: suppose that no two of the three sets cover the whole space. Then there exist points $u \notin A \cup B$, $v \notin A \cup C$, and $w \notin B \cup C$. Evaluating the half-cover condition at each point eliminates two of the three weights, leaving $x + y + z \le 2z$, $x + y + z \le 2y$, and $x + y + z \le 2x$ (or an upper bound of 0 if a point is omitted by all three sets). Summing these inequalities yields $3(x + y + z) \le 2(x + y + z)$, which contradicts the positivity hypothesis $0 < x + y + z$.
We may assume that no pair of sets among $\{A, B\}$, $\{A, C\}$, and $\{B, C\}$ covers the domain $\alpha$.
We case split on each pair-covering condition. If $A \cup B = \alpha$, the theorem holds via the first disjunct (`Or.inl`). If not, but $A \cup C = \alpha$, it holds via the second disjunct (`Or.inr (Or.inl ...)`). If neither holds, but $B \cup C = \alpha$, it holds via the third disjunct (`Or.inr (Or.inr ...)`). Hence, we may assume that all three pair covers fail.
uses
Or.inl,Or.inrclassical by_cases hAB : ∀ v, v ∈ A ∨ v ∈ B · exact Or.inl hAB by_cases hAC : ∀ v, v ∈ A ∨ v ∈ C · exact Or.inr (Or.inl hAC) by_cases hBC : ∀ v, v ∈ B ∨ v ∈ C · exact Or.inr (Or.inr hBC)
There exist elements $u, v, w \in \alpha$ such that $u \notin A \cup B$, $v \notin A \cup C$, and $w \notin B \cup C$.
Pushing the negations through the universal quantifiers in the three assumed failures produces existential witnesses: a point $u$ not in $A$ and not in $B$, a point $v$ not in $A$ and not in $C$, and a point $w$ not in $B$ and not in $C$.
push_neg at hAB hAC hBC obtain ⟨u,huA,huB⟩ := hAB obtain ⟨v,hvA,hvC⟩ := hAC obtain ⟨w,hwB,hwC⟩ := hBC
The half-cover inequality holds at each of $u$, $v$, and $w$.
We specialize the universal covering hypothesis `hcover` to the three witness points $u$, $v$, and $w$.
have hu := hcover u have hv := hcover v have hw := hcover w
The inequalities reduce to $x + y + z \le 2 \cdot (\text{if } u \in C \text{ then } z \text{ else } 0)$, $x + y + z \le 2 \cdot (\text{if } v \in B \text{ then } y \text{ else } 0)$, and $x + y + z \le 2 \cdot (\text{if } w \in A \text{ then } x \text{ else } 0)$.
Using the known non-memberships, the indicator conditions simplify to false via `if_false`. At $u$, $u \notin A$ and $u \notin B$ eliminate the $x$ and $y$ terms, simplifying with `zero_add`. At $v$, $v \notin A$ and $v \notin C$ eliminate the $x$ and $z$ terms using `zero_add` and `add_zero`. At $w$, $w \notin B$ and $w \notin C$ eliminate the $y$ and $z$ terms using `add_zero`.
uses
if_false,zero_add,add_zerosimp only [huA,huB,if_false,zero_add] at hu simp only [hvA,hvC,if_false,zero_add,add_zero] at hv simp only [hwB,hwC,if_false,add_zero] at hw
The three reduced inequalities contradict $x + y + z > 0$. automation
Case splitting (`split_ifs`) on whether $u \in C$, $v \in B$, and $w \in A$ yields eight cases. If any witness does not belong to its third set, the right-hand side is $0$, forcing $x + y + z \le 0$ and contradicting $x + y + z > 0$. If all three belong, the inequalities become $x + y + z \le 2z$, $x + y + z \le 2y$, and $x + y + z \le 2x$; summing them yields $3(x + y + z) \le 2(x + y + z)$, which is impossible since $x + y + z > 0$. In all branches, linear integer arithmetic (`omega`) derives the contradiction.
split_ifs at hu hv hw <;> omega
Or.inl- From a proof of $P$, infer $P \lor Q$.
Or.inr- From a proof of $Q$, infer $P \lor Q$.
if_false- An if-then-else expression with a false condition evaluates to its else branch: `if False then t else e = e`.
zero_add- Zero is a left additive identity: `0 + a = a`.
add_zero- Zero is a right additive identity: `a + 0 = a`.
- The tactic `omega` automatically closes all eight branches resulting from `split_ifs` using linear integer arithmetic, finding the contradiction $3(x + y + z) \le 2(x + y + z)$ without manually displaying the summation.
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_three_weighted_sets_half_cover_implies_pair_cover {α : Type*} [DecidableEq α] (A B C : Finset α) (x y z : ℕ) (hpos : 0 < x + y + z) (hcover : ∀ v : α, x + y + z ≤ 2 * ((if v ∈ A then x else 0) + (if v ∈ B then y else 0) + (if v ∈ C then z else 0))) : (∀ v, v ∈ A ∨ v ∈ B) ∨ (∀ v, v ∈ A ∨ v ∈ C) ∨ (∀ v, v ∈ B ∨ v ∈ C) := by classical by_cases hAB : ∀ v, v ∈ A ∨ v ∈ B · exact Or.inl hAB by_cases hAC : ∀ v, v ∈ A ∨ v ∈ C · exact Or.inr (Or.inl hAC) by_cases hBC : ∀ v, v ∈ B ∨ v ∈ C · exact Or.inr (Or.inr hBC) push_neg at hAB hAC hBC obtain ⟨u,huA,huB⟩ := hAB obtain ⟨v,hvA,hvC⟩ := hAC obtain ⟨w,hwB,hwC⟩ := hBC have hu := hcover u have hv := hcover v have hw := hcover w simp only [huA,huB,if_false,zero_add] at hu simp only [hvA,hvC,if_false,zero_add,add_zero] at hv simp only [hwB,hwC,if_false,add_zero] at hw split_ifs at hu hv hw <;> omega