|
Interpretability Logic
Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability, tolerance, cotolerance, and arithmetic complexities. Main contributors to the field are Alessandro Berarducci, Petr Hájek, Konstantin Ignatiev, Giorgi Japaridze, Franco Montagna, Vladimir Shavrukov, Rineke Verbrugge, Albert Visser, and Domenico Zambella. Examples Logic ILM The language of ILM extends that of classical propositional logic by adding the unary modal operator \Box and the binary modal operator \triangleright (as always, \Diamond p is defined as \neg \Box\neg p). The arithmetical interpretation of \Box p is “p is provable in Peano arithmetic (PA)”, and p \triangleright q is understood as “PA+q is interpretable in PA+p”. Axiom schemata: 1. All classical tautologies 2. \Box(p \rightarrow q) \rightarrow ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modal Logic
Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend other systems by adding unary operators \Diamond and \Box, representing possibility and necessity respectively. For instance the modal formula \Diamond P can be read as "possibly P" while \Box P can be read as "necessarily P". Modal logics can be used to represent different phenomena depending on what kind of necessity and possibility is under consideration. When \Box is used to represent epistemic necessity, \Box P states that P is epistemically necessary, or in other words that it is known. When \Box is used to represent deontic necessity, \Box P states that P is a moral or legal obligation. In the standard relational semantics for modal logic, formulas are assigned truth values relative to a ''possible world''. A formula's truth value at ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Provability Logic
Provability logic is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich formal theory, such as Peano arithmetic. Examples There are a number of provability logics, some of which are covered in the literature mentioned in . The basic system is generally referred to as GL (for Gödel– Löb) or L or K4W (W stands for well-foundedness). It can be obtained by adding the modal version of Löb's theorem to the logic K (or K4). Namely, the axioms of GL are all tautologies of classical propositional logic plus all formulas of one of the following forms: * Distribution axiom: * Löb's axiom: And the rules of inference are: * ''Modus ponens'': From ''p'' → ''q'' and ''p'' conclude ''q''; * Necessitation: From \vdash ''p'' conclude \vdash . History The GL model was pioneered by Robert M. Solovay in 1976. Since then, until his death in 1996, the prime inspirer ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interpretability
In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other. Informal definition Assume ''T'' and ''S'' are formal theories. Slightly simplified, ''T'' is said to be ''interpretable'' in ''S'' if and only if the language of ''T'' can be translated into the language of ''S'' in such a way that ''S'' proves the translation of every theorem of ''T''. Of course, there are some natural conditions on admissible translations here, such as the necessity for a translation to preserve the logical structure of formulas. This concept, together with weak interpretability, was introduced by Alfred Tarski in 1953. Three other related concepts are cointerpretability, logical tolerance, and cotolerance, introduced by Giorgi Japaridze in 1992–93. See also * Interpretation (logic) * Interpretation (model theory) * Interpretability logic References * Japaridze, G., and De Jongh, D. (1998) "The logic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Weak Interpretability
In mathematical logic, weak interpretability is a notion of translation of logical theories, introduced together with interpretability by Alfred Tarski in 1953. Let ''T'' and ''S'' be formal theories. Slightly simplified, ''T'' is said to be weakly interpretable in ''S'' if, and only if, the language of ''T'' can be translated into the language of ''S'' in such a way that the translation of every theorem of ''T'' is consistent with ''S''. Of course, there are some natural conditions on admissible translations here, such as the necessity for a translation to preserve the logical structure of formulas. A generalization of weak interpretability, tolerance, was introduced by Giorgi Japaridze Giorgi Japaridze (also spelled Giorgie Dzhaparidze) is a Georgian-American researcher in logic and theoretical computer science. He currently holds the title of Full Professor at the Computing Sciences Department of Villanova University. Japaridze i ... in 1992. See also * Interpretability logic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cointerpretability
In mathematical logic, cointerpretability is a binary relation on formal theories: a formal theory ''T'' is cointerpretable in another such theory ''S'', when the language of ''S'' can be translated into the language of ''T'' in such a way that ''S'' proves every formula whose translation is a theorem of ''T''. The "translation" here is required to preserve the logical structure of formulas. This concept, in a sense dual to interpretability In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other. Informal definition Assume ''T'' and ''S'' are formal theories. Slightly simplified, '' ..., was introduced by , who also proved that, for theories of Peano arithmetic and any stronger theories with effective axiomatizations, cointerpretability is equivalent to \Sigma_1-conservativity. See also * Cotolerance * Interpretability logic. * Tolerance (in logic) References *. *. Math ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tolerance (in Logic)
In mathematical logic, a tolerant sequence is a sequence :T_1,...,T_n of formal theories such that there are consistent extensions :S_1,...,S_n of these theories with each S_{i+1} interpretable in S_i. Tolerance naturally generalizes from sequences of theories to trees of theories. Weak interpretability can be shown to be a special, binary case of tolerance. This concept, together with its dual concept of cotolerance, was introduced by Japaridze in 1992, who also proved that, for Peano arithmetic and any stronger theories with effective axiomatizations, tolerance is equivalent to \Pi_1-consistency. See also *Interpretability *Cointerpretability * Interpretability logic References G. Japaridze ''The logic of linear tolerance''. Studia Logica ''Studia Logica'' (full name: Studia Logica, An International Journal for Symbolic Logic), is a scienific journal publishing papers employing formal tools from Mathematics and Logic. The scope of papers published in Studia Lo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Petr Hájek
Petr Hájek (; 6 February 1940 – 26 December 2016) was a Czech scientist in the area of mathematical logic and a professor of mathematics. Born in Prague, he worked at the Institute of Computer Science at the Academy of Sciences of the Czech Republic and as a lecturer at the Faculty of Mathematics and Physics at the Charles University in Prague and at the Faculty of Nuclear Sciences and Physical Engineering of the Czech Technical University in Prague. Academics Petr Hájek studied at the Faculty of Mathematics and Physics of the Charles University in Prague. Influenced by Petr Vopěnka, he specialized in set theory and arithmetic, and later also in logic and artificial intelligence. He contributed to establishing the mathematical fundamentals of fuzzy logic. Following the Velvet Revolution, he was appointed a senior lecturer (1993) and a professor (1997). From 1992 to 2000 he held the position of chairman of the Institute of Computer Science at the Academy of Sciences of the Czec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Giorgi Japaridze
Giorgi Japaridze (also spelled Giorgie Dzhaparidze) is a Georgian-American researcher in logic and theoretical computer science. He currently holds the title of Full Professor at the Computing Sciences Department of Villanova University. Japaridze is best known for his invention of computability logic, cirquent calculus, and Japaridze's polymodal logic. Research During 1985–1988 Japaridze elaborated the system GLP, known as Japaridze's polymodal logic. This is a system of modal logic with the "necessity" operators …, understood as a natural series of incrementally weak provability predicates for Peano arithmetic. In "The polymodal logic of provability" Japaridze proved the arithmetical completeness of this system, as well as its inherent incompleteness with respect to Kripke frames. GLP has been extensively studied by various authors during the subsequent three decades, especially after Lev Beklemishev, in 2004, pointed out its usefulness in understanding the proof theory of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rineke Verbrugge
Laurina Christina (Rineke) Verbrugge (born 12 March 1965 in Amsterdam) is a Dutch logician and computer scientist known for her work on interpretability logic and provability logic. She completed her PhD at the University of Amsterdam in 1993 under the supervision of Dick de Jongh, Anne Troelstra, and Albert Visser. She holds the chair of Logic and Cognition at the University of Groningen's Bernoulli Institute of Mathematics, Computer Science and Artificial Intelligence, where she has been the leader of the Multi-Agent Systems working group since 2002. She is particularly known for her work connecting formal logic to cognition and developmental psychology and the role of logic in explaining social behaviour. From 2005 to 2021, she was the President (''voorzitter'') of the ''Nederlandse Vereniging voor Logica & Wijsbegeerte der Exacte Wetenschappen'' (VvL; Dutch Association for Logic and Philosophy of the Exact Sciences). In 2021, she was elected a fellow of the Royal Neth ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Peano Arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete. The need to formalize arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and induction. In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic. In 1888, Richard Dedekind proposed another axiomatization of natural-number arithmetic, and in 1889, Peano published a simplified version of them as a collection of axioms in his book, ''The principles of arithmetic presented by a new method'' ( la, Arithmetice ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tolerant Sequence
In mathematical logic, a tolerant sequence is a sequence :T_1,...,T_n of theory (mathematical logic), formal theories such that there are theory (mathematical logic)#Consistency and completeness, consistent theory (mathematical logic)#Subtheories and extensions, extensions :S_1,...,S_n of these theories with each S_{i+1} interpretability, interpretable in S_i. Tolerance naturally generalizes from sequences of theories to trees of theories. Weak interpretability can be shown to be a special, binary case of tolerance. This concept, together with its dual concept of cotolerance, was introduced by Giorgi Japaridze, Japaridze in 1992, who also proved that, for Peano arithmetic and any stronger theories with effective axiomatizations, tolerance is equivalent to \Pi_1-consistency. See also *Interpretability *Cointerpretability *Interpretability logic References G. Japaridze ''The logic of linear tolerance''. Studia Logica 51 (1992), pp. 249–277. G. Japaridze ''A general ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
