Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
I started an article about Martin-Löf dependent type theory. I hope there aren't any major mistakes!
One minor point: I overloaded $\mathrm{cases}$ by using it for both finite sum types and dependent sum types. Can anyone think of a better name for the operation for finite sum types?
Dear Zhen Lin,<br /><br />In programming languages research (closely connected to, but not quite the same as, type theory) $\mathrm{case}$ is the usual name of the finite sum type. However, the dependent sum type is usually given a projective elimination:<br /><br /><img src="https://nforum.ncatlab.org/extensions//vLaTeX/cache/latex_e347ec5f74fb4fb8e72ac63ece801330.png" title="\begin{matrix}<br />\frac{\Gamma \;\vdash\; t \;:\; \Sigma a:A.\,B}<br /> {\Gamma \;\vdash\; \pi_1(t) \;:\; A}<br />\\<br />\\<br />\frac{\Gamma \;\vdash\; t \;:\; \Sigma a:A.\,B}<br /> {\Gamma \;\vdash\; \pi_2(t) \;:\; B[\pi_1(t)/a]}<br />\end{matrix}<br />" style="vertical-align:-20%;" class="tex" alt="\begin{matrix}<br />\frac{\Gamma \;\vdash\; t \;:\; \Sigma a:A.\,B}<br /> {\Gamma \;\vdash\; \pi_1(t) \;:\; A}<br />\\<br />\\<br />\frac{\Gamma \;\vdash\; t \;:\; \Sigma a:A.\,B}<br /> {\Gamma \;\vdash\; \pi_2(t) \;:\; B[\pi_1(t)/a]}<br />\end{matrix}<br />" /><br /><br />My understanding is that this formulation is equivalent to, but has a slightly simpler metatheory than, the $\mathrm{cases}$ form given in your article.
Here’s Neel’s comment:
Dear Zhen Lin,
In programming languages research (closely connected to, but not quite the same as, type theory) is the usual name of the finite sum type. However, the dependent sum type is usually given a projective elimination:
My understanding is that this formulation is equivalent to, but has a slightly simpler metatheory than, the form given in your article.
@Zhen: Thanks!! I added the unit and empty types, which Martin-Lof obtains as special cases of finite types, and added a remark about how to get the other finite types from those. I also added some links and some comments about identity types and AC. Finally, I changed your remark about ex falso quodlibet to refer to excluded middle, since ex falso is just the eliminator of the empty type (Martin-Lof actually mentions this in the reference, when he gives the -elimination rule).
There are, of course, more type constructors in Martin-Lof’s paper than you’ve given here: he describes natural numbers, lists, W-types, and universes. Did you plan to expand this article to include those, and possibly more general inductive types and families? I’m not entirely sure exactly what collection of type-formers is officially called “Martin-Lof type theory”.
@Neel: I suspect that Zhen wanted to stay close to the choices made in Martin-Lof’s original paper, where he uses the “cases” eliminator for dependent sums. I don’t have a problem with using the same name for the eliminators of binary sums and dependent sums, since both are after all special cases of inductive types.
@Zhen and Neel: I think math tends to give the best results on the forum if you use the “Markdown+Itex” filter.
There is an important difference between eliminating sum types through cases and eliminating them through projections. (This difference disappears in the presence of identity types, however, so possibly only I care about it.) This is analogous to the difference between the inductive types in Thierry Coquand’s Calculus of Inductive Constructions (perhaps best known through its implementation in the theorem prover Coq) and Martin-Löf’s -types (although the equivalence between these is more complicated).
Categorially, at least when restricted to a sum of a constant family, the difference is that between a copower (a kind of colimit, elimination through cases) and a product (a kind of limit, elimination through the projection operators of the cone).
@Toby: I care about that too. I’ve gathered that it matters in syntactic study of type theory as well, e.g. the theory of “logical relations” has to treat the two cases differently (maybe one is called “positive” and the other “negative”, though I can never remember which is which). Maybe that is part of the “metatheory” Neel was referring to.
I thought that Martin-Lof’s W-types were literally a special case of CiC’s inductive types, though — why do you say that that difference is analogous?
@Mike:
Is that (reflexivity, symmetry, and transitivity) a rule we are giving, or an assertion we are making about derivability?
Hmmm. I’m not very sure. I believe it is derivable for the equality judgement in the presence of substitution rules (which I have omitted). On the other hand, in Maietti’s 2005 paper, Modular correspondence between dependent type theories and categories including pretopoi and topoi, she says
[…] we need to add all the inference rules that express the reflexivity, symmetry and transitivity of the equality between types and terms […] The structural rules of weakening, substitution and of a suitable exchange are not added since they are derivable.
This is also the approach taken by Nordström, Petersson and Smith in their article Martin-Löf’s type theory. So perhaps it’s a matter of taste? As for distinguishing between the equality type and equality judgement, I must defer to the expertise of others here; I thought it might be neater to get rid of the equality judgement given that ‘ is a judgement, which will turn out to be equivalent to ’, according to Martin-Löf [1984].
@Neel, @Toby:
Maietti [2005] states,
[…] we will refer to an equivalent formulation of the lex calculus in which the elimination and conversion rules for the indexed sum type are replaced by projections satisfying and conversions. This formulation with projections is equivalent to that of the indexed sum type given previously, but only because of the presence of the extension equality type (see Martin-Löf (1984) for a proof of the equivalence), that is, the equivalence does not hold in the intensional version of Martin-Löf’s type theory […]
Question: Why do we demand that the (extensional) equality type has at most one canonical inhabitant? This seems to be one of the differences between the equality type and the (intensional) identity type.
I thought that Martin-Lof’s W-types were literally a special case of CiC’s inductive types, though — why do you say that that difference is analogous?
That is true; in fact, identity types and dependents sums are both themselves examples of CiC inductive types, and for that matter so is everything else other than dependent products. But I meant to focus only on those CiC inductive types that correspond directly to -types.
On the other hand, I think that it was too strong to say that this is analogous. The elimination rule for all CiC inductive types is basically the same; they’re all eliminated by case analysis on the constructors, and Martin-Löf’s -type elimination rule is different, and correct only via using the identity types. However, it’s not really analogous to elimination by projection, so the analogy falls apart there.
This formulation with projections is equivalent to that of the indexed sum type given previously, but only because of the presence of the extension equality type (see Martin-Löf (1984) for a proof of the equivalence), that is, the equivalence does not hold in the intensional version of Martin-Löf’s type theory
That seems too strong to me; I’ll have to review the equivalence, which I thought worked even in the intensional version.
Why do we demand that the (extensional) equality type has at most one canonical inhabitant?
Because we’re not doing homotopy type theory, I guess!
Here’s what Martin-Lof gives as the W-elimination rule (p44 in my copy, p81 in the Bibliopolis version). I’ll write for the W-type defined from a dependent type , which Martin-Lof writes as , and sup for the constructor . Here C is a type dependent on W.
Here’s some Coq:
Parameter A : Type.
Parameter B : A -> Type.
Inductive W : Type :=
| sup : forall a:A, (B a -> W) -> W.
Check W_rect.
which prints
forall P : W -> Type,
(forall (a : A) (w : B a -> W),
(forall b : B a, P (w b)) -> P (sup a w)) ->
forall w : W, P w
from which, applying some alpha-equivalence, we get
forall C : W -> Type,
(forall (x : A) (y : B x -> W),
(forall v : B x, C (y v)) -> C (sup x y)) ->
forall c : W, C c
which looks the same as Martin-Lof’s eliminator to me.
Why do we demand that the (extensional) equality type has at most one canonical inhabitant?
I would say that’s more or less the definition of “extensional”.
Sorry, Mike, that’s my faulty memory. It’s not the -types per se, but those -types that CiC can implement without thinking of them as -types (that is, without having a constructor with “->” in it).
For example, to construct (if you don’t already have it by hand) as a -type, you take (following your notation above) to be and to be defined by cases, first and next . So the eliminator is
But a much simpler eliminator is
And now I see no clear analogy, except this: I want to think of the latter eliminator as correct, and (IIRC) we need identity types to prove them equivalent.
I should probably look at this in more detail, lest more of my memory be wrong.
Toby: Ah, yes, I see. I didn’t realize you needed identity types for that equivalence. I just tried messing around in Coq, and I was able to prove without using equality that the CiC eliminator implies the W-type eliminator. But I couldn’t see how to do the other direction without assuming not just identity types but function extensionality!
Gee, that’s bothersome. If that’s correct, it makes me much less happy about W-types. Maybe we ought to consider initial joint-algebras for finite families of polynomial endofunctors all the time instead.
without assuming not just identity types but function extensionality
That fits with the quotation from Maietti above, even though I didn’t remember the need for extensionality.
I have edited the sub-section structure at Martin-Löf dependent type theory. Originally the section “Equality type” had lots of subsections, which I think was unintentional.
Also I created a Properties-subsection, made “Axiom of choise” be subordinate to that and created a new subordinate section “Models” with a very brief remark on models for the extensional and the intensional version.
Finally I added in the References a pointer to chapter 1 in Michael Warren’s PhD thesis, which I am finding a useful text to read.
This looks like a mistake to me; there should be tags. (Common tags are “inl” and “inr”.) If you can fix it that would be great!
In general, I would say that whether to ask first or just make the edit depends on how confident you are that your change is correct! It’s never wrong to ask for approval first, although you can’t be guaranteed that someone will answer. If you’re pretty confident the change is right, you can go ahead and make it, but be sure to enter a changelog message so that people here will be notified in case someone disagrees.
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 -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 (), which ostensibly get you judgments you didn’t have before (in this case, that and 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 corresponds to (), which implies () (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:
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 rule, equality reflection, and rules for judgmental equality, you can prove, internally, that any element of any equality is just the canonical 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 -groupoids. That includes -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.
1 to 24 of 24