Arrow's theorem, ultrafilters, and reverse mathematics

Abstract

This paper initiates the reverse mathematics of social choice theory, studying Arrow's impossibility theorem and related results including Fishburn's possibility theorem and the Kirman--Sondermann theorem within the framework of reverse mathematics. We formalise fundamental notions of social choice theory in second-order arithmetic, yielding a definition of countable society which is tractable in ${\mathsf{RCA}}_0$. We then show that the Kirman--Sondermann analysis of social welfare functions can be carried out in ${\mathsf{RCA}}_0$. This approach yields a proof of Arrow's theorem in ${\mathsf{RCA}}_0$, and thus in $\mathrm{PRA}$, since Arrow's theorem can be formalised as a ${\Pi }_1^0$ sentence. Finally we show that Fishburn's possibility theorem for countable societies is equivalent to ${\mathsf{ACA}}_0$ over ${\mathsf{RCA}}_0$.

23 pages