strictMajority_all_ones
For any integer n > 0, evaluating the strict Majority function on the all-ones input yields true.
Statement
theorem strictMajority_all_ones (n : ℕ) (hn : 0 < n) : strictMajority n (fun _ => true) = true
- 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$, if $0 < n$, then the strict majority function strictMajority evaluated on $n$ and the constant-true vector $(\lambda \_ \mapsto \text{true})$ on $\text{Fin } n$ is equal to $\text{true}$.
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
To show that the strict majority function returns true on the all-ones input of length $n > 0$, we unfold the definition of strict majority and simplify. The condition requires that twice the number of true coordinates strictly exceeds $n$. Because all $n$ coordinates are true, this reduces to the inequality $n < 2n$, which holds immediately since $n > 0$.
Evaluating strict majority on the all-ones input reduces to the inequality $n < 2n$.
By definition, `strictMajority` tests whether $n < 2 \cdot |\{i \in \text{Fin } n \mid x_i = \text{true}\}|$. For the constantly true input, every index satisfies the predicate, so the filtered set is all of $\text{Fin } n$, which has cardinality $n$. Simplifying `decide (n < 2 * n) = true` leaves the strict inequality $n < 2n$.
unfold strictMajority simp
The inequality $n < 2n$ holds.
Linear arithmetic (`omega`) discharges $n < 2n$ directly from the hypothesis $n > 0$.
omega
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 n > 0, the all-ones input satisfies strict Majority. -/theorem strictMajority_all_ones (n : ℕ) (hn : 0 < n) : strictMajority n (fun _ => true) = true := by unfold strictMajority simp omega