|
Double-negation Translation
In proof theory, a discipline within mathematical logic, double-negation translation, sometimes called negative translation, is a general approach for embedding classical logic into intuitionistic logic, typically by translating formulas to formulas which are classically equivalent but intuitionistically inequivalent. Particular instances of double-negation translation include Glivenko's translation for propositional logic, and the Gödel–Gentzen translation and Kuroda's translation for first-order logic. Propositional logic The easiest double-negation translation to describe comes from Glivenko's theorem, proved by Valery Glivenko in 1929. It maps each classical formula φ to its double negation ¬¬φ. Glivenko's theorem states: :If φ is a propositional formula, then φ is a classical tautology if and only if ¬¬φ is an intuitionistic tautology. Glivenko's theorem implies the more general statement: :If ''T'' is a set of propositional formulas and φ a propositional formu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proof Theory
Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Jon Barwise, Barwise (1978) consists of four corresponding parts, with part D being about "Proof Theory and Constructive Mathematics". of mathematical logic that represents Mathematical proof, proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as Recursive data type, inductively-defined data structures such as list (computer science), lists, boxed lists, or Tree (data structure), trees, which are constructed according to the axioms and rule of inference, rules of inference of the logical system. Consequently, proof theory is syntax (logic), syntactic in nature, in contrast to model theory, which is Formal semantics (logic), semantic in nature. Some of the major areas of proof theory include structural proof theory, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Functional Programming Languages
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program. In functional programming, functions are treated as first-class citizens, meaning that they can be bound to names (including local identifiers), passed as arguments, and returned from other functions, just as any other data type can. This allows programs to be written in a declarative and composable style, where small functions are combined in a modular manner. Functional programming is sometimes treated as synonymous with purely functional programming, a subset of functional programming which treats all functions as deterministic mathematical functions, or pure functions. When a pure function is called with some ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dirk Van Dalen
Dirk van Dalen (born 20 December 1932, Amsterdam) is a Dutch mathematician and historian of science. Van Dalen studied mathematics and physics and astronomy at the University of Amsterdam. Inspired by the work of Brouwer and Heyting, he received his Ph.D. in 1963 from the University of Amsterdam for the thesis ''Extension problems in intuitionistic plane Projective geometry.'' From 1964 to 1966 Van Dalen taught logic and mathematics at MIT, and later Oxford. From 1967 he was professor at the University of Utrecht. In 2003 Dirk van Dalen was awarded the Academy Medal 2003 of the Royal Dutch Academy of Sciences for bringing the works of Brouwer to international attention. Works * 1958: (with Yehoshua Bar-Hillel and Azriel Levy) ''Foundations of Set Theory'', North Holland Publishing * 1963: Extension problems in intuitionistic plane projective geometry * 1978: (with H.C. Doets and H. De Swart) ''Sets: Naive, Axiomatic and Applied'', Pergamon Press * 1980: ''Logic and Structure'', ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jon Barwise
Kenneth Jon Barwise (; June 29, 1942 – March 5, 2000) was an American mathematician, philosopher and logician who proposed some fundamental revisions to the way that logic is understood and used. Education and career Born in Independence, Missouri to Kenneth T. and Evelyn Barwise, Jon was a precocious child. A pupil of Solomon Feferman at Stanford University, Barwise started his research in infinitary logic. After positions as assistant professor at Yale University and the University of Wisconsin, during which time his interests turned to natural language, he returned to Stanford in 1983 to direct the Center for the Study of Language and Information. He began teaching at Indiana University in 1990. He was elected a Fellow of the American Academy of Arts and Sciences in 1999. In his last year, Barwise was invited to give the 2000 Gödel Lecture; he died prior to the lecture. Philosophical and logical work Barwise contended that, by being explicit about the context in whic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Anne S
Anne, alternatively spelled Ann, is a form of the Latin female given name Anna. This in turn is a representation of the Hebrew Hannah, which means 'favour' or 'grace'. Related names include Annie. Anne is sometimes used as a male name in the Netherlands, particularly in the Frisian speaking part (for example, author Anne de Vries). In this incarnation, it is related to Germanic arn-names and means 'eagle'.See entry on "Anne" in th''Behind the Name'' databaseand th"Anne"an"Ane"entries (in Dutch) in the Nederlandse Voornamenbank (Dutch First Names Database) of the Meertens Instituut (23 October 2018). It has also been used for males in France (Anne de Montmorency) and Scotland (Lord Anne Hamilton). Anne is a common name and the following lists represent a small selection. For a comprehensive list, see instead: . As a feminine name Anne * Saint Anne, Mother of the Virgin Mary * Anne, Queen of Great Britain (1665–1714), Queen of England, Scotland, and Ireland (1702–07) and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Samuel Buss
Samuel R. (Sam) Buss is an American computer scientist and mathematician who has made major contributions to the fields of mathematical logic, complexity theory and proof complexity. He is currently a professor at the University of California, San Diego, Department of Computer Science and Department of Mathematics. Biography Buss received his bachelor's degree in 1979 from the Emory University, and his master's degree and Ph.D. from Princeton University, respectively in 1983 and 1985. He joined the University of California, Berkeley, mathematics department in 1986 as an Lecturer, and stayed there until 1988. Buss joined the faculty of University of California, San DiegoComputer ScienceanMathematicsDepartments in 1988 as an assistant professor, where he was promoted to Professor in 1993. In 2019, Buss gave the Gödel Lecture titled ''Totality, provability and feasibility.'' Research Buss is considered one of the forefathers of bounded arithmetic and proof complexity. During ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solomon Feferman
Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to the United States after World War I and had met and married in New York. Neither parent had any advanced education. The family moved to Los Angeles, where Feferman graduated from high school at age 16. He received his B.S. from the California Institute of Technology in 1948, and in 1957 his Ph.D. in mathematics from the University of California, Berkeley, under Alfred Tarski, after having been drafted and having served in the U.S. Army from 1953 to 1955. In 1956 he was appointed to the Departments of Mathematics and Philosophy at Stanford University, where he later became the Patrick Suppes Professor of Humanities and Sciences. Feferman died on 26 July 2016 at his home in Stanford, following an illness that lasted three months and a stroke ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jeremy Avigad
Jeremy Avigad is a professor of philosophy at Carnegie Mellon University. He received a B.A. in mathematics from Harvard University in 1989, and a Ph.D. in mathematics from the University of California at Berkeley in 1995 under the supervision of Jack Silver. He has contributed to the areas of mathematical logic and foundations, formal verification and interactive theorem proving, and the philosophy and history of mathematics. He became Director of the Hoskinson Center for Formal Mathematics at Carnegie Mellon University after Charles Hoskinson Charles Hoskinson is an American entrepreneur who is a co-founder of the blockchain engineering company Input Output Global, Inc. (formerly IOHK), and the Cardano blockchain platform, and was a co-founder of the Ethereum blockchain platform. E ... donated $20 Million in September 2021 to establish it. References 20th-century American mathematicians 21st-century American mathematicians American logicians Living people ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dialectica Interpretation
In proof theory, the Dialectica interpretation is a proof interpretation of intuitionistic arithmetic (Heyting arithmetic) into a finite type extension of primitive recursive arithmetic, the so-called System T. It was developed by Kurt Gödel to provide a consistency proof of arithmetic. The name of the interpretation comes from the journal ''Dialectica'', where Gödel's paper was published in a 1958 special issue dedicated to Paul Bernays on his 70th birthday. Motivation Via the Gödel–Gentzen negative translation, the consistency of classical Peano arithmetic had already been reduced to the consistency of intuitionistic Heyting arithmetic. Gödel's motivation for developing the dialectica interpretation was to obtain a relative consistency proof for Heyting arithmetic (and hence for Peano arithmetic). Dialectica interpretation of intuitionistic logic The interpretation has two components: a formula translation and a proof translation. The formula translation describes how ... [...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_1 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Friedman Translation
In mathematical logic, the Friedman translation is a certain transformation of intuitionistic formulas. Among other things it can be used to show that the Π02-theorems of various first-order theories of classical mathematics are also theorems of intuitionistic mathematics. It is named after its discoverer, Harvey Friedman. Definition Let ''A'' and ''B'' be intuitionistic formulas, where no free variable of ''B'' is quantified in ''A''. The translation ''AB'' is defined by replacing each atomic subformula ''C'' of ''A'' by . For purposes of the translation, ⊥ is considered to be an atomic formula as well, hence it is replaced with (which is equivalent to ''B''). Note that ¬''A'' is defined as an abbreviation for hence Application The Friedman translation can be used to show the closure of many intuitionistic theories under the Markov rule, and to obtain partial conservativity results. The key condition is that the \Delta^0_0 sentences of the logic be decidable, allowing ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Heyting Arithmetic
In mathematical logic, Heyting arithmetic is an axiomatization of arithmetic in accordance with the philosophy of intuitionism.Troelstra 1973:18 It is named after Arend Heyting, who first proposed it. Axiomatization As with first-order Peano arithmetic , the intended model of this theory are the natural numbers and the theories characterize addition and multiplication. Heyting arithmetic adopts the axioms of Peano arithmetic, including the signature with zero "0" and the successor "S", but uses intuitionistic logic for inference. In particular, the principle of the excluded middle does not hold in general. Metalogic and theorems As with other theories over intuitionistic logic, various instances of can be proven. For instance, proves equality "=" is decidable for all numbers, :\vdash \forall n. \forall m. \big((n = m)\lor\neg(n = m)\big) In fact, since equality is the only predicate symbol in Heyting arithmetic, it then follows that, for any quantifier-free formula \phi, w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
