ArrowTheorem.arrow_theorem
Arrow's impossibility theorem. Let $n$ be a natural number and let $f:\{0,1\}^n\to\bbr$ be a social welfare function that aggregates the pairwise opinions of $n$ voters. Suppose $f$ is odd, meaning $f(\bar x) = -f(x)$ for every $x$, where $\bar x$ is the bitwise complement of $x$; is $\pm 1$-valued, meaning $f(x)\in\{-1,1\}$ for every $x$; is unanimous, meaning $f$ takes the value $1$ at the all-zeros input; and is acyclic, meaning that no profile of voter orderings produces a Condorcet cycle. Here a profile assigns to each of the $n$ voters one of the six linear orderings of three alternatives $a,b,c$, and from it one forms three vote vectors in $\{0,1\}^n$ whose $i$-th entries record voter $i$'s preference in the $a$-vs-$b$, $b$-vs-$c$, and $c$-vs-$a$ comparisons; acyclicity requires that $f$ never sends all three of these vectors to $1$, and never sends all three to $-1$. Then $f$ is a dictatorship: there is a voter $i$ such that $f(x) = (-1)^{x_i}$ for all $x$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option maxHeartbeats 800000 in open scoped BigOperators in open BooleanAnalysis in variable {n : ℕ} in theorem ArrowTheorem.arrow_theorem (f : BooleanFunc n) (hodd : isOddFunc f) (hpm : isPmOne f) (huniv : unanimity f) (hacyc : acyclic f) : isDictator f
- Formalizes
- Arrow's impossibility theorem, as formalized in TCSlib (`ArrowTheorem.arrow_theorem`)
- Lean proof
- By Mina, Allan Li, Owen McGinty (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.ArrowTheorem.arrow_theorem← ArrowTheorem.arrow_theorem (TCSlib/BooleanAnalysis/ArrowTheorem.lean:721): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- ArrowTheorem.acyclicA social welfare function $f$ is acyclic if no profile of transitive voter orderings produces a Condorcet cycle in society's…
- ArrowTheorem.isDictator$f$ is a dictatorship if there exists a voter $i$ such that $f = \mathrm{dict}_i$, i.e.\ society's preference always equals voter…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- ArrowTheorem.degree_one_implies_dictatorDegree-one unanimous voting rules are dictatorships. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function that is odd, is $\pm 1$-valued, and is…
- ArrowTheorem.corrFunc_eq_neg_third_of_weight_oneExtremal correlation concentrates weight on level one. Let $f:\{0,1\}^n\to\bbr$ be a $\pm 1$-valued Boolean function that is odd, meaning…
- BooleanAnalysis.isOddFuncA Boolean function $f$ is odd if $f(\lnot x) = -f(x)$ for all $x$. This models antisymmetry of pairwise preferences in social choice.
- ArrowTheorem.unanimityA social welfare function $f:\{0,1\}^n\to\bbr$ is unanimous if $f(\texttt{false},\dots,\texttt{false}) = 1$: when all voters prefer…
- BooleanAnalysis.isPmOne$f$ is $\pm 1$-valued if $f(x)\in\{-1,1\}$ for all $x$.
- ArrowTheorem.acyclic_implies_corrFuncAcyclicity forces correlation $-1/3$. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function that is odd, $\pm 1$-valued, and acyclic. Then its…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- ArrowTheorem.corrFuncThe Fourier correlation function of $f$ is \[ \mathrm{corr}(f) \;=\; \sum_{S\subseteq[n]} \hat f(S)^2\,(-1/3)^{|S|}. \] For odd…
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option maxHeartbeats 800000 inopen scoped BigOperators inopen BooleanAnalysis invariable {n : ℕ} in/-- **Arrow's Impossibility Theorem** (via Kalai's Fourier proof): Any social welfare function f that is: - odd (antisymmetric: f(¬x) = -f(x)) - ±1-valued (gives definite preferences) - unanimous (unanimously preferred alternatives are socially preferred) - acyclic (no Condorcet cycles arise) must be a **dictatorship** (there is one voter whose preference always wins). The proof uses Fourier analysis on Boolean functions: 1. Acyclicity forces the Fourier cycle probability to be 0. 2. This forces all Fourier weight onto level 1 (degree-1 functions). 3. A degree-1 ±1-valued unanimous function must be a dictator. **Source:** [OD14, Ch. 2]. -/theorem ArrowTheorem.arrow_theorem (f : BooleanFunc n) (hodd : isOddFunc f) (hpm : isPmOne f) (huniv : unanimity f) (hacyc : acyclic f) : isDictator f := by -- Step 1: Acyclicity implies the correlation function equals -1/3 have hcorr : corrFunc f = -1/3 := acyclic_implies_corrFunc f hodd hpm hacyc -- Step 2: corrFunc = -1/3 implies all weight on level 1 have hdeg1 : ∀ S : Finset (Fin n), S.card ≠ 1 → fourierCoeff f S = 0 := corrFunc_eq_neg_third_of_weight_one hodd hpm hcorr -- Step 3: Degree-1 + unanimous + ±1-valued implies dictator exact degree_one_implies_dictator f hodd hpm huniv hdeg1