type theory phd

I do type theory and category theory, I mean ∞-ones.

Publications

A General Framework for the Semantics of Type Theory. Mathematical Structures in Computer Science, 2023. doi:10.1017/S0960129523000208 arXiv:1904.04097
Homotopy type theory as internal languages of diagrams of ∞-logoses. 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023) , 2023. doi:10.4230/LIPIcs.FSCD.2023.5 This is a short version of arXiv:2212.02444 .
On Church’s Thesis in Cubical Assemblies (joint with Andrew Swan ). Mathematical Structures in Computer Science, 2022. doi:10.1017/S0960129522000068
The universal exponentiable arrow. Journal of Pure and Applied Algebra, Volume 226, Issue 7, 2022. doi:10.1016/j.jpaa.2021.106991
Cubical Assemblies, a Univalent and Impredicative Universe and a Failure of Propositional Resizing. 24th International Conference on Types for Proofs and Programs (TYPES 2018) , 2019. doi:10.4230/LIPICS.TYPES.2018.7
Fibred Fibration Categories. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , 2017. doi:10.1109/LICS.2017.8005084 arXiv:1602.08206
Normalization and coherence for ∞-type theories. 2022. arXiv:2212.11764
Homotopy type theory as internal languages of diagrams of ∞-logoses. 2022. arXiv:2212.02444
∞-type theories (joint with Hoang Kim Nguyen ). 2022. arXiv:2205.00798
Homotopies for Free! 2017. arXiv:1701.07937

Abstract and Concrete Type Theories. Institute for Logic, Language and Computation , University of Amsterdam , 9 July, 2021. abstract pdf UvA DARE

SNS accounts

GitHub: uemurax
Mastodon: @[email protected]

PhD studentship in homotopy type theory and univalent foundations

Note: this position has been filled.

The TU Delft Department of Software Technology has a open position for a PhD student in Programming Languages, working with Benedikt Ahrens .

The starting date for the position could be as soon as September 1, 2021.

Code: TUD01190

About Homotopy Type Theory and Univalent Foundations

Homotopy Type Theory is a young area of logic, combining ideas from several established fields: the use of dependent type theory as a foundation for mathematics, inspired by ideas and tools from abstract homotopy theory. Univalent Foundations are foundations of mathematics based on the homotopical interpretation of type theory.

Topics in HoTT/UF

Despite a flurry of discoveries in HoTT/UF in recent years, many open questions remain. Possible PhD projects include

Syntax and semantics of type theories,
Formalization and mechanization of results from mathematics and computer science in univalent foundations / two-level type theory,
Design and implementation of domain-specific type theories,
Univalence principle and its applications.

The PhD student should have knowledge in some of the following areas:

Type theory
Category theory
Computer proof assistants
Functional programming

and be interested in learning in the other areas.

About the Position

A fully funded PhD position is open for an excellent candidate working in an area related to HoTT/UF. The PhD student will be supervised by Benedikt Ahrens .

Conditions of Employment

Fixed-term contract: 4 years.

TU Delft offers a customisable compensation package, a discount for health insurance and sport memberships, and a monthly work costs contribution. Flexible work schedules can be arranged. An International Children’s Centre offers childcare and an international primary school. Dual Career Services offers support to accompanying partners. Salary and benefits are in accordance with the Collective Labour Agreement for Dutch Universities: Gross salary PhD student ranging from € 2.395,– (1st year) to € 3.061,– (4th year) per month, plus holiday allowance (8%) and end-of-year bonus (8.3%).

As a PhD candidate you will be enrolled in the TU Delft Graduate School. TU Delft Graduate School provides an inspiring research environment; an excellent team of supervisors, academic staff and a mentor; and a Doctoral Education Programme aimed at developing your transferable, discipline-related and research skills. Please visit http://www.tudelft.nl/phd for more information.

The Organization

The Programming Languages Research Group is an internationally leading research group in programming languages, and active in areas such as language engineering, language design, domain-specific languages, software verification, and program logics. The section employs over 15 people, including academic staff, around 10 PhD students, and two postdoctoral researchers. The group is responsible for programming and programming languages education at the bachelor and master’s levels in the TU Delft Computer Science curriculum.

The Software Technology (ST) Department is one of the leading Dutch departments in research and academic education in computer science, employing over 150 people. The ST Department is responsible for a large part of the curriculum of the bachelor’s and master’s programmes in Computer Science as well as the master’s programme Embedded Systems. The inspiration for its research topics is largely derived from technical ICT problems in industry and society related to large-scale distributed processing, embedded systems, programming productivity, and web-based information analysis.

The Faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) is known worldwide for its high academic quality and the societal relevance of its research programmes. Offering an international working environment, the faculty has more than 1100 employees (including about 500 PhD students) and more than 3000 bachelor’s and master’s students. Together they work on a broad range of technical innovations in the fields of electrical sustainable energy, microelectronics, intelligent systems, software technology, and applied mathematics. Additional Information

For more information about this position contact Benedikt Ahrens ( [email protected] ).

Application procedure

To apply, please send your application letter by e-mail as soon as possible to Benedikt Ahrens ( [email protected] ) including in the subject the position code “TUD01190”. It is highly recommended to get in touch informally prior to submitting an application.

All applications should include a PDF attachment with:

an application letter, including a statement of research interests that demonstrates an understanding of one or more areas of relevance to the PhD topic,
a detailed CV (including list of publications if available),
a list of courses taken and grades obtained,
a copy or link to your Master’s thesis,
contact details of 2-3 references.

Postdoctoral Position in HoTT at the University of San Diego

The University of San Diego invites applications for a postdoctoral research fellowship in homotopy type theory beginning Fall 2021, or earlier if desired. This is a two-year position with potential extension to a third year, funded by the second AFOSR MURI grant for HoTT, entitled "Synthetic and Constructive Mathematics of Higher Structures in Homotopy Type Theory".

This is the same grant that’s funding Emily’s postdoc at Johns Hopkins , but due to delays in job posting, I won’t be able to make an offer before the AMS coordinated postdoc response deadline of February 1. Indeed, February 1, 2021 is only the priority submission deadline for the application, less than 2 weeks away. However, I’ll do my best to make a quick turnaround, and if you’re interested in the position but have other offers requiring a response, please let me know before giving up. As with the Johns Hopkins position, you must at least be able to obtain a visa to come and work physically in the U.S.; I’m still working on the details of visa sponsorship, but it should be possible.

Applications are encouraged from candidates working in any area related to homotopy type theory, broadly construed. If your background is in a related area but you’re interested in getting into the field, don’t let that deter you. Please include in your cover letter a discussion of your background and future research goals as they relate specifically to homotopy type theory, as well as any specific interests you may have in collaborating with the team for the grant, which in addition to myself includes Steve Awodey, Bob Harper, Favonia, Dan Licata, and Emily Riehl, and their students and postdocs. This is especially important if you’re new to the field and HoTT doesn’t figure prominently in your CV and past research.

The University of San Diego (not to be confused with the University of California, San Diego) is a relatively small private Catholic university. Although the university includes a few graduate schools, the mathematics department is in the College of Arts and Sciences, which is purely an undergraduate liberal arts college. We have no graduate students, and this will be the first postdoc ever in the math department. So you should be aware what you’re getting into; but on the other hand, if you have any interest in eventually becoming faculty at a liberal-arts college, this could be a good opportunity to get a feel for what such a department is like. Although I can’t make any promises, the postdoc may have the opportunity to help supervise undergraduate research students and/or to teach undergraduate courses if they are interested (though this is not required, and will be decided later).

Applications should be submitted through the University of San Diego recruitment system . Please email to alert me of your application, as well as with any questions you have!

USD is an Equal Opportunity employer, and is especially interested in candidates who can contribute to the diversity and excellence of the academic community.

Type Theory with Records: From Perception to Communication

The course introduces TTR, a Type Theory with Records, as a framework for natural language grammar and interaction. We follow Cooper (in preparation) in taking a dialogical view of semantics. The course covers the formal foundations of TTR as well as TTR accounts of perception, intensionality, information exchange, grammar (syntax and semantics), quantification, modality and other linguistic phenomena. It also covers the relation between TTR and other type theories for natural language semantics, as well as recent extensions and applications of TTR.

The course webpage can be accessed

The course syllabus can be found here .

Towards a practical programming language based on dependent type theory

Table of Contents
Random Entry
Chronological
Editorial Information
About the SEP
Editorial Board
How to Cite the SEP
Special Characters
Advanced Tools
Support the SEP
PDFs for SEP Friends
Make a Donation
SEPIA for Libraries
Entry Contents

Bibliography

Academic tools.

Friends PDF Preview
Author and Citation Info
Back to Top

Type Theory

The topic of type theory is fundamental both in logic and computer science. We limit ourselves here to sketch some aspects that are important in logic. For the importance of types in computer science, we refer the reader for instance to Reynolds 1983 and 1985.

1. Paradoxes and Russell’s Type Theories

2. simple type theory and the \(\lambda\)-calculus, 3. ramified hierarchy and impredicative principles, 4. type theory/set theory, 5. type theory/category theory, 6. extensions of type system, polymorphism, paradoxes, 7. univalent foundations, other internet resources, related entries.

The theory of types was introduced by Russell in order to cope with some contradictions he found in his account of set theory and was introduced in “Appendix B: The Doctrine of Types” of Russell 1903. This contradiction was obtained by analysing a theorem of Cantor that no mapping

(where \(\Pow(X)\) is the class of subclasses of a class \(X)\) can be surjective; that is, \(F\) cannot be such that every member \(b\) of \(\Pow(X)\) is equal to \(F(a)\) for some element \(a\) of \(X\). This can be phrased “intuitively” as the fact that there are more subsets of \(X\) than elements of \(X\). The proof of this fact is so simple and basic that it is worthwhile giving it here. Consider the following subset of \(X\):

This subset cannot be in the range of \(F\). For if \(A = F(a)\), for some \(a\), then

which is a contradiction.

Some remarks are in order. First, the proof does not use the law of excluded middle and is thus valid intuitionistically. Second, the method that is used, called diagonalisation was already present in the work of du Bois-Reymond for building real functions growing faster than any function in a given sequence of functions.

Russell analysed what happens if we apply this theorem to the case where A is the class of all classes, admitting that there is such a class. He was then lead to consider the special class of classes that do not belong to themselves

We then have

It seems indeed that Cantor was already aware of the fact that the class of all sets cannot be considered itself to be a set.

Russell communicated this problem to Frege, and his letter, together with Frege’s answer appear in van Heijenoort 1967. It is important to realise that the formulation (*) does not apply as it is to Frege’s system. As Frege himself wrote in his reply to Russell, the expression “a predicate is predicated of itself” is not exact. Frege had a distinction between predicates (concepts) and objects . A (first-order) predicate applies to an object but it cannot have a predicate as argument. The exact formulation of the paradox in Frege’s system uses the notion of the extension of a predicate \(P\), which we designate as \(\varepsilon P\). The extension of a predicate is itself an object. The important axiom V is:

This axiom asserts that the extension of \(P\) is identical to the extension of \(Q\) if and only if \(P\) and \(Q\) are materially equivalent. We can then translate Russell’s paradox (*) in Frege’s system by defining the predicate

It can then been checked, using Axiom V in a crucial way, that

and we have a contradiction as well. (Notice that for defining the predicate \(R\), we have used an impredicative existential quantification on predicates. It can be shown that the predicative version of Frege’s system is consistent (see Heck 1996 and for further refinements Ferreira 2002).

It is clear from this account that an idea of types was already present in Frege’s work: there we find a distinction between objects, predicates (or concepts), predicates of predicates, etc. (This point is stressed in Quine 1940.) This hierarchy is called the “extensional hierarchy” by Russell (1959), and its necessity was recognised by Russell as a consequence of his paradox.

As we saw above, the distinction: objects, predicates, predicate of predicates, etc., seems enough to block Russell’s paradox (and this was recognised by Chwistek and Ramsey). We first describe the type structure as it is in Principia and later in this section we present the elegant formulation due to Church 1940 based on \(\lambda\)-calculus. The types can be defined as

\(i\) is the type of individuals
\((\,)\) is the type of propositions
if \(A_1 ,\ldots ,A_n\) are types then \((A_1 ,\ldots ,A_n)\) is the type of \(n\)-ary relations over objects of respective types \(A_1 ,\ldots ,A_n\)

For instance, the type of binary relations over individuals is \((i, i)\), the type of binary connectives is \(((\,),(\,))\), the type of quantifiers over individuals is \(((i))\).

For forming propositions we use this type structure: thus \(R(a_1 ,\ldots ,a_n)\) is a proposition if \(R\) is of type \((A_1 ,\ldots ,A_n)\) and \(a_i\) is of type \(A_i\) for \(i = 1,\ldots ,n\). This restriction makes it impossible to form a proposition of the form \(P(P)\): the type of \(P\) should be of the form \((A)\), and \(P\) can only be applied to arguments of type \(A\), and thus cannot be applied to itself since \(A\) is not the same as \((A)\).

However simple type theory is not predicative: we can define an object \(Q(x, y)\) of type \((i, i)\) by

Assume that we have two individuals \(a\) and \(b\) such that \(Q(a, b)\) holds. We can define \(P(x)\) to be \(Q(x, a)\). It is then clear that \(P(a)\) holds, since it is \(Q(a, a)\). Hence \(P(b)\) holds as well. We have proved, in an impredicative way, that \(Q(a, b)\) implies \(Q(b, a)\).

Alternative simpler formulations, which retain only the notion of classes, classes of classes, etc., were formulated by Gödel and Tarski. Actually this simpler version was used by Gödel in his 1931 paper on formally undecidable propositions. The discovery of the undecidable propositions may have been motivated by a heuristic argument that it is unlikely that one can extend the completeness theorem of first-order logic to type theory (see the end of his Lecture at Königsberg 1930 in Gödel Collected Work, Volume III, Awodey and Carus 2001 and Goldfarb 2005). Tarski had a version of the definability theorem expressed in type theory (see Hodges 2008). See Schiemer and Reck 2013.

We have objects of type 0, for individuals, objects of type 1, for classes of individuals, objects of type 2, for classes of classes of individuals, and so on. Functions of two or more arguments, like relations, need not be included among primitive objects since one can define relations to be classes of ordered pairs, and ordered pairs to be classes of classes. For example, the ordered pair of individuals a, b can be defined to be \(\{\{a\},\{a,b\}\}\) where \(\{x,y\}\) denotes the class whose sole elements are \(x\) and \(y\). (Wiener 1914 had suggested a similar reduction of relations to classes.) In this system, all propositions have the form \(a(b)\), where \(a\) is a sign of type \(n+1\) and \(b\) a sign of type \(n\). Thus this system is built on the concept of an arbitrary class or subset of objects of a given domain and on the fact that the collection of all subsets of the given domain can form a new domain of the next type. Starting from a given domain of individuals, this process is then iterated. As emphasised for instance in Scott 1993, in set theory this process of forming subsets is iterated into the transfinite .

In these versions of type theory, as in set theory, functions are not primitive objects, but are represented as functional relation. The addition function for instance is represented as a ternary relation by an object of type \((i,i,i)\). An elegant formulation of the simple type theory which extends it by introducing functions as primitive objects was given by Church in 1940. It uses the \(\lambda\)-calculus notation (Barendregt 1997). Since such a formulation is important in computer science, for the connection with category theory, and for Martin-Löf type theory, we describe it in some detail. In this formulation, predicates are seen as a special kind of functions (propositional functions), an idea that goes back to Frege (see for instance Quine 1940). Furthermore, the notion of function is seen as more primitive than the notion of predicates and relations, and a function is not defined anymore as a special kind of relation. (Oppenheimer and Zalta 2011 presents some arguments against such a primitive representation of functions.) The types of this system are defined inductively as follows

there are two basic types \(i\) (the type of individuals) and \(o\) (the type of propositions)
if \(A, B\) are types then \(A \rightarrow B\), the type of functions from \(A\) to \(B\), is a type

We can form in this way the types:

which correspond to the types \((i)\) and \(((i))\) but also the new types

It is convenient to write

In this way

corresponds to the type \((A_1 ,\ldots ,A_n)\).

First-order logic considers only types of the form

Notice that

(association to the right).

For the terms of this logic, we shall not follow Church’s account but a slight variation of it, due to Curry (who had similar ideas before Church’s paper appeared) and which is presented in detail in R. Hindley’s book on type theory. Like Church, we use \(\lambda\)-calculus, which provides a general notation for functions

Here we have used the so-called BNF notation, very convenient in computing science. This gives a syntactic specification of the \(\lambda\)-terms which, when expanded, means:

every variable is a function symbol;
every juxtaposition of two function symbols is a function symbol;
every \(\lambda x.M\) is a function symbol;
there are no other function symbols.

The notation for function application \(M N\) is a little different than the mathematical notation, which would be \(M(N)\). In general,

(association to the left). The term \(\lambda x.M\) represents the function which to \(N\) associates \(M[x:=N\)]. This notation is so convenient that one wonders why it is not widely used in mathematics. The main equation of \(\lambda\)-calculus is then \((\beta\)-conversion)

which expresses the meaning of \(\lambda x.M\) as a function. We have used \(M[x:=N\)] as a notation for the value of the expression that results when \(N\) is substituted for the variable \(x\) in the matrix \(M\). One usually sees this equation as a rewrite rule \((\beta\)-reduction)

In untyped lambda calculus, it may be that such rewriting does not terminate. The canonical example is given by the term \(\Delta = \lambda x.x x\) and the application

(Notice the similarity with Russell’s paradox.) The idea of Curry is then to look at types as predicates over lambda terms, writing \(M:A\) to express that \(M\) satisfies the predicate/type \(A\). The meaning of

which justifies the following rules

In general one works with judgements of the form

where \(x_1,..., x_n\) are distinct variables, and \(M\) is a term having all free variables among \(x_1,..., x_n\). In order to be able to get Church’s system, one adds some constants in order to form propositions. Typically

represents the predicate of predicates that do not apply to themselves. This term does not have a type however, that is, it is not possible to find \(A\) such that

which is the formal expression of the fact that Russell’s paradox cannot be expressed. Leibniz equality

will be defined as

One usually writes \(\forall x[M\)] instead of \(\forall(\lambda x.M)\), and the definition of \(Q\) can then be rewritten as

This example again illustrates that we can formulate impredicative definitions in simple type theory.

The use of \(\lambda\)-terms and \(\beta\)-reduction is most convenient for representing the complex substitution rules that are needed in simple type theory. For instance, if we want to substitute the predicate \(\lambda x.Q a x\) for \(P\) in the proposition

and, using \(\beta\)-reduction,

In summary, simple type theory forbids self-application but not the circularity present in impredicative definitions.

The \(\lambda\)-calculus formalism also allows for a clearer analysis of Russell’s paradox. We can see it as the definition of the predicate

If we think of \(\beta\)-reduction as the process of unfolding a definition, we see that there is a problem already with understanding the definition of R R

In some sense, we have a non-wellfounded definition, which is as problematic as a contradiction (a proposition equivalent to its negation). One important theorem, the normalisation theorem, says that this cannot happen with simple types: if we have \(M:A\) then \(M\) is normalisable in a strong way (any sequence of reductions starting from \(M\) terminates).

For more information on this topic, we refer to the entry on Church’s simple type theory.

Russell introduced another hierarchy, that was not motivated by any formal paradoxes expressed in a formal system, but rather by the fear of “circularity” and by informal paradoxes similar to the paradox of the liar. If a man says “I am lying”, then we have a situation reminiscent of Russell’s paradox: a proposition which is equivalent to its own negation. Another informal such paradoxical situation is obtained if we define an integer to be the “least integer not definable in less than 100 words”. In order to avoid such informal paradoxes, Russell thought it necessary to introduce another kind of hierarchy, the so-called “ramified hierarchy”. The need for such a hierarchy is hinted in Appendix B of Russell 1903. Interestingly this is connected there to the question of the identity of equivalent propositions and of the logical product of a class of propositions. A thorough discussion can be found in Chapter 10 of Russell 1959. Since this notion of ramified hierarchy has been extremely influential in logic and especially proof theory, we describe it in some details.

In order to further motivate this hierarchy, here is one example due to Russell. If we say

Napoleon was Corsican.

we do not refer in this sentence to any assemblage of properties. The property “to be Corsican” is said to be predicative . If we say on the other hand

Napoleon had all the qualities of a great general

we are referring to a totality of qualities. The property “to have all qualities of a great general” is said to be impredicative .

Another example, also coming from Russell, shows how impredicative properties can potentially lead to problems reminiscent of the liar paradox. Suppose that we suggest the definition

A typical Englishman is one who possesses all the properties possessed by a majority of Englishmen.

It is clear that most Englishmen do not possess all the properties that most Englishmen possess. Therefore, a typical Englishman, according to this definition, should be untypical. The problem, according to Russell, is that the word “typical” has been defined by a reference to all properties and has been treated as itself a property. (It is remarkable that similar problems arise when defining the notion of random numbers, cf. Martin-Löf “Notes on constructive mathematics” (1970).) Russell introduced the ramified hierarchy in order to deal with the apparent circularity of such impredicative definitions. One should make a distinction between the first-order properties, like being Corsican, that do not refer to the totality of properties, and consider that the second-order properties refer only to the totality of first-order properties . One can then introduce third-order properties, that can refer to the totality of second-order property, and so on. This clearly eliminates all circularities connected to impredicative definitions.

At about the same time, Poincaré carried out a similar analysis. He stressed the importance of “predicative” classifications, and of not defining elements of a class using a quantification over this class (Poincaré 1909). Poincaré used the following example. Assume that we have a collection with elements 0, 1 and an operation + satisfying

Let us say that a property is inductive if it holds of 0 and holds for \(x+1\) if it holds for \(x\).

An impredicative, and potentially “dangerous”, definition would be to define an element to be a number if it satisfies all inductive properties. It is then easy to show that this property “to be a number” is itself inductive. Indeed, 0 is a number since it satisfies all inductive properties, and if \(x\) satisfies all inductive properties then so does \(x+1\). Similarly it is easy to show that \(x+y\) is a number if \(x,y\) are numbers. Indeed the property \(Q(z)\) that \(x+z\) is a number is inductive: \(Q\)(0) holds since \(x+0=x\) and if \(x+z\) is a number then so is \(x+(z+1) = (x+z)+1\). This whole argument however is circular since the property “to be a number” is not predicative and should be treated with suspicion.

Instead, one should introduce a ramified hierarchy of properties and numbers. At the beginning, one has only first-order inductive properties, which do not refer in their definitions to a totality of properties, and one defines the numbers of order 1 to be the elements satisfying all first-order inductive properties. One can next consider the second-order inductive properties, that can refer to the collection of first-order properties, and the numbers of order 2, that are the elements satisfying the inductive properties of order 2. One can then similarly consider numbers of order 3, and so on. Poincaré emphasizes the fact that a number of order 2 is a fortiori a number of order 1, and more generally, a number of order \(n+1\) is a fortiori a number of order \(n\). We have thus a sequence of more and more restricted properties: inductive properties of order 1, 2, … and a sequence of more and more restricted collections of objects: numbers of order 1, 2, … Also, the property “to be a number of order \(n\)” is itself an inductive property of order \(n+1\).

It does not seem possible to prove that \(x+y\) is a number of order \(n\) if \(x,y\) are numbers of order \(n\). On the other hand, it is possible to show that if \(x\) is a number of order \(n+1\), and \(y\) a number of order \(n+1\) then \(x+y\) is a number of order \(n\). Indeed, the property \(P(z)\) that “\(x+z\) is a number of order \(n\)” is an inductive property of order \(n+1: P\)(0) holds since \(x+0 = x\) is a number of order \(n+1\), and hence of order \(n\), and if \(P(z)\) holds, that is if \(x+z\) is a number of order \(n\), then so is \(x+(z+1) = (x+z)+1\), and so \(P(z+1)\) holds. Since \(y\) is a number of order \(n+1\), and \(P(z)\) is an inductive property of order \(n+1, P(y)\) holds and so \(x+y\) is a number of order \(n\). This example illustrates well the complexities introduced by the ramified hierarchy.

The complexities are further amplified if one, like Russell as for Frege, defines even basic objects like natural numbers as classes of classes. For instance the number 2 is defined as the class of all classes of individuals having exactly two elements. We again obtain natural numbers of different orders in the ramified hierarchy. Besides Russell himself, and despite all these complications, Chwistek tried to develop arithmetic in a ramified way, and the interest of such an analysis was stressed by Skolem. See Burgess and Hazen 1998 for a recent development.

Another mathematical example, often given, of an impredicative definition is the definition of least upper bound of a bounded class of real numbers. If we identify a real with the set of rationals that are less than this real, we see that this least upper bound can be defined as the union of all elements in this class. Let us identify subsets of the rationals as predicates. For example, for rational numbers \(q, P(q)\) holds iff \(q\) is a member of the subset identified as \(P\). Now, we define the predicate \(L_C\) (a subset of the rationals) to be the least upper bound of class \(C\) as:

which is impredicative: we have defined a predicate \(L\) by an existential quantification over all predicates. In the ramified hierarchy, if \(C\) is a class of first-order classes of rationals, then \(L\) will be a second-order class of rationals. One obtains then not one notion or real numbers, but real numbers of different orders 1, 2, … The least upper bound of a collection of reals of order 1 will then be at least of order 2 in general.

As we saw earlier, yet another example of an impredicative definition is given by Leibniz’ definition of equality. For Leibniz, the predicate “is equal to \(a\)” is true for \(b\) iff \(b\) satisfies all the predicates satisfied by \(a\).

How should one deal with the complications introduced by the ramified hierarchy? Russell showed, in the introduction to the second edition to Principia Mathematica , that these complications can be avoided in some cases. He even thought, in Appendix B of the second edition of Principia Mathematica , that the ramified hierarchy of natural numbers of order 1,2,… collapses at order 5 for defining the reflexive transitive closure of a relation. However, Gödel later found a problem in his argument, and indeed, it was shown by Myhill 1974 that this hierarchy actually does not collapse at any finite level. A similar problem, discussed by Russell in the introduction to the second edition to Principia Mathematica arises in the proof of Cantor’s theorem that there cannot be any injective functions from the collection of all predicates to the collection of all objects (the version of Russell’s paradox in Frege’s system that we presented in the introduction). Can this be done in a ramified hierarchy? Russell doubted that this could be done within a ramified hierarchy of predicates and this was indeed confirmed indeed later (see Chwistek 1926, Fitch 1939 and Heck 1996).

Because of these problems, Russell and Whitehead introduced in the first edition of Principia Mathematica the following reducibility axiom : the hierarchy of predicates, first-order, second-order, etc., collapses at level 1. This means that for any predicate of any order, there is a predicate of the first-order level which is equivalent to it. In the case of equality for instance, we postulate a first-order relation “\(a=b\)” which is equivalent to “\(a\) satisfies all properties that \(b\) satisfies”. The motivation for this axiom was purely pragmatic. Without it, all basic mathematical notions, like real or natural numbers are stratified into different orders. Also, despite the apparent circularity of impredicative definitions, the axiom of reducibility does not seem to lead to inconsistencies.

As noticed however first by Chwistek, and later by Ramsey, in the presence of the axiom of reducibility, there is actually no point in introducing the ramified hierarchy at all! It is much simpler to accept impredicative definitions from the start. The simple “extensional” hierarchy of individuals, classes, classes of classes, … is then enough. We get in this way the simpler systems formalised in Gödel 1931 or Church 1940 that were presented above.

The axiom of reducibility draws attention to the problematic status of impredicative definitions. To quote Weyl 1946, the axiom of reducibility “is a bold, an almost fantastic axiom; there is little justification for it in the real world in which we live, and none at all in the evidence on which our mind bases its constructions”! So far, no contradictions have been found using the reducibility axiom. However, as we shall see below, proof-theoretic investigations confirm the extreme strength of such a principle.

The idea of the ramified hierarchy has been extremely important in mathematical logic. Russell considered only the finite iteration of the hierarchy: first-order, second-order, etc., but from the beginning, the possibility of extending the ramification transfinitely was considered. Poincaré (1909) mentions the work of Koenig in this direction. For the example above of numbers of different order, he also defines a number to be inductive of order \(\omega\) if it is inductive of all finite orders. He then points out that x+y is inductive of order \(\omega\) if both \(x\) and \(y\) are. This shows that the introduction of transfinite orders can in some case play the role of the axiom of reducibility. Such transfinite extension of the ramified hierarchy was analysed further by Gödel who noticed the key fact that the following form of the reducibility axiom is actually provable : when one extends the ramified hierarchy of properties over the natural numbers into the transfinite this hierarchy collapses at level \(\omega_1\), the least uncountable ordinal (Gödel 1995, and Prawitz 1970). Furthermore, while at all levels \(\lt \omega_1\), the collection of predicates is countable, the collection of predicates at level \(\omega_1\) is of cardinality \(\omega_1\). This fact was a strong motivation behind Gödel’s model of constructible sets. In this model the collection of all subsets of the set of natural numbers (represented by predicates) is of cardinality \(\omega_1\) and is similar to the ramified hierarchy. This model satisfies in this way the Continuum Hypothesis, and gives a relative consistency proof of this axiom. (The motivation of Gödel was originally only to build a model where the collection of all subsets of natural numbers is well-ordered.)

The ramified hierarchy has been also the source of much work in proof theory. After the discovery by Gentzen that the consistency of Arithmetic could be proved by transfinite induction (over decidable predicates) along the ordinal \(\varepsilon_0\), the natural question was to find the corresponding ordinal for the different levels of the ramified hierarchy. Schütte (1960) found that for the first level of the ramified hierarchy, that is if we extend arithmetic by quantifying only over first-order properties, we get a system of ordinal strength \(\varepsilon_{\varepsilon_0}\). For the second level we get the ordinal strength \(\varepsilon_{\varepsilon_{ \varepsilon_0}}\), etc. We recall that \(\varepsilon_{\alpha}\) denotes the \(\alpha\)-th \(\varepsilon\)-ordinal number, an \(\varepsilon\)-ordinal number being an ordinal \(\beta\) such that \(\omega^{\beta} = \beta\), see Schütte (1960).

Gödel stressed the fact that his approach to the problem of the continuum hypothesis was not constructive, since it needs the uncountable ordinal \(\omega_1\), and it was natural to study the ramified hierarchy along constructive ordinals. After preliminary works of Lorenzen and Wang, Schütte analysed what happens if we proceed in the following more constructive way. Since arithmetic has for ordinal strength \(\varepsilon_0\) we consider first the iteration of the ramified hierarchy up to \(\varepsilon_0\). Schütte computed the ordinal strength of the resulting system and found an ordinal strength \(u(1)\gt \varepsilon_0\). We iterate then ramified hierarchy up to this ordinal \(u(1)\) and get a system of ordinal strength \(u(2)\gt u(1)\), etc. Each \(u(k)\) can be computed in terms of the so-called Veblen hierarchy: \(u(k+1)\) is \(\phi_{u(k)}(0)\). The limit of this process gives an ordinal called \(\Gamma_0\): if we iterate the ramified hierarchy up to the ordinal \(\Gamma_0\) we get a system of ordinal strength \(\Gamma_0\). Such an ordinal was obtained independently about the same time by S. Feferman. It has been claimed that \(\Gamma_0\) plays for predicative systems a role similar to \(\varepsilon_0\) for Arithmetic. Recent proof-theoretical works however are concerned with systems having bigger proof-theoretical ordinals that can be considered predicative (see for instance Palmgren 1995).

Besides these proof theoretic investigations related to the ramified hierarchy, much work has been devoted in proof theory to analysing the consistency of the axiom of reducibility, or, equivalently, the consistency of impredicative definitions. Following Gentzen’s analysis of the cut-elimination property in the sequent calculus, Takeuti found an elegant sequent formulation of simple type theory (without ramification) and made the bold conjecture that cut-elimination should hold for this system. This conjecture seemed at first extremely dubious given the circularity of impredicative quantification, which is well reflected in this formalism. The rule for quantifications is indeed

where \(T\) is any term predicate, which may itself involve a quantification over all predicates. Thus the formula \(A[X:=T]\) may be itself much more complex than the formula \(A(X)\).

One early result is that cut-elimination for Takeuti’s impredicative system implies in a finitary way the consistency of second-order Arithmetic. (One shows that this implies the consistency of a suitable form of infinity axiom, see Andrews 2002.) Following work by Schütte (1960b), it was later shown by W. Tait and D. Prawitz that indeed the cut-elimination property holds (the proof of this has to use a stronger proof theoretic principle, as it should be according to the incompleteness theorem.)

What is important here is that these studies have revealed the extreme power of impredicative quantification or, equivalently, the extreme power of the axiom of reducibility. This confirms in some way the intuitions of Poincaré and Russell. The proof-theoretic strength of second-order Arithmetic is way above all ramified extensions of Arithmetic considered by Schütte. On the other hand, despite the circularity of impredicative definitions, which is made so explicit in Takeuti’s calculus, no paradoxes have been found yet in second-order Arithmetic.

Another research direction in proof theory has been to understand how much of impredicative quantification can be explained from principles that are available in intuitionistic mathematics. The strongest such principles are strong forms of inductive definitions. With such principles, one can explain a limited form of an impredicative quantification, called \(\Pi_{1}^1\)-comprehension, where one uses only one level of impredicative quantification over predicates. Interestingly, almost all known uses of impredicative quantifications: Leibniz equality, least upper bound, etc., can be done with \(\Pi_{1}^1\)-comprehension. This reduction of \(\Pi_{1}^1\)-comprehension was first achieved by Takeuti in a quite indirect way, and was later simplified by Buchholz and Schütte using the so-called \(\Omega\)-rule. It can be seen as a constructive explanation of some restricted, but nontrivial, uses of impredicative definitions.

Type theory can be used as a foundation for mathematics, and indeed, it was presented as such by Russell in his 1908 paper, which appeared the same year as Zermelo’s paper, presenting set theory as a foundation for mathematics.

It is clear intuitively how we can explain type theory in set theory: a type is simply interpreted as a set, and function types \(A \rightarrow B\) can be explained using the set theoretic notion of function (as a functional relation, i.e. a set of pairs of elements). The type \(A \rightarrow o\) corresponds to the powerset operation.

The other direction is more interesting. How can we explain the notion of sets in terms of types? There is an elegant solution, due to A. Miquel, which complements previous works by P. Aczel (1978) and which has also the advantage of explaining non necessarily well-founded sets a la Finsler. One simply interprets a set as a pointed graph (where the arrow in the graph represents the membership relation). This is very conveniently represented in type theory, a pointed graph being simply given by a type A and a pair of elements

We can then define in type theory when two such sets \(A, a, R\) and \(B, b, S\) are equal: this is the case iff there is a bisimulation \(T\) between \(A\) and \(B\) such that \(Tab\) holds. A bisimulation is a relation

such that whenever \(Txy\) and \(Rxu\) hold, there exists \(v\) such that \(Tuv\) and \(Syv\) hold, and whenever \(Txy\) and \(Ryv\) hold, there exists \(u\) such that \(Tuv\) and \(Rxu\) hold. We can then define the membership relation: the set represented \(B, b, S\) is a member of the set represented by \(A, a, R\) iff there exists \(a_1\) such that \(Ra_1a\) and \(A, a_1, R\) and \(B, b, S\) are bisimilar.

It can then be checked that all the usual axioms of set theory extensionality, power set, union, comprehension over bounded formulae (and even antifoundation, so that the membership relation does not need to be well-founded) hold in this simple model. (A bounded formula is a formula where all quantifications are of the form \(\forall x \in a\ldots\) or \(\exists x \in a\ldots\)). In this way it can been shown that Church’s simple type theory is equiconsistent with the bounded version of Zermelo’s set theory.

There are deep connections between type theory and category theory. We limit ourselves to presenting two applications of type theory to category theory: the constructions of the free cartesian closed category and of the free topos (see the entry on category theory for an explanation of “cartesian closed” and “topos”).

For building the free cartesian closed category, we extend simple type theory with the type 1 (unit type) and the product type \(A \times B\), for \(A, B\) types. The terms are extended by adding pairing operations and projections and a special element of type 1. As in Lambek and Scott 1986, one can then define a notion of typed conversions between terms, and show that this relation is decidable. One can then show (Lambek and Scott 1986) that the category with types as objects and as morphisms from \(A\) to \(B\) the set of closed terms of type \(A \rightarrow B\) (with conversion as equality) is the free cartesian closed category. This can be used to show that equality between arrows in this category is decidable.

The theory of types of Church can also be used to build the free topos. For this we take as objects pairs \(A,E\) with \(A\) type and \(E\) a partial equivalence relation, that is a closed term \(E:A \rightarrow A \rightarrow o\) which is symmetric and transitive. We take as morphisms between \(A, E\) and \(B, F\) the relations \(R:A\rightarrow B\rightarrow o\) that are functional that is such that for any \(a:A\) satisfying \(E a a\) there exists one, and only one (modulo \(F)\) element \(b\) of \(B\) such that \(F b b\) and \(R a b\). For the subobject classifier we take the pair \(o, E\) with \(E:o\rightarrow o\rightarrow o\) defined as

One can then show that this category forms a topos, indeed the free topos.

It should be noted that the type theory in Lambek and Scott 1986 uses a variation of type theory, introduced by Henkin and refined by P. Andrews (2002) which is to have an extensional equality as the only logical connective, i.e. a polymorphic constant

and to define all logical connectives from this connective and constants \(T, F : o\). For instance, one defines

The equality at type \(o\) is logical equivalence.

One advantage of the intensional formulation is that it allows for a direct notation of proofs based on \(\lambda\)-calculus (Martin-Löf 1971 and Coquand 1986).

We have seen the analogy between the operation A \(\rightarrow\) A \(\rightarrow\) o on types and the powerset operation on sets. In set theory, the powerset operation can be iterated transfinitely along the cumulative hierarchy. It is then natural to look for analogous transfinite versions of type theory.

One such extension of Church’s simple type theory is obtained by adding universes (Martin-Löf 1970). Adding a universe is a reflection process: we add a type \(U\) whose objects are the types considered so far. For Church’s simple type theory we will have

and, furthermore, \(A\) is a type if \(A:U\). We can then consider types such as

and functions such as

The function id takes as argument a “small” type \(A:U\) and an element \(x\) of type \(A\), and outputs an element of type \(A\). More generally if \(T(A)\) is a type under the assumption \(A:U\), one can form the dependent type

That \(M\) is of this type means that \(M A:T(A)\) whenever \(A:U\). We get in this way extensions of type theory whose strength is similar to the one of Zermelo’s set theory (Miquel 2001). More powerful form of universes are considered in (Palmgren 1998). Miquel (2003) presents a version of type theory of strength equivalent to the one of Zermelo-Fraenkel.

One very strong form of universe is obtained by adding the axiom \(U:U\). This was suggested by P. Martin-Löf in 1970. J.Y. Girard showed that the resulting type theory is inconsistent as a logical system (Girard 1972). Though it seems at first that one could directly reproduce Russell’s paradox using a set of all sets, such a direct paradox is actually not possible due to the difference between sets and types. Indeed the derivation of a contradiction in such a system is subtle and has been rather indirect (though, as noticed in Miquel 2001, it can now be reduced to Russell’s paradox by representing sets as pointed graphs). J.Y. Girard first obtained his paradox for a weaker system. This paradox was refined later (Coquand 1994 and Hurkens 1995). (The notion of pure type system, introduced in Barendregt 1992, is convenient for getting a sharp formulation of these paradoxes.) Instead of the axiom \(U:U\) one assumes only

if \(T(A) : U [A:U]\). Notice the circularity, indeed of the same kind as the one that is rejected by the ramified hierarchy: we define an element of type \(U\) by quantifying over all elements of \(U\). For instance the type

will be the type of the polymorphic identity function. Despite this circularity, J.Y. Girard was able to show normalisation for type systems with this form of polymorphism. However, the extension of Church’s simple type theory with polymorphism is inconsistent as a logical system, i.e. all propositions (terms of type o) are provable.

J.Y. Girard’s motivation for considering a type system with polymorphism was to extend Gödel’s Dialectica (Gödel 1958) interpretation to second-order arithmetic. He proved normalisation using the reducibility method, that had been introduced by Tait (1967) while analysing Gödel 1958. It is quite remarkable that the circularity inherent in impredicativity does not result in non-normalisable terms. (Girard’s argument was then used to show that cut-elimination terminates in Takeuti’s sequent calculus presented above.) A similar system was introduced independently by J. Reynolds (1974) while analysing the notion of polymorphism in computer science.

Martin-Löf’s introduction of a type of all types comes from the identification of the concept of propositions and types, suggested by the work of Curry and Howard. It is worth recalling here his three motivating points:

Russell’s definition of types as ranges of significance of propositional functions
the fact that one needs to quantify over all propositions (impredicativity of simple type theory)
identification of proposition and types

Given (1) and (2) we should have a type of propositions (as in simple type theory), and given (3) this should also be the type of all types. Girard’s paradox shows that one cannot have (1),(2) and (3) simultaneously. Martin-Löf’s choice was to take away (2), restricting type theory to be predicative (and, indeed, the notion of universe appeared first in type theory as a predicative version of the type of all types). The alternative choice of taking away (3) is discussed in Coquand 1986.

The connections between type theory, set theory and category theory gets a new light through the work on Univalent Foundations (Voevodsky 2015) and the Axiom of Univalence . This involves in an essential way the extension of type theory described in the previous section, in particular dependent types, the view of propositions as types, and the notion of universe of types. These development are also relevant for discussing the notion of structure, the importance of which was for instance emphasized in Russell 1959.

Martin-Löf 1975 [1973] introduced a new basic type \(\mathbf{Id}_A (a,b)\), if \(a\) and \(b\) are in the type \(A\), which can be thought as the type of equality proofs of the element \(a\) and \(b\). An important feature of this new type is that it can be iterated, so that we can consider the type \(\mathbf{Id}_{\mathbf{Id}_A (a,b)}(p,q)\) if \(p\) and \(q\) are of type \(\mathbf{Id}_A (a,b)\). If we think of a type as a special kind of set, it is natural to conjecture that such a type of equality proofs is always inhabited for any two equality proofs \(p\) and \(q\). Indeed, intuitively, there seems to be at most an equality proof between two elements \(a\) and \(b\). Surprisingly, Hofmann and Streicher 1996 designed a model of dependent type theory where this is not valid, that is a model where they can be different proofs that two elements are equal. In this model, a type is interpreted by a groupoid and the type \(\mathbf{Id}_A (a,b)\) by the set of isomorphisms between \(a\) and \(b\), set which may have more than one element. The existence of this model has the consequence that it cannot be proved in general in type theory that an equality type has at most one element. This groupoid interpretation has been generalized in the following way, which gives an intuitive interpretation of the identity type. A type is interpreted by a topological space , up to homotopy, and a type \(\mathbf{Id}_A (a,b)\) is interpreted by the type of paths connecting \(a\) and \(b\). (See Awodey et al. 2013 and [HoTT 2013, Other Internet Resources].)

Voevodsky 2015 introduced the following stratification of types. (This stratification was motivated in part by this interpretation of a type as a topological space, but can be understood directly without reference to this interpretation.) We say that a type \(A\) is a proposition if we have \(\mathbf{Id}_A (a,b)\) for any element \(a\) and \(b\) of \(A\) (this means that the type \(A\) has at most one element). We say that a type \(A\) is a set if the type \(\mathbf{Id}_A (a,b)\) is a proposition for any element \(a\) and \(b\) of \(A\). We say that a type \(A\) is a groupoid if the type \(\mathbf{Id}_A (a,b)\) is a set for any element \(a\) and \(b\) of \(A\). The justification of this terminology is that it can be shown, only using the rules of type theory, that any such type can indeed be seen as a groupoid in the usual categorical sense, where the objects are the elements of this type, the set of morphisms between \(a\) and \(b\) being represented by the set \(\mathbf{Id}_A (a,b)\). The composition is the proof of transitivity of equality, and the identity morphism is the proof of reflexivity of equality. The fact that each morphism has an inverse corresponds to the fact that identity is a symmetric relation. This stratification can then be extended and we can define when a type is a 2-groupoid, 3-groupoid and so on. In this view, type theory appears as a vast generalization of set theory , since a set is a particular kind of type.

Voevodsky 2015 introduces also a notion of equivalence between types, notion which generalizes in an uniform way the notions of logical equivalence between propositions, bijection between sets, categorical equivalence between groupoids, and so on. We say that a map \(f:A\rightarrow B\) is an equivalence if, for any element \(b\) in \(B\) the type of pairs \(a,p\) where \(p\) is of type \(\mathbf{Id}_B (f a,b)\), is a proposition and is inhabited. This expresses in a strong way that an element in \(B\) is the image of exactly one element in \(A\), and if \(A\) and \(B\) are sets, we recover the usual notion of bijection between sets. (In general if \(f:A\rightarrow B\) is an equivalence, then we have a map \(B\rightarrow A\), which can be thought of as the inverse of \(f\).) It can be shown for instance that the identity map is always an equivalence. Let \(\text{Equiv}(A,B)\) be the type of pairs \(f,p\) where \(f:A\rightarrow B\) and \(p\) is a proof that \(f\) is an equivalence. Using the fact that the identity map is an equivalence we have an element of \(\text{Equiv}(A,A)\) for any type \(A\). This implies that we have a map

and the Axiom of Univalence states that this map is an equivalence. In particular, we have the implication

and so if there is an equivalence between two small types then these types are equal.

This Axiom can be seen as a strong form of the extensionality principle. It indeed generalizes the Axiom of propositional extensionality mentioned by Church 1940, which states that two logically equivalent propositions are equal. Surprisingly, it also implies the Axiom of function extensionality , Axiom 10 in Church 1940, which states that two pointwise equal functions are equal (Voevodsky 2015). It also directly implies that two isomorphic sets are equal, that two categorically equivalent groupoids are equal, and so one.

This can be used to give a formulation of the notion of transport of structures (Bourbaki 1957) along equivalences. For instance, let \(M A\) be the type of monoid structures on the set \(A\): this is the type of tuples \(m, e, p\) where \(m\) is a binary operation on \(A\) and \(e\) an element of \(A\) and \(p\) a proof that these elements satisfy the usual monoid laws. The rule of substitution of equal by equal takes the form

If there is a bijection between \(A\) and \(B\) they are equal by the Axiom of Univalence, and we can use this implication to transport any monoid structure of \(A\) in a monoid structure of \(B\).

Both Russell 1919 and Russell 1959 stress the importance of the notion of structure. For instance, in Chapter VI of Russell 1919, it is noticed that two similar relations essentially have the same properties, and hence have the same “structure”. (The notion of “similarity” of relations was introduced in Russell 1901.) We can also use this framework to refine Russell’s discussions on the notion of structure. For instance, let Monoid be the type of pairs \(A,p\) where \(p\) is an element of \(M A\). Two such pairs \(A,p\) and \(B,q\) are isomorphic if there exists a bijection \(f\) from \(A\) to \(B\) such that \(q\) is equal to the transport of structure of \(p\) along \(f\). A consequence of the Axiom of Univalence is that two isomorphic elements of the type Monoid are equal, and hence shares the same properties. Notice that such a general transport of properties is not possible when structures are formulated in a set theoretic framework. Indeed, in a set theoretic framework, it is possible to formulate properties using the membership relations, for instance the property that the carrier set of the structure contains the natural number \(0\), property that is not preserved in general by isomorphisms. Intuitively, the set theoretical description of a structure is not abstract enough since we can talk about the way this structure is built up. This difference between set theory and type theory is yet another illustration of the characterization by J.Reynolds 1983 of a type structure as a “syntactical discipline for enforcing level of abstraction”.

Aczel, P., 1978, “The type theoretic interpretation of constructive set theory”, Logic Colloquium ’77 , Amsterdam: North-Holland, 55–66.
Andrews, P., 2002, An introduction to mathematical logic and type theory: to truth through proof (Applied Logic Series: Volume 27), Dordrecht: Kluwer Academic Publishers, second edition.
Awodey, S. and Carus, A.W., 2001, “Carnap, completeness and categoricity: the Gabelbarkeitssatz of 1928”, Erkenntnis , 54: 145–171.
––– and Pelayo, A., Warren, M. 2013, “The Axiom of Univalence in Homotopy Type Theory”, Notices of the American Mathematical Society , 60(9): 1157–1164.
Barendregt, H., 1997, “The impact of the lambda calculus in logic and computer science”, Bulletin of Symbolic Logic , 3(2): 181–215.
–––, 1992, Lambda calculi with types. Handbook of logic in computer science , Volume 2, Oxford, New York: Oxford University Press, 117–309.
Bell, J.L., 2012, “Types, Sets and Categories”, in Akihiro Kanamory Handbook of the History of Logic. Volume 6: Sets and Extensions in the Twentieth Century , Amsterdam: North Holland.
Bourbaki, N., 1958, Théorie des Ensembles , 3rd edition, Paris: Hermann.
de Bruijn, N. G., 1980, “A survey of the project AUTOMATH”, in To H. B. Curry: essays on combinatory logic, lambda calculus and formalism , London-New York: Academic Press, 579–606.
Burgess J. P. and Hazen A. P., 1998, “Predicative Logic and Formal Arithmetic Source,” Notre Dame J. Formal Logic , 39(1): 1–17.
Buchholz, W. and K. Schütte, 1988, Proof theory of impredicative subsystems of analysis (Studies in Proof Theory: Monograph 2), Naples: Bibliopolis.
Church, A., 1940, “A formulation of the simple theory of types,” Journal of Symbolic Logic , 5: 56–68
–––, 1984, “Russell’s theory of identity of propositions,” Philosophia Naturalis , 21: 513–522
Chwistek, L., 1926, “Ueber die Hypothesen der Mengelehre,” Mathematische Zeitschrift , 25: 439–473
–––, 1948, The Limits of Science: Outline of Logic and of the Methodology of the Exact Sciences , London: Routledge and Kegan Paul.
Coquand, T., 1986, “An analysis of Girard’s paradox,” Proceedings of the IEEE Symposium on Logic in Computer Science , 227–236.
–––, 1994, “A new paradox in type theory,” Stud. Logic Found. Math. (Volume 134), Amsterdam: North-Holland, 555–570.
du Bois-Reymond, P., 1875, “Ueber asymptotische Werthe, infintaere Appproximationen und infitaere Aufloesung von Gleichungen,” Mathematische Annalen , 8: 363–414.
Feferman, S., 1964, “Systems of predicative analysis,” Journal of Symbolic Logic , 29: 1–30.
Ferreira, F. and Wehmeier, K., 2002, “On the consistency of the Delta-1-1-CA fragment of Frege’s Grundgesetze,” Journal of Philosophic Logic , 31: 301–311.
Fitch, F. B., 1964, “The hypothesis that infinite classes are similar,” Journal of Symbolic Logic , 4: 159–162.
Girard, J.Y., 1972, Interpretation fonctionelle et eleimination des coupures dans l’arithmetique d’ordre superieure , These d’Etat, Université Paris 7.
Goldfarb, Warren, 2005. “On Godel’s way in: The influence of Rudolf Carnap.” Bulletin of Symbolic Logic 11(2): 185–193.
Gödel, K., 1995, Collected Works Volume III, Unpublished Essays and Lectures , Oxford: Oxford University Press, 1995.
–––, 1931, “Über formal untentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte fü Mathematik und Physik , 38: 173–198.
–––, 1944, “Russell’s mathematical logic,” in The philosophy of Bertrand Russell , P. A. Schilpp (ed.), Evanston: Northwestern University Press, 123–153.
–––, 1958, “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes,”, Dialectica , 12: 280–287.
Heck, R., Jr., 1996, “The consistency of predicative fragments of Frege’s Grundgesetze der Arithmetik,” History and Philosophy of Logic , 17(4): 209–220.
van Heijenoort, 1967, From Frege to Gödel. A source book in mathematical logic 1879–1931 , Cambridge, MA: Harvard University Press.
Hindley, R., 1997, Basic Simple Type Theory , Cambridge: Cambridge University Press.
Hodges, W., 2008, “Tarski on Padoa’s Method: a test case for understanding logicians of other traditions”, in Logic, Navya-Nyāya and Applications: Homage to Bimal Krishna Matilal , Mihir K. Chakraborti et al. (eds.), London: College Publications, pp. 155–169
Hofmann, M. and Streicher, Th. 1996, “The Groupoid interpretation of Type Theory,” in Twenty-five years of constructive type theory (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 83–111.
Howard, W. A., 1980, “The formulae-as-types notion of construction,” in To H. B. Curry: essays on combinatory logic, lambda calculus and formalism , London, New York: Academic Press, 480–490.
Hurkens, A. J. C., 1995, “A simplification of Girard’s paradox. Typed lambda calculi and applications,” in Lecture Notes in Computer Science (Volume 902), Berlin: Springer: 266–278.
Lambek, J., 1980. “From \(\lambda\)-calculus to Cartesian Closed Categories” in To H.B. Curry: Essays on Combinatory Logic, \(\lambda\)-calculus and Formalism , J. Seldin and J. Hindley (eds.), London, New York: Academic Press. pp. 375–402.
Lambek, J. and Scott, P. J., 1986, Introduction to higher order categorical logic (Cambridge Studies in Advanced Mathematics: Volume 7), Cambridge: Cambridge University Press; reprinted 1988.
Lawvere, F. W. and Rosebrugh, R., 2003, Sets for mathematics , Cambridge: Cambridge University Press.
Martin-Löf, P., 1970, Notes on constructive mathematics , Stockholm: Almqvist & Wiksell.
–––, 1971, A Theory of Types , Technical Report 71–3, Stockholm: Stockholm University.
–––, 1998, “An intuitionistic theory of types,” in Twenty-five years of constructive type theory (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 127–172.
–––, 1975 [1973], “An intuitionistic theory of types: Predicative Part,” in Logic Colloquium ’73 (Proceedings of the Logic Colloquium, Bristol 1973) (Studies in Logic and the Foundations of Mathematics: Volume 80), H.E. Rose and J.C. Shepherdson (eds.), Amsterdam: North-Holland, 73–118.
Myhill, J., 1974, “The Undefinability of the Set of Natural Numbers in the Ramified Principia”, in Bertrand Russell’s Philosophy , G. Nakhnikian (ed.), London: Duckworth, 19–27.
Miquel, A., 2001, Le Calcul des Constructions implicite: syntaxe et sémantique , Thèse de doctorat, Université Paris 7.
–––, 2003, “A strongly normalising Curry-Howard correspondence for IZF set theory,” in Computer science Logic (Lecture Notes in Computer Science, 2803), Berlin: Springer: 441–454.
Oppenheimer, P. and E. Zalta, 2011, “Relations Versus Functions at the Foundations of Logic: Type-Theoretic Considerations”, Journal of Logic and Computation, 21: 351–374.
Palmgren, Erik, 1998, “On universes in type theory,” in Twenty-five years of Constructive Type Theory (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 191–204.
Poincaré, 1909, “H. La logique de l’infini” Revue de metaphysique et de morale , 17: 461–482.
Prawitz, D., 1967, “Completeness and Hauptsatz for second order logic”, Theoria , 33: 246–258.
–––, 1970, “On the proof theory of mathematical analysis,” in Logic and value (Essays dedicated to Thorild Dahlquist on his fiftieth birthday), Filosofiska Studier (Filosof. Föreningen och Filosof. Inst.), No. 9, Uppsala: Uppsala University, 169–180.
Quine, W., 1940, “Review of Church ‘A formulation of the simple theory of types’,” Journal of Symbolic Logic , 5: 114.
Ramsey, F.P., 1926, “The foundations of mathematics,” Proceedings of the London Mathematical Society , s2–25 (1), 338–384.
Russell, B., 1901, “Sur la logique des relations avec des applications a la théorie des séries”, Revue de Mathématique , 7: 115–136, 137–148.
–––, 1903, The Principles of Mathematics , Cambridge: Cambridge University Press.
–––, 1908, “Mathematical logic as based on the theory of types,” American Journal of Mathematics , 30: 222–262.
–––, 1919, Introduction to Mathematical Philosophy , London: George Allen and Unwin.
–––, 1959, My philosophical development , London, New York: Routledge.
Russell, B. and Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 volumes), Cambridge: Cambidge University Press.
Reynolds, J., 1974, “Towards a theory of type structure,” in Programming Symposium (Lecture Notes in Computer Science: Volume 19), Berlin: Springer, 408–425.
–––, 1983, “Types, Abstraction and Parametric Polymorphism,” Proceedings of the IFIP 9th World Computer Congress , Paris, 513–523.
–––, 1984, “Polymorphism is not set-theoretic. Semantics of data types,” Lecture Notes in Computer Science (Volume 173), Berlin: Springer, 145–156.
–––, 1985, “Three approaches to type structure. Mathematical foundations of software development,” in Lecture Notes in Computer Science (Volume 185), Berlin: Springer, 97–138.
Schiemer, G. and Reck, E.H., 2013, “Logic in the 1930s: Type Theory and Model Theory,” The Bulletin of Symbolic Logic , 19(4): 433–472.
Schütte, K., 1960, Beweistheorie , Berlin: Springer-Verlag.
–––, 1960b, “Syntactical and Semantical Properties of Simple Type Theory,” Journal of Symbolic Logic , 25: 305–326.
Scott, D., 1993 “A type-theoretic alternative to ISWIM, CUCH, OWHY,” Theoretical Computer Science , 121: 411–440.
Skolem, T., 1970, Selected works in logic , Jens Erik Fenstad (ed.), Oslo: Universitetsforlaget.
Tait, W. W., 1967, “Intensional interpretations of functionals of finite type,” Journal of Symbolic Logic , 32 (2): 198–212.
Takeuti, G., 1955 “On the fundamental conjecture of GLC: I”, Journal of the Mathematical Society of Japan , 7: 249–275.
–––, 1967, “Consistency proofs of subsystems of classical analysis,” The Annals of Mathematics (Second Series), 86 (2): 299–348.
Tarski, A., 1931, “Sur les ensembles definissables de nombres reels I,” Fundamenta Mathematicae , 17: 210–239.
Urquhart, A., 2003, “The Theory of Types,” in The Cambridge Companion to Bertrand Russell , Nicholas Griffin (ed.), Cambridge: Cambridge University Press.
Voevodsky, V., 2015, “An experimental library of formalized mathematics based on univalent foundations,” Mathematical Structures in Computer Science , 25: 1278–1294, available online .
Wiener, N., 1914, “A simplification of the logic of relations,” Proceedings of the Cambridge Philosophical Society , 17: 387–390.
Weyl, H., 1946, “Mathematics and Logic,” American Mathematical Monthly , 53: 2–13.
Zermelo, E., 1908, “Untersuchungen über die Grundlagen der Mengenlehre I,” Mathematische Annalen , 65: 261–281.

How to cite this entry . Preview the PDF version of this entry at the Friends of the SEP Society . Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers , with links to its database.

Kubota, K., 2018, “ Foundations of Mathematics. Genealogy and Overview ,” manuscript, draft of March 27, 2018.
[HoTT 2013], Homotopy Type Theory: Univalent Foundations of Mathematics , Institute for Advanced Study.

Accessibility

Support SEP

Mirror sites.

View this site from another server:

Info about mirror sites

Library of Congress Catalog Data: ISSN 1095-5054

Institute for Logic, Language and Computation

News and Events: Open Positions

Please note that this newsitem has been archived, and may contain outdated information or links.

PhD position in Homotopy Type Theory

The Institute for Logic, Language and Computation (ILLC) at the University of Amsterdam is an interdisciplinary research institute where logicians, mathematicians, computer scientists, cognitive scientists, and philosophers collaborate. It offers an international research environment with world-class faculty in all of its areas of specialisation. The institute is located in the beautiful city of Amsterdam, renowned for its historic system of canals, its laid-back cosmopolitan atmosphere, and its excellent connections to the rest of Europe and the world.

The ILLC invites applications for a PhD position in Homotopy Type Theory, under supervison of Dr Benno van den Berg.

Project description

The position is part of a research project, The Computational Content of Homotopy Type Theory. The project is funded by the Netherlands Organisation for Scientific Research (NWO) under the TOP2 scheme.

The aim of the project is to develop a computational understanding of Homotopy Type Theory by using concepts from category theory and realizability.

The successful applicant will be asked to perform the following tasks:

to complete and defend a PhD thesis within the official appointment duration of four years;
to regularly present intermediate research results at international workshops and conferences, and to publish them in conference proceedings and journals;
to participate in and to contribute to the organisation of research activities and events at the ILLC, such as conferences, workshops, and colloquia.

All PhD candidates at the ILLC furthermore are expected to make a small contribution to the institute's educational mission, e.g., by working as teaching assistants for courses in their area of expertise and by assisting with the supervision of student research projects.

The PhD position will be embedded into the ILLC's PhD Programme , which offers training in a range of transferable skills that are relevant for a successful research career.

Requirements

Applicants should hold, or expect to obtain by the end of the academic year 2016/17, a Master's degree in a relevant discipline, such as Computer Science, Mathematics, or Logic.

Applicants furthermore should possess:

an excellent academic track record;
a serious interest in pursuing fundamental research of an interdisciplinary nature;
good writing and presentation skills;
good social and organisational skills;
full professional proficiency in spoken and written English.

Prior exposure to relevant topics such as Category Theory or Type Theory will be considered an advantage.

Further information

For further information about this position, please feel free to contact:

Benno van den Berg

Appointment

The successful candidate will be employed by the Faculty of Science of the University of Amsterdam on a fixed-term full-time contract (38 hours per week).

The appointment is intended to be for a period of four years. The initial contract will be for 18 months. This will be extended with a further 30 months after a positive evaluation.

The gross monthly salary amounts to €2,191 during the first year, rising to €2,801 during the fourth year, excl. 8% holiday allowance and 8,3% annual allowance. The Collective Labour Agreement for Dutch Universities is applicable.

The preferred starting date is 1 September 2017 (some deviation from this date is possible, subject to mutual agreement).

Job application

Your application should include the following information (in one single PDF file, using your surname as the file name):

a cover letter, including a statement of your research interests and a motivation for why you are applying for this position (at most 2 pages);
a detailed curriculum vitae;
a list of a all Master-level modules you have taken, with an official transcript of grades;
a link to a writing sample available online, such as a Master's thesis, a term paper, or a publication;
the names, affiliations, and email addresses of two or (at most) three people we can contact for letters of reference for you.

Applications must be submitted no later than 15 March 2017 to [email protected] . Please state both your name and vacancy number 17-058 in the subject field.

15-819 Homotopy Type Theory

Course information.

This is a graduate research seminar on Homotopy Type Theory (HoTT), a recent enrichment of Intuitionistic Type Theory (ITT) to include "higher-dimensional" types. The dimensionality of a type refers to the structure of its paths , the constructive witnesses to the equality of pairs of elements of a type, which themselves form a type, the identity type . In general a type is infinite dimensional in the sense that it exhibits non-trivial structure at all dimensions: it has elements, paths between elements, paths between paths, and so on to all finite levels. Moreover, the paths at each level exhibit the algebraic structure of a (higher) groupoid , meaning that there is always the "null path" witnessing reflexivity, the "inverse" path witnessing symmetry, and the "concatenation" of paths witnessing transitivity such that group-like laws hold "up to higher homotopy". Specifically, there are higher-dimensional paths witnessing the associative, unital, and inverse laws for these operations. Altogether this means that a type is a weak ∞-groupoid .

The significance of the higher-dimensional structure of types lies in the concept of a type-indexed family of types . Such families exhibit the structure of a fibration , which means that a path between two indices "lifts" to a transport mapping between the corresponding instances of the family that is, in fact, an equivalence. Thinking of paths as constructive witnesses for equality, this amounts to saying that equal indices give rise to equivalent types, and hence, by univalence, equal elements of the universe in which the family is valued. Thus, for example, if we think of the interval I as a type with two endpoints connected by a path, then an I-indexed family of types must assign equivalent types to the endpoints. In contrast the type B of booleans consists of two disconnected points, so that a B-indexed family of types may assign unrelated types to the two points of B. Similarly, mappings from I into another type A must assign connected points in A to the endpoints of the interval, whereas mappings from B into A are free to assign arbitrary points of A to the two booleans. These preservation principles are central to the structure of HoTT.

In many cases the path structure of a type becomes trivial beyond a certain dimension, called the level of the type. By convention the levels start at -2 and continue through -1, 0, 1, 2, and so on indefinitely. At the lowest, -2, level, the path structure of a type is degenerate in that there is an element to which all other elements are equal; such a type is said to be contractible , and is essentially a singleton. At the next higher level, -1, the type of paths between any two elements is contractible (level -2), which means that any two elements are equal, if there are any elements at all; such as type is a sub-singleton or h-proposition . At the next level, 0, the type of paths between paths between elements is contractible, so that any two elements are equal "in at most one way"; such a type is a set whose types of paths (equality relations) are all h-prop's. Continuing in this way, types of level 1 are groupoids , those of level 2 are 2-groupoids , and so on for all finite levels.

ITT is capable of expressing only sets, which are types of level 0. Such types may have elements, and two elements may be considered equal in at most one way. A large swath of (constructive) mathematics may be formulated using only sets, and hence is amenable to representation in ITT. Computing applications, among others, require more than just sets. For example, it is often necessary to suppress distinctions among elements of a type so as to avoid over-specification; this is called proof irrelevance . Traditionally ITT has been enriched with an ad hoc treatment of proof irrelevance by introducing a universe of "propositions" with no computational content. In HoTT such propositions are types of level -1, requiring no special treatment or distinction. Such types arise by propositional truncation of a type to render degenerate the path structure of a type above level -1, ensuring that any two elements are equal in the sense of having a path between them.

Propositional truncation is just one example of a higher inductive type , one that is defined by specifying generators not only for its elements, but also for its higher-dimensional paths. The propositional truncation of a type is one that includes all of the elements of the type, and, in addition, a path between any two elements, rendering them equal. It is a limiting case of a quotient type in which only certain paths between elements are introduced, according to whether they are deemed to be related. Higher inductive types also permit the representation of higher-dimensional objects, such as the spheres of arbitrary dimension, as types, simply by specifying their "connectivity" properties. For example, the topological circle consists of a base point and a path starting and ending at that point, and the topological disk may be thought of as two half circles that are connected by a higher path that "fills in" the interior of the circle. Because of their higher path structure, such types are not sets, and neither are constructions such as the product of two circles.

The univalence axiom implies that an equivalence between types (an "isomorphism up to isomorphism") determines a path in a universe containing such types. Since two types can be equivalent in many ways (for example, there can be distinct bijections between two sets), univalence gives rise to types that are not sets, but rather are of a higher level, or dimension. The univalence axiom is mathematically efficient because it allows us to treat equivalent types as equal, and hence interchangeable in all contexts. In informal settings such identifications are often made by convention; in formal homotopy type theory such identifications are true equations.

Requirements

The class is open to any PhD student, and to undergraduate or other graduate students with permission of the instructor. The course will be self-contained. A well-prepared student will have some background in formal logic and some prior experience with simple type theory.

No letter grades will be assigned for this class. It should not be taken with the expectation of fulfilling any course requirement or degree credit. Full participation is required of all students to pass the course.

All students are required to complete assigned homework in a timely manner (no later than one week after assigned) for review by the teaching assistant. (Please send your homework as a PDF to Favonia.)

All students are required to participate in the weekly note-taking process. Each week two students are responsible for preparing typeset course notes to be distributed before lecture each Monday.

Please register yourself as a student on the Piazza web page linked above.

Academic Integrity

Unless explicitly instructed otherwise, all homework and exam work is to be solely your own , and may not be shared with or borrowed from any other person in the course. You are not permitted to draw upon assignments or solutions from previous instances of the course, nor to use course materials (such as assignments or programs) obtained from any web site or other external source in preparing your work.

You may discuss homework assignments with other students in the class, but you must adhere to the whiteboard policy . At the end of discussion the whiteboard must be erased, and you must not transcribe or take with you anything that has been written on the board during your discussion. You must be able to reproduce the results solely on your own after any such discussion.

Schedule of Lectures

To get the latest versions of notes, please check out the repository favonia/hott-notes on GitHub.

An Introduction to Dependent Type Theory

Conference paper
First Online: 01 January 2002
Cite this conference paper

Gilles Barthe 5 &
Thierry Coquand 6

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2395))

Included in the following conference series:

International Summer School on Applied Semantics

1014 Accesses

4 Citations

Functional programming languages often feature mechanisms that involve complex computations at the level of types. These mechanisms can be analyzed uniformly in the framework of dependent types, in which types may depend on values. The purpose of this chapter is to give some background for such an analysis.

We present here precise theorems, that should hopefully help the reader to understand to which extent statements like “introducing dependent types in a programming language implies that type checking is undecidable”, are justified.

Type System
Type Theory
Dependent Type
Functional Programming
Typing Rule

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Available as PDF
Read on any device
Instant download
Own it forever
Compact, lightweight edition
Dispatched in 3 to 5 business days
Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview. Download preview PDF.

A. Abel. On relating type theories and set theories. In T. Coquand, P. Dybjer, B. Nordström, and J. Smith, editors, Proceedings of TYPES’99 , volume 1956 of Lecture Notes in Computer Science , pages 1–20. Springer-Verlag, 2000.

Chapter Google Scholar

A. Abel. Termination checking with types. Technical Report 0201, Institut fur Informatik, Ludwig-Maximilians-Universität München, 2002.

Google Scholar

A. Abel and T. Altenkirch. A predicative analysis of structural recursion. Journal of Functional Programming , 12(1):1–41, January 2002.

P. Aczel. The Type Theoretic Interpretation of Constructive Set Theory. In A. MacIntyre, A. Pacholski, and J. Paris, editors, Proceedings of Logic Colloqium 77 , Studies in Logic and the Foundations of Mathematics, pages 55–66. North-Holland, 1978.

P. Aczel. Frege structures and the notions of proposition, truth and set. In J. Barwise, H. J. Keisler, and K. Kunen, editors, Proceedings of the Kleene Symposium , volume 101 of Studies in Logic and the Foundations of Mathematics , pages 31–59. North-Holland, Amsterdam, 1980.

P. Aczel. On Relating Type Theories and Set Theories. In T. Altenkirch, W. Naraschewski, and B. Reus, editors, Proceedings of TYPES’98 , volume 1657 of Lecture Notes in Computer Science , pages 1–18. Springer-Verlag, 1999.

T. Altenkirch and C. McBride. Generic programming within dependently typed programming. In J. Gibbons and J. Jeuring, editors, Proceedings of WCGP’02 . Kluwer Academic Publishers, 2002.

R. Amadio and S. Coupet-Grimal. Analysis of a guard condition in type theory. In M. Nivat, editor, Proceedings of FOSSACS’98 , volume 1378 of Lecture Notes in Computer Science , pages 48–62. Springer-Verlag, 1998.

R. M. Amadio and L. Cardelli. Subtyping recursive types. ACM Transactions on Programming Languages and Systems , 15(4):575–631, September 1993.

D. Aspinall. Subtyping with singleton types. In L. Pacholski and J. Tiuryn, editors, Proceedings of CSL’94 , volume 933 of Lecture Notes in Computer Science , pages 1–15. Springer-Verlag, 1994.

P. Audebaud. Partial Objects in the Calculus of Constructions. In Proceedings of LICS’91 , pages 86–95. IEEE Computer Society Press, 1991.

L. Augustsson. Cayenne: A language with dependent types. In Proceedings of ICFP’98 , pages 239–250. ACM Press, 1998.

L. Augustsson and M. Carlsson. An exercise in dependent types: A well-typed interpreter. In Informal Proceedings of DTP’99 , 1999.

R. Backhouse, P. Jansson, J. Jeuring, and L. Meertens. Generic programming— an introduction. In S. D. Swierstra, P. R. Henriques, and J. N. Oliveira, editors, Proceedings of AFP’98 , volume 1608 of Lecture Notes in Computer Science , pages 28–115. Springer-Verlag, 1999.

S. van Bakel, L. Liquori, S. Ronchi della Rocca, and P. Urzyczyn. Comparing cubes of typed and type assignment systems. Annals of Pure and Applied Logic , 86(3):267–303, July 1997.

H. Barendregt. Introduction to Generalised Type Systems. Journal of Functional Programming , 1(2):125–154, April 1991.

H. Barendregt. Lambda calculi with types. In S. Abramsky, D. Gabbay, and T. Maibaum, editors, Handbook of Logic in Computer Science , pages 117–309. Oxford Science Publications, 1992. Volume 2.

H. Barendregt and H. Geuvers. Proof assistants using dependent type systems. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning , volume II, chapter 18, pages 1149–1238. Elsevier Publishing, 2001.

G. Barthe. The semi-full closure of Pure Type Systems. In L. Brim, J. Gruska, and J. Zlatuska, editors, Proceedings of MFCS’98 , volume 1450 of Lecture Notes in Computer Science , pages 316–325. Springer-Verlag, 1998.

G. Barthe. Type-Checking Injective Pure Type Systems. Journal of Functional Programming , 9(6):675–698, 1999.

Article MATH MathSciNet Google Scholar

G. Barthe and T. Coquand. On the equational theory of non-normalizing pure type systems. Journal of Functional Programming , 200x. To appear.

G. Barthe, M. J. Frade, E. Giménez, L. Pinto, and T. Uustalu. Type-based termination of recursive definitions. Mathematical Structures in Computer Science , 2002. To appear.

G. Barthe and M.H. Sørensen. Domain-free pure type systems. Journal of Functional Programming , 10(5):417–452, September 2000.

D. Basin and S. Matthews. Logical Frameworks. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic , volume 9. Kluwer Academic Publishers, 2002.

L.S. van Benthem Jutting. Typing in pure type systems. Information and Computation , 105(1):30–41, July 1993.

L.S. van Benthem Jutting, J. McKinna, and R. Pollack. Checking algorithms for pure type systems. In H. Barendregt and T. Nipkow, editors, Proceedings of TYPES’93 , volume 806 of Lecture Notes in Computer Science , pages 19–61. Springer-Verlag, 1994.

G. Betarte. Dependent Record Types and Algebraic Structures in Type Theory . PhD thesis, Department of Computer Science, Chalmers Tekniska Högskola, 1998.

G. Betarte and A. Tasistro. Extension of Martin-Löf’s type theory with record types and subtyping. In G. Sambin and J. Smith, editors, Twenty-five Years of Constructive Type Theory . Oxford University Press, 1998.

R. Bird. Introduction to Functional Programming using Haskell . Prenctice Hall, 2 edition, 1998.

F. Blanqui, J.-P. Jouannaud, and M. Okada. Inductive Data Type Systems. Theoretical Computer Science , 272(1/2):41–68, February 2002.

D. Bolignano. Towards a mechanization of cryptographic protocol verification. In O. Grumberg, editor, Proceedings of CAV’97 , volume 1254 of Lecture Notes in Computer Science , pages 131–142. Springer-Verlag, 1997.

M. Brandt and F. Henglein. Coinductive axiomatization of recursive type equality and subtyping. Fundamenta Informaticae , 33(4):309–338, April 1998.

W. Buchholz, S. Feferman, W. Pohlers, and W. Sieg. Iterated Inductive Definitions and Subsystems of Analysis: Recent Proof-Theoretical Results , volume 897 of Lectures Notes in Mathematics . Springer-Verlag, 1981.

L. Cardelli. A polymorphic lambda-calculus with Type:Type. Technical Report 10, SRC, May 1986.

L. Cardelli. Phase distinctions in type theory. Unpublished Mansucript, January 1988.

L. Cardelli. Structural subtyping and the notion of power type. In Proceedings of POPL’88 , pages 70–79. ACM Press, 1988.

C. Coquand. Agda. See http://www.cs.chalmers.se/~catarina/agda .

C. Coquand. Computation in Type Theory . PhD thesis, Department of Computing Science, Chalmers University of Technology, 1996.

T. Coquand. Metamathematical Investigations of a Calculus of Constructions. In P. Odifreddi, editor, Logic and Computer Science , pages 91–122. Academic Press, 1990.

T. Coquand. An algorithm for testing conversion in type theory. In G. Huet and G. Plotkin, editors, Logical Frameworks , pages 255–279. Cambridge University Press, 1991.

T. Coquand. Pattern matching with dependent types. In B. Nordström, editor, Informal proceedings of Logical Frameworks’92 , pages 66–79, 1992.

T. Coquand. An algorithm for type-checking dependent types. Science of Computer Programming , 26(1–3):167–177, May 1996.

T. Coquand and P. Dybjer. Inductive definitions and type theory: an introduction (preliminary version). In P.S. Thiagarajan, editor, Proceedings of FSTTCS’94 , volume 880 of Lecture Notes in Computer Science , pages 60–76. Springer-Verlag, 1994.

T. Coquand and H. Herbelin. A-translation and looping combinators in pure type systems. Journal of Functional Programming , 4(1):77–88, January 1994.

T. Coquand and G. Huet. The Calculus of Constructions. Information and Computation , 76(2/3):95–120, February/March 1988.

T. Coquand and C. Paulin. Inductively defined types. In P. Martin-Löf and G. Mints, editors, Proceedings of COLOG’88 , volume 417 of Lecture Notes in Computer Science , pages 50–66. Springer-Verlag, 1988.

T. Coquand, R. Pollack, and M. Takeyama. Modules as Dependently Typed Records. Manuscript, 2002.

J. Courant. Un calcul de modules pour les systèmes de types purs . PhD thesis, Ecole Normale Supérieure de Lyon, 1998.

G. Cousineau and M. Mauny. The functional approach to programming . Cambridge University Press, 1998.

K. Crary. Sound and complete elimination of singleton kinds. In R. Harper, editor, Proceedings of TIC’00 , volume 2071 of Lecture Notes in Computer Science , pages 1–26. Springer-Verlag, 2001.

K. Crary and S. Weirich. Resource bound certification. In Proceedings of POPL’00 , pages 184–198. ACM Press, 2000.

P. Dybjer. Inductive sets and families in Martin-Löf’s type theory and their set-theoretic semantics. In G. Huet and G. Plotkin, editors, Logical Frameworks , pages 280–306. Cambridge University Press, 1991.

P. Dybjer. Inductive families. Formal Aspects of Computing , 6:440–465, 1994.

Article MATH Google Scholar

P. Dybjer. Representing inductively defined sets by well-orderings in Martin-Löf’s type theory. Theoretical Computer Science , 176(1–2):329–335, April 1997.

P. Dybjer. A general formulation of simultaneous inductive-recursive definitions in type theory. Journal of Symbolic Logic , 65(2):525–549, June 2000.

H. Geuvers. Logics and type systems . PhD thesis, University of Nijmegen, 1993.

H. Geuvers. Induction is not derivable in second order dependent type theory. In S. Abramsky, editor, Proceedings of TLCA’01 , Lecture Notes in Computer Science, pages 166–181. Springer-Verlag, 2001.

H. Geuvers and M.J. Nederhof. A modular proof of strong normalisation for the Calculus of Constructions. Journal of Functional Programming , 1(2):155–189, April 1991.

H. Geuvers, E. Poll, and J. Zwanenburg. Safe proof checking in type theory with Y. In J. Flum and M. Rodríguez-Artalejo, editors, Proceedings of CSL’99 , volume 1683 of Lecture Notes in Computer Science , pages 439–452. Springer-Verlag, 1999.

H. Geuvers and B. Werner. On the Church-Rosser property for expressive type systems and its consequence for their metatheoretic study. In Proceedings of LICS’94 , pages 320–329. IEEE Computer Society Press, 1994.

J. Giesl, C. Walther, and J. Brauburger. Termination analysis for functional programs. In W. Bibel and P. Schmitt, editors, Automated Deduction-A Basis for Applications , volume 3 of Applied Logic Series , pages 135–164. Kluwer Academic Publishers, 1998.

E. Giménez. Un calcul de constructions infinies et son application à la vérification de systèmes communicants . PhD thesis, Ecole Normale Superieure de Lyon, 1996.

E. Giménez. Structural recursive definitions in Type Theory. In K.G. Larsen, S. Skyum, and G. Winskel, editors, Proceedings of ICALP’98 , volume 1443 of Lecture Notes in Computer Science , pages 397–408. Springer-Verlag, 1998.

J-Y. Girard. Interprétation fonctionnelle et élimination des coupures dans l’arithmétique d’ordre supérieur . Thèse d’Etat, Université Paris 7, 1972.

J.-Y. Girard, Y. Lafont, and P. Taylor. Proofs and Types . Number 7 in Tracts in Theoretical Computer Science. Cambridge University Press, 1989.

B. Grégoire and X. Leroy. A compiled implementation of strong reduction. In Proceedings of ICFP’02 . ACM Press, 2002.

B. Grobauer. Cost recurrences for DML programs. In Proceedings of ICFP’01 , pages 253–264. ACM Press, September 2001.

P. Hancock and A. Setzer. Interactive programs in dependent type theory. In P. Clote and H. Schwichtenberg, editors, Proceedings of CSL’00 , volume 1862 of Lecture Notes in Computer Science , pages 317–331. Springer-Verlag, 2000.

R. Harper, F. Honsell, and G. Plotkin. A framework for defining logics. Journal of the ACM , 40(1):143–184, January 1993.

R. Harper, J. C. Mitchell, and E. Moggi. Higher-order modules and the phase distinction. In Proceedings of POPL’90 , pages 341–354. ACM Press, 1990.

R. Harper and J.C. Mitchell. On the type structure of Standard ML. ACM Transactions on Programming Languages and Systems , 15(2):211–252, April 1993.

R. Hinze. A new approach to generic functional programming. In Proceedings of POPL’00 , pages 119–132. ACM Press, 2000.

J. G. Hook and D. J. Howe. Impredicative strong existential equivalent to type:type. Technical Report TR86-760, Cornell University, Computer Science Department, June 1986.

J. Hughes, L. Pareto, and A. Sabry. Proving the correctness of reactive systems using sized types. In Proceedings of POPL’96 , pages 410–423. ACM Press, 1996.

A. Hurkens. A Simplification of Girard’s Paradox. In M. Dezani-Ciancaglini and G. Plotkin, editors, Proceedings of TLCA’ 95 , volume 902 of Lecture Notes in Computer Science , pages 266–278. Springer-Verlag, 1995.

P. Jansson and J. Jeuring. PolyP—a polytypic programming language extension. In Proceedings of POPL’97 , pages 470–482. ACM Press, 1997.

S. Jha, J. Palsberg, and T. Zhao. Efficient type matching. In M. Nielsen and U. Engberg, editors, Proceedings of FOSSACS 2002 , volume 2303 of Lecture Notes in Computer Science , pages 187–204. Springer-Verlag, 2002.

M. P. Jones. Type classes with functional dependencies. In G. Smolka, editor, Proceedings of ESOP’00 , volume 1782 of Lecture Notes in Computer Science , pages 230–244, 2000.

J.-P. Jouannaud and M. Okada. Abstract data type systems. Theoretical Computer Science , 173(2):349–391, February 1997.

D. Kozen, J. Palsberg, and M. Schwartzback. Efficient recursive subtyping. Mathematical Structures in Computer Science , 5(1):113–125, March 1995.

B. Lampson and R. Burstall. Pebble, a kernel language for modules and abstract data types. Information and Computation , 76(2/3):278–346, February/March 1988.

C.-S. Lee, N. D. Jones, and A. M. Ben-Amram. The size-change principle for program termination. In Proceedings of POPL’01 , pages 81–92. ACM Press, 2001.

X. Leroy. A modular module system. Journal of Functional Programming , 10(3):269–303, May 2000.

G. Longo and E. Moggi. Constructive natural deduction and its ‘ w -set’ interpretation. Mathematical Structures in Computer Science , 1(2):215–254, July 1991.

Z. Luo. Computation and Reasoning: A Type Theory for Computer Science . Number 11 in International Series of Monographs on Computer Science. Oxford University Press, 1994.

Z. Luo. Coercive subtyping. Journal of Logic and Computation , 9(1):105–130, February 1999.

D. MacQueen. Using dependent types to express modular structure. In Proceedings of POPL’86 , pages 277–286. ACM Press, 1986.

L. Magnusson. The implementation of ALF: a proof editor based on Martin-Löf’s monomorphic type theory with explicit substitution . PhD thesis, Department of Computer Science, Chalmers University, 1994.

P. Martin-Löf. Hauptsatz for the intuitionistic theory of iterated inductive definitions. In J. E. Fenstad, editor, Proceedings 2nd Scandinavian Logic Symposium , volume 63 of Studies in Logic and the Foundations of Mathematics , pages 179–216. North-Holland, Amsterdam, 1971.

P. Martin-Löf. A theory of types. Technical Report, Stockholm University, February 1971.

P. Martin-Löf. An intuitionistic theory of types. Unpublished Manuscript, 1972.

P. Martin-Löf. Intuitionistic Type Theory , volume 1 of Studies in Proof Theory . Bibliopolis, Naples, 1984.

P. Martin-Löf. Constructive mathematics and computer programming. In C. A. R. Hoare and J. C. Shepherdson, editors, Mathematical Logic and Programming Languages , pages 167–184. Prentice-Hall, 1985.

C. McBride. Dependently typed functional programs and their proofs . PhD thesis, University of Edinburgh, 2000.

C. McBride. Faking It (Simulating Dependent Types in Haskell). Journal of Functional Programming , 2002. To appear.

N. P. Mendler. Inductive types and type constraints in second-order lambda calculus. In Proceedings of LICS’87 , pages 30–36. IEEE Computer Society Press, 1987.

N. P. Mendler. Inductive types and type constraints in the second-order lambda calculus. Annals of Pure and Applied Logic , 51(1–2):159–172, March 1991.

R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences , 17:348–375, 1978.

R. Milner, M. Tofte, and R. Harper. The Definition of Standard ML . The MIT Press, 1991.

R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML (Revised) . The MIT Press, 1997.

A. Miquel. The implicit calculus of constructions. In S. Abramsky, editor, Proceedings of TLCA’01 , volume 2044 of Lecture Notes in Computer Science , pages 344–359. Springer-Verlag, 2001.

A. Miquel. Le Calcul des Constructions implicite: syntaxe et sémantique . PhD thesis, Université Paris 11, 2001.

J. C. Mitchell and G. D. Plotkin. Abstract types have existential type. ACM Transactions on Programming Languages and Systems , 10(3):470–502, July 1988.

G. C. Necula. Proof-carrying code. In Proceedings of POPL’97 , pages 106–119. ACM Press, 1997.

G. C. Necula and P. Lee. Efficient representation and validation of logical proofs. In Proceedings of LICS’98 , pages 93–104, 1998.

R. Nederpelt, H. Geuvers, and R. de Vrijer, editors. Selected Papers on Automath , volume 133 of Studies in Logic and the Foundations of Mathematics . North-Holland, 1994.

M. Neubauer, P. Thiemann, M. Gasbichler, and M. Sperber. Functional logic overloading. In Proceedings of POPL’02 , pages 233–244. ACM Press, 2002.

B. Nordström. Terminating general recursion. BIT , 28(3):605–619, 1988.

B. Nordström, K. Petersson, and J. Smith. Programming in Martin-Löf’s Type Theory. An Introduction . Number 7 in International Series of Monographs on Computer Science. Oxford University Press, 1990.

J. Palsberg and T. Zhao. Efficient and flexible matching of recursive types. Information and Computation , 171:364–387, November 2001.

L. Pareto. Types for crash prevention . PhD thesis, Department of Computing, Chalmers Tekniska Högskola, 2000.

C. Paulin-Mohring. Inductive definitions in the system Coq. Rules and properties. In M. Bezem and J.F. Groote, editors, Proceedings of TLCA’ 93 , volume 664 of Lecture Notes in Computer Science , pages 328–345. Springer-Verlag, 1993.

C. Paulin-Mohring. Définitions Inductives en Theorie des Types d’Ordre Superieur . Habilitation à diriger les recherches, Université Claude Bernard Lyon I, 1996.

L. C. Paulson. ML for the Working Programmer . Cambridge University Press, 1996.

L.C. Paulson. The inductive approach to verifying cryptographic protocols. Journal of Computer Security , 6(1/2):85–128, 1998.

S. Peyton Jones and E. Meijer. Henk: a typed intermediate language. Appeared as Technical Report BCCS-97-03, Computer Science Department, Boston College, 1997.

H. Pfeifer and H. Rueß. Polytypic abstraction in type theory. In R. Backhouse and T. Sheard, editors, Informal Proceedings of WGP’98 . Department of Computing Science, Chalmers University, June 1998.

H. Pfeifer and H. Rueß. Polytypic proof construction. In Y. Bertot, G. Dowek, H. Hirshowitz, C. Paulin, and L. Théry, editors, Proceedings of TPHOLs’99 , volume 1690 of Lecture Notes in Computer Science , pages 55–72. Springer-Verlag, 1999.

F. Pfenning. Elf: a meta-language for deductive systems. In A. Bundy, editor, Proceedings of CADE-12 , volume 814 of Lecture Notes in Artificial Intelligence , pages 811–815. Springer-Verlag, 1994.

F. Pfenning. Logical Frameworks. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning , volume II, chapter 17, pages 1063–1147. Elsevier Publishing, 2001.

F. Pfenning and C. Paulin. Inductively Defined Types in the Calculus of Constructions. In M. Main, A. Melton, M. Mislove, and D. Schmidt, editors, Proceedings of MFPS’89 , volume 442 of Lecture Notes in Computer Science , pages 209–228. Springer-Verlag, 1989.

R. Pollack. Typechecking in pure type systems. In B. Nordström, editor, Informal proceedings of Logical Frameworks’92 , pages 271–288, 1992.

R. Pollack. The Theory of LEGO: A Proof Checker for the Extended Calculus of Constructions . PhD thesis, University of Edinburgh, 1994.

R. Pollack. Dependently typed records for representing mathematical structures. In M. Aagard and J. Harrison, editors, Proceedings of TPHOLs’00 , volume 1869 of Lecture Notes in Computer Science , pages 462–479. Springer-Verlag, 2000.

M. B. Reinhold. Typechecking is undecidable’ TYPE’ is a type. Technical Report MIT/LCS/TR-458, Massachusetts Institute of Technology, December 1989.

D. Rémy. Using, Understanding, and Unraveling the OCaml Language—From Practice to Theory and vice versa. This volume.

J. W. Roorda. Pure Type Systems for Functional Programming. Master’s thesis, Department of Computer Science, University of Utrecht, 2000.

C. Russo. Types For Modules . PhD thesis, University of Edinburgh, 1998.

A. Salvesen and J. Smith. The Strength of the Subset Type in Martin-Löf’s Type Theory. In Proceedings of LICS’88 , pages 384–391. IEEE Computer Society Press, 1988.

D. Scott. Constructive validity. In M. Laudet, D. Lacombe, L. Nolin, and M. Schützenberger, editors, Proceedings of Symposium on Automatic Demonstration , volume 125 of Lecture Notes in Mathematics , pages 237–275. Springer-Verlag, 1970.

P. Severi. Type Inference for Pure Type Systems. Information and Computation , 143(1):1–23, May 1998.

Z. Shao, B. Saha, V. Trifonov, and N. Papaspyrou. A type system for certified binaries. In Proceedings of POPL’02 , pages 217–232. ACM Press, 2002.

M. H. Sørensen and P. Urzyczyn. Lectures on the Curry-Howard Isomorphism. Available as DIKU Rapport 98/14, 1998.

M. Stefanova and H. Geuvers. A simple set-theoretic semantics for the Calculus of Constructions. In S. Berardi and M. Coppo, editors, Proceedings of TYPES’95 , volume 1158 of Lecture Notes in Computer Science , pages 249–264. Springer-Verlag, 1996.

C. A. Stone and R. Harper. Deciding Type Equivalence with Singleton Kinds. In Proceedings of POPL’00 , pages 214–227. ACM Press, 2000.

M. D. G. Swaen. Weak and strong sum elimination in intuitionistic type theory . PhD thesis, Faculty of Mathematics and Computer Science, University of Amsterdam, 1989.

W. W. Tait. Constructive reasoning. In Proceedings of the Third International Congress in Logic, Methodology and Philosophy of Science , pages 185–199. North-Holland Publishing, 1968.

S. Thompson. Haskell. The Craft of Functional Programming . Addison-Wesley, 1996.

D. Walker. A Type System for Expressive Security Policies. In Proceedings of POPL’00 , pages 254–267. ACM Press, 2000.

B. Werner. Sets in Types, Types in Sets. In M. Abadi and T. Ito, editors, Proceedings of TACS’97 , volume 1281 of Lecture Notes in Computer Science , pages 530–546. Springer-Verlag, 1997.

H. Xi. Dependent types in practical programming . PhD thesis, Department of Computer Science, Carnegie-Mellon University, 1998.

H. Xi. Dead Code Elimination through Dependent Types. In G. Gupta, editor, Proceedings of PADL’99 , volume 1551, pages 228–242. Springer-Verlag, 1999.

H. Xi and R. Harper. A Dependently Typed Assembly Language. In Proceedings of ICFP’01 , pages 169–180. ACM Press, 2001.

H. Xi and F. Pfenning. Eliminating array bound checking through dependent types. In Proceedings of PLDI’98 , pages 249–257. ACM Press, 1998.

H. Xi and F. Pfenning. Dependent types in practical programming. In Proceedings of POPL’99 , pages 214–227. ACM Press, 1999.

Download references

Author information

Authors and affiliations.

INRIA Sophia-Antipolis, France

Gilles Barthe

Institutionen för Datavetenskap, Chalmers Tekniska Högskola, Göteborg, Sweden

Thierry Coquand

You can also search for this author in PubMed Google Scholar

Editor information

Editors and affiliations.

Projet Lemme, INRIA Sophia-Antipolis, 2004 Route des Lucioles, BP 93, 06902, Sophia Antipolis Cedex, France

Department of Computing Science, Chalmers University of Technology, 412 96, Göteborg, Sweden

Peter Dybjer

Departamento de Matemática, Universidade do Minho, Campus de Gualtar, 4710-057, Braga, Portugal

Departamento de Informática, Universidade do Minho, Campus de Gualtar, 4710-057, Braga, Portugal

João Saraiva

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper.

Barthe, G., Coquand, T. (2002). An Introduction to Dependent Type Theory. In: Barthe, G., Dybjer, P., Pinto, L., Saraiva, J. (eds) Applied Semantics. APPSEM 2000. Lecture Notes in Computer Science, vol 2395. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45699-6_1

Download citation

DOI : https://doi.org/10.1007/3-540-45699-6_1

Published : 20 September 2002

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-540-44044-4

Online ISBN : 978-3-540-45699-5

eBook Packages : Springer Book Archive

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Publish with us

Policies and ethics

Find a journal
Track your research

Type A and Type B Personality Theory

Type C, Type D

Reviewed by Psychology Today Staff

You know the "type:" So-called “Type A” personalities are hard-charging, determined to compete and to win. Combining traits such as drive and impatience, Type A was once thought to be related to heart disease—an association that has since been challenged. “Type B” was proposed as the more easygoing, tolerant personality , in contrast to Type A.

More recently, the concept of “Type D” (for “distressed”) personality has been studied by psychologists, leading to new explorations of personality-health associations.

Despite the popularity of personality-type concepts, personality scientists say that thinking in terms of distinct types is an oversimplified approach to personality.

Type A, Type B, and Type C

Type A personality (or Type A Behavior) was originally described not by personality psychologists but by cardiologists, who thought that people who showed such personalities were at greater risk of cardiovascular disease. Type B personality was conceived as a less-intense personality type . A “Type C” was later proposed as a predictor of cancer risk. There is now ample reason to doubt that these supposed personality types are in fact correlated with disease progression.

Type A has been described as a behavioral pattern involving impatience and a sense of time-related pressure, irritability, and a competitive drive.

Physicians Meyer Friedman and R.H. Rosenman originated the concept in the 1950s after reportedly observing a connection between heart disease in patients and certain personality characteristics.

Individuals whose personality traits resonate with the “Type A” description—including characteristics like hostility—could potentially experience interpersonal difficulties as a result. But the more striking claims about Type A personality, namely that it is linked to heart disease, have been undermined by subsequent research as well as revelations about the role of tobacco industry funding in research on Type A.

Recently, psychologists have argued that “Type A” does not actually appear to be a category of its own, distinct from other personalities. As with other proposed “types,” someone who might have been called “Type A” can instead be thought of as having a collection of various personality traits, such as competitiveness and impatience, on which they rate relatively high.

Type B personality was proposed as a complement to Type A: a personality that lacked Type A’s hard-driving, irritable features.

In the 1980s, researchers described a “Type C cancer-prone behavior pattern” involving the suppression of one’s needs and negative emotions, compliance, and unassertiveness. They defined it as the “polar opposite” of the Type A pattern (whereas Type B entailed a lack of Type A traits). Subsequent work challenged the hypothesis that characteristics such as negative emotion suppression play an important role in cancer survival.

Type D—the D stands for “distressed”—is described as a combination of being inhibited in social situations and tending to experience negative emotions. The concept of Type D is distinct from Types A, B, and C, which have been defined based on characteristics such as high or low assertiveness and hostility. But as with the other "types," researchers who have assessed traits associated with Type D are interested in their potential connections to physical health.

Type D personality is a term for the combination of negative affectivity and social inhibition. Negative affectivity involves a tendency to experience negative states such as worry, irritability, and unhappiness. Social inhibition is gauged based on a person's agreement with statements like "I find it hard to start a conversation" and "I am a closed kind of person."

Early research suggested a possible connection between Type D traits and poorer outcomes for those with coronary heart disease, but follow-up work by other scientists failed to find supportive evidence for that link. Some evidence suggests measures of Type D characteristics are associated with certain psychological difficulties, including symptoms of insomnia and depression .

The negative affectivity factor of Type D was found to be related to the Big Five trait of neuroticism , while the social inhibition factor was associated with lower extroversion .

A purely Biomedical model of health and disease may be inadequate, needing to be replaced by a Biopsychosocial model, but let's keep in mind that "Bio" appears in both.

Learning your A, B, and especially C's in relationships might help you have longer-lasting, healthier, and more balanced connections.

The greatest gift we can give anyone this holiday season is our best self.

Have you been under a lot of stress lately? There is a very important sense in which you do not know the answer to that question. This has some useful implications.

Lessons from a success story.

Is your partner preoccupied with orderliness, perfectionism, and control? They may have Obsessive-Compulsive Personality Disorder.

How to identify and integrate our weaknesses into our strengths, both musically and in our lives.

Find a Therapist
Find a Treatment Center
Find a Psychiatrist
Find a Support Group
Find Teletherapy
United States
Brooklyn, NY
Chicago, IL
Houston, TX
Los Angeles, CA
New York, NY
Portland, OR
San Diego, CA
San Francisco, CA
Seattle, WA
Washington, DC
Asperger's
Bipolar Disorder
Chronic Pain
Eating Disorders
Passive Aggression
Personality
Goal Setting
Positive Psychology
Stopping Smoking
Low Sexual Desire
Relationships
Child Development
Therapy Center NEW
Diagnosis Dictionary
Types of Therapy

Understanding what emotional intelligence looks like and the steps needed to improve it could light a path to a more emotionally adept world.

Coronavirus Disease 2019
Affective Forecasting
Neuroscience

IMAGES

(PDF) Introduction to Type Theory
Is Type and Temperament the Same?
Martin-Löf type theory.
[Solved] Type Theory for Beginners
Eysenck's Theory of Personality
(PDF) Type Theory Handbook

VIDEO

What does a Probability Theory PhD Qualifying Exam look like?
Peter Dybjer: Intuitionistic Type Theory (Lecture II)
Type Theory Foundations 4.3
Type Theory Foundations 4.1
Philip Merry: The Synchro In the Room
Awodey, Algebraic Type Theory

COMMENTS

Taichi Uemura
Homotopy type theory as internal languages of diagrams of ∞-logoses. 2022. arXiv:2212.02444; ∞-type theories (joint with Hoang Kim Nguyen) ... arXiv:1701.07937; PhD Thesis. Abstract and Concrete Type Theories. Institute for Logic, Language and Computation, University of Amsterdam, 9 July, 2021. abstract pdf UvA DARE. Other documents ...
PhD studentship in homotopy type theory and univalent foundations
Syntax and semantics of type theories, Formalization and mechanization of results from mathematics and computer science in univalent foundations / two-level type theory, Design and implementation of domain-specific type theories, Univalence principle and its applications. The PhD student should have knowledge in some of the following areas ...
Type Theory and Formal Proof
Type theory is a fast-evolving field at the crossroads of logic, computer science and mathematics. This gentle step-by-step introduction is ideal for graduate students and researchers who need to understand the ins and outs of the mathematical machinery, the role of logical rules therein, the essential contribution of definitions and the decisive nature of well-structured proofs.
Postdoctoral Position in HoTT at the University of San Diego
Posted on 20 January 2021 by Mike Shulman. The University of San Diego invites applications for a postdoctoral research fellowship in homotopy type theory beginning Fall 2021, or earlier if desired. This is a two-year position with potential extension to a third year, funded by the second AFOSR MURI grant for HoTT, entitled "Synthetic and ...
Type theory
In mathematics and theoretical computer science, a type theory is the formal presentation of a specific type system. 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 have been proposed as foundations are Alonzo Church's typed λ-calculus and Per Martin-Löf's ...
PhD in Homotopy Type Theory
PhD in Homotopy Type Theory. Deadline: Friday 15 April 2022. Faculty/Services: Faculty of Science. Educational level: Master. Function type: PhD position. Closing date: 15 April 2022. Vacancy number: 8411. Do you have the technical skills and the passion for science to conduct cutting-edge research at the intersection of mathematics and ...
PDF A General Framework for the Semantics of Type Theory
of type theory: every type theory has a bi-initial model; every model of a type theory has its internal language; the category of theories over a type theory is bi-equivalent to a full sub-2-category of the 2-category of models of the type theory. 1 Introduction One of the key steps in the semantics of type theory and logic is to estab-
Introduction: Modern Perspectives in Type Theoretical Semantics
Dependent record types and algebraic structures in type theory. PhD thesis, Chalmers University of Technology. Google Scholar Betarte, G., & Tasistro, A. (1998). Extension of Martin-Löf's type theory with record types and subtyping. In G. Sambin & J. Smith (eds.), Twenty-five Years of Constructive Type Theory. Oxford: Oxford University Press.
Type Theory with Records: From Perception to Communication
The course introduces TTR, a Type Theory with Records, as a framework for natural language grammar and interaction. We follow Cooper (in preparation) in taking a dialogical view of semantics. The course covers the formal foundations of TTR as well as TTR accounts of perception, intensionality, information exchange, grammar (syntax and semantics ...
PDF TYPE THEORIES IN CATEGORY THEORY
We use boxes to distinguish type theory or cat-egory theory notations from natural language text, e.g. "we combine a term a with a term b to get a term a b ". 2. BACKGROUND AND MOTIVATION Remark 2.1. The notion of substitution in type theory is the process of replacing a variable with a term. We sometimes refer to the action of replacement ...
An Overview of Type Theories
Pure type systems arise as a generalisation of simply typed lambda calculus. The contemporary development of mathematics has renewed the interest in type theories, as they are not just the object of mere historical research, but have an active role in the development of computational science and core mathematics. It is worth exploring some of them in depth, particularly predicative Martin-Löf ...
PhD Thesis
Towards a practical programming language based on dependent type theory. PhD thesis, Chalmers University of Technology and Göteborg University, 2007. [pdf, bib] Dependent type theories have a long history of being used for theorem proving. One aspect of type theory which makes it very powerful as a proof language is that it mixes deduction ...
Type Theory
1. Paradoxes and Russell's Type Theories. The theory of types was introduced by Russell in order to cope with some contradictions he found in his account of set theory and was introduced in "Appendix B: The Doctrine of Types" of Russell 1903. This contradiction was obtained by analysing a theorem of Cantor that no mapping.
PhD position in Homotopy Type Theory
PhD position in Homotopy Type Theory. The Institute for Logic, Language and Computation (ILLC) at the University of Amsterdam is an interdisciplinary research institute where logicians, mathematicians, computer scientists, cognitive scientists, and philosophers collaborate. It offers an international research environment with world-class ...
15-819 Homotopy Type Theory
Synopsis. This is a graduate research seminar on Homotopy Type Theory (HoTT), a recent enrichment of Intuitionistic Type Theory (ITT) to include "higher-dimensional" types. The dimensionality of a type refers to the structure of its paths, the constructive witnesses to the equality of pairs of elements of a type, which themselves form a type ...
PDF CS6180: Introduction to Constructive Type Theory
methods that did not appeal to all constructive logicians. This resulted in a type theory much richer than Martin-L of type theory as we will see, but Agda and Coq basically use a 1998 \intensional" version of Martin-L of type theory [102]. At Cornell, some core type theory concepts are taught in the graduate programming language
PDF Introduction to Type Theory
The lecture was meant as an introduction to typed -calculus for PhD. students that have some (but possibly not much) familiarity with logic or functional programming. The lecture consisted of 5 hours of lecturing, using a beamer ... 3.Simple Type Theory: \Curry" type assignment, principle type algorithm and normalization 4.Polymorphic type ...
Full article: Simple Type Theory is not too Simple: Grothendieck's
2.1 Isabelle/HOL and Simple Type Theory. Isabelle/HOL [Citation 22] is a proof assistant for higher-order logic—Church's simple type theory [Citation 8]—and is therefore based on the typed λ-calculus with Boolean and function types.A Boolean-valued function is a predicate, which yields a simple typed set theory that is expressive enough to express abstract mathematics, as we demonstrate ...
PDF Type Theory & Functional Programming
system for type theory, developing examples of both programs and proofs as we go along. These tend to be short, illustrating the construct just introduced - chapter 6 contains many more examples. The system of type theory is complex, and in chapter which follows we explore a number of diﬀerent aspects of the theory. We prove certain results
An Introduction to Dependent Type Theory
Weak and strong sum elimination in intuitionistic type theory. PhD thesis, Faculty of Mathematics and Computer Science, University of Amsterdam, 1989. Google Scholar W. W. Tait. Constructive reasoning. In Proceedings of the Third International Congress in Logic, Methodology and Philosophy of Science, pages 185-199. North-Holland Publishing, 1968.
PhD course
The goal of the type theory seminar is to keep up with current state of the art research in type theory and application of type theory. As such, the goal of attending the seminar is to discuss current trends in type theory, relate application and theory across wide ranging areas, apply state of the art techniques and identify application in new ...
PDF Introduction to Type Theory
The lecture was meant as an introduction to types -calculus for PhD. students that have some (but possibly not much) familiarity with logic or functional ... 3.Simple Type Theory: \Curry" type assignment, principle type algorithm and normalization 4.Polymorphic type theory: full polymorphism and ML style polymorphism ...
Type A and Type B Personality Theory
Type A and Type B Personality Theory. You know the "type:" So-called "Type A" personalities are hard-charging, determined to compete and to win. Combining traits such as drive and impatience ...

Publications

Other documents

SNS accounts

PhD studentship in homotopy type theory and univalent foundations

About Homotopy Type Theory and Univalent Foundations

Topics in HoTT/UF

About the Position

Conditions of Employment

The Organization

Application procedure

Postdoctoral Position in HoTT at the University of San Diego

Share this:

Type Theory with Records: From Perception to Communication

Towards a practical programming language based on dependent type theory

Bibliography

Type Theory

1. Paradoxes and Russell’s Type Theories

Support SEP

Institute for Logic, Language and Computation

News and Events: Open Positions

PhD position in Homotopy Type Theory

Project description

Requirements

Further information

Appointment

Job application

15-819 Homotopy Type Theory

Requirements

Academic Integrity

Schedule of Lectures

An Introduction to Dependent Type Theory

Access this chapter

Author information

Editor information

Rights and permissions

Copyright information

About this paper

Download citation

Share this paper

Type A and Type B Personality Theory

IMAGES

VIDEO

COMMENTS