|
Deep Inference
Deep inference names a general idea in structural proof theory that breaks with the classical sequent calculus by generalising the notion of structure to permit inference to occur in contexts of high structural complexity. The term ''deep inference'' is generally reserved for proof calculi where the structural complexity is unbounded; in this article we will use non-shallow inference to refer to calculi that have structural complexity greater than the sequent calculus, but not unboundedly so, although this is not at present established terminology. Deep inference is not important in logic outside of structural proof theory, since the phenomena that lead to the proposal of formal systems with deep inference are all related to the cut-elimination theorem. The first calculus of deep inference was proposed by Kurt Schütte,Kurt Schütte. Proof Theory. Springer-Verlag, 1977. but the idea did not generate much interest at the time. Nuel Belnap proposed display logic in an attempt to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Structural Proof Theory
In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof, a kind of proof whose semantic properties are exposed. When all the theorems of a logic formalised in a structural proof theory have analytic proofs, then the proof theory can be used to demonstrate such things as consistency, provide decision procedures, and allow mathematical or computational witnesses to be extracted as counterparts to theorems, the kind of task that is more often given to model theory. Analytic proof The notion of analytic proof was introduced into proof theory by Gerhard Gentzen for the sequent calculus; the analytic proofs are those that are cut-free. His natural deduction calculus also supports a notion of analytic proof, as was shown by Dag Prawitz; the definition is slightly more complex—the analytic proofs are the normal forms, which are related to the notion of normal form in term rewriting. ... [...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] |
Abstract Structure
An abstract structure is an abstraction that might be of the Euclidean space, geometric spaces or a set structure, or a hypostatic abstraction that is defined by a set of mathematical theorems and laws, properties and relationships in a way that is logically if not always historically independent However historical dependencies are partially considered in event theory as part of the combinatorics theory in Kolmogorov complexity and Wiener–Khinchin theorem, Kolmogorov-Khinchin equations of the structure of contingent experiences, for example, those involving physical objects. Abstract structures are studied not only in logic and mathematics but in the fields that apply them, as computer science and computer graphics, and in the studies that reflect on them, such as philosophy (especially the philosophy of mathematics). Indeed, modern mathematics has been defined in a very general sense as the study of abstract structures (by the Nicolas Bourbaki, Bourbaki group: see discussion there ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proof Calculi
In mathematical logic, a proof calculus or a proof system is built to prove statements. Overview A proof system includes the components: * Language: The set ''L'' of formulas admitted by the system, for example, propositional logic or first-order logic. * Rules of inference: List of rules that can be employed to prove theorems from axioms and theorems. * Axioms: Formulas in ''L'' assumed to be valid. All theorems are derived from axioms. Usually a given proof calculus encompasses more than a single particular formal system, since many proof calculi are under-determined and can be used for radically different logics. For example, a paradigmatic case is the sequent calculus, which can be used to express the consequence relations of both intuitionistic logic and relevance logic. Thus, loosely speaking, a proof calculus is a template or design pattern, characterized by a certain style of formal inference, that may be specialized to produce specific formal systems, namely by specifying ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal System
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A formal system is essentially an "axiomatic system". In 1921, David Hilbert proposed to use such a system as the foundation for the knowledge in mathematics. A formal system may represent a well-defined abstraction, system of abstract thought. The term ''formalism'' is sometimes a rough synonym for ''formal system'', but it also refers to a given style of notation, for example, Paul Dirac's bra–ket notation. Background Each formal system is described by primitive Symbol (formal), symbols (which collectively form an Alphabet (computer science), alphabet) to finitely construct a formal language from a set of axioms through inferential rules of formation. The system thus consists of valid formulas built up through finite combinations of the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cut-elimination Theorem
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] |
Kurt Schütte
Kurt Schütte (14 October 1909, Salzwedel – 18 August 1998, Munich) was a Germans, German mathematician who worked on proof theory and ordinal analysis. The Feferman–Schütte ordinal, which he showed to be the precise ordinal bound for predicativity, is named after him. He was the doctoral advisor of 16 students, including Wolfgang Bibel, Wolfgang Maaß, Wolfram Pohlers, and Martin Wirsing. Publications * ** ''Beweistheorie'', Springer, Grundlehren der mathematischen Wissenschaften, 1960; new edition trans. into English as ''Proof Theory'', Springer-Verlag 1977 * ''Vollständige Systeme modaler und intuitionistischer Logik'', Springer 1968 * with Wilfried Buchholz: ''Proof Theory of Impredicative Subsystems of Analysis'', Bibliopolis, Naples 1988 * with Helmut Schwichtenberg''Mathematische Logik'' in Fischer, Hirzebruch et al. (eds.) ''Ein Jahrhundert Mathematik 1890-1990'', Vieweg 1990 References * * External links Kurt Schütte at the Mathematics Genealogy Project ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nuel Belnap
Nuel Dinsmore Belnap Jr. (; born 1930) is an American logician and philosopher who has made contributions to the philosophy of logic, temporal logic, and structural proof theory. He taught at the University of Pittsburgh from 1963 until his retirement in 2011. Biography As an undergraduate, Belnap studied at the University of Illinois where he obtained his B.A. He recalled Max Fisch assigned Whitehead readings. After military service he attended Yale University and enjoyed metaphysics. His professors included Paul Weiss, Arthur Pap, Henry Margenau, Frederic Fitch, and Rulon Wells. On a Fulbright Fellowship in 1958 he went to Louvain to study with Canon Robert Feys. Belnap domiciled in Brussels with wife and 2-year-old. Feys directed Belnap to read Wilhelm Ackermann's article on rigorous implication in the ''Journal of Symbolic Logic''. Alan Ross Anderson and Belnap began to discuss relevant implication. In 1960 Anderson told Belnap to write up the work he had done on releva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Display Logic
In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof, a kind of proof whose semantic properties are exposed. When all the theorems of a logic formalised in a structural proof theory have analytic proofs, then the proof theory can be used to demonstrate such things as consistency, provide decision procedures, and allow mathematical or computational witnesses to be extracted as counterparts to theorems, the kind of task that is more often given to model theory. Analytic proof The notion of analytic proof was introduced into proof theory by Gerhard Gentzen for the sequent calculus; the analytic proofs are those that are cut-elimination theorem, cut-free. His natural deduction calculus also supports a notion of analytic proof, as was shown by Dag Prawitz; the definition is slightly more complex—the analytic proofs are the Natural deduction#Consistency.2C completeness.2C and normal fo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Calculus Of Structures
The calculus of structures is a proof calculus with deep inference for studying the structural proof theory of noncommutative logic. The calculus has since been applied to study linear logic, classical logic, modal logic, and process calculi, and many benefits are claimed to follow in these investigations from the way in which deep inference is made available in the calculus. References * Alessio Guglielmi (2004)., 'A System of Interaction and Structure'. ACM Transactions on Computational Logic. * Kai Brünnler (2004). ''Deep Inference and Symmetry in Classical Proofs''. Logos Verlag. External links Calculus of structures homepage page documenting implementations of logical systems in the calculus of structures, using the Maude system The Maude system is an implementation of rewriting logic. It is similar in its general approach to Joseph Goguen's OBJ3 implementation of equational logic, but based on rewriting logic rather than order-sorted equational logic, and with a heavy ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Noncommutative Logic
Noncommutative logic is an extension of linear logic which combines the commutative connectives of linear logic with the noncommutative multiplicative connectives of the Lambek calculus. Its sequent calculus relies on the structure of order varieties (a family of cyclic orders which may be viewed as a species of structure), and the correctness criterion for its proof nets is given in terms of partial permutations. It also has a denotational semantics in which formulas are interpreted by modules over some specific Hopf algebras. Noncommutativity in logic By extension, the term noncommutative logic is also used by a number of authors to refer to a family of substructural logics in which the exchange rule is inadmissible. The remainder of this article is devoted to a presentation of this acceptance of the term. The oldest noncommutative logic is the Lambek calculus, which gave rise to the class of logics known as categorial grammars. Since the publication of Jean-Yves Girard's lin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cirquent Calculus
Cirquent calculus is a proof calculus that manipulates graph-style constructs termed ''cirquents'', as opposed to the traditional tree-style objects such as formulas or sequents. Cirquents come in a variety of forms, but they all share one main characteristic feature, making them different from the more traditional objects of syntactic manipulation. This feature is the ability to explicitly account for possible sharing of subcomponents between different components. For instance, it is possible to write an expression where two subexpressions ''F'' and ''E'', while neither one is a subexpression of the other, still have a common occurrence of a subexpression ''G'' (as opposed to having two different occurrences of ''G'', one in ''F'' and one in ''E''). Overview The approach was introduced by G. Japaridze in as an alternative proof theory capable of "taming" various nontrivial fragments of his computability logic, which had otherwise resisted all axiomatization attempts within the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
