AFTD Auto-Formalizing Theoretical Domains

strictMajority_all_zeros

theoremverified

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.

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

    line 4

    uses strictMajority

      simp [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

/-- The all-zeros input does not satisfy strict Majority. -/theorem strictMajority_all_zeros (n : ℕ) :    strictMajority n (fun _ => false) = false := by  simp [strictMajority]
See it in the graphDiscuss this resultChallenge it