This book presents contributions from world-renowned logicians, discussing important topics of logic from the point of view of their further development in light of requirements arising from successful application in Computer Science and AI language. Coverage includes: the logic of provability, computability theory applied to biology, psychology, physics, chemistry, economics, and other basic sciences; computability theory and computable models; logic and space-time geometry; hybrid systems; logic and region-based theory of space.
Author(s): Dov M. Gabbay, Sergei S. Goncharov, Michael Zakharyaschev (eds.)
Series: International Mathematical Series 05
Publisher: Springer
Year: 2007
Language: English
Pages: 377
Content of Volume II......Page 22
On Two Models of Provability......Page 27
1. Introduction......Page 28
2. Provability Logic......Page 33
2.1. Solovay's completeness theorem......Page 34
2.2. Fixed point theorem......Page 36
2.3. First-order provability logics......Page 37
2.5. Classification of provability logics......Page 38
2.6. Provability logics with additional operators......Page 40
2.8. Interpretability and conservativity logics......Page 41
2.10. 'True and Provable' modality......Page 44
2.11. Applications......Page 45
3. Logic of Proofs......Page 47
3.1. Arithmetical Completeness......Page 50
3.2. Realization Theorem......Page 52
3.3. Fitting models......Page 54
3.4. Joint logics of proofs and provability......Page 56
3.5. Quantified logics of proofs......Page 57
3.6. Intuitionistic logic of proofs......Page 58
3.7. The logic of single conclusion proofs......Page 59
3.8. Applications......Page 60
4. Acknowledgements......Page 64
References......Page 65
Directions for Computability Theory Beyond Pure Mathematical......Page 79
1. Motivations......Page 80
2. Directions......Page 82
3. Progress So Far And How One Might Go From Here......Page 83
3.1. Biology......Page 84
3.2. Machine inductive inference and computability-theoretic learning......Page 86
3.3. Machine self-reflection......Page 105
3.4. CT for computational complexity......Page 107
3.5. Physics and all the rest......Page 109
References......Page 111
Computability and Computable Models......Page 125
1. Preliminaries......Page 126
1.1. Algebraic structures, models, and theories......Page 127
1.2. Numberings......Page 137
1.3. Models and Computability......Page 140
1.4. Perspective directions in the theory of computable models......Page 158
2.1. Bounds for the theory of computable models......Page 159
3. Structure Complexity of Computable Models......Page 174
3.1. Definability of computable models......Page 175
3.3. Computable infinitary formulas......Page 176
3.4. Computable rank......Page 178
3.5. Rank and isomorphisms......Page 179
4.1. Isomorphisms of countably categorical models......Page 189
4.2. Isomorphisms of uncountably categorical models......Page 193
4.3. Computable categoricity......Page 195
4.4. Basic results in numbering theory......Page 197
4.5. Categories of graphs and partial orders......Page 204
4.6. Lift of basic results......Page 211
5. Classes of Computable Models and Index Sets......Page 212
5.1. Computable classification or structure theorem......Page 213
5.2. Special isomorphisms......Page 218
5.3. Definability and index sets of natural classes of computable models......Page 231
References......Page 232
First-Order Logic Foundation of Relativity Theories......Page 243
1. Introduction (Logic and Spacetime Geometry)......Page 244
2. More Concrete Introduction (Foundation of Spacetime)......Page 245
3. Intriguing Features of GR Spacetimes (Challenges for the Logician)......Page 247
4. A FOL Axiom System of SR Extended with Accelerated Observers......Page 251
5. One Step toward GR (Effect of Gravitation on Clocks)......Page 261
6. Questions, Suggestions for Future Research......Page 270
References......Page 274
Preface......Page 279
2. Continuous Plants and Controllers......Page 282
3. Hybrid Systems......Page 283
5. Continualization......Page 284
6.1. Summary......Page 286
6.2. Multiple models......Page 287
References......Page 289
Preface......Page 293
1. Historical Excursion in the Region-Based Theory of Space......Page 294
2.1. Contact algebras......Page 305
2.2. Extensions of contact algebras by adding new axioms......Page 309
2.3. Points in contact algebras and topological representation theorems. A simple case......Page 313
2.4. Another topological representation of contact algebras......Page 319
2.5. Models of contact algebras in proximity spaces......Page 322
2.6. Contact algebras with predicate of boundedness......Page 326
2.7. Algebras of regions based on non-Boolean lattices......Page 329
2.8. Precontact algebras and discrete spaces......Page 331
3. Region-Based Propositional Modal Logics of Space......Page 335
3.1. Syntax and semantics of RPMLS......Page 336
3.2. Modal definability and undefinability in Kripke semantics......Page 339
3.3. Axiomatizations and completeness theorems......Page 343
3.4. Filtration with respect to Kripke semantics and small canonical models......Page 348
3.5. Logics related to RCC......Page 352
3.6. Strong completeness theorems for RCC-like logics......Page 358
3.7. Extending the language with new primitives......Page 365
References......Page 369
E......Page 375
O......Page 376
T......Page 377
