|
Ludics
In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic. Key features of ludics include notion of compound connectives, using a technique known as ''focusing'' or ''focalisation'' (invented by the computer scientist Jean-Marc Andreoli), and its use of ''locations'' or ''loci'' over a base instead of propositions. More precisely, ludics tries to retrieve known logical connectives and proof behaviours by following the paradigm of interactive computation, similarly to what is done in game semantics to which it is closely related. By abstracting the notion of formulae and focusing on their concrete uses—that is distinct occurrences—it provides an abstract syntax for computer science, as loci can be seen as pointers on memory. The primary achievement of ludics is the discovery of a relationship between two natural, but distinct notions of type, or proposition. The first view, which might be termed the proof-theoretic or Gentzen-s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jean-Yves Girard
Jean-Yves Girard (; born 1947) is a French logician working in proof theory. He is the research director ( emeritus) at the mathematical institute of the University of Aix-Marseille, at Luminy. Biography Jean-Yves Girard is an alumnus of the École normale supérieure de Saint-Cloud. He made a name for himself in the 1970s with his proof of strong normalization in a system of second-order logic called System F. This result gave a new proof of Takeuti's conjecture, which was proven a few years earlier by William W. Tait, Motō Takahashi and Dag Prawitz. For this purpose, he introduced the notion of "reducibility candidate" ("candidat de réducibilité"). He is also credited with the discovery of Girard's paradox, linear logic, the geometry of interaction, ludics, and (satirically) the mustard watch. He obtained the CNRS Silver medal in 1983 and is a member of the French Academy of Sciences. Bibliography * * * * Jean-Yves Girard (2011). ''The Blind Spot: Lectures on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also been studied for its own sake, more broadly, ideas from linear logic have been influential in fields such as programming languages, game semantics, and quantum physics (because linear logic can be seen as the logic of quantum information theory), as well as linguistics, particularly because of its emphasis on resource-boundedness, duality, and interaction. Linear logic lends itself to many different presentations, explanations, and intuitions. Proof-theoretically, it derives from an analysis of classical sequent calculus in which uses of (the structural rules) contraction and weakening are carefully controlled. Operationally, this means that logical deduction is no longer merely about an ever-expanding collection of persistent "truths", ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Game Semantics
Game semantics (german: dialogische Logik, translated as ''dialogical logic'') is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player, somewhat resembling Socratic dialogues or medieval theory of Obligationes. History In the late 1950s Paul Lorenzen was the first to introduce a game semantics for logic, and it was further developed by Kuno Lorenz. At almost the same time as Lorenzen, Jaakko Hintikka developed a model-theoretical approach known in the literature as ''GTS'' (game-theoretical semantics). Since then, a number of different game semantics have been studied in logic. Shahid Rahman (Lille) and collaborators developed dialogical logic into a general framework for the study of logical and philosophical issues related to logical pluralism. Beginning 1994 this triggered a kind of renaissance with lasting consequences. This new philosophical impulse experienced a pa ... [...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] |
Gentzen
Gerhard Karl Erich Gentzen (24 November 1909 – 4 August 1945) was a German mathematician and logician. He made major contributions to the foundations of mathematics, proof theory, especially on natural deduction and sequent calculus. He died of starvation in a Soviet prison camp in Prague in 1945, having been interned as a German national after the Second World War. Life and career Gentzen was a student of Paul Bernays at the University of Göttingen. Bernays was fired as "non-Aryan" in April 1933 and therefore Hermann Weyl formally acted as his supervisor. Gentzen joined the Sturmabteilung in November 1933 although he was by no means compelled to do so. Nevertheless he kept in contact with Bernays until the beginning of the Second World War. In 1935, he corresponded with Abraham Fraenkel in Jerusalem and was implicated by the Nazi teachers' union as one who "keeps contacts to the Chosen People." In 1935 and 1936, Hermann Weyl, head of the Göttingen mathematics department in 1 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logician
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises in a topic-neutral way. When used as a countable noun, the term "a logic" refers to a logical formal system that articulates a proof system. Formal logic contrasts with informal logic, which is associated with informal fallacies, critical thinking, and argumentation theory. While there is no general agreement on how formal and informal logic are to be distinguished, one prominent approach associates their difference with whether the studied arguments are expressed in formal or informal languages. Logic plays a central role in multiple fields, such as philosophy, mathematics, computer science, and linguistics. Logic studies arguments, which consist of a set of premises together with a conclusion. Premises and conclusions are usually und ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Affine Logic
Affine logic is a substructural logic whose proof theory rejects the structural rule of contraction. It can also be characterized as linear logic with weakening. The name "affine logic" is associated with linear logic, to which it differs by allowing the weakening rule. Jean-Yves Girard introduced the name as part of the geometry of interaction semantics of linear logic, which characterizes linear logic in terms of linear algebra; here he alludes to affine transformations on vector spaces. Affine logic predated linear logic. V. N. Grishin used this logic in 1974, after observing that Russell's paradox cannot be derived in a set theory without contraction, even with an unbounded comprehension axiom.Cf. Frederic Fitch's demonstrably consistent set theory Likewise, the logic formed the basis of a decidable sub-theory of predicate logic, called 'Direct logic' (Ketonen & Wehrauch, 1984; Ketonen & Bellin, 1989). Affine logic can be embedded into linear logic by rewriting th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Second-order Logic
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies only variables that range over individuals (elements of the domain of discourse); second-order logic, in addition, also quantifies over relations. For example, the second-order sentence \forall P\,\forall x (Px \lor \neg Px) says that for every formula ''P'', and every individual ''x'', either ''Px'' is true or not(''Px'') is true (this is the law of excluded middle). Second-order logic also includes quantification over sets, functions, and other variables (see section below). Both first-order and second-order logic use the idea of a domain of discourse (often called simply the "domain" or the "universe"). The domain is a set over which individual elements may be quantified. Examples First-order logic can quantify over individuals, bu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Realizability
In mathematical logic, realizability is a collection of methods in proof theory used to study constructive proofs and extract additional information from them. Formulas from a formal theory are "realized" by objects, known as "realizers", in a way that knowledge of the realizer gives knowledge about the truth of the formula. There are many variations of realizability; exactly which class of formulas is studied and which objects are realizers differ from one variation to another. Realizability can be seen as a formalization of the BHK interpretation of intuitionistic logic; in realizability the notion of "proof" (which is left undefined in the BHK interpretation) is replaced with a formal notion of "realizer". Most variants of realizability begin with a theorem that any statement that is provable in the formal system being studied is realizable. The realizer, however, usually gives more information about the formula than a formal proof would directly provide. Beyond giving insight in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Brouwer–Heyting–Kolmogorov Interpretation
In mathematical logic, the Brouwer–Heyting–Kolmogorov interpretation, or BHK interpretation, of intuitionistic logic was proposed by L. E. J. Brouwer and Arend Heyting, and independently by Andrey Kolmogorov. It is also sometimes called the realizability interpretation, because of the connection with the realizability theory of Stephen Kleene. It is the standard explanation of intuitionistic logic. The interpretation The interpretation states what is intended to be a proof of a given formula. This is specified by induction on the structure of that formula: *A proof of P \wedge Q is a pair \langle a, b \rangle where a is a proof of P and b is a proof of Q. *A proof of P \vee Q is either \langle 0, a \rangle where a is a proof of P or \langle 1, b\rangle where b is a proof of Q. *A proof of P \to Q is a function f that converts a proof of P into a proof of Q. *A proof of (\exists x S) P is a pair \langle x, a \rangle where x is an element of S and a is a proof of P. *A proof ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pointer (computing)
In computer science, a pointer is an object in many programming languages that stores a memory address. This can be that of another value located in computer memory, or in some cases, that of memory-mapped computer hardware. A pointer ''references'' a location in memory, and obtaining the value stored at that location is known as ''dereferencing'' the pointer. As an analogy, a page number in a book's index could be considered a pointer to the corresponding page; dereferencing such a pointer would be done by flipping to the page with the given page number and reading the text found on that page. The actual format and content of a pointer variable is dependent on the underlying computer architecture. Using pointers significantly improves performance for repetitive operations, like traversing iterable data structures (e.g. strings, lookup tables, control tables and tree structures). In particular, it is often much cheaper in time and space to copy and dereference pointers t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Type Theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of mathematics. Two influential type theories that were proposed as foundations are Alonzo Church's typed λ-calculus and Per Martin-Löf's intuitionistic type theory. Most computerized proof-writing systems use a type theory for their foundation. A common one is Thierry Coquand's Calculus of Inductive Constructions. History Type theory was created to avoid a paradox in a mathematical foundation based on naive set theory and formal logic. Russell's paradox, which was discovered by Bertrand Russell, existed because a set could be defined using "all possible sets", which included itself. Between 1902 and 1908, Bertrand Russell proposed various "theories of type" to fix the problem. By 1908 Russell arrived at a "ramified" theory ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
