AFTD Auto-Formalizing Theoretical Domains

strictMajority_all_ones

theoremverified

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

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

    lines 4–5

      unfold strictMajority
      simp
  2. The inequality $n < 2n$ holds.

    Linear arithmetic (`omega`) discharges $n < 2n$ directly from the hypothesis $n > 0$.

    line 6

      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

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