AFTD Auto-Formalizing Theoretical Domains

finite_three_weighted_sets_half_cover_implies_pair_cover

theoremverified

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

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

    lines 9–15

    uses Or.inl, Or.inr

      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)
  2. 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$.

    lines 16–19

      push_neg at hAB hAC hBC
      obtain ⟨u,huA,huB⟩ := hAB
      obtain ⟨v,hvA,hvC⟩ := hAC
      obtain ⟨w,hwB,hwC⟩ := hBC
  3. 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$.

    lines 20–22

      have hu := hcover u
      have hv := hcover v
      have hw := hcover w
  4. 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`.

    lines 23–25

    uses if_false, zero_add, add_zero

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

    line 26

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

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