|
Relative Interpretation
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 Theory (mathematical logic), 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 Well-formed formula, formulas. This concept, together with weak interpretability, was introduced by Alfred Tarski in 1953. Three other related concepts are cointerpretability, tolerance (in logic), logical tolerance, and cotolerance, introduced by Giorgi Japaridze in 1992–93. See also * Conservative extension * Interpretation (logic) * Interpretation (model ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematical Logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics. Since its inception, mathematical logic has both contributed to and been motivated by the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and Mathematical analysis, analysis. In the early 20th century it was shaped by David Hilbert's Hilbert's program, program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Andrzej Mostowski
Andrzej Mostowski (1 November 1913 – 22 August 1975) was a Polish mathematician. He worked primarily in logic and foundations of mathematics and is perhaps best remembered for the Mostowski collapse lemma. He was a member of the Polish Academy of Sciences and a representative of the Warsaw School of Mathematics. Biography Born in Lemberg, Austria-Hungary, Mostowski entered University of Warsaw in 1931. He was influenced by Kuratowski, Lindenbaum, and Tarski. His Ph.D. came in 1939, officially directed by Kuratowski but in practice directed by Tarski who was a young lecturer at that time. He became an accountant after the German invasion of Poland but continued working in the Underground Warsaw University. After the Warsaw uprising of 1944, the Nazis tried to put him in a concentration camp. With the help of some Polish nurses, he escaped to a hospital, choosing to take bread with him rather than his notebook containing his research. Some of this research he reconstruct ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interpretation (model Theory)
In model theory, interpretation of a structure ''M'' in another structure ''N'' (typically of a different signature) is a technical notion that approximates the idea of representing ''M'' inside ''N''. For example, every reduct or definitional expansion of a structure ''N'' has an interpretation in ''N''. Many model-theoretic properties are preserved under interpretability. For example, if the theory of ''N'' is stable and ''M'' is interpretable in ''N'', then the theory of ''M'' is also stable. Note that in other areas of mathematical logic, the term "interpretation" may refer to a structure, rather than being used in the sense defined here. These two notions of "interpretation" are related but nevertheless distinct. Similarly, "interpretability" may refer to a related but distinct notion about representation and provability of sentences between theories. Definition An interpretation of a structure ''M'' in a structure ''N'' with parameters (or without parameters, respectiv ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation. The general study of interpretations of formal languages is called formal semantics. The most commonly studied formal logics are propositional logic, predicate logic and their modal analogs, and for these there are standard ways of presenting an interpretation. In these contexts an interpretation is a function that provides the extension of symbols and strings of an object language. For example, an interpretation function could take the predicate symbol T and assign it the extension \. All our interpretation does is assign the extension \ to the non-logical symbol T, and does not make a claim about whether T is to stand for tall and \mathrm for Abraham Lincoln. On the other hand, an interpretation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conservative Extension
In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a supertheory which is not conservative, and can prove more theorems than the original. More formally stated, a theory T_2 is a ( proof theoretic) conservative extension of a theory T_1 if every theorem of T_1 is a theorem of T_2, and any theorem of T_2 in the language of T_1 is already a theorem of T_1. More generally, if \Gamma is a set of formulas in the common language of T_1 and T_2, then T_2 is \Gamma-conservative over T_1 if every formula from \Gamma provable in T_2 is also provable in T_1. Note that a conservative extension of a consistent theory is consistent. If it were not, then by the principle of explosion, every formula in the language of T_2 would be a theorem of T_2, so every formula in the language of T_1 would be a theorem of T ... [...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 ... [...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 scientific journal publishing papers employing formal tools from Mathematics and Logic. The scope of papers published in Studi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theory (mathematical Logic)
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduction rules. An element \phi\in T of a deductively closed theory T is then called a theorem of the theory. In many deductive systems there is usually a subset \Sigma \subseteq T that is called "the set of axioms" of the theory T, in which case the deductive system is also called an " axiomatic system". By definition, every axiom is automatically a theorem. A first-order theory is a set of first-order sentences (theorems) recursively obtained by the inference rules of the system applied to the set of axioms. General theories (as expressed in formal language) When defining theories for foundational purposes, additional care must be taken, as normal set-theoretic language may not be appropriate. The construction of a theory begins ... [...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, was introduced by , who also proved that, for theories of Peano arithmetic and any stronger theories with effective axiomatization In mathematics and logic, an axiomatic system is a set of formal statements (i.e. axioms) used to logically derive other statements such as lemmas or theorems. A proof within an axiom system is a sequence of deductive steps that establishes ...s, cointerpretability is equivalent to \Sigma_1-conservativity. See also * Cotolerance * Interpretability logic * Tolerance (in logic) References *. *. Mathema ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alfred Tarski
Alfred Tarski (; ; born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician and mathematician. A prolific author best known for his work on model theory, metamathematics, and algebraic logic, he also contributed to abstract algebra, topology, geometry, measure theory, mathematical logic, set theory, type theory, and analytic philosophy. Educated in Poland at the University of Warsaw, and a member of the Lwów–Warsaw school, Lwów–Warsaw school of logic and the Warsaw school of mathematics, he immigrated to the United States in 1939 where he became a naturalized citizen in 1945. Tarski taught and carried out research in mathematics at the University of California, Berkeley, from 1942 until his death in 1983.#FefA, Feferman A. His biographers Anita Burdman Feferman and Solomon Feferman state that, "Along with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
