|
Induction-induction
In intuitionistic type theory (ITT), some discipline within mathematical logic, induction-induction is for simultaneously declaring some inductive type and some inductive predicate over this type. An inductive definition is given by rules for generating elements of some type. One can then define some predicate on that type by providing constructors for forming the elements of the predicate , such inductively on the way the elements of the type are generated. Induction-induction generalizes this situation since one can ''simultaneously'' define the type and the predicate, because the rules for generating elements of the type A : \mathsf are allowed to refer to the predicate B : A \to \mathsf. Induction-induction can be used to define larger types including various universe constructions in type theory. and limit constructions in category/topos theory. Example 1 Present the type A as having the following constructors , note the early reference to the predicate B : * aa : A * \ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induction-recursion
In intuitionistic type theory (ITT), a discipline within mathematical logic, induction-recursion is a feature for simultaneously declaring a type and function on that type. It allows the creation of larger types, such as universes, than Intuitionistic type theory#Inductive types, inductive types. The types created still remain Predicativity, predicative inside ITT. An inductive definition is given by rules for generating elements of a type. One can then define functions from that type by induction on the way the elements of the type are generated. Induction-recursion generalizes this situation since one can ''simultaneously'' define the type and the function, because the rules for generating elements of the type are allowed to refer to the function. Induction-recursion can be used to define large types including various universe constructions. It increases the proof-theoretic strength of type theory substantially. Nevertheless, inductive-recursive recursive definitions are still c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Intuitionistic Type Theory
Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative foundation of mathematics. Intuitionistic type theory was created by Per Martin-Löf, a Swedish mathematician and philosopher, who first published it in 1972. There are multiple versions of the type theory: Martin-Löf proposed both intensional and extensional variants of the theory and early impredicative versions, shown to be inconsistent by Girard's paradox, gave way to predicative versions. However, all versions keep the core design of constructive logic using dependent types. Design Martin-Löf designed the type theory on the principles of mathematical constructivism. Constructivism requires any existence proof to contain a "witness". So, any proof of "there exists a prime greater than 1000" must identify a specific number that is both prime and greater than 1000. Intuitionistic type theory accomplished this design goal by internaliz ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematical Logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion 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 analysis. In the early 20th century it was shaped by David Hilbert's program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory sho ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inductive Definition
In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set ( Aczel 1977:740ff). Some examples of recursively-definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set. A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the factorial function ''n''! is defined by the rules :0! = 1. :(''n'' + 1)! = (''n'' + 1)·''n''!. This definition is valid for each natural number ''n'', because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure for computing the value of the function ''n''!, starting from ''n'' = 0 and proceeding onwards with ''n'' = 1, ''n'' = 2, ''n'' = 3 etc. The recursion theorem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
