Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic (Outstanding Contributions to Logic, 19)

✍ Scribed by Judit Madarász (editor), Gergely Székely (editor)

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 513
• Category: Library

✦ Synopsis

This book features more than 20 papers that celebrate the work of Hajnal Andréka and István Németi. It illustrates an interaction between developing and applying mathematical logic. The papers offer new results as well as surveys in areas influenced by these two outstanding researchers. They also provide details on the after-life of some of their initiatives.

Computer science connects the papers in the first part of the book. The second part concentrates on algebraic logic. It features a range of papers that hint at the intricate many-way connections between logic, algebra, and geometry. The third part explores novel applications of logic in relativity theory, philosophy of logic, philosophy of physics and spacetime, and methodology of science. They include such exciting subjects as time travelling in emergent spacetime.

The short autobiographies of Hajnal Andréka and István Németi at the end of the book describe an adventurous journey from electric engineeringand Maxwell’s equations to a complex system of computer programs for designing Hungary’s electric power system, to exploring and contributing deep results to Tarskian algebraic logic as the deepest core theory of such questions, then on to applications of the results in such exciting new areas as relativity theory in order to rejuvenate logic itself.

✦ Table of Contents

Preface
Contents
Contributors
Part I Computing
1 Algebraic Logic and Knowledge Bases
1.1 Introduction
1.2 Preliminaries
1.2.1 Basic Notions and Notations
1.2.2 Halmos Categories and Halmos Algebras
1.2.3 The Galois Correspondence
1.3 Knowledge Base Model
1.3.1 What Is Knowledge?
1.3.2 Category of Knowledge Description FΘ(calH)
1.3.3 Category of Knowledge Content DΘ(calH)
1.3.4 The Knowledge Functor CtcalH
1.3.5 Definition of a Knowledge Base
1.4 Knowledge Bases Equivalences
1.4.1 Informationally Equivalent Knowledge Bases
1.4.2 LG-equivalent and LG-isotypic Knowledge Bases
1.4.3 LG-Equivalence and Informational Equivalence of Knowledge Bases
References
2 Guarded Ontology-Mediated Queries
2.1 Introduction
2.1.1 Rule-Based Ontology-Mediated Queries
2.1.2 Guardedness to the Rescue
2.2 Preliminaries
2.3 Query Evaluation
2.3.1 From Eval(G,CQ) to Satisfiability for the Guarded Fragment
2.4 Query Containment
2.4.1 Atomic Queries
2.4.2 From Conjunctive Queries to Atomic Queries
2.5 First-Order Rewritability
2.5.1 Atomic Queries
2.5.2 From Conjunctive Queries to Atomic Queries
2.6 Reasoning over Finite Instances
2.7 Conclusions
References
3 Semiring Provenance for Guarded Logics
3.1 Introduction
3.2 Modal Logic and the Guarded Fragment
3.3 Semiring Provenance for First-Order Logic and Acyclic Games
3.3.1 Commutative Semirings
3.3.2 Provenance for First-Order Logic
3.3.3 Provenance Analysis for Acyclic Games
3.3.4 Provenance Analysis via Model-Checking Games
3.4 Provenance Analysis for Modal Logic and the Guarded Fragment
3.5 Algorithmic Analysis
3.6 A More Abstract View of Guarded Logics
3.7 Guarded Negation First-Order Logic
3.7.1 Provenance Analysis for GNF
3.7.2 Model Checking Games for GNF* and Their Provenance Analysis
3.7.3 Algorithmic Analysis
References
4 Implicit Partiality of Signature Morphisms in Institution Theory
4.1 Introduction
4.1.1 Institution Theory
4.1.2 From Total to Partial Signature Morphisms in Institution Theory
4.1.3 Contributions and Structure of the Paper
4.2 Category-Theoretic and Other Preliminaries
4.2.1 Categories
4.2.2 Partial Functions
4.2.3 3/2-categories
4.2.4 Various Colimits in 3/2-categories
4.3 3/2-institutions
4.3.1 Institutions
4.3.2 3/2-institutions: Definition
4.3.3 3/2-institutions: Examples
4.3.4 3/2-institutional Seeds
4.3.5 Model Amalgamation in 3/2-institutions
4.3.6 Theory Morphisms in 3/2-institutions
4.3.7 Lifting Properties
4.4 Theory Blending in 3/2-institutions
4.4.1 Computational Creativity and Conceptual Blending
4.4.2 Theory Blending in 3/2-institutions
4.5 Theory Changes
4.5.1 The Problem of Merging Software Changes
4.5.2 Theory Changes
4.6 Conclusions
References
5 The Four Essential Aristotelian Syllogisms, via Substitution and Symmetry
5.1 Dedication
5.2 The Main Theorem
5.3 Aristotle
5.4 From Aristotle to the 19th Century
5.5 20th Century Treatments of the Aristotelian Syllogisms
5.6 The Aristotelian Syllogisms
5.6.1 Moods
5.6.2 Figures
5.7 Obversion and Conversion
5.8 Contraposition
5.9 Proof of Theorem 1
5.10 Conclusion
References
6 Adding Guarded Constructions to the Syllogistic
6.1 Introduction
6.2 Technical Preliminaries
6.3 Lower Complexity Bounds
6.4 Upper Complexity Bounds
6.5 Proof-Theoretic Consequences
References
7 The Significance of Relativistic Computation for the Philosophy of Mathematics
7.1 A Short Refresher on the RTM Model
7.2 RTM and Mathematical Knowledge
7.3 “RTM Proofs” and the Problem of Mathematical Explanation
7.4 The Theoretical Virtues of the RTM Model
7.5 Concluding Remarks
References
Part II Algebraic Logic
8 Generalized Quantifiers Meet Modal Neighborhood Semantics
8.1 Introduction: Quantifiers and Neighborhoods
8.2 Locality and Conservativity
8.2.1 Locality in Modal Semantics
8.2.2 Conservativity and Domain Restriction for Quantifiers
8.3 Invariance and Simulation
8.3.1 Modal Logic and Invariance
8.3.2 Invariance and Generalized Quantifiers
8.4 Modal Logics of Quantifiers
8.4.1 Modal Logic of Permutation-Invariant Quantifiers
8.4.2 Imposing More Conditions
8.4.3 Modal Logics of Specific Quantifiers
8.5 Conclusion
References
9 On the Semilattice of Modal Operators and Decompositions of the Discriminator
9.1 Introduction
9.2 Notation and First Definitions
9.2.1 Boolean Algebras
9.3 Modal Algebras
9.4 The Semilattice of Modal Operators
9.5 Decomposing Discriminators
9.6 Proper Companions
References
10 Modal Logics that Bound the Circumference of Transitive Frames
10.1 Algebraic Logic and Logical Algebra
10.2 Grzegorczyk and Löb
10.3 Clusters and Cycles
10.4 Models and Valid Schemes
10.5 Logics and Canonical Models
10.6 Finite Model Property for K4mathbbCn
10.7 Extensions of K4mathbbCn
10.7.1 Seriality
10.7.2 S4mathbbCn
10.7.3 Linearity
10.7.4 Simple Final Clusters
10.7.5 Degenerate Final Clusters
10.8 Models on Irresolvable Spaces
10.9 Generating Varieties of Algebras
References
11 Undecidability of Algebras of Binary Relations
11.1 Introduction
11.2 Definitions
11.3 Main Results
11.4 Some Earlier Results
11.5 Tiling
11.6 Partial Group Embedding
11.7 Extending the Results
References
12 On the Representation of Boolean Magmas and Boolean Semilattices
12.1 Introduction
12.2 Representable Boolean Magmas
12.3 Representable Boolean Semilattices
12.4 Constructions of Representable Boolean Magmas
12.5 Appendix: Known Representations for 8-Element Boolean Semilattices
References
13 Canonical Relativized Cylindric Set Algebras and Weak Associativity
13.1 Introduction
13.2 Definition of
13.3 Canonical Extensions
13.4 Algebras of Binary Relations
13.5 Characterizing WA
13.6 The Relativized Cylindric Set Algebra of a Suitable Structure
13.7 The Suitable Structure of a WA
13.8 The Complex Algebra of a Suitable Structure
13.9 Relation-Algebraic Reducts
13.10 Cylindric-Relativized Representation
13.11 Relativized Relational Representation
13.12 Elementary Laws of WA
References
14 Blow Up and Blur Constructions in Algebraic Logic
14.1 Introduction
14.2 The Algebras and Some Basic Concepts
14.3 Non-atom Canonicity of Infinitely Many Varieties Between CAn and RCAn
14.3.1 Clique Guarded Semantics
14.3.2 Blowing up and Blurring Finite Rainbow Cylindric Algebras
14.3.3 An Application on Omitting Types for the Clique Guarded Fragment of Ln
References
Part III Relativity Theory
15 Freeing Structural Realism from Model Theory
15.1 Introduction
15.2 Predicate Functors
15.3 Tractarian Geometry
15.4 Cylindric Algebras
15.5 Conclusion
References
16 In the Footsteps of Hilbert: The Andréka-Németi Group’s Logical Foundations of Theories in Physics
16.1 Introduction
16.2 Hilbert’s Axiomatic Approach to the Sciences
16.3 The Programme of the Andréka-Németi Group and Its Close Correspondence to Hilbert’s Dynamic Methodology
16.4 Conclusion: The Hilbert-Andréka-Németi View of the Unity of Science
References
17 General Relativity as a Collection of Collections of Models
17.1 Introduction
17.2 Preliminaries
17.3 Possibility
17.4 Inextendibility
17.5 Singularities
17.6 Conclusion
References
18 Why Not Categorical Equivalence?
18.1 Introduction
18.2 Categorically Equivalent Theories
18.3 Interlude: Concerns I Will Not Pursue
18.4 Category Structure and Ideology
18.5 The G' Property 18.6 Where Do We Go from Here? 18.7 Conclusion References 19 Time Travelling in Emergent Spacetime 19.1 Introduction 19.2 Global Hyperbolicity and Energy Conditions 19.2.1 At the Classical Level 19.3 Theories of Quantum Gravity 19.3.1 Semi-classical Quantum Gravity 19.3.2 Causal Set Theory 19.3.3 Loop Quantum Gravity 19.3.4 String Theory 19.4 Emergent Time Travel? 19.4.1 Causal Set Theory as a Cosmological Theory 19.4.2 Loop Quantum Gravity as a Cosmological Theory 19.4.3 Quantum Gravity asAstrophysics'
19.5 Conclusions
References
Appendix A From Computing to Relativity Theory Through Algebraic Logic: A Joint Scientific Autobiography
Large-Scale AI Program for the Hungarian Power System (c. 1966–1970)
Software Department, Theorem Prover, General Logic, Universal Algebra (c. 1970–1976)
Categorical Injectivity Logic, Partial Algebras (c. 1976–1983)
Nonstandard-Time Semantics for Dynamic Logic of Programs (c. 1978–1986)
Algebraic Logic, Tarski's School, Cylindric and Relation Algebras (1971– )
Logic Graduate School, the Amsterdam–Budapest–London Triangle (c. 1991–1998)
Relativity Theory, Relativistic Computing, Methodology of Science (c. 1998– )
Appendix B Joint Annotated Bibliography of Hajnal Andréka and István Németi
Books
Books Edited
Dissertations
Publications (Articles, Book Chapters, Other)