Mathematical Problems from Applied Logic I: Logics for the XXIst Century

Content......Page 19
Nonstandard Inferences in Description Logics: The Story So Far......Page 25
1. Introduction......Page 26
2. Description Logics and Standard Inferences......Page 30
3. Nonstandard Inferences—Motivation and Definitions......Page 35
3.1. Motivation......Page 36
3.2. Definitions......Page 39
3.3. Techniques......Page 45
4. A Structural Characterization of Subsumption......Page 47
4.1. Getting started — The characterization for EL......Page 48
4.2. Extending the characterization to ALE......Page 51
4.3. Characterization of subsumption for other DLs......Page 55
5.1. The LCS for EL......Page 56
5.2. The LCS for ALE......Page 58
6.1. Existence and approximation of the MSC......Page 60
7. Rewriting......Page 68
7.1. The minimal rewriting decision problem......Page 69
7.2. The minimal rewriting computation problem......Page 70
7.3. Approximation......Page 76
8. Matching......Page 77
8.1. Deciding matching problems......Page 78
8.2. Solutions of matching problems......Page 79
8.3. Computing matchers......Page 82
9. Conclusion and Future Perspectives......Page 88
10. References......Page 90
 Problems in the Logic of Provability......Page 100
1. Introduction......Page 101
2.1. Formal and informal provability and the problem of equivalence of proofs......Page 104
2.2. Strengthening Hilbert's thesis......Page 108
2.3. Coordinate-free proof theory......Page 110
3. Basics of Provability Logic......Page 114
4. Provability Logic for Intuitionistic Arithmetic......Page 116
4.1. Propositional logics of arithmetical theories......Page 117
4.2. Admissible rules......Page 120
4.3. The provability logic of HA and related theories......Page 123
5. Provability Logic and Bounded Arithmetic......Page 125
6. Classification of Bimodal Provability Logics......Page 129
7. Magari Algebras......Page 132
8. Interpretability Logic......Page 137
9. Graded Provability Algebras......Page 143
10. List of Problems......Page 148
References......Page 152
1. Logical Dynamics......Page 160
2. Standard Epistemic Logic......Page 162
2.1. Language......Page 163
2.2. Semantics......Page 164
2.3. Basic model theory......Page 165
2.5. Complexity......Page 166
3. Public Announcement: Epistemic Logic Dynamified......Page 167
3.1. World elimination: the system PAL......Page 168
3.2. What are the real update laws?......Page 173
3.3. Model theory of learning......Page 176
3.4. Communication and planning......Page 178
3.5. Group knowledge......Page 179
4. Dynamic Epistemic Logic......Page 180
4.1. Information from arbitrary events: product update......Page 181
4.2. Update evolution......Page 183
4.3. Questions of language design......Page 185
4.4. Extensions of empirical coverage......Page 186
5. Background in Standard Logics......Page 187
5.1. Modal logic......Page 188
5.2. First-order logic......Page 189
5.3. Fixed-point logics......Page 191
6.1. From knowledge to belief......Page 193
6.2. Dynamic doxastic logic......Page 194
6.3. Better-known theories of belief revision......Page 198
6.4. Probabilistic update......Page 200
7.1. Broader temporal perspectives on update......Page 201
7.2. Knowledge and ignorance over time......Page 202
7.3. Representation of update logics......Page 204
7.4. Connections with other parts of mathematics......Page 206
8. Game Logics and Game Theory......Page 207
9. Conclusion......Page 208
References......Page 209
Computability and Emergence......Page 216
1. An Emergent World around Us......Page 217
2. Descriptions, Algorithms, and the Breakdown of Inductive Structure......Page 218
3. Ontology and Mathematical Structure......Page 225
4. Where does It All Start?......Page 227
5. Towards a Model Based on Algorithmic Content......Page 232
6. Levels of Reality......Page 237
7. Algorithmic Content Revisited......Page 244
8. What Is to Be Done?......Page 247
References......Page 251
 Samsara......Page 255
1.1. The structure of the paper......Page 256
2. An Example of a Process......Page 257
3. What Logics Do We Need?......Page 258
3.1. Extracting constructions from proofs......Page 264
3.2. The Lambda Calculus and the Curry–Howard correspondence......Page 265
3.3. Proofs as types......Page 267
3.4. Strong normalization and program extraction......Page 270
3.5. Beyond traditional logic in program extraction......Page 272
3.6. Proofs from programs......Page 278
3.7. Programs then proofs......Page 279
4. What are Logical Systems and What Should They Be?......Page 280
4.1. Higher order logic......Page 281
4.2. A note on set theory......Page 283
5. The Nature of Proof......Page 284
5.1. The question of scale and the role of technology......Page 285
5.2. Foundations......Page 290
6. Final Remarks......Page 291
References......Page 292
 Two Doors to Open......Page 299
1. Logic and Cognitive Science......Page 301
1.1. Spatial intuition......Page 303
1.2. Kurt Gödel and the choice of representation......Page 307
1.3. A sample cognitive description of reasoning......Page 315
1.4. Frege versus Peirce: comparison of representations......Page 320
2. Medieval Arabic Semantics......Page 322
References......Page 335
1. What is Applied Logic?......Page 339
2. Mathematics and Logic, but Different from Mathematical Logic......Page 341
2.1. Mathematical Logic and Mathematics......Page 342
2.2. Where applied logic differs......Page 344
2.3. Applied mathematics is good mathematics......Page 346
2.4. Applied logic is applied mathematics......Page 347
3. Applied Philosophical Logic......Page 348
4. What Does Computer Science Have to Do with It?......Page 350
4.1. Logic is the calculus of computer science......Page 351
4.2. Computer science motivates logic......Page 352
4.3. Going beyond the traditional boundaries of logic......Page 353
5.1. Neural networks and non-monotonic logic......Page 354
5.2. Dynamic epistemic logic......Page 355
5.3. Linguistics, logic, and mathematics......Page 357
5.4. But is it dead?......Page 362
6. Being as catholic as Possible......Page 363
References......Page 365
C......Page 366
K......Page 367
O......Page 368
Z......Page 369