2025/04/09 by Livson, Ori, Prokopenko, Mikhail · 1 voice · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2504.06589
Incomputability results in Formal Logic and the Theory of Computation (i.e., incompleteness and undecidability) have deep implications for the foundations of mathematics and computer science. Likewise, Social Choice Theory, a branch of Welfare Economics, contains various impossibility results that place limits on the potential fairness, rationality and consistency of social decision-making processes. However, a relationship between the fields' most seminal results: Gödel's First Incompleteness Theorem of Formal Logic, and Arrow's Impossibility Theorem in Social Choice Theory is lacking. In this paper, we address this gap by introducing a general mathematical object called a Self-Reference System. Correspondences between the two theorems are formalised by abstracting well-known diagonalisation and fixed-point arguments, and consistency and completeness properties of provability predicates in the language of Self-Reference Systems. Nevertheless, we show that the mechanisms generating Arrovian impossibility and Gödelian incompleteness have subtle differences.