Type theory

theory of typestypestypetype-theoretictype theorieslogical typelogical typesramified theory of typesSimple Theory of Typestype theoretic
In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.wikipedia
288 Related Articles

Type system

dynamicstatictype checking
Type theory is closely related to (and in some cases overlaps with) type systems, which are a programming language feature used to reduce bugs.
Type theory is the study of type systems.

Bertrand Russell

RussellRussell, BertrandBertrand Russel
Between 1902 and 1908 Bertrand Russell proposed various "theories of type" in response to his discovery that Gottlob Frege's version of naive set theory was afflicted with Russell's paradox. By 1908 Russell arrived at a "ramified" theory of types together with an "axiom of reducibility" both of which featured prominently in Whitehead and Russell's Principia Mathematica published between 1910 and 1913.
His work has had a considerable influence on mathematics, logic, set theory, linguistics, artificial intelligence, cognitive science, computer science (see type theory and type system) and philosophy, especially the philosophy of language, epistemology and metaphysics.

Axiom of reducibility

By 1908 Russell arrived at a "ramified" theory of types together with an "axiom of reducibility" both of which featured prominently in Whitehead and Russell's Principia Mathematica published between 1910 and 1913.
The axiom of reducibility was introduced by Bertrand Russell in the early 20th century as part of his ramified theory of types.

Russell's paradox

Russell paradoxPrinciple of comprehensionRussell
Between 1902 and 1908 Bertrand Russell proposed various "theories of type" in response to his discovery that Gottlob Frege's version of naive set theory was afflicted with Russell's paradox.
In 1908, two ways of avoiding the paradox were proposed, Russell's type theory and the Zermelo set theory.

Principia Mathematica

Principiaramified theory of typesRamified type theory
By 1908 Russell arrived at a "ramified" theory of types together with an "axiom of reducibility" both of which featured prominently in Whitehead and Russell's Principia Mathematica published between 1910 and 1913.
This third aim motivated the adoption of the theory of types in PM.

Higher-order logic

higher order logichigher-orderHigher Order
Church demonstrated that it could serve as a foundation of mathematics and it was referred to as a higher-order logic.
Here "simple" indicates that the underlying type theory is the theory of simple types, also called the simple theory of types (see Type theory).

Mathematical logic

formal logicsymbolic logiclogic
Type theory was created to avoid paradoxes in a variety of formal logics and rewrite systems.
This seminal work developed the theory of functions and cardinality in a completely formal framework of type theory, which Russell and Whitehead developed in an effort to avoid the paradoxes.

Calculus of constructions

Calculus of Inductive Constructionscalculus of (co)inductive constructions
Thierry Coquand's calculus of constructions and its derivatives are the foundation used by Coq and others.
In mathematical logic and computer science, the calculus of constructions (CoC) is a type theory created by Thierry Coquand.

Computer science

computer scientistcomputer sciencescomputer scientists
In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.

Programming language

programming languageslanguagedialect
Type theory is closely related to (and in some cases overlaps with) type systems, which are a programming language feature used to reduce bugs.
The formal design and study of type systems is known as type theory.

Coq

Coq proof assistantCoq (Gallina)Gallina
Thierry Coquand's calculus of constructions and its derivatives are the foundation used by Coq and others.
Seen as a programming language, Coq implements a dependently typed functional programming language, while seen as a logical system, it implements a higher-order type theory.

Tagged union

sum typediscriminated unionSum
In type theory, a tagged union is called a sum type.

Bottom type

bottomempty type
There is usually no judgement to say two terms are not equal; instead, as in the Brouwer–Heyting–Kolmogorov interpretation, we map \neg(a = b) to, where \bot is the bottom type having no values.
In type theory, a theory within mathematical logic, the bottom type is the type that has no values.

Simply typed lambda calculus

simply-typed lambda calculusdescribed belowlambda calculus
The most famous early example is Alonzo Church's simply typed lambda calculus.
of type theory, is a typed interpretation of the lambda calculus with only one type constructor: \to that builds function types.

Curry–Howard correspondence

Curry–Howard isomorphismCurry-Howard correspondencepropositions-as-types
This field of research is usually referred to as modern type theory.

Type constructor

type constructorstype operatorshigher-order type operator
Other systems have inductive types: a set of base types and a set of type constructors that generate types with well-behaved properties.
In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old ones.

ST type theory

The following system is Mendelson's (1997, 289–293) ST type theory.

Logical framework

LFLF (logical framework)LF Logical Framework
In logic, a logical framework provides a means to define (or present) a logic as a signature in a higher-order type theory in such a way that provability of a formula in the original logic reduces to a type inhabitation problem in the framework type theory.

Lambda cube

λ-cube
In mathematical logic and type theory, the λ-cube is a framework introduced by Henk Barendregt to investigate the different dimensions in which the calculus of constructions is a generalization of the simply typed λ-calculus.

Constructivism (philosophy of mathematics)

constructive mathematicsconstructivismconstructive
Some other type theories include Per Martin-Löf's intuitionistic type theory, which has been the foundation used in some areas of constructive mathematics and for the proof assistant Agda.
In intuitionistic theories of type theory (especially higher-type arithmetic), many forms of the axiom of choice are permitted.

Set-theoretic definition of natural numbers

as defined in standard set theoryconstructions of the set of natural numbersordinal natural numbers
This definition goes through in type theory, and in set theories that grew out of type theory, such as New Foundations and related systems.

Pure type system

pure type systemsBarendregt–Geuvers–Klop conjectureGirard's Paradox
In the branches of mathematical logic known as proof theory and type theory, a pure type system (PTS), previously known as a generalized type system (GTS), is a form of typed lambda calculus that allows an arbitrary number of sorts and dependencies between any of these.

Currying

curriedcurried formcurries
Not using parentheses is more common, because multiple argument functions can be defined using currying.
In type theory, the general idea of a type system in computer science is formalized into a specific algebra of types.

Isabelle (proof assistant)

IsabelleIsabelle theorem proverIsabelle proof assistant
Multiple type theories are supported by LEGO and Isabelle.
Isabelle is generic: it provides a meta-logic (a weak type theory), which is used to encode object logics like first-order logic (FOL), higher-order logic (HOL) or Zermelo–Fraenkel set theory (ZFC).

First-order logic

predicate logicfirst-orderpredicate calculus
This is also called typed first-order logic, and the sorts called types (as in data type), but it is not the same as first-order type theory.