Institutional model theory
Encyclopedia
Institutional model theory generalizes a large portion of first-order
model theory
to an arbitrary logical system.
. Institutions constitute a model-oriented meta-theory on logical systems similar to how the theory of ring
s and module
s constitute a meta-theory for classical linear algebra
. Another analogy can be made with universal algebra
versus group
s, ring
s, module
s etc. By abstracting away from the realities of the actual conventional logics, it can be noticed that institution theory comes in fact closer to the realities of non-conventional logics.
Institutional model theory analyzes and generalizes classical model-theoretic notions and results, like
For each concept and theorem, the infrastructure and properties required are analyzed and formulated as conditions on institutions, thus providing a detailed insight on which properties of first-order logic they rely and how much they can be generalized to other logics.
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
to an arbitrary logical system.
Overview
The notion of "logical system" here is formalized as an institutionInstitution (computer science)
The notion of institution has been created by Joseph Goguen and Rod Burstall in the late 1970sin order to deal with the "population explosion among the logical systems used incomputer science"...
. Institutions constitute a model-oriented meta-theory on logical systems similar to how the theory of ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
s and module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
s constitute a meta-theory for classical linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
. Another analogy can be made with universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
versus group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
s, ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
s, module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
s etc. By abstracting away from the realities of the actual conventional logics, it can be noticed that institution theory comes in fact closer to the realities of non-conventional logics.
Institutional model theory analyzes and generalizes classical model-theoretic notions and results, like
- Elementary diagrams
- Elementary embeddings
- UltraproductUltraproductThe ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...
s, Los' theorem - Saturated modelSaturated modelIn mathematical logic, and particularly in its subfield model theory, a saturated model M is one which realizes as many complete types as may be "reasonably expected" given its size...
s - axiomatizability
- VarietiesVariety (universal algebra)In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
, BirkhoffGarrett BirkhoffGarrett Birkhoff was an American mathematician. He is best known for his work in lattice theory.The mathematician George Birkhoff was his father....
axiomatizability - Craig interpolationCraig interpolationIn mathematical logic, Craig's interpolation theorem is a result about the relationship between different logical theories. Roughly stated, the theorem says that if a formula φ implies a formula ψ then there is a third formula ρ, called an interpolant, such that every nonlogical symbol...
- Robinson consistencyRobinson's joint consistency theoremRobinson's joint consistency theorem is an important theorem of mathematical logic. It is related to Craig interpolation and Beth definability.The classical formulation of Robinson's joint consistency theorem is as follows:...
- BethEvert Willem BethEvert Willem Beth was a Dutch philosopher and logician, whose work principally concerned the foundations of mathematics.- Biography :...
definability - GödelGodelGodel or similar can mean:*Kurt Gödel , an Austrian logician, mathematician and philosopher*Gödel...
's completeness theorem
For each concept and theorem, the infrastructure and properties required are analyzed and formulated as conditions on institutions, thus providing a detailed insight on which properties of first-order logic they rely and how much they can be generalized to other logics.
Further reading
- Razvan Diaconescu: Institution-Independent Model Theory. Birkhäuser, 2008. ISBN 978-3-7643-8707-5.
- Razvan Diaconescu: Jewels of Institution-Independent Model Theory. In: K. Futatsugi, J.-P- Jouannaud, J. Meseguer (eds.): Algebra, Meaning and Computation. Essays Dedicated to Joseph A. GoguenJoseph GoguenJoseph Amadee Goguen was a computer science professor in the Department of Computer Science and Engineering at the University of California, San Diego, USA, who helped develop the OBJ family of programming languages. He was author of A Categorical Manifesto and founder and Editor-in-Chief of the...
on the Occasion of His 65th Birthday. Lecture Notes in Computer Science 4060, p. 65-98, Springer-Verlag, 2006. - Marius Petria and Rãzvan Diaconescu: Abstract Beth definability in institutions. Journal of Symbolic Logic 71(3), p. 1002-1028, 2006.
- Daniel Gǎinǎ and Andrei Popescu: An institution-independent generalisation of Tarski's elementary chain theorem, Journal of Logic and Computation 16(6), p. 713-735, 2006.
- Till Mossakowski, Joseph GoguenJoseph GoguenJoseph Amadee Goguen was a computer science professor in the Department of Computer Science and Engineering at the University of California, San Diego, USA, who helped develop the OBJ family of programming languages. He was author of A Categorical Manifesto and founder and Editor-in-Chief of the...
, Rãzvan Diaconescu, Andrzej Tarlecki: What is a Logic?. In Jean-Yves Beziau, editor, Logica Universalis, pages 113-133. Birkhauser, 2005. - Andrzej Tarlecki: Quasi-varieties in abstract algebraic institutions. Journal of Computer and System Sciences 33(3), p. 333-360, 1986.
External links
- Razvan Diaconescu's publication list - contains recent work on institutional model theory