Time: 2019 September 27, 13:30-16:00
Venue: 蒙民伟科技大楼南楼S527, Tsinghua Univ.
Speaker: Johan van Benthem (Stanford University)
Dependence is a notion that pervades both ordinary and scientific discourse. We present a decidable base logic of functional dependence whose semantics uses generalized assignment models for first-order logic. This seminar is a survey and crash course in the topic.
We determine the structural properties of dependence, in analogy with those of abstract consequence relations, and show how they fit with introducing explicit functional definitions. Next, we discuss the philosophical significance of this semantics, and then, using analogies with modal logic, we go on to show completeness, decidability and other keyproperties of the core logic of dependence. For perspective, we also indicate extensions in expressive power: e.g., the core logic of independence turns out to be undecidable, while natural dynamic extensions straddle the borderline with undecidability. All these notions and results turn out to extend naturally to a topological setting where a major intuition of dependence is correlated approximability.
Finally, we sketch how our logical perspective can also incorporate richer notions of dependence found in data bases, vector spaces, and strategic behavior in games. If time permits, we will also make a few comparisons with already existing systems of dependence logic.