In
mathematical logic
Mathematical logic is the study of logic, 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 for ...
, System U and System U
− are
pure type system __NOTOC__
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 d ...
s, i.e. special forms of a
typed lambda calculus
A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a ...
with an arbitrary number of
sorts, axioms and rules (or dependencies between the sorts). They were both proved inconsistent by
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 ...
in 1972.
This result led to the realization that
Martin-Löf's original
1971 type theory was inconsistent as it allowed the same "Type in Type" behaviour that Girard's paradox exploits.
Formal definition
System U is defined
as a pure type system with
* three
sorts ;
* two axioms
; and
* five rules
.
System U
− is defined the same with the exception of the
rule.
The sorts
and
are conventionally called “Type” and “
Kind”, respectively; the sort
doesn't have a specific name. The two axioms describe the containment of types in kinds (
) and kinds in
(
). Intuitively, the sorts describe a hierarchy in the ''nature'' of the terms.
# All values have a ''type'', such as a base type (''e.g.''
is read as “ is a boolean”) or a (dependent) function type (''e.g.''
is read as “ is a function from natural numbers to booleans”).
#
is the sort of all such types (
is read as “ is a type”). From
we can build more terms, such as
which is the ''kind'' of unary type-level operators (''e.g.''
is read as “ is a function from types to types”, that is, a polymorphic type). The rules restrict how we can form new kinds.
#
is the sort of all such kinds (
is read as “ is a kind”). Similarly we can build related terms, according to what the rules allow.
#
is the sort of all such terms.
The rules govern the dependencies between the sorts:
says that values may depend on values (
functions),
allows values to depend on types (
polymorphism),
allows types to depend on types (
type operators), and so on.
Girard's paradox
The definitions of System U and U
− allow the assignment of
polymorphic kinds to ''generic constructors'' in analogy to polymorphic types of terms in classical polymorphic lambda calculi, such as
System F
System F (also polymorphic lambda calculus or second-order lambda calculus) is a typed lambda calculus that introduces, to simply typed lambda calculus, a mechanism of universal quantification over types. System F formalizes parametric polymorphis ...
. An example of such a generic constructor might be (where ''k'' denotes a kind variable)
:
.
This mechanism is sufficient to construct a term with the type
(equivalent to the type
), which implies that every type is
inhabited. By the
Curry–Howard correspondence
In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct relati ...
, this is equivalent to all logical propositions being provable, which makes the system inconsistent.
Girard's paradox is the
type-theoretic analogue of
Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
in
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
.
References
Further reading
*
* {{cite book , first=Thierry , last=Coquand , author-link=Thierry Coquand , chapter=An analysis of Girard's paradox , title=Logic in Computer Science , pages=227–236 , publisher=
IEEE Computer Society
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operati ...
Press , year=1986
Lambda calculus
Proof theory
Type theory