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)

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 as `Astrophysics\'
	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)