strictMajority_all_zeros
For any natural number n, evaluating the strict Majority function on the all-zeros input yields false.
Statement
theorem strictMajority_all_zeros (n : ℕ) : strictMajority n (fun _ => false) = false
- Source
- folklore
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- strictMajorityThe strict Majority function on n Boolean inputs, returning true if strictly more than n/2 inputs are true, and false otherwise.
Read back from the Lean
For every natural number $n$, the function strictMajority applied to $n$ and the constant false function on Fin n evaluates to false.
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 theorem states that for any natural number n, the strict majority function evaluates to false on the all-zeros input vector. Unfolding the definition of strictMajority, the set of indices where the input is true is empty and has cardinality zero. The strict majority condition n < 2 * 0 is false for every natural number n, so the function simplifies directly to false.
The strict majority function applied to the all-zeros input evaluates to false for every natural number n. automation
The simplifier unfolds the definition of strictMajority and evaluates the expression. For the constant false input, the subset of indices where the entry is true is empty, so its cardinality is 0. The strict majority condition thus reduces to n < 2 * 0, which is n < 0; since no natural number is strictly less than 0, this inequality is false, and decide false simplifies to false, closing the goal.
uses
strictMajoritysimp [strictMajority]
strictMajority- The boolean function on n-bit vectors that returns true if strictly more than half the entries are true, defined by decide (n < 2 * card) where card is the number of true coordinates.
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.
/-- The all-zeros input does not satisfy strict Majority. -/theorem strictMajority_all_zeros (n : ℕ) : strictMajority n (fun _ => false) = false := by simp [strictMajority]