Dependence logic: a new approach to independence friendly logic

Vaananen J.0511286856, 0511285396, 0521700159, 0521876591, 9780521876599, 9780521700153

Dependence is a common phenomenon wherever one looks: ecological systems, astronomy, human history, stock markets -but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first-order logic. Here the syntax and semantics of dependence logic are studied, dependence logic is given an alternative game-theoretic semantics, and sharp results about its complexity are proven. This is a textbook suitable for a special course in logic in mathematics, philosophy, and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers with a basic knowledge of logic, interested in new phenomena in logic.

---

Table of contents :
Half-title……Page 3
Series-title……Page 5
Title……Page 7
Copyright……Page 8
Contents……Page 9
Preface……Page 11
1 Introduction……Page 13
Historical remarks……Page 16
2.2 Vocabularies and structures……Page 17
2.3 Terms and formulas……Page 18
2.4 Truth and satisfaction……Page 19
3 Dependence logic……Page 22
3.1 Examples and a mathematical model for teams……Page 23
3.2 Formulas as types of teams……Page 28
3.3 Logical equivalence and duality……Page 41
3.4 First order formulas……Page 49
3.5 The flattening technique……Page 54
3.6 Dependence/independence friendly logic……Page 56
4.1 Even cardinality……Page 60
4.2 Cardinality……Page 63
4.3 Completeness……Page 65
4.4 Well-foundedness……Page 67
4.5 Connectedness……Page 68
4.6 Natural numbers……Page 69
4.7 Real numbers……Page 71
4.8 Set theory……Page 72
5.1 Semantic game of first order logic……Page 75
5.2 Perfect information game for dependence logic……Page 81
5.3 Imperfect information game for dependence logic……Page 92
6.1 From to D to………Page 98
6.2 Applications of………Page 102
6.3 From………Page 106
6.4 Truth definitions……Page 112
6.4.1 Undefinability of truth……Page 113
6.4.2 Definability of truth in first order logic……Page 115
6.4.3 Definability of truth in D……Page 119
6.5.1 First order case……Page 122
6.5.2 Model existence game for Skolem Normal Form……Page 129
6.6 Ehrenfeucht–Fraisse game for dependence logic……Page 133
7.1 Decision and other problems……Page 146
7.2 Some set theory……Page 147
7.3 …2-completeness in set theory……Page 152
8.1 Preorder of determination……Page 156
8.2 Dependence and independence……Page 160
8.3 Formulas of team logic……Page 162
8.4 From team logic to L2……Page 170
8.5 From L2 to team logic……Page 173
8.6 Ehrenfeucht–Fraisse game for team logic……Page 175
Exercise 2.7……Page 181
Exercise 3.3……Page 182
Exercise 3.7……Page 183
Exercise 3.11……Page 184
Exercise 3.13……Page 185
Exercise 3.17……Page 186
Exercise 3.21……Page 187
Exercise 3.23……Page 188
Exercise 3.24……Page 189
Exercise 3.28……Page 190
Exercise 3.29……Page 191
Exercise 3.31……Page 193
Exercise 3.40……Page 194
Exercise 3.41……Page 195
Exercise 3.45……Page 196
Exercise 3.48……Page 197
Exercise 4.15……Page 199
Exercise 6.1……Page 201
Exercise 6.6……Page 202
Exercise 6.14……Page 203
Exercise 6.19……Page 204
Exercise 6.22……Page 205
Exercise 6.27……Page 206
Exercise 6.33……Page 207
Exercise 6.39……Page 208
Exercise 6.40……Page 210
Exercise 6.42……Page 211
Exercise 6.45……Page 212
Exercise 6.54……Page 215
Exercise 6.60……Page 216
Exercise 6.71……Page 217
Exercise 7.2……Page 218
Exercise 7.3……Page 219
Exercise 7.4……Page 220
Exercise 7.5……Page 222
Exercise 7.6……Page 223
Exercise 8.3……Page 225
Exercise 8.6……Page 226
Exercise 8.7……Page 227
Exercise 8.9……Page 228
Exercise 8.11……Page 229
Exercise 8.15……Page 230
References……Page 232
Index……Page 235