|
Completeness Of Atomic Initial Sequents
In sequent calculus, the completeness of atomic initial sequents states that initial sequents (where is an arbitrary formula) can be derived from only atomic initial sequents (where is an atomic formula). This theorem plays a role analogous to eta expansion in lambda calculus, and dual to cut-elimination and beta reduction. Typically it can be established by induction on the structure of , much more easily than cut-elimination. References * Gaisi Takeuti. ''Proof theory''. Volume 81 of ''Studies in Logic and the Foundation of Mathematics''. North-Holland, Amsterdam, 1975. * Anne Sjerp Troelstra and Helmut Schwichtenberg Helmut Schwichtenberg (born 5 April 1942 in Żagań) is a German mathematical logician. Schwichtenberg studied mathematics from 1961 at the FU Berlin and from 1964 at the University of Münster, where he received his doctorate in 1968 from D .... ''Basic Proof Theory''. Edition: 2, illustrated, revised. Published by Cambridge University Pres ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sequent Calculus
In mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. Each conditional tautology is inferred from other conditional tautologies on earlier lines in a formal argument according to rules and procedures of inference, giving a better approximation to the natural style of deduction used by mathematicians than to David Hilbert's earlier style of formal logic, in which every line was an unconditional tautology. More subtle distinctions may exist; for example, propositions may implicitly depend upon non-logical axioms. In that case, sequents signify conditional theorems in a first-order language rather than conditional tautologies. Sequent calculus is one of several extant styles of proof calculus for expressing line-by-line logical arguments. * Hilbert style. Every line is an unconditional tautology (or theorem). * Gentzen s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Atomic Formula
In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms are thus the simplest well-formed formulas of the logic. Compound formulas are formed by combining the atomic formulas using the logical connectives. The precise form of atomic formulas depends on the logic under consideration; for propositional logic, for example, a propositional variable is often more briefly referred to as an "atomic formula", but, more precisely, a propositional variable is not an atomic formula but a formal expression that denotes an atomic formula. For predicate logic, the atoms are predicate symbols together with their arguments, each argument being a term. In model theory, atomic formulas are merely strings of symbols with a given signature, which may or may not be satisfiable with respect to a given mo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Eta Expansion
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing § lambda terms and performing § reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules: * x – variable, a character or string representing a parameter or mathematical/logical value. * (\lambda x.M) – abstraction, function definition (M is a lambda term). The variable x becomes bound in the expression. * (M\ N) – application, applying a function M to an argument N. M and N are lambda terms. The reduction operations include: * (\lambda x.M \rightarro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing § lambda terms and performing § reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules: * x – variable, a character or string representing a parameter or mathematical/logical value. * (\lambda x.M) – abstraction, function definition (M is a lambda term). The variable x becomes bound in the expression. * (M\ N) – application, applying a function M to an argument N. M and N are lambda terms. The reduction operations include: * (\lambda x.M \rightarrow(\l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cut-elimination
The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for the systems LJ and LK formalising intuitionistic and classical logic respectively. The cut-elimination theorem states that any judgement that possesses a proof in the sequent calculus making use of the cut rule also possesses a cut-free proof, that is, a proof that does not make use of the cut rule. The cut rule A sequent is a logical expression relating multiple formulas, in the form , which is to be read as proves , and (as glossed by Gentzen) should be understood as equivalent to the truth-function "If (A_1 and A_2 and A_3 …) then (B_1 or B_2 or B_3 …)." Note that the left-hand side (LHS) is a conjunction (and) and the right-hand side (RHS) is a disjunction (or). The LHS may have arbitrarily many or few formulae; when the LH ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Beta Reduction
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing § lambda terms and performing § reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules: * x – variable, a character or string representing a parameter or mathematical/logical value. * (\lambda x.M) – abstraction, function definition (M is a lambda term). The variable x becomes bound in the expression. * (M\ N) – application, applying a function M to an argument N. M and N are lambda terms. The reduction operations include: * (\lambda x.M \rightarrow(\la ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gaisi Takeuti
was a Japanese mathematician, known for his work in proof theory. After graduating from Tokyo University, he went to Princeton to study under Kurt Gödel. He later became a professor at the University of Illinois at Urbana–Champaign. Takeuti was president (2003–2009) of the Kurt Gödel Society, having worked on the book ''Memoirs of a Proof Theorist: Godel and Other Logicians''. His goal was to prove the consistency of the real numbers. To this end, Takeuti's conjecture speculates that a sequent formalisation of second-order logic has cut-elimination The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for ..... An erratum to this article was published in the same journal as . He is also known for his work on ordinal diagrams with Akiko Kino. Publications * * * 2013 Dover repr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Anne Sjerp Troelstra
Anne Sjerp Troelstra (10 August 1939 – 7 March 2019) was a professor of pure mathematics and foundations of mathematics at the Institute for Logic, Language and Computation (ILLC) of the University of Amsterdam. He was a Constructivism (mathematics), constructivist logician, who was influential in the development of intuitionistic logic With Georg Kreisel, he was a developer of the theory of choice sequences. He wrote one of the first texts on linear logic, and, with Helmut Schwichtenberg, he co-wrote an important book on proof theory. He became a member of the Royal Netherlands Academy of Arts and Sciences in 1976. Troelstra died on 7 March 2019. Notes External linksHomepage of A. S. Troelstra: Dead Link - Archived : Retrieved on 27 June 2018 * 1939 births 2019 deaths Dutch mathematicians Members of the Royal Netherlands Academy of Arts and Sciences People from De Bilt University of Amsterdam alumni University of Amsterdam faculty 20th-century Dutch people {{europ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Helmut Schwichtenberg
Helmut Schwichtenberg (born 5 April 1942 in Żagań) is a German mathematical logician. Schwichtenberg studied mathematics from 1961 at the FU Berlin and from 1964 at the University of Münster, where he received his doctorate in 1968 from Dieter Rödding. He then worked as an assistant and then as a professor in Münster, and since 1978 has been professor of mathematical logic at the Ludwig-Maximilians-Universität Munich (successor of Kurt Schütte). Schwichtenberg deals with, among other things, proof theory, theory of computability, lambda calculus and applications of logic in computer science. He is a member of the Bavarian Academy of Sciences The Bavarian Academy of Sciences and Humanities (german: Bayerische Akademie der Wissenschaften) is an independent public institution, located in Munich. It appoints scholars whose research has contributed considerably to the increase of knowledg .... Selected publications * * (2nd edition 2000: ) * * References ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theorems In The Foundations Of Mathematics
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of the axioms and previously proved theorems. In the mainstream of mathematics, the axioms and the inference rules are commonly left implicit, and, in this case, they are almost always those of Zermelo–Fraenkel set theory with the axiom of choice, or of a less powerful theory, such as Peano arithmetic. A notable exception is Wiles's proof of Fermat's Last Theorem, which involves the Grothendieck universes whose existence requires the addition of a new axiom to the set theory. Generally, an assertion that is explicitly called a theorem is a proved result that is not an immediate consequence of other known theorems. Moreover, many authors qualify as ''theorems'' only the most important results, and use the terms ''lemma'', ''proposition'' and '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.PNG "Click for more on -> Theorems In The Foundations Of Mathematics")