Dependence Logic - A New Approach to Independence Friendly Logic
This book develops and studies a conservative extension of first order logic called dependency logic, which approaches the study of the phenomena of dependency and independency on a logical basis. Dependency logic introduces a new type of atomic formula, written as = (t1,t2,...,tn), with an intuitive meaning that the value of the term tn depends only on the values of the terms t1,t2,... tn-1. Given proper semantics, the basic language of dependency logic is more expressive than that of first order logic. This is demonstrated on several examples (chapter 4), e.g. by giving a formula with no extralogical symbols whose models are all finite sets with no infinite set. This expressiveness, of course, cannot endure without a cost, which in the case of this logic is the dropping of the law of the excluded middle.
The author acknowledges his inspiration as the Independence Friendly Logic of Hintikka and Sandu, whose basic instrument for expressing (in)dependency is instead the quantifier “there exists xn independently of x1,x2,... xn-1”. While these two logics turn out to have the same expressiveness at the level of sentences, the author argues that dependency logic is actually the more expressive of the two at the level of formulae (section 3.6). Model theory for dependency logic is developed by relating the logic to existential second order logic (chapter 6). A brief yet informative chapter 7 deals with the complexity of the decision problem for dependency logic. The last chapter studies a further extension of dependency logic called team logic, which besides the non-classical negation of dependency logic also contains Boolean negation obeying the law of the excluded middle.
The book is based on real teaching experience and it contains many instructive exercises (for which many of the solutions are given in an appendix by Ville Nurmi). In several places, the reader is given the chance to acquire basic skills in a game-theoretic approach to logic and model theory. The book is probably best suited to advanced students of special courses but it remains accessible to all students with a basic knowledge of logic.