Dependence logic and its proof-theoretic aspects

Fan Yang

Fan Yang (University of Helsinki)

Dependence logic was introduced by Väänänen (2007) as a novel formalism for expressing and reasoning about dependence and independence relations. The logic adopts the team semantics of Hodges (1997). The basic idea of team semantics is that dependency properties can only manifest themselves in multitudes, and thus formulas of dependence logic are evaluated on sets of assignments (called teams) instead of single assignment as in the usual Tarskian semantics. A team can be naturally viewed as a relational database, a dataset, an information state, etc. Thanks to the simple structure of teams and the abundance of their interpretations in various fields of science, team semantics and dependence logic have been investigated recently to address issues in database theory, linguistics, quantum foundations, social choice and so on.

Course’s webpage: https://sites.google.com/view/nls2022deplog

Course’s description. This 4-lecture course aims to provide a concise introduction to dependence logic and its proof-theoretic aspects. The first lecture introduces team semantics and first-order dependence logic. In the second lecture, we show that first-order dependence logic is equivalent to existential second-order logic. Thus, first-order dependence logic is not axiomatizable in full, but we will discuss the possibility of partially axiomatizing the logic. In the third lecture we study the complete proof systems for propositional logics of dependence. Building on these systems, in the last lecture we provide partial axiomatizations for first-order dependence logic.

Back to courses