Project description:

The key theorem in social choice theory, Arrow’s Impossibility Theorem, states that a few natural requirements of aggregation functions are inconsistent with the fundamental condition that aggregation functions should rule out dictatorship. The first no-go theorem in quantum mechanics, Bell’s Theorem, states that the principle of locality is inconsistent with certain other assumptions of the hidden variable theory, proposed in connection with the Einstein-Podolsky-Rosen paradox to account for certain counter-intuitive predictions of quantum mechanics. Both theorems can be understood as a paradox highlighting the global inconsistency of certain locally consistent dependency conditions. This project aims at providing a logical framework in which the commonalities between these two theorems as well as other no-go theorems in social choice and quantum foundations can be fully accounted for. We will use logics of dependence and independence as our basic formal framework for this research.

Logics of dependence and independence (DIL) is a logical formalism, introduced by Väänänen (2007), for reasoning about dependence and independence concepts. DIL adopts an innovative semantics, called team semantics, which was introduced by Hodges (1997). In team semantics formulas are evaluated on a model with respect to sets of assignments, called teams, in contrast to single assignements as in the usual first-order logic. Thanks to the simple structure of teams and the abundance of their interpretations in various contexts, DIL has proven itself to be a useful tool in many fields. In this project, we will develop applications of DIL and team semantics in analyzing the no-go paradoxes in social choice and quantum foundations, and we will also address relevant open problems in the theory of DIL.

Researchers:

• Dr. Fan Yang (PI)

• Davide Quadrellaro

• Analyzing Arrow's Theorem Through Dependence and Independence Logic, Fan Yang, a talk at UH-CAS Workshop on Mathematical Logic, Helsinki, November 2018

• Characterizing dependencies in logic and sciences, Fan Yang, a talk at the 24th Workshop on Logic, Language, Information and Computation (WoLLIC), London, July 2017

• Dependence and independence in logic, Erich Grädel, a tutorial at Logic Colloquium, Helsinki, August 2015

Logics of dependence and independence:

• F. Yang and J. Väänänen, Propositional Team Logics, Annals of Pure and Applied Logic, Volume 168, Issue 7, July 2017, pp. 1406–1441

• F. Yang, Negation and Partial Axiomatizations of Dependence and Independence Logic Revisited, Proceedings of the 23rd Workshop on Logic, Language, Information and Computation (WoLLIC 2016), LNCS 9803, Springer-Verlag, 2016, pp 410-43

• F. Yang and J. Väänänen, Propositional Logics of Dependence, Annals of Pure and Applied Logic, Volume 167, Issue 7, July 2016, pp. 557–589

• M. Hannula, Axiomatizing first-order consequences in independence logic. Annals of Pure and Applied Logic, 166(1): 61-91, 2015.

• P. Galliani and L. Hella, Inclusion logic and fixed point logic. CSL 2013.

• J. Kontinen and J. Väänänen, Axiomatizing first order consequences in dependence logic. Annals of Pure and Applied Logic, 164(11): 1101-1117, 2013.

• E. Grädel and J. Väänänen, Dependence and independence. Studia Logica: Volume 101, Issue 2 (2013), pp 233-236.

• Pietro Galliani, Inclusion and Exclusion in Team Semantics: On some logics of imperfect information. Annals of Pure and Applied Logic, Volume 163, Issue 1, January 2012, pp 68–84

Click here to find out more research papers on DIL.

Logical methods and applications of DIL in social choice:

• W. Holliday and E. Pacuit, Arrow’s decisive coalitions, Social Choice and Welfare (2018)

• E. Pacuit and F. Yang, Dependence and Independence in Social Choice: Arrow’s Theorem, in S. Abramsky, J. Kontinen, H. Vollmer and J. Väänänen, eds, Dependence Logic: Theory and Applications, Progress in Computer Science and Applied Logic, Birkhauser, June 2016, pp 235-260

• G. Ciná and U. Endriss. Proving classical theorems of social choice theory in modal logic. Autonomous Agents and Multi-Agent Systems, 30(5):963–989, 2016.

• S. Abramsky. Arrow’s theorem by arrow theory. In Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics, pp. 15–30. De Gruyter, 2015.

• U. Grandi and U. Endriss. First-order logic formalisation of impossibility theorems in preference aggregation. Journal of Philosophical Logic, 42(4):595–618, 2013.

• U. Endriss. Logic and social choice theory. In A. Gupta and J. van Benthem, editors, Logic and Philosophy Today, pages 333–377. College Publications, London, 2011.

• N. Troquard, W. van der Hoek, and M. Wooldridge. Reasoning about social choice functions. Journal of Philosophical Logic, 40(4):473–498, 2011.

• P. Tang, F. Lin, Computer-aided proofs of Arrow’s and other impossibility theorems. Artificial Intelligence 173(11), 1041–1053 (2009)

• T. Nipkow. Social choice theory in HOL. Journal of Automated Reasoning, 43(3):289–304, 2009.

• F. Wiedijk. Arrow’s impossibility theorem. Formalized Mathematics, 15(4):171–174, 2007.

• T. Ågotnes, W. van der Hoek, M. Wooldridge, Reasoning about judgment and preference aggregation. In: Proc. 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007), IFAAMAS (2007)

Logical methods and applications of DIL in quantum theory:

• K. Kishida. Logic of Local Inference for Contextuality in Quantum Physics and Beyond. In Proceedings of ICALP 2016, LIPIcs 55, pp. 113:1–113:14. 2016.

• T. Hyttinen, G. Paolini and J. Väänänen, A logic for arguing about probabilities in measure teams, Archiv for mathematical logic, August 2017, Vol 56, Issue 5-6, pp 475-489

• T. Hyttinen, G. Paolini and J. Väänänen, Quantum team logic and Bell's inequalities, Review of Symbolic Logic, Volume 81(1), 32 - 55, 2016

• S. Abramsky. Relational hidden variables and non-locality. Studia Logica, 101(2):411–452, 2013.

• S. Abramsky. Relational databases and Bell’s theorem. In Search of Elegance in the Theory and Practice of Computation, LNCS 8000, pp.13–35. Springer, 2013.

• S. Abramsky and L. Hardy. Logical Bell inequalities. Physical Review A, 85:1–11, 2012.