Not signed in (Sign In)

Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorZhen Lin
    • CommentTimeSep 9th 2011

    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?

    • CommentRowNumber2.
    • CommentAuthorNeel Krishnaswami
    • CommentTimeSep 9th 2011
    • (edited Sep 9th 2011)
    This comment is invalid XML; displaying source. 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.
  1. This comment worked in the preview...?
    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeSep 9th 2011
    • (edited Sep 9th 2011)

    Here’s Neel’s comment:

    Dear Zhen Lin,

    In programming languages research (closely connected to, but not quite the same as, type theory) case\mathrm{case} is the usual name of the finite sum type. However, the dependent sum type is usually given a projective elimination:

    Γt:Σa:A.BΓπ 1(t):A\frac{\Gamma \;\vdash\; t \;:\; \Sigma a:A.\,B}{\Gamma \;\vdash\; \pi_1(t) \;:\; A}

     

    Γt:Σa:A.BΓπ 2(t):B[π 1(t)/a]\frac{\Gamma \;\vdash\; t \;:\; \Sigma a:A.\,B}{\Gamma \;\vdash\; \pi_2(t) \;:\; B[\pi_1(t)/a]}

    My understanding is that this formulation is equivalent to, but has a slightly simpler metatheory than, the cases\mathrm{cases} form given in your article.

    • CommentRowNumber5.
    • CommentAuthorMike Shulman
    • CommentTimeSep 9th 2011

    @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 \bot-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.

    • CommentRowNumber6.
    • CommentAuthorTobyBartels
    • CommentTimeSep 9th 2011

    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 WW-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).

    • CommentRowNumber7.
    • CommentAuthorMike Shulman
    • CommentTimeSep 9th 2011

    @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?

    • CommentRowNumber8.
    • CommentAuthorZhen Lin
    • CommentTimeSep 10th 2011

    @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 ‘I(A,a,b)trueI(A, a, b) \; \mathrm{true} is a judgement, which will turn out to be equivalent to a=bAa = b \in A’, 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 β\beta and η\eta 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.

    • CommentRowNumber9.
    • CommentAuthorTobyBartels
    • CommentTimeSep 10th 2011

    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 WW-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 WW-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.

    • CommentRowNumber10.
    • CommentAuthorTobyBartels
    • CommentTimeSep 10th 2011

    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!

    • CommentRowNumber11.
    • CommentAuthorMike Shulman
    • CommentTimeSep 10th 2011
    • (edited Sep 10th 2011)

    Here’s what Martin-Lof gives as the W-elimination rule (p44 in my copy, p81 in the Bibliopolis version). I’ll write WW for the W-type defined from a dependent type x:AB(x):Typex\colon A \vdash B(x)\colon Type, which Martin-Lof writes as (𝒲xA)B(x)(\mathcal{W}x\in A)B(x), and sup for the constructor x:A,y:B(x)Wsup(x,y):Wx\colon A, y\colon B(x) \to W \vdash sup(x,y) \colon W. Here C is a type dependent on W.

    c:Wx:A,y:B(x)W,z:Π v:B(x)C(y(v))d(x,y,z):C(sup(x,y))something:C(c)\frac{\vdash c \colon W \qquad x\colon A, y\colon B(x) \to W, z\colon \Pi_{v\colon B(x)} C(y(v)) \vdash d(x,y,z)\colon C(sup(x,y)) }{ something \colon C(c) }

    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.

    • CommentRowNumber12.
    • CommentAuthorMike Shulman
    • CommentTimeSep 10th 2011

    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”.

    • CommentRowNumber13.
    • CommentAuthorTobyBartels
    • CommentTimeSep 10th 2011

    Sorry, Mike, that’s my faulty memory. It’s not the WW-types per se, but those WW-types that CiC can implement without thinking of them as WW-types (that is, without having a constructor with “->” in it).

    For example, to construct \mathbb{N} (if you don’t already have it by hand) as a WW-type, you take (following your notation above) AA to be 1+11 + 1 and BB to be defined by cases, first 00 and next 11. So the eliminator is

    c:;x:1+1,y:B(x),z:Π v:B(x)C(y(v))d(x,y,z):C(sup(x,y))something:C(c). \frac {\vdash c\colon \mathbb{N}; \qquad x\colon 1 + 1, y\colon B(x) \to \mathbb{N}, z\colon \Pi_{v\colon B(x)} C(y(v)) \vdash d(x,y,z)\colon C(sup(x,y)) } { something \colon C(c) } .

    But a much simpler eliminator is

    c:;d:C(0);y:e(y):C(y +)something:C(c). \frac {\vdash c\colon \mathbb{N}; \qquad d\colon C(0); \qquad y\colon \mathbb{N} \vdash e(y)\colon C(y^+) } { something \colon C(c) } .

    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.

    • CommentRowNumber14.
    • CommentAuthorMike Shulman
    • CommentTimeSep 10th 2011

    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.

    • CommentRowNumber15.
    • CommentAuthorTobyBartels
    • CommentTimeSep 11th 2011

    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.

    • CommentRowNumber16.
    • CommentAuthorUrs
    • CommentTimeNov 17th 2011

    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.

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)