added the proceedings/conference name and the link to the book collection to this item:

- Per Martin-Löf,
*Constructive Mathematics and Computer Programming*, in:*Proceedings of the Sixth International Congress of Logic, Methodology and Philosophy of Science (1979)*, Studies in Logic and the Foundations of Mathematics**104**(1982) 153-175 [doi:10.1016/S0049-237X(09)70189-2, ISBN:978-0-444-85423-0]

following a suggestion in another thread (here)

]]>While I am looking at this entry:

The organization into “Presentation 1” and “Presentation 2” is not helpful but is irritating.

The problem is that both sections are very large and yet almost complete duplicates of each other, leaving it to the reader to hunt for potential minute differences.

(This duplication was introduced by “Anonymous” in rev 31 on 3rd Nov 2022 — a move which was not recognizable as such from the edit log in comment #28.)

Instead of “Presentation 2” repeating all material verbatim except for silent exceptions, it should just point out explicitly which changes need to be made to Presentation 1!

]]>I have touched the section “Judgements and Contexts” (here), trying to make it flow a little better. Also added a table showing the intended categorical semantics.

Still, this section suffers from the common disease of our type theoretic entries: It’s content will be trivial to expert and mysterious to everybody else, since type-theoretical concepts are mostly not explained but just *named*.

Eventually it would be nice to improve on this. On the other hand, the fact that nobody seems worried about this probably just means that humans, just as contemporary AI, learn not by logical rules but by osmosis of the mysterious.

]]>added (here) a table with a pretty-printed form of the structural rules together with their categorical semantics.

I also tried to add references, but have trouble finding original ones:

In Martin-Löf’s and in Hofmann’s original articles and also in Thompson’s textbook I see shadows of the rules scattered throughout the text, but not in a form that could be cited. (Or maybe I have missed it.)

The textbook Jacobs (1998) mentions at least two structural rules briefly on p. 122 (and apologizes for doing so).

The number and form of the rules which our entry used to be referring to all along is shown in Lecture 1 Rijke (2018) but without any referencing.

My impression is that somewhere along the way from 1998 to 2018 the notion of “structural rules” became canonized. What’s a canonical reference?

]]>We have individual entries to link to, such as dependent sum type, but not tonight.

]]>So the computation rules there needed correcting too.

]]>Re #35, you’re right. Removed that premise.

The $\Gamma,x:A \vdash B(x):U$ you mention is there as a premise for the formation rule.

]]>--Simeon ]]>

added pointer to:

- Per Martin-Löf,
*A Theory of Types*, unpublished note (1971) [pdf]

added pointer to:

- Martin Hofmann,
*Syntax and semantics of dependent types*, Chapter 2 in:*Extensional concepts in intensional type theory*, Ph.D. thesis, University of Edinburgh (1995), Distinguished Dissertations, Springer (1997) [ECS-LFCS-95-327, HofmannExtensionalIntensionalTypeTheory.pdf:file, doi:10.1007/978-1-4471-0963-1]

split contexts not needed in second presentation

Anonymous

]]>I believe \mapsto rather than \to was intended in these two locations (uniqueness rules for function types).

SteveDunham

]]>readding section on propositions as types

Anonymous

]]>added section on propositional reflection in the second presentation of Martin-Löf dependent type theory

Anonymous

]]>replaced existing syntax section, which was incomplete (lacking structural rules, identity types and a natural numbers type) and somewhat poorly explained - especially when it came to the different notions of equality, with two different formal presentations of Martin-Löf type theory in the language of natural deduction.

Anonymous

]]>added this pointer:

]]>added publication data and pdf-link for:

- Per Martin-Löf (notes by Giovanni Sambin),
*Intuitionistic type theory*, Lecture notes Padua 1984, Bibliopolis, Napoli (1984) (pdf)

added full publication data and DOI for:

- Per Martin-Löf,
*An intuitionistic theory of types: predicative part*, H. E. Rose, J. C. Shepherdson (eds.)*Logic Colloquium ’73, Proceedings of the Logic Colloquium*, Studies in Logic and the Foundations of Mathematics**80**Pages 73-118, Elsevier 1975 ((doi:10.1016/S0049-237X(08)71945-1, CiteSeer)

Yes, atmacen, by the way, ML explicitly stated that the equality relations were to be reflexive, symmetric and transitive in his 1979 and 1980 treatments.

Items, directly relevant to this, that may be of interest are the following:

Homotopy Type Theory (HoTT):

The code: https://github.com/HoTT/HoTT/blob/master/README.md

The book: https://github.com/HoTT/book

Univalent Foundations (aka the post-2012 state of Martin-Loef): https://en.wikipedia.org/wiki/Univalent_foundations

Yes, Martin-Loef was in on this.

Homotopy Type Theory ... the Wikipedia link. There's also the link, in this forum, cited by atmacen

https://en.wikipedia.org/wiki/Homotopy_type_theory

Setoids - what you need to formalize and digitize higher-order analysis

https://en.wikipedia.org/wiki/Setoid

The idea of linking this directly to n-categories ... I don't yet see in any of this. This may represent a different way to approach the issue. But it almost looks like you can use ML as The Language for n-categories.

-- Darth Ninja (aka MW Hopkins) ]]>

Re #21,22:

Hello Lydia,

I think you’re mostly rediscovering existing ideas, except there’s a well-known problem you’ve missed, which splits your proposal into two incompatible styles of type system.

I will call equality expressed with a judgment “judgmental equality”, and equality expressed with the equality/identity types “typal equality”. (It has traditionally been called “propositional equality”, but that was arguably a bad idea.)

The equality type I(A,a,b) in Martin-Löf was, in fact, actually meant as an internalization of the equality judgement a = b ∈ A,

I believe you’re correct about this, but…

which is equivalent to the judgement r ∈ I(A,a,b), where “r” is the distinguished constant that Martin-Löf uses to represent the sole inhabitant of all inhabited equality types.

This is only true for variants of type theory with equality reflection. I will refer to these variants as having “reflective equality”. (They have traditionally been called “extensional type theories”, but that was arguably a bad idea. `:)`

)

For a while, Martin-Löf wrote about versions of his type theory that included an equality reflection rule, making equality reflective by fiat. It turns out that this style of type theory is not amenable to the sort of direct implementation that Martin-Löf wanted. When he found out, he abandoned the equality reflection rule.

Most proof assistants implementing type theory implement a variant *without* reflective equality. The basic starting point for most of these variants is called “intensional type theory”, since judgmental equality ends up being rather intensional. (And with equality reflection, judgmental equality is more extensional, hence the term “extensional type theory”. But equality reflection doesn’t imply any of the usual extensionality principles from set theory.)

This shows that the typed equality judgement, itself, actually isn’t needed in the formalism since it is already subsumed by the equality type.

You mean that judgmental equality implies typal equality? That is not enough to eliminate the equality judgment from the formal system, because it’s used in premises of rules, and typal equality does not provide a way to derive those premises. Only when typal equality also implies judgmental equality—which is exactly equality reflection—can you eliminate the equality judgment form.

Even when studying type theory with reflective equality, it’s technically convenient to keep both judgmental and typal equality, as two ways of saying the same thing.

But Nuprl formally has no equality judgments. All equality rules are about the equality types. This was from the mid 80’s, inspired my Martin-Löf’s type theory with equality reflection.

[…] a much larger, more interesting and clearer picture […] directly links Martin-Löf theory to n-categories … and exposes the true nature of the type theory that’s been hiding in disguise.

Have you seen homotopy type theory? Yeah yeah, only $\infty$-groupoids. They’re working on it.

The first gap is that since the typed equality relation is already subsumed by the equality judgement, then there should also be a equality type for type judgements, so that types A = B if and only if the judgement type I(A,B) is inhabited. It’s not clear why Martin-Löf failed to include this in his formalism; but I think it was just an oversight.

Nuprl has added a type equality type constructor relatively recently. (2014, I think.) It’s not as straightforward as it might look. The problem is that now you have types like ($I(A,B) \to N_0$), which ostensibly get you judgments you didn’t have before (in this case, that $A$ and $B$ are not equal), risking making the formal system too strong or inconsistent. The Nuprl guys avoided that issue in a slick and somehow disappointing way.

Meanwhile, with universes, you already have that $I(U_n,A,B)$ corresponds to ($A = B \in U_n$), which implies ($A = B$) (with Russell-style universes, which is what Martin-Löf used at the time, and Nuprl uses).

There’s also “extensional” type equality: the property that elements of one type are elements of the other. (So, a conversion-focused equality.) This turns out to be definable in Nuprl for reasons that might be considered awesome or horrifying.

Once it is included, then there is no longer a need to have any equality judgements in the theory, at all. Everything is reduced to type membership judgements.

By the way, it turns out that the type equality judgments aren’t actually all that important, formally. The important use case for them is the “conversion” rule:

$\frac{A = B \qquad t \in A}{t \in B}$So you can metamathematically consider types equal when you can derive all the consequent conversion instances. Then you look at all the ways of deriving type equality, other than with other type equalities, and make sure you can derive all the conversions without going through type equality.

So in other words, using a type equality judgment form is the straightforward way, but there are shortcuts.

If all (definable) types are contained in some universe, it’s particularly obvious that type equality isn’t needed. But it turns out you don’t really need universes. Nuprl has only type membership judgments.

Second, Martin-Löf makes clear that the equality relation is to be reflexive, symmetric, transitive and is to also be a congruence. When expressed in terms of the equality types, these first set of conditions become […]

This is where I think you’re mistaken. The implication that reflective equality is a useful way of talking about morphisms. With the $J$ rule, equality reflection, and rules for judgmental equality, you can prove, internally, that any element of any equality is just the canonical $r$ constant. (I noticed you used your proposed type equality types, but I’m pretending you used universes. It shouldn’t make much difference, since you expect reflection for type equality.)

So you can use elements of equality types as morphisms, but with equality reflection, they’re all trivial. All your categories are discrete categories (“sets”). In fact, equality reflection is not the key thing trivializing the categories; it’s just that any two elements of any equality type are actually equal. This property is called uniqueness of identity proofs (UIP).

But do take a look at homotopy type theory (HoTT), where elements of equality types can be nontrivial, and correspond to morphisms and higher cells of $\infty$-groupoids. That includes $n$-groupoids, sets, and propositions as degenerate cases. But no equality reflection.

Some people around here are very hyped about HoTT. (And I’m probably the only one here who likes Nuprl…)

There’s actually a way, two-level type theory, to combine reflective equality and HoTT equality into a single system. But they remain different notions of equality. There are restrictions to ensure that the UIP principle of reflective equality doesn’t spread to HoTT equality. To my intuition, HoTT is *always* essentially two-level; the difference is whether the equality with trivial proofs is axiomatized as intensional judgmental equality, or typal equality satisfying UIP. You need (at least) two notions of equality (not counting syntactic equality) in any case.

The fact that it is a congruence, with the substitution of equals for equals rule shows that each of the operators in the Martin-Löf formalism is actually a functor. For instance, consider the following. […]

Yeah, the HoTT people have worked out a lot of really nice higher categorical interpretations for constructions in type theory.

If we eliminate symmetry,

This turns out to be pretty tricky, axiomatically. There are a few approaches in the works, to get more general higher categories, but I don’t know much about them.

Martin-Löf requires that each equality type I(A,a,b) have at most one member (this member being called “r”). This corresponds to a “coherence condition” that if f: a→b and g: a→b then f = g.

OK, so you know about this. And yeah, it’s technically a coherence condition, but that’s kind of like calling “0 = 1” an equational constraint.

All of this reveals another gap: the usual categorical identities are absent; e.g. f∘1 = f = 1∘f ∈ I(A,B), for f ∈ I(A,B).

No, those equations are already provable. (For element equality, including universe elements.) And much much more.

]]>To answer Zhen-Lin's question: Martin-Löf used D.

All of the non-canonical operators and canonical operators were given names by Martin-Löf. Excluding the universe types; this includes:

∙ λb = (λx)b(x) ∈ Π(A,B)

∙ (a,b) ∈ Σ(A,B)

∙ sup(a,b) ∈ W(A,B)

∙ i(a), j(b) ∈ A+B

∙ r ∈ I(A,a,b)

∙ 0 ∈ N,

∙ n ∈ N ↦ n' ∈ N

∙ m_n ∈ N_n, where 0 ≤ m < n ∈ N

for canonical objects and operators; and

∙ Ap(c,d) = cd, for the type Π(A,B)

∙ E(c,d) for the type Σ(A,B)

∙ T(c,d) for the type W(A,B)

∙ D(c,d,e) for the type A+B

∙ J(c,d) for the type I(A,a,b) (this changed from version to version)

∙ R(c, ]]>

This shows that the typed equality judgement, itself, actually isn't needed in the formalism since it is already subsumed by the equality type. Once you realize this, then you begin to see a much larger, more interesting and clearer picture which also shows a significant gap in the formalism - which when filled, directly links Martin-Löf theory to n-categories ... and exposes the true nature of the type theory that's been hiding in disguise.

The first gap is that since the typed equality relation is already subsumed by the equality judgement, then there should also be a equality type for type judgements, so that types A = B if and only if the judgement type I(A,B) is inhabited. It's not clear why Martin-Löf failed to include this in his formalism; but I think it was just an oversight.

Once it is included, then there is no longer a need to have any equality judgements in the theory, at all. Everything is reduced to type membership judgements.

Second, Martin-Löf makes clear that the equality relation is to be reflexive, symmetric, transitive and is to also be a congruence. When expressed in terms of the equality types, these first set of conditions become:

A type │ 1 ∈ I(A,A)

A type, B type │ f ∈ I(A,B) ⇒ f⁻¹ ∈ I(B,A)

A type, B type, C type │ f ∈ I(B,C), g ∈ I(A,B) ⇒ f∘g ∈ I(A,C)

with a similar set of constructors for the reflexive, symmetric and transitive relations for typed judgements.

This shows that we are actually dealing with a family of categories. First: the master category of all types whose objects are the types, themselves, and whose morphisms f: A→B are the members f ∈ I(A,B), for types A and B; Second, there is a category for each type A, whose objects are the members a∈A, and whose morphisms f: a→b, for a, b ∈ A are the members f ∈ I(A,a,b). So, overall, the master category has categories as its objects - it is a 2-category.

The fact that it is a congruence, with the substitution of equals for equals rule shows that each of the operators in the Martin-Löf formalism is actually a functor. For instance, consider the following.

If A is a type and B(x) is a type for each x ∈ A, then Σ(A,B) is a type. In this type, there is the pairing operator (a ∈ A, b ∈ B(a) ↦ (a,b) ∈ Σ(A,B)).

The congruence rule states that if a=a' ∈ A, b=b' ∈ B(a), then (a,b)=(a',b') ∈ Σ(A,B). Expressed in terms of the equality types, it states that the pairing operator is actually a functor which applies also to the morphisms f ∈ I(A,a,a') and g ∈ I(B(a),b,b') to yield the morphism (f,g) ∈ I(Σ(A,B),(a,b),(a',b')). That is: if f: a → a' in A, and g: b → b' in B(a), then (f,g): (a,b) → (a',b') in Σ(A,B).

The symmetry condition makes the arrows of each category reversible; so each category is also a groupoid. So, it's also a 2-groupoid if symmetry is included. If we eliminate symmetry, then this reduces to a category whose morphisms are the "reduction" relations of a reduction algebra.

Martin-Löf requires that each equality type I(A,a,b) have at most one member (this member being called "r"). This corresponds to a "coherence condition" that if f: a→b and g: a→b then f = g. We could also extend this to include a set of coherence conditions for the equality types I(A,B).

All of this reveals another gap: the usual categorical identities are absent; e.g. f∘1 = f = 1∘f ∈ I(A,B), for f ∈ I(A,B). Representing these in terms of the equality types gives us the elements of a monoidal category; λ(f) ∈ I(I(A,B),1∘f,f), ρ(f) ∈ I(I(A,b),f∘1,f) for f ∈ I(A,B); and α(f,g,h) ∈ I(I(A,D),f∘(g∘h), (f∘g)∘h), for f ∈ I(C,D), g ∈ I(B,C) and h ∈ I(A,B). For the composition, for coherence, we would then also add in the Triangle Diagram and Pentagon Diagram as "coherence identities".

But the objects of the monoidal category are the morphisms, themselves and the product is the composition. So, reiterating the earlier observation: this is actually a 2-category in disguise.

Since the I's can be nested to arbitrary depth, then this may even ramify up to 3-categories, 4-categories, etc.

-- Lydia Marie Williamson ]]>

More (similar) binary sum edits.

]]>Add explicit injections $\sigma_0,\sigma_1$ to the binary sums.

]]>