Bounded-arithmetic provability of Arrow's theorem

Arrow's theorem concerns finite societies and social welfare functions, and its first-order formalisation is a sentence θ\theta in the language of first-order arithmetic. The theory IΔ0+exp\mathrm{I}\Delta_0+\mathrm{exp} is bounded arithmetic with induction for bounded formulas and an exponential function.

Bounded-arithmetic conjecture for Arrow's theorem. The first-order formalisation of Arrow's theorem is provable in

IΔ0+exp.\mathrm{I}\Delta_0 + \mathrm{exp}.

The paper has established that the formalisation is provable in primitive recursive arithmetic and observes that its bounds are exponential; the conjecture asks for the corresponding proof in IΔ0+exp\mathrm{I}\Delta_0+\mathrm{exp}, but no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Benedict Eastaugh, “Arrow's theorem, ultrafilters, and reverse mathematics”, arXiv:2306.06471 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.