Speaker: Alexandru Baltag
Date and Time: Thursday, October 11th 2018, 16:30-18:00
To be rescheduled
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: The Logic of Correlations.
Abstract. I present a Logic of Correlations (LC), as an extension of the Epistemic Dependence Logic presented in my 2016 AiML paper, that essentially axiomatized a “feasible” version of Vaananen’s Dependence Logic. The semantics extends van Benthem’s Generalized-Assignment Semantics of First-Order Logic (on “dependency models”). While the usual semantics of FOL allows all possible assignments of variables to objects, a dependency model restricts the range of available assignments to a given subset. One can think of the available assignments as “possible worlds”, and the FOL quantifiers become Kripke modalities.
Dependency models were proposed as a model for capturing dependencies and correlations between variables: essentially, they are the same as the “teams” (sets of assignments) used in Hodges’ team semantics for Dependence Logic. This modal version of FOL is known to be decidable, but unfortunately it is so weak that it cannot actually express variable dependencies in an explicit manner (though the model still implicitly captures these dependencies). My Epistemic Dependence Logic proposed a remedy to this limitation, by adding an epistemic operator K_y x (x is knowable given y), that captures a ‘local’ version of the so-called dependence atoms from Dependence Logic: all assignments (available in the model) that agree with the current assignment on y also agree with it on x.
In this talk I generalize this further, by introducing accessibility relations R for informational “links” between assignments. A link is a finite relation between variables. Two assignments w and v are linked by the corresponding accessibility relation if for every pair (x,y) in the link we have w(x)=v(y). In other words, links capture commonality of objects between assignments: x denotes the same object in world w as the one denoted by y in world v. Correlations are dependencies between links, that express informational dependencies between them.
LC can be of use in Computer Science to reason about functional dependencies in a database, but also in Physics to encode natural laws capturing causal correlations between physical variables, etc..Unlike Dependence Logic, LC is decidable. Time-permitting, I will try to sketch the main ideas behind the decidability proof (based on an elaboration of the quasi-model method pioneered by van Benthem, and closely related to the mosaic method of Andreka and Nemeti).
.