Comparing and Contrasting Arrow's Impossibility Theorem and Gödel's Incompleteness Theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908639503056896 |
|---|---|
| author | Livson, Ori Prokopenko, Mikhail |
| author_facet | Livson, Ori Prokopenko, Mikhail |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06589 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Comparing and Contrasting Arrow's Impossibility Theorem and Gödel's Incompleteness Theorem Livson, Ori Prokopenko, Mikhail Logic Logic in Computer Science 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. |
| title | Comparing and Contrasting Arrow's Impossibility Theorem and Gödel's Incompleteness Theorem |
| topic | Logic Logic in Computer Science |
| url | https://arxiv.org/abs/2504.06589 |