Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 18, 2011

Homotopy Type Theory, II

Posted by Mike Shulman

First, an announcement: the homotopy type theory project now has its own web site! Follow the blog there for announcements of current developments.

Now, let’s pick up where we left off. The discussion in the comments at the last post got somewhat advanced, which is fine, but in the main posts I’m going to try to continue developing things sequentially, assuming you haven’t read anything other than the previous main posts. (I hope that after I’m done, you’ll be able to go back and read and understand all the comments.)

Last time we talked about the correspondence between the syntax of intensional type theory, and in particular of identity types, and the semantics of homotopy theory, and in particular that of a nicely-behaved weak factorization system. This time we’re going to start developing mathematics in homotopy type theory, mostly following Vladimir Voevodsky’s recent work.

From a foundational point of view, what we’re doing today is analogous to developing mathematics in set theory. When you learn ZFC, you learn to define (for instance) Kuratowski ordered pairs, cartesian products, functions as sets of ordered pairs, and so on, eventually building up all the familiar structures of mathematics. Similarly, starting from homotopy type theory, we need to do some building up of familiar concepts, although of course the process will be different since we have different starting notions.

I’m mostly going to describe this informally, avoiding the formal syntax of type theory with its turnstiles, judgements, and derivations. And I’m not going to make any use of the correspondence we talked about last time, but there is one advantage to having described that correspondence first: namely, if it makes you more comfortable, you can think of everything I say today as a description of constructions performed in a category with a nicely-behaved WFS. You can even (and, in fact, should) think of topological spaces or simplicial sets with their usual (acyclic cofibration, fibration) WFS (although there are technical issues involved in making that precise, which are discussed in the references I linked to last time).

Now, where do we start developing mathematics? What we have is a basic notion of homotopy type (a.k.a. \infty-groupoid), including dependent types, identity (or “path”) types, dependent sums and products, and perhaps some other constructors (like inductive and coinductive types). This is great for doing homotopy theory, but in a lot of mathematics there is not (yet) visible any homotopical behavior; thus we really need also a notion of “set” to be a good foundational system.

Classically, sets can be identified with homotopy types that are discrete: they contain no nonidentity morphisms/paths/homotopies (or higher such). That notion isn’t invariant under equivalence, but there is a corresponding notion which is: we require instead that the space of paths/morphisms between any two points is either empty or contractible. (If it is contractible, then the two points represent the “same element” of the corresponding set.) I’m going to follow the homotopy theorists and call types of this form homotopy 0-types, or 0-types for short.

Of course, we should also have a notion of homotopy nn-type (a.k.a. nn-groupoid) for all natural numbers nn. We can define these inductively by saying that the space of paths between any two points in an nn-type should be an (n1)(n-1)-type. And, as regular nn-Café readers will know, we can continue downwards a couple of steps: the inductive definition gives the right answer for n=0n=0 if a “(-1)-type” is one which is either empty or contractible, which is equivalent to saying that the space of paths between any two points in it is contractible. And the inductive definition then gives the right answer for n=1n=-1 if a “(-2)-type” is one which is contractible. Cf. negative thinking.

(By the way, Voevodsky says a type is of h-level (n+2)(n+2) where I would say it is an nn-type. This has the benefit of starting the numbering at 00 rather than 2-2, but it has the disadvantage of not matching the well-known numbering of homotopy types and groupoids. Use whichever you prefer.)

Thus, in order to define nn-types inductively for all nn, we just need to get things started at n=2n=-2 by defining when a type is “contractible.” However, before we do that, we need to address a different issue, which may be one of the trickiest aspects of homotopy type theory for a non-type-theorist to get used to.


We’ve said that we expect to recover set theory from 0-types, groupoid theory from 1-types, and so on. But that means we should also expect to recover logic from (1)(-1)-types. (The empty type represents “false,” while the contractible one represents “true”—and in intuitionistic logic, there can be more (1)(-1)-types than that.) In particular, we should not include an external “logic” in our foundational theory. Statements such as “XX is a 0-type” or “YY is contractible” should not be things we say about the theory which can be true or false; rather they should be (-1)-types themselves. The “truth” or “falsity” of such a proposition then corresponds to whether or not we can exhibit a point of the corresponding (-1)-type.

It may seem like we’ve painted ourselves into a bit of a corner here: we need to define what it means to be a (-1)-type, as part of our inductive definition of nn-types for all nn, but that “definition” must itself be a (-1)-type. However, if we sit back calmly and think about it, we can see there isn’t really a problem. All we need to do is define, for any type XX, a type IsContr(X)IsContr(X) representing the proposition “XX is contractible,” such that when we then go on to define “XX is a (-1)-type” in terms of “XX is contractible,” the type IsContr(X)IsContr(X) turns out to in fact be a (-1)-type. It’s a bit bootstrappy, but not circular or paradoxical.


So how do we define IsContr(X)IsContr(X), in such a way that it is always either empty or contractible? A natural idea, if we should happen to think of it, is that we should define IsContr(X)IsContr(X) to be the type of contractions of XX. This is logical because if a space XX is contractible, then its space of contractions is itself contractible, while if XX is not contractible, then its space of contractions is of course empty. We formalize this as follows:

IsContr(X)Σ xXΠ yXPaths X(x,y) IsContr(X) \coloneqq \Sigma_{x\in X} \Pi_{y\in X} Paths_X(x,y)

I’m writing Paths X(x,y)Paths_X(x,y) for the identity type of XX (what was previously written Id X(x,y)Id_X(x,y)), since in homotopy type theory we interpret it as a type of paths, or equivalences, rather than equalities. If we unpack the above definition, we see that a point of IsContr(X)IsContr(X) consists of a point xXx\in X together with, for every yXy\in X, a path from xx to yy. The point xx is the “basepoint” or “center” to which we are contracting, and the paths supply the “contraction.” Remember that all constructions on types are “natural” or “continuous,” so that the selection of paths is necessarily natural/continuous in yy, as we should require.

The above definition of IsContr(X)IsContr(X), due to Voevodsky (like pretty much everything else we’re doing today), is a bedrock on which the rest of the edifice rests. I’ve tried to make it seem inevitable in hindsight, but I certainly don’t think I could have come up with it myself!

Voevodsky then proved the following theorem:

IsContr(X)IsContr(IsContr(X)) IsContr(X) \to IsContr(IsContr(X))

Now actually, like everything else in type theory, IsContr(X)IsContr(IsContr(X))IsContr(X) \to IsContr(IsContr(X)) is a type: the type of functions from IsContr(X)IsContr(X) to IsContr(IsContr(X))IsContr(IsContr(X)). So when I say he “proved” it, I mean that he exhibited, by formal type-theoretic constructions, a specified point of that type: a function from IsContr(X)IsContr(X) to IsContr(IsContr(X))IsContr(IsContr(X)). Once we define (-1)-types, we can show that IsContr(X)IsContr(IsContr(X))IsContr(X) \to IsContr(IsContr(X)) is actually a (-1)-type, so that it contains at most one point; hence exhibiting a point of it is sufficient to show that it is “true,” which is what we mean in general by “proving a theorem.”

So what does this theorem mean? The type of functions between two propositions is just an implication, so this theorem means that if XX is contractible, then so is IsContr(X)IsContr(X): the space of contractions of a contractible space is contractible. On the other hand, if XX is not contractible, then IsContr(X)IsContr(X) is empty, since a point of IsContr(X)IsContr(X) would be a contraction of XX. Thus IsContr(X)IsContr(X) is, at least intuitively, a (-1)-type, as desired.

There’s a slight subtlety here, though: we almost certainly can’t prove this theorem in plain unmodified intensional type theory. This is because IsContr(X)IsContr(X) contains, among other things, a (dependent) function type, and so IsContr(IsContr(X))IsContr(IsContr(X)) contains, among other things, the path (identity) type of a function type—but fully intensional type theory does not specify what the identity types of function types are like. In particular, it can be the case there that two functions are pointwise equal everywhere—i.e. the type Π xXId Y(f(x),g(x))\Pi_{x\in X} Id_Y(f(x), g(x)) is inhabited—but not themselves equal—i.e. the type Id XY(f,g)Id_{X\to Y}(f,g) is not inhabited. However, for homotopy type theory, we expect a path from ff to gg to consist exactly of a natural/continuous family of paths from f(x)f(x) to g(x)g(x), so that these two types should actually be equivalent. Thus we need to augment intensional type theory by an axiom called functional extensionality which asserts this—or else a stronger axiom which implies functional extensionality. I’ll come back to this in the next post.


Before we go on, I want to address a point that’s confused several people, including myself. (If this paragraph confuses you rather than clarifying anything, just skip it.) I described above the homotopical interpretation of IsContr(X)IsContr(X): a point of IsContr(X)IsContr(X) is a point of XX together with a continuous deformation retraction to that point. On the other hand, we can interpret the same definition from a propositions as types point of view, in which the identity type represents equality, Σ\Sigma represents “there exists,” and Π\Pi represents “for all.” In this case, IsContr(X)IsContr(X) translates to “there exists a point xXx\in X such that all other points yXy\in X are equal to xx.” This is a perfectly good notion of what it means for a set to be “contractible”. The mistake is to start thinking of identity types as representing paths, but to keep trying to interpret Σ\Sigma and Π\Pi as logical quantifiers, forgetting that for consistency with Path XPath_X, they must also be interpreted as continuous or natural operations. This mismatched interpretation leads to the conclusion that IsContr(X)IsContr(X) means “there exists a point xXx\in X such that every point yXy\in X is connected to xx by a path”, which sounds like a definition of connectedness, not contractibility.


Okay, let’s go back to our in-progress inductive definition of nn-types. We’ve defined what it means to be contractible, i.e. to be a (-2)-type. Now we can define “XX is a (-1)-type”, a.k.a. “XX is a proposition”, as follows:

IsProp(X)Π x,yXIsContr(Paths X(x,y)) IsProp(X) \coloneqq \Pi_{x,y\in X} IsContr(Paths_X(x,y))

This is almost a translation of our proposed definition from above: we wanted to say that XX is a (-1)-type if the space of paths between any two points of XX is contractible. However, instead of merely asserting that each path space is contractible, giving a point of IsProp(X)IsProp(X) specifies a contraction of each path space. In fact, we don’t have any tools yet to construct types which assert that things exist without specifying them—but since the theorem above shows that contractions are unique when they exist, we can hope that the extra data in IsProp(X)IsProp(X) will be redundant.

And indeed, Vladimir goes on to prove the following theorems:

IsProp(IsContr(X)) IsProp(IsContr(X))

IsProp(IsProp(X)) IsProp(IsProp(X))

So our bootstrap process is working: we’ve defined the notions of a type “being contractible” and “being a proposition” as types, which are themselves in fact propositions ((-1)-types). Now we can go on:

IsSet(X)Π x,yXIsProp(Paths X(x,y)) IsSet(X) \coloneqq \Pi_{x,y\in X} IsProp(Paths_X(x,y))

and inductively:

IsNType(X,n+1)Pi x,yXIsNType(Paths X(x,y),n) IsNType(X,n+1) \coloneqq Pi_{x,y\in X} IsNType(Paths_X(x,y),n)

Now that we have these definitions, we can hope to prove that sets behave the way we expect sets to, and so on. For instance, the category of sets ought to be an elementary topos. However, all we can prove so far is that it is locally cartesian closed. We can remedy this by assuming, as an additional axiom, that we have a type of all propositions. This will give us a subobject classifier in the category of sets, which will therefore be an elementary topos. (Vladimir calls this a resizing axiom, for reasons that I’ll explain in the next post.)


With a type of all propositions, we can also construct familiar logical operations on (-1)-types, just as we can for subobjects in any topos. I’m talking about connectives like “and” and “or” and quantifiers like “there exists” and “for all”. Of course, since our propositions are (particular) types, we already have the type-theoretic operations like ×\times, Σ\Sigma, and Π\Pi, and these sometimes do what we want, but not always—the issue is that they don’t necessarily preserve the property of being a (-1)-type.

For instance, one can prove that if XX and YY are (-1)-types, then so are X×YX\times Y (which we therefore call “XX and YY”) and the function type XYX\to Y (which we call “XX implies YY”). Similarly, if XX is any type at all and Y(x)Y(x) is a (-1)-type dependent on XX, then Π xXY(x)\Pi_{x\in X} Y(x) is a (-1)-type (which we call “for all xXx\in X, Y(x)Y(x)”). On the other hand, under the same hypotheses Σ xXY(x)\Sigma_{x\in X} Y(x) need not be a (-1)-type; rather than the proposition “there exists an xXx\in X such that Y(x)Y(x)” it is the type “{xX|Y(x)}\{ x\in X | Y(x) \}”. What we need is a way of “squashing” any type ZZ down to a (-1)-type which is inhabited just when ZZ is. From a homotopy perspective, is natural to call this “squashed” type π 1(Z)\pi_{-1}(Z).

There are several ways to obtain this squashing operation. We can assert it as part of the structure of the type theory, as in this paper by Steve Awodey and Andrej Bauer; there π 1(X)\pi_{-1}(X) is written as [X][X]. We can hope to obtain it as a consequence of a general “quotienting” or “exactness” axiom, whose structure is currently unclear, but which I may talk a bit about later on. But we can also derive it from a subobject classifier, in the same way that we prove that any elementary topos is a regular category:

π 1(Z)Π PΩ(ZP) \pi_{-1}(Z) \coloneqq \Pi_{P\in \Omega} (Z\to P)

where Ω\Omega is the subobject classifier (the type of all propositions).


Thus, intensional type theory with functional extensionality and a subobject classifier seems to be a pretty good foundational system: at least, we can derive familiar-looking theories of logic and sets. Let me finish today by describing another one of Voevodsky’s insights: the definition of when a map is an equivalence. Homotopically, it’s natural to define f:XYf\colon X\to Y to be an equivalence if we have a map g:YXg\colon Y\to X and paths pPaths XX(gf,id X)p\in Paths_{X\to X}(g f, id_X) and qPaths YY(fg,id Y)q\in Paths_{Y\to Y}(f g, id_Y). This might lead us to the definition

??IsEquiv(f)Σ g:YX(Paths XX(gf,id X)×Paths YY(fg,id Y))?? ?? \qquad IsEquiv(f) \coloneqq \Sigma_{g\colon Y\to X} \; (Paths_{X\to X}(g f, id_X) \; \times \; Paths_{Y\to Y}(f g, id_Y)) \qquad ??

but unfortunately this definition does not give us a (-1)-type. We could squash it down to a (-1)-type with π 1\pi_{-1}, but it’d be nice to be able to talk about equivalences without needing the axioms that give us π 1\pi_{-1}. Voevodsky’s idea was to make use of the fact that IsContrIsContr is a (-1)-type, and define f:XYf\colon X\to Y to be a weak equivalence if all its (homotopy) fibers are contractible:

IsEquiv(f)Π yYIsContr(Σ xXPaths Y(f(x),y)) IsEquiv(f) \coloneqq \Pi_{y\in Y} IsContr( \Sigma_{x\in X} Paths_Y(f(x),y))

Here Σ xXPaths Y(f(x),y)\Sigma_{x\in X} Paths_Y(f(x),y) is the (homotopy) fiber of ff over yy: a point of it is a point xXx\in X equipped with a path from f(x)f(x) to yy. He was then able to prove:

IsProp(IsEquiv(f)). IsProp(IsEquiv(f)).

There’s also another way to define IsEquivIsEquiv that also gives a (-1)-type. Recall that any equivalence of categories can be improved to an adjoint equivalence, but we need to change one of the natural isomorphisms. In fact, given the two functors and one of the natural isomorphism, there is a unique choice of the second one such that the triangle identities hold. However, given just the two functors (assuming they are known to be inverse equivalences), the choice of the two natural isomorphisms is not unique.

This suggests that we need to add more “adjointness” data to make the first definition IsEquivIsEquiv into a (-1)-type. The first thing we may think of is to add all the higher data going all the way up, to make it a “fully coherent” \infty-equivalence. This “would work,” but it is not expressible in the type theory (at least, not easily). However, it turns out that if we cut off at any finite level with “half” of the data at that level, then we still get a (-1)-type. So, for instance, it suffices to specify, in addition to ff, gg, pp, and qq, a secondary homotopy asserting that pp and qq satisfy one of the triangle identities. There will then be a contractible space of choices of all the higher data. (It would also work to specify only ff, gg, and pp, except for the fact that given only that data we can’t necessarily conclude that ff is an equivalence; qq might not exist at all.)

To get some homotopical intuition for why this works, think of constructing S S^\infty (which is contractible) as follows. First take two points, which is S 0S^0. Then glue on two paths (1-discs) connecting them, to make S 1S^1. Then glue on two 2-discs to form the two hemispheres of S 2S^2. And so on. None of the S nS^n’s are contractible, although S S^\infty is, but if we stop after gluing on one of the kk-discs for any kk, then we end up with D kD^k which is contractible.

This other way to define IsEquivIsEquiv should be attributed to a handful of people who came up with it a year ago at an informal gathering at CMU, but I don’t know the full list of names; maybe someone else can supply it.

Next time: the univalence axiom!

Posted at March 18, 2011 8:00 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2373

90 Comments & 4 Trackbacks

Re: Homotopy Type Theory, II

I would like to know if such new foundations would change the view on consistency issues etc.

Posted by: Thomas on March 18, 2011 10:07 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I would like to know if such new foundations would change the view on consistency issues etc.

I’m not sure what you mean; can you clarify? Homotopy type theory as a foundation is at least as consistent as ZFC, since you can construct a model of it out of spaces or simplicial sets in ZFC. And the axioms I’ve presented so far are certainly much weaker than ZFC. In fact, so far, I haven’t mentioned any axioms which prevent all homotopy types from being sets! So any elementary topos would satisfy all the axioms I’ve mentioned so far. But even once we add quotients and/or the univalence axiom, which ensure the existence of higher homotopy types, I think we would still need some additional axioms of the replacement/collection/separation type to get up to anything comparable to ZFC. (It’s also less clear how to phrase such axioms in a type-theoretic framework.)

Posted by: Mike Shulman on March 21, 2011 4:31 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

we require instead that the space of paths/morphisms between any two points is either empty or contractible

That you keep writing thinks like ‘either empty or contractible’, when you could just as easily write ‘empty if not contractible’, means that I really must still exclude you from the class of constructive mathematicians. (One could also say ‘either contractible or, if not, then empty’, which allows one to be technically correct in constructive mathematics without sounding like a constructivist.)

Posted by: Toby Bartels on March 19, 2011 5:20 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Toby, are you joking?

Posted by: Tom Leinster on March 19, 2011 6:47 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

In the context of the linked discussion, no.

Posted by: Toby Bartels on March 20, 2011 6:03 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

But I’m not being too serious either.

Posted by: Toby Bartels on March 20, 2011 10:16 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I’m perfectly happy with the label “pluralist.” (Mathematicians having debates nowadays about whether constructive or classical mathematics is “true” or “correct” seems to me kind of like physicists having debates about whether the aether is an inertial reference frame.)

But I’m curious about the definition of “constructive mathematician” that your comment implies: is a constructive mathematician not allowed to write in classical mathematics when writing to an audience including many classical mathematicians he wants to avoid alienating, about a subject which can be done classically just as well as constructively? Or would a “real” constructive mathematician not place himself in such a position? (-:

Posted by: Mike Shulman on March 21, 2011 4:06 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

If you felt a twinge of guilt when writing ‘either empty or contractible’, then you could (if you cared to) reapply for admission to the club. I assumed that you didn't feel such a twinge, since you could have avoided it with an alternative phrasing that classical audiences can still comprehend.

As a pluralist, I want the things that I write to make sense in the broadest possible context, which ‘either empty or contractible’ does not. It's one thing if such a treatment is more complicated; the digressions necessary to make some things constructively rigorous would probably alienate ordinary mathematicians, and in any case they would take time. But when making the treatment constructive is a trivial edit, why not just do it?

Don't take any of this too seriously. I only brought it up to correct a parenthetical remark in the previous discussion.

Posted by: Toby Bartels on March 21, 2011 6:11 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I maintain that “empty if not contractible” sounds more awkward than “either empty or contractible,” especially to a classical ear. And in fact, I don’t even know offhand why “empty if not contractible” is correct constructively. I know that in intuitionistic logic, everything is “false if not true” (in fact being “not true” is essentially the definition of being “false”), though it need not be “either true or false”—but why does that extend to the characterization of (-1)-types? E.g. if I know that a type X is empty if not contractible, and I have two points x,yXx,y\in X, then how can I conclude that they are connected by a path? Obviously if they weren’t connected by a path, then X would not be contractible, hence it would be empty, a contradiction, so I know that xx and yy are not not connected by a path… but how do I get to the positive assertion that they are?

I can see that “contractible if inhabited” would do the job, though. Right?

I did feel a slight twinge of guilt writing “either empty or contractible”, but I don’t think it is necessary, even as a pluralist, to always write things that make sense in the broadest possible context, especially when being expository and informal. I feel that anyone who cares about making things constructive should be perfectly capable of translating the one to the other in their head.

(Don’t worry, I’m not taking this too seriously; but I’m enjoying the discussion.)

Posted by: Mike Shulman on March 21, 2011 6:19 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I did feel a slight twinge of guilt

Then maybe you are a practising constructivist mathematician after all!

I maintain that “empty if not contractible” sounds more awkward than “either empty or contractible,” especially to a classical ear.

That’s why I suggested ‘contractible or, if not, then empty’.

I don’t even know offhand why“empty if not contractible” is correct constructively.

You're right! This is all a mathematical error on my part. You’ve effectively given a weak counterexample already. (Making it more explicit, let PP be a truth value that is not false; we’ll show that PP is true if my definition is correct. Consider the subspace AA of the unit interval such that each point xx belongs to AA iff xx is an endpoint or PP is true. Then AA is not not contractible, so (by hypothesis) a (1)(-1)-type, so (since inhabited) contractible, so PP is true.)

I can see that “contractible if inhabited” would do the job, though.

Yes, that’s what I should have said. That’s even harder to make look normal to a classicist. Perhaps ‘either empty or, if nonempty, then contractible’ (although classical mathematicians really should learn the word ‘inhabited’).

Posted by: Toby Bartels on March 21, 2011 11:54 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I don’t think “either empty or, if nonempty, then contractible” really looks normal to a classical mathematician either.

Posted by: Mike Shulman on March 22, 2011 12:46 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

However, it’s worth noting that “contractible if inhabited” is precisely the correct interpretation of the theorem IsContr(X)IsContr(IsContr(X))IsContr(X) \to IsContr(IsContr(X))! If I had thought about this, then perhaps I would have written “contractible if inhabited”.

Posted by: Mike Shulman on March 23, 2011 5:11 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I must admit, I had the same impulse as Toby when reading the post, to take you to task for this! I’d agree it’s good to try to keep to classically familiar phrasings as far as possible. But this is a case where it introduces a pretty serious inaccuracy — the distinction between a proposition and a decidable proposition is a big one. (And especially when developing maths in a framework that’s actively inconsistent with classical logic!)

One of the things I love in these posts is that you’re writing in normal mathematical prose, not formal syntax. There’s a somewhat widely held misconception — which confused me for some time — that to do logic in weaker foundations, one needs to work absolutely formally, not just semi-formally as usual. And it’s important to dispel this by example… but in the process, we do have to be extra-careful about some subtleties of phrasing that don’t matter classically.

Posted by: Peter LeFanu Lumsdaine on March 22, 2011 11:34 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I’m not sure what you’re implying by “actively inconsistent with classical logic.” Homotopy type theory, as a foundation, is perfectly consistent with classical logic, as long as by “logic” you refer only to propositions (i.e. (-1)-types). For instance, the logic in Voevodsky’s “univalent model” is classical. The propositions-as-types logic is not classical, but I don’t intend “logic” to refer to that.

Posted by: Mike Shulman on March 22, 2011 11:49 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I’ll let Peter speak for himself, but one thing one *could* mean is that the Univalence Axiom is inconsistent with the standard, set theoretic interpretation of type theory, under which Σ\Sigma and Π\Pi are sums and products and Id AA×A\mathrm{Id}_A \to A\times A is the diagonal. The reason is simply that it would force every isomorphism to be the identity.

Looking instead at Mike’s proposal to have only the “logic” of subobjects (or “propositions”) be classical, within a not-necessarily classical system of type theory, we know this makes sense at least in the extensional case, where e.g. in any topos \mathcal{E} we take the [-]-operation to be the left adjoint “image” reflection from the slice category /X\mathcal{E}/X of types over XX into subobjects of XX. Then we can simply compose with double-negation to get a further left adjoint Sub(X)Sub ¬¬(X)\mathrm{Sub}(X) \to \mathrm{Sub}_{\neg\neg}(X) into the ¬¬\neg\neg-stable propositions. The whole thing even has the form of a “big double-negation” on the slice category: for any AXA\to X we take A¬¬A=0 0 AA\mapsto \neg\neg A = 0^{0^A}, since ¬¬A\neg\neg A is always a proposition (i.e. ¬¬AX\neg\neg A \rightarrowtail X), even when AA is arbitrary.

What about the intensional case? As Vladimir mentions somewhere, at least in simplicial sets one wants to use 22 rather than the subobject classifier as Prop – taking *complemented* subobjects rather than arbitrary ones as propositions – since the sub-*types* of a homotopy type are complemented. Of course, Vladimir’s model of the Univalence Axiom in SSets shows that it is compatible with this combination of non-classical “type theory” and classical “logic” (if that’s your preferred point of view), respectively constructive logic over a classical Prop.

Posted by: Steve Awodey on March 23, 2011 4:45 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

some kind of LaTeX problem there: ¬¬A=0 0 A\neg\neg A = 0^{0^A} should read as iterated exponents: 0^{0^A}. It comes out OK in the preview, but not in the posting for some reason.

Posted by: Steve Awodey on March 23, 2011 4:54 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I think that for purposes of homotopy models, the fact that SSets is itself a 1-topos (and hence has a subobject classifier) is basically irrelevant. What one wants is a classifier of “homotopy-subobjects” in the sense of a monomorphism in an (∞,1)-category. In the 1-category SSet, regarded as a presentation of the (,1)(\infty,1) category HoTypes=GpdHoTypes = \infty Gpd, it so happens that the classifier of complemented subobjects in the 1-categorical sense (namely 2) also classifies all homotopy-subobjects in the homotopy sense, and that the logic of the latter is classical.

But in general, I think this coincidence is unlikely to hold true, even when considering (,1)(\infty,1)-categories which happen to be presented by 1-categories that are themselves 1-topoi. Rather, the classifier of homotopy-subobjects should coincide with the ordinary subobject classifier in the 1-category of “internal sets” (= categorically-discrete objects = 0-types = objects of h-level 2). In SSet, the latter is just Set, so of course (assuming a classical metatheory) its logic is classical. But in general, the 1-topos of discrete objects need not be Boolean.

(The expression 0 0 A0^{0^A} looks fine to me—maybe your browser doesn’t fully support MathML?)

Posted by: Mike Shulman on March 23, 2011 5:09 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

OK, I don't know Voevodsky's theory like you do, but it seems from this discussion that you (Mike and Steve) only say that Voevodsky's univalent model has a classical logic of (1)(-1)-types because you must both be excluded from the class of constructivist mathematicians? Because his model is based on SetSet and one must assume that SetSet is boolean to conclude that his (1)(-1)-types have a classical logic? Is that right?

PS: I also view 0^{0^A} just fine, on Windows XP running Firefox 3.6.

Posted by: Toby Bartels on March 23, 2011 6:55 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Well, his construction is certainly based on a Boolean version of Set. I think I can say that without committing myself to a personal belief in the Booleanness of Set. (-:

And I think it’s not entirely clear whether it would work starting from a non-Boolean Set. At least, there’s some work to do there, and I’m not aware of anyone who’s done it. Classical homotopy theory uses the axiom of choice in constructing lifting properties, for instance. Perhaps constructively we should work with algebraic Kan complexes instead of Kan complexes; does that create any problems? Maybe not… but we’d have to go through and check all the little bits of classical homotopy theory that get used to make sure that they still work.

(I think Voevodsky’s model is not really morally different from the models in categories with weak factorization systems that I described in Part I. He works with Kan complexes and Kan fibrations, and deals with the coherence issues in a somewhat different way, I think, but his main focus is on ensuring that the univalence axiom holds.)

Posted by: Mike Shulman on March 23, 2011 7:49 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Ah, so it's Voevodsky who's not a constructivist. Fair enough.

And I think it’s not entirely clear whether it would work starting from a non-Boolean Set. At least, there’s some work to do there, and I’m not aware of anyone who’s done it.

Then maybe I need to learn his theory and do this!

Posted by: Toby Bartels on March 23, 2011 6:51 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Ah, so it’s Voevodsky who’s not a constructivist.

I’m not sure I would even say that; he certainly seems to display some interest in the fact that homotopy type theory enables one to do homotopy theory constructively. It’s just that the construction of that particular model starts from a Boolean Set; his goal with it was to show the consistency of the univalence axiom relative to ZFC. I think one can be a constructivist and still prove theorems that contain PEM (and even AC) as a hypothesis; Boolean toposes exist even if Set isn’t one. (-:

Posted by: Mike Shulman on March 23, 2011 7:59 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

his goal with it was to show the consistency of the univalence axiom relative to ZFC

Well, if that's all that he's doing, then never mind.

I think one can be a constructivist and still prove theorems that contain PEM (and even AC) as a hypothesis

Some constructivists would disagree with this, but they must be wrong, because as you say

Boolean toposes [with NNO] exist even if Set isn’t one.

Much as constructive mathematics tells the classicist something about arbitrary toposes, so classical mathematics tells the constructivist something about the boolean ones.

Posted by: Toby Bartels on March 24, 2011 6:29 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

(The expression 0 0 A0^{0^A} looks fine to me—maybe your browser doesn’t fully support MathML?)

I use a browser with no MathML support and see it fine. However, the script that processes all the math on the page has a tendency to not work a fair amount of the time, which may be what happened to him (the script now seems to run for me even in firefox). I often have to refresh to see math correctly, and in my comments, I usually have difficulty getting it to format more than half my post in a preview.

Not to be a complainer, but I kind of preferred the old system that forced me to use firefox (for the MathML), but at least always worked. :)

Posted by: Dan Doel on March 23, 2011 8:28 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I recently got a new phone (Android), with free Internet, and I've started using it to check some websites. But I've given up on using it for the Café (and the Lab), because the math rendering always hangs. (Sometimes I can see a little, more often none at all.)

Posted by: Toby Bartels on March 23, 2011 6:54 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Can someone explain briefly why ‘empty if not contractible’ is acceptable in constructive mathematics, whereas ‘either empty or contractible’ is not?

Posted by: Tom Ellis on March 21, 2011 10:52 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I can’t tell you exactly what Toby is thinking. However…

Here is some Agda code:

lemma1 : {A : Set} -> Proposition A -> (¬ Contractible A -> ¬ A)
lemma1 pa nca x = nca (x , \y -> proj1 (pa x y))

It demonstrates that the univalent statement “A is a proposition” implies “A is empty if not contractible.” The converse is not, as far as I can tell (given a few minutes thought), provable, so they are not equivalent statements.

However, it is not the case that “A is a proposition” constructively implies “A is either contractible or empty.” That essentially implies the existence of a decision procedure for which of the two an arbitrary A is, and there’s no way to write that.

If I postulate excluded middle, it’s easy to prove both the converse and the ‘either or’ statement:

lemma2 : {A : Set} -> Proposition A -> Contractible A \/ ¬ A
lemma2 {A} pa with lem A
... | inl  x = inl (x , \y -> proj1 (pa x y))
... | inr ¬x = inr ¬x

lemma3 : {A : Set} -> (¬ Contractible A -> ¬ A) -> Proposition A
lemma3 {A} pf x y with lem (Contractible A)
... | inl  cna = h-lift cna x y
... | inr ¬cna = false-elim (pf ¬cna x)

(h-lift demonstrates than an n-type is also an (n+1)-type). Maybe there’s a constructive way to prove the converse I’m missing, though.

Anyhow, if Mike were to say, “empty if not contractible,” he would at least be making a constructively weaker statement than, “is a proposition.” When he says, “either empty or contractible,” he is actually saying something constructively stronger than, “is a proposition.”

Posted by: Dan Doel on March 21, 2011 10:03 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Actually, it seems the best ‘informal’ characterization of, “is a proposition,” would be, “contractible if inhabited.”

lemma1 : {A : Set} -> Proposition A -> (A -> Contractible A)
lemma1 pa x = (x , \y -> proj1 (pa x y))

lemma2 : {A : Set} -> (A -> Contractible A) -> Proposition A
lemma2 {A} ci x y = h-lift (ci x) x y

The first lemma gets you from proposition to “empty if not contractible” by contraposition. But, “empty if not contractible,” is constructively weaker than, “contractible if inhabited.”

Posted by: Dan Doel on March 21, 2011 11:01 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

So this is saying that from a construction of a point in A we can always construct a contraction of A?

Posted by: Tom Ellis on March 23, 2011 11:05 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I believe it says that A is a proposition if and only if we can construct a contraction of A given a point of A. For true propositions this is due to them being contractible. For false propositions it is vacuously true because it is impossible to construct a point.

If I tried with sets and above, though, lemma2 would hold, but lemma1 would not.

Posted by: Dan Doel on March 23, 2011 12:18 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

For true propositions this is due to them being contractible. For false propositions it is vacuously true because it is impossible to construct a point.

And for arbitrary propositions this is due to them being contractible if they have a point.

Posted by: Toby Bartels on March 23, 2011 6:55 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

This other way to define IsEquiv should be attributed to a handful of people who
came up with it a year ago at an informal gathering at CMU, but I don’t know the
full list of names; maybe someone else can supply it.

Let’s see: Mike Shulman, Peter Lumdaine, Michael Warren, Dan Licata – right?
I think it’s called “gradlemma” in VV’s coq files (although only 2 of the 4 were actually still grad students at the time).

Great post, BTW.

Posted by: Steve Awodey on March 19, 2011 5:51 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

This mismatched interpretation leads to the conclusion that IsContr(X)IsContr(X) means “there exists a point xXx \in X such that every point yXy \in X is connected to xx by a path”, which sounds like a definition of connectedness, not contractibility.

One should read it as ‘there exists a point xx in XX such that every point yy in XX is connected to xx by a path which varies continuously with yy’. Then it's a definition of contractibility.

Posted by: Toby Bartels on March 19, 2011 5:55 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

exactly – the quantifiers have to be read the right way. Mike has put his finger on a very important point here (the one he says is sometimes confusing) about the way to read the quantifiers constructively (propositions as types, etc.). He says:

“The mistake is to start thinking of identity types as representing paths, but to keep trying to interpret Σ and Π as logical quantifiers, forgetting that for consistency with PathX, they must also be interpreted as continuous or natural operations. This mismatched interpretation leads to the conclusion that IsContr(X) means “there exists a point x∈X such that every point y∈X is connected to x by a path”, which sounds like a definition of connectedness, not contractibility.”

But I wouldn’t say it’s a “mistake” or a “mismatch” to keep reading these operations as quantifiers – one just needs to read them as *constructive* quantifiers. It was Dana Scott who introduced the idea that constructively definable operations are always continuous. It’s like the fact that the logic of a topos of sheaves is intuitionistic, but here we have an even more extreme form of it.

My point is that we don’t want to deny or ignore the fact that these quantifiers (or the type of Paths) are logical operations – only differently construed – rather we want to make use of that to develop an internal logic that is (not just intuitionistic but) constructive.

Posted by: Steve Awodey on March 19, 2011 3:32 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Can you say more about this?

But I wouldn’t say it’s a “mistake” or a “mismatch” to keep reading these operations as quantifiers – one just needs to read them as constructive quantifiers. It was Dana Scott who introduced the idea that constructively definable operations are always continuous. It’s like the fact that the logic of a topos of sheaves is intuitionistic, but here we have an even more extreme form of it.

Posted by: Emily Riehl on March 19, 2011 6:21 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

… well, it got a bit long, so I put it on HoTT over here.

Posted by: Steve Awodey on March 20, 2011 5:06 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Technically, you are of course right, in that that is a valid (at least, self-consistent) way to read the type.

But I’ve never been able to understand why one would want to artifically restrict the expressive power of language by forcing “such that there exists” to mean the same thing as “equipped with”. If in some context that’s the only meaning of “such that there exists” you have available, it makes sense, but in homotopy theory we have a perfectly good, and more natural, candidate for that. If you want to read Σ xXΠ yXPaths X(x,y)\Sigma_{x\in X} \Pi_{y\in X} Paths_X(x,y) as “there exists an xXx\in X such that for every yXy\in X, there exists a path from xx to yy,” then how would you read

π 1Σ xXΠ yXπ 1Paths X(x,y) \pi_{-1} \Sigma_{x\in X} \Pi_{y\in X} \pi_{-1} Paths_X(x,y)

(which is what I would read as “there exists an xXx\in X such that for every yXy\in X, there exists a path from xx to yy”)?

Posted by: Mike Shulman on March 21, 2011 3:48 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

One way of thinking about IsContr(XX) is as the homotopy pullback of the identity function along the canonical map X δXX^\delta \to X where () δ(-)^\delta sends XX to the space with the discrete topology on same underlying set. For the purposes of what we are considering here, the actual set underlying XX doesn’t make much sense, because we can’t point to a set underlying a homotopy type, so this makes me think that at least in this interpretation using spaces, we are implicitly using the cohesiveness of TopSetTop \to Set. I could imagine other settings where we might want to interpret IsContr, using other cohesive categories, not least some sort of algebraic geometric setting. Perhaps this is a way to build up to an \infty-cohesive (,1)(\infty,1)-category?? (Complete speculation on my behalf)

Another way to think about IsContr if we want to think about simplicial sets as modelling homotopy types is via the decalage functor Dec:sSetsSetDec:sSet \to sSet.

Another way of thinking about it with higher groupoids (say Trimble groupoids, for choice), is the ‘tangent category’ functor that Urs and I use in our paper The inner automorphism 3-group of a strict 2-group. One can consider the tangent category of the fundamental nn- or \infty-groupoid and it looks very much like the construction from the first paragraph, using the path space and then the path space again and so on…

Posted by: David Roberts on March 20, 2011 2:31 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

One way of thinking about IsContr(X)IsContr(X) is as the homotopy pullback of the identity function along the canonical map X δXX^\delta\to X where () δ(-)^\delta sends XX to the space with the discrete topology on same underlying set.

I don’t see that. Homotopy pullbacks preserve homotopy equivalences, which identities are, so it seems to me that the homotopy pullback you describe should be homotopy equivalent to X δX^\delta.

Posted by: Mike Shulman on March 21, 2011 3:51 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Yeah, I realised that a bit later. What I (think) I really meant was to consider X δ× XX IX^\delta\times_X X^I as being a a space over XX via the endpoint evaluation and then consider the space of sections XX δ× XX IX\to X^\delta\times_X X^I. But hmmm this doesn’t capture what I want. Something more like sections of Π 0(X)× XX IX\Pi_0(X)\times_X X^I \to X for some section Π 0(X)X\Pi_0(X) \to X of the canonical map, but we don’t necessarily have Π 0\Pi_0 available. This is where bringing in cohesiveness would come in handy. Back to the drawing board then…

Posted by: David Roberts on March 21, 2011 7:32 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

David is trying to see the analog of IsContr()IsContr(-) as a familiar construction on path spaces of topological space.

I don’t think this has to do with cohesion, but I agree that it would be helpful for following the discussion to have this spelled out. If I understand correctly, the claim is that there is a canonical and natural construction on any topological space that sends it to a conctractible space if it is contractible and sends it to an empty space if not.

Let me see, we start with the path fibration

X I δ 0,δ 1 X×X \array{ X^I \\ \downarrow^{\mathrlap{{\delta_0, \delta_1}}} \\ X \times X }

and are supposed to first take the dependent product with respect to δ 1\delta_1 and then the dependent sum with respect to δ 0\delta_0, both along the terinal morphism

X* X \to *

right?

For this morphism the left adjoint to pullback is simply forgetting the map to XX. The right adjoint is more interesting.

Hm…

Posted by: Urs Schreiber on March 21, 2011 10:16 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Ah, I’ve realised where I went wrong. I hadn’t read what the type IsContr is defined as properly. Really I want something like the space Γ(X)\Gamma(X) of sections of xXP xXev 1X \prod_{x\in X} P_x X \xrightarrow{ev_1} X If XX is not path-connected, Γ(X)\Gamma(X) is obviously empty. If XX is connected but not contractible there are also no sections, but if XX is contractible, there is at least one section, and Γ\Gamma seems to be contractible, but one should show this by some topological analogue of the theorem Γ(X)Γ(Γ(X))\Gamma(X) \to \Gamma(\Gamma(X)). This would (should?) be that Γ(X) Γ(Γ(X))\Gamma(X)^{\Gamma(\Gamma(X))} is (canonically?) contractible.

Posted by: David Roberts on March 22, 2011 5:22 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

David says:

Really I want something like the space Γ(X)\Gamma(X) of sections of xXP xev 1X\prod_{x \in X} P_x \stackrel{ev_1}{\to} X […]

Yes, this sounds good now!

(Don’t have time for more, right now.)

Posted by: Urs Schreiber on March 22, 2011 8:51 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Ok, so here’s the general set-up. Take a category u:CSetu:C \to Set, such that uu has a left adjoint dd, and CC has a path object () I(-)^I (I’m not assuming CC has weak equivalences, but that will b). Also assume that CC has pullbacks and is cartesian closed. Then for any aCa\in C we can define IsContr(a)CIsContr(a)\in C by IsContr(a):=C(dua×a,(dua×a)× a×aa I). IsContr(a)\colon = C(d u a\times a,(d u a\times a)\times_{ a\times a}a^I). When CC has small products then the dependent product along the projection dua×aad u a\times a \to a exists and is isomorphic to IsContr(a)IsContr(a) as defined here. How much more structure is this than is present in the axiomatic HoTT version? (obviously apart from being a category over SetSet, which isn’t a priori defined) It should cover the general structure when looking at models in other categories however.

Actually, since CC is cartesian closed, we have IsContr(a)=C(a,((dua×a)× a×aa I) dua) IsContr(a) = C(a,\left((d u a\times a)\times_{ a\times a}a^I\right)^{d u a}) and the object ((dua×a)× a×aa I) dua\left((d u a\times a)\times_{ a\times a}a^I\right)^{d u a} is almost xuaP xa\prod_{x\in ua} P_x a (where P xa=d{x}× aa IP_x a = d\{ x\} \times_a a^I), which is almost the dependent product. Is is in some cases. Obviously one can play around a bit with the adjoints here, but I won’t for the time being.

I also think this covers the three cases I considered in my wrong post above, namely the topological setting, the simplicial setting and the nn-groupoid setting.

Here is a naive question along a different line: is IsContrIsContr some sort of comonad?

Obviously one can take CC relative to other categories, but SetSet is the one which fit in my examples above.

Posted by: David Roberts on March 23, 2011 12:56 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I can’t figure out how what you are describing is supposed to be IsContrIsContr. Let’s consider a topological space A. Then a point of the space you want to call IsContr(A)IsContr(A) is a continuous map f:A δ×A(A δ×A)× A×AA If\colon A^\delta \times A \to (A^\delta\times A)\times_{A\times A} A^I. Since A δA^\delta is discrete, A δ×AA^\delta \times A is a copower of that many copies of AA; thus for each point xAx\in A we have a continuous map f x:A(A δ×A)× A×AA If_x \colon A \to (A^\delta\times A)\times_{A\times A} A^I. Suppose for simplicity that AA is connected. Then each map pr 1f x:AA δ×Apr_1 f_x \colon A \to A^\delta\times A must factor through one copy of AA, say the one indexed by g(x)A δg(x)\in A^\delta. Thus so far, we have a discontinuous map g:AAg\colon A\to A, and for each xAx\in A a continuous map h xpr 1f x:AAh_x \coloneqq pr_1 f_x \colon A\to A. Now the composite Af xA δ×AA×AA \xrightarrow{f_x} A^\delta \times A \to A\times A sends yAy\in A to (g(x),h x(y))(g(x),h_x(y)). The rest of the data says that for each xx, we have paths from g(x)g(x) to h x(y)h_x(y) which depend continuously on yy.

It seems to me that if AA is any connected space (or probably any space at all), then I can pick a basepoint zAz\in A and define g(x)=zg(x) = z and h x(y)=zh_x(y)=z for all x and y, and let the paths be constant, obtaining a point of your space. Which is of course not what we want. Am I misunderstanding something?

I’m also not sure why you want to try to drag in a forgetful functor to Set. Topological spaces and simplicial sets happen to have such functors, but I certainly wouldn’t expect a general (presentation of a) (,1)(\infty,1)-topos to have a well-behaved such functor. I think one of the nice things about IsContrIsContr is that it’s defined purely intrinsically to the category in question. I think Urs had the right way to think about it categorically: take the path space A IA×AA^I \to A\times A as an object of C/(A×A)C/(A\times A), apply the right adjoint to pullback along one projection A×AAA\times A \to A, then forget the remaining morphism to AA.

Posted by: Mike Shulman on March 23, 2011 3:35 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

Arg, it should be sections, not maps. Thus we need CC locally cartesian closed (as you’ve pointed out that SetSet is in this theory), and it should be maps over dua×ad u a\times a, or if the dependent product exists, maps over aa.

If the dependent product (in TopTop, say, which is where my intuition is) along the projection pr:X×XXpr:X\times X \to X is the same as along the projection X δ×XXX^\delta \times X \to X, then I agree with most of what you say in the last paragraph. I would prefer to drop reference to an extrinsic category SetSet. But I still maintain that we need the space of sections of Π prX IX\Pi_{pr}X^I \to X

Posted by: David Roberts on March 23, 2011 6:14 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

If I understand you correctly, now you want to talk about the space of maps from dua×ad u a\times a to (dua×a)× a×aa I(d u a\times a)\times_{a\times a} a^I over dua×ad u a\times a, which is equivalently the space of maps from dua×ad u a \times a to a Ia^I over a×aa\times a. So a point of that space consists of a choice, for every x,yax,y\in a, of a path from xx to yy, which depends continuously on yy. Which is to say, it consists of, for every point xax\in a, a contraction to xx.

I think now I agree that this will give you something equivalent to IsContr(a)IsContr(a), since a contractible space can be contracted (essentially uniquely) to any of its points, but I still don’t understand why you want to bring in duad u a. The construction of IsContr(a)IsContr(a) I described above gives you the right answer without it, and is with less superfluity (only one contraction rather than a whole bunch).

Posted by: Mike Shulman on March 23, 2011 8:16 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

I think Urs had the right way to think about it categorically: take the path space A IA×AA^I \to A \times A as an object of C/A×AC/A \times A, apply the right adjoint to pullback along one projection A×AAA \times A \to A, then forget the remaining morphism to AA.

What’s the right adjoint Π xX\Pi_{x \in X} on topological spaces?

For

Top/X xX()×X xXTop Top/X \stackrel{\overset{\sum_{x \in X}}{\to}}{\stackrel{\overset{(-)\times X}{\leftarrow}}{\underset{\prod_{x \in X}}{\to}}} Top

we compute

Hom Top/X(A×X,BX) =Hom Top(A×X,B)× Hom Top(A×X,X){p 2} =Hom Top(A,[X,B])× Hom Top(A,[X,X]){p˜ 2} =Hom Top(A,[X,B]× [X,X]{Id}) =Hom Top(A,Γ(B)) \begin{aligned} Hom_{Top/X}(A \times X , B \to X) & = Hom_{Top}( A\times X, B) \times_{Hom_{Top}(A \times X, X)} \{p_2\} \\ & = Hom_{Top}( A, [X,B]) \times_{Hom_{Top}(A , [X,X])} \{\tilde p_2\} \\ &= Hom_{Top}(A, [X,B] \times_{[X,X]} \{Id\}) \\ &= Hom_{Top}(A, \Gamma(B)) \end{aligned}

to find that

xXB=Γ(B) \prod_{x \in X} B = \Gamma(B)

indeed is the space of sections. But for the case at hand we need

Top/(X×X) xX()×X xXTop/X. Top/(X \times X) \stackrel{\overset{\sum_{x \in X}}{\to}}{\stackrel{\overset{(-)\times X}{\leftarrow}}{\underset{\prod_{x \in X}}{\to}}} Top/X \,.

Posted by: Urs Schreiber on March 23, 2011 9:18 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

For any map f:YXf\colon Y\to X, the right adjoint Π f:Top/YTop/X\Pi_f\colon Top/Y \to Top/X takes a space p:EYp\colon E\to Y to the space Π fEX\Pi_f E \to X whose fiber over xXx\in X is the space of sections of p| f 1(x):p 1(f 1(x))f 1(x)p|_{f^{-1}(x)} \colon p^{-1}(f^{-1}(x)) \to f^{-1}(x), with a suitable topology. (This is not quite true, of course, since TopTop is not locally cartesian closed, but there are various fixes.)

Posted by: Mike Shulman on March 23, 2011 9:48 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

This is not quite true, of course, since TopTop is not locally cartesian closed, but there are various fixes.

Let’s talk sSetsSet.

Hm, or rather, remind me: if we want to model the homotopy type theory on a 1-category of topological spaces, what do we need? I guess we need at least to restrict to CW-complexes?

Posted by: Urs Schreiber on March 23, 2011 10:59 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

The values of the Π\Pi-functors in sSetsSet should also be easy to compute using representable functors. An nn-simplex of Π fE\Pi_f E over an nn-simplex xX nx\in X_n is a map Δ nΠ fE\Delta^n \to \Pi_f E whose composite with Π fEX\Pi_f E \to X is x:Δ nXx\colon \Delta^n \to X, so by adjointness such a thing is the same as a map f 1(x)Ef^{-1}(x) \to E over YY, i.e. a section of EE over f 1(x)f^{-1}(x) (where f 1(x)f^{-1}(x) means the pulllback of x:Δ nXx\colon \Delta^n \to X along ff).

Posted by: Mike Shulman on March 24, 2011 6:10 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

You’ve caught me! (-: I’ve been invoking topological spaces for intuition, but there are issues with trying to use them to model the entire theory.

On the one hand, it’s easier with topological spaces than with simplicial sets to get a weak factorization system which satisfies the necessary niceness properties: we can construct a “mapping path space” using Moore paths (paths of variable length, which concatenate strictly associatively). This is described in the paper of van den Berg and Garner. In this way we get a model of dependent type theory with identity types, where the display maps are the Hurewicz fibrations.

There are issues with exponentials, of course, since TopTop is not locally cartesian closed, nor does it seem to have a nice subcategory which is. But I think that Benno and Richard’s construction should work just as well if we replace TopTop by pseudotopological spaces or subsequential spaces, both of which are lcc. There will be the usual coherence issues with functoriality of pullback, but hopefully they can be dealt with in the usual ways without messing up the identity types.

Thus it seems likely to me that we can indeed get a model of homotopy type theory this way, or at least the fragment of it that I’ve described so far.

However, it isn’t the “canonical intended” model in \infty-groupoids, because as you point out, we’re using all spaces rather than only the “cofibrant” ones, so there aren’t enough morphisms. But unfortunately, CW complexes are not closed under pullbacks, nor exponentials, nor under mapping path spaces; so we can’t just “restrict to the subcategory of CW complexes.”

There is something a bit magical that happens, though: if we instead restrict to spaces with the homotopy type of CW complexes (m-cofibrant spaces), which are just as “cofibrant” as CW complexes for the purposes of Whitehead’s theorem, then we do get a category which is closed under mapping-path-spaces (this is clear) and under pullbacks of Hurewicz fibrations. The latter fact is not at all obvious to me, but it follows from the fact that given a fibration over an m-cofibrant space, the total space is m-cofibrant iff each fiber is. I’m told that this is originally due to Jim Stasheff; there’s a proof in 3.5.2 of May-Sigurdsson.

So I think that we can restrict to m-cofibrant spaces and get a model of the exponential-free fragment of homotopy type theory. Unfortunately, as far as I can tell, this trick seems to be incompatible with exponentials. Firstly, it’s totally unclear to me whether Stasheff’s theorem above could be proven for any lcc replacement of TopTop. (The proof I know uses Milnor’s theorem that exponentials by compact spaces preserve m-cofibrancy, and the proof of that uses some serious point-set topology.) Moreover, even if we had exponentials, m-cofibrant spaces won’t in general be closed under them.

On the other hand, m-cofibrant spaces do present the same (,1)(\infty,1)-category as simplicial sets, and the latter are lcc. So it seems possible that we could pass back and forth across that equivalence to get “exponentials up to homotopy,” which would at least satisfy the rules of Π\Pi-types up to homotopy.

Posted by: Mike Shulman on March 24, 2011 7:22 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

However, all we can prove so far is that [SetSet] is locally cartesian closed.

Can we at least prove that it's also a pretopos?

Posted by: Toby Bartels on March 19, 2011 5:58 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Actually, I can see that the answer is bound to be No using only ordinary type theory, since modding out a set by an equivalence relation gives a groupoid that is not a set. But I hope that there are still pullback-stable disjoint finitary coproducts in SetSet, and that SetSet is a pretopos assuming the existence of Π 0\Pi_0 or one of these mysterious exactness axioms (although these results are less likely to have actually been considered and proved).

Posted by: Toby Bartels on March 19, 2011 6:07 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I hope that there are still pullback-stable disjoint finitary coproducts in Set

Well, that depends on the “perhaps some other constructors” that I mentioned. With just identity types, dependent sums, and functionally-extensional dependent products, I don’t think you can construct coproducts. But in extensional type theory, coproducts are one of the simplest “inductive types,” so if you include some inductive types, then you almost certainly have coproducts. (Probably some type theorist is going to jump on me now saying something about injectivity of constructors, but I think that the fragment of HoTT relating to sets should be sufficiently extensional for that not to be an issue.)

(It’s also worth mentioning that if you have general enough “inductive types” then you can even define identity types and dependent sums as particular cases of them. That’s in fact what Coq and Agda do. It seems that one still has to take dependent products as basic, though.)

Just having a π 0\pi_0 operation won’t give you ordinary exactness of SetSet, unless you also have some sort of homotopy exactness. And actually, the homotopy quotient of an equivalence relation on a set, if it exists, will already be a set without any need for π 0\pi_0—at least if we interpret “equivalence relation” in the usual sense (internal to SetSet) which I am advocating, rather than in the propositions-as-types sense where the “relation” map RX×XR \to X\times X is not required to be monic.

Posted by: Mike Shulman on March 21, 2011 4:00 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

With just identity types, dependent sums, and functionally-extensional dependent products, I don’t think you can construct coproducts. But in extensional type theory, coproducts are one of the simplest “inductive types,” so if you include some inductive types, then you almost certainly have coproducts.

Yes, I took it for granted that we have binary sums as one of the type constructors, since otherwise you can hardly have a foundation of (in this case weakly predicative constructive) mathematics (and, as you say, they won't come free). So my question is whether we have enough axioms to prove that they're disjoint pullback-stable coproducts when restricted to SetSet. (Anyway, I guess that if we don't, then we can always add this as an axiom while we're putting in the constructor itself, so maybe it's not a very important question.)

Posted by: Toby Bartels on March 21, 2011 5:29 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

It’s true that we could always add that as an axiom, but it would be more satisfying if the standard axioms for inductive types implied disjointness and stability of coproducts.

Coq’s dependent elimination is strong enough to prove disjointness of coproducts (this is just a translation into “paths language” of the standard ‘discriminate’ and ‘injection’ tactics for equality). However, I don’t fully understand the theoretical basis of Coq’s dependent elimination: it uses a “match” construct as primitive rather than a recursor, and I neither understand precisely the semantics of “match,” nor whether/how it can be implemented in terms of a recursor. (I think I remember Vladimir commenting briefly on this question at Oberwolfach, indicating he didn’t know the answer either.) So I’m a little leery of asserting the validity of all of Coq’s dependent elimination in homotopy type theory—especially since as Dan Doel pointed out, Agda’s dependent elimination is (by default) strong enough to prove the uniqueness of reflexivity proofs (“axiom K”), which is inconsistent with nontrivial homotopy models. But I would love for someone to tell me I don’t have to worry.

I haven’t tried pullback-stability yet, but I expect that it should also be provable, and probably less worrisome.

Posted by: Mike Shulman on March 22, 2011 6:39 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

For what it's worth, if you write out standard axioms for inductive types in a theory of homotopy 00-types (sets, or perhaps completely presented sets in a theory without quotient types) using recursion (instead of match) as your primitive elimination operation, then you can still prove disjointness there.

Posted by: Toby Bartels on March 23, 2011 7:29 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Disjointness of coproducts is pretty easy. Here is an Agda file proving they are. I used –without-K to be sure, but beyond that, I tried to restrict myself to Martin-loef combinators as much as possible, so I only use pattern matching to define those.

The large elimination corresponds to use of recursion to define an element of U in intuitionistic type theory. It’s pretty standard that proving disjointness of constructors requires use of universes or the equivalent.

I also had to expand some of the categorical definitions to read x.fx=gx\forall x. f x = g x instead of f=gf = g for the obvious reason. Sums aren’t even coproducts (only weak coproducts) in intuitionistic type theory up to the normal equality, of course.

I toyed a bit with pullback stability, but it actually seemed like it’d be a more difficult proof. For instance, I got into a spot where it seemed like I’d actually need K, and thus would have to require the objects involved in the pullback to actually be sets in the homotopy sense. So, I punted, and only proved that my datatype:

record _×_ {A B Z : Set} (f : A -> Z) (g : B -> Z) : Set where
  constructor _,_<_>
  field
    fst : A
    snd : B
    cmm : f fst == g snd

is a pullback up to extensional equality that ignores the last field.

Actually proving the stability property is something I’m not sure how to do, either. Getting the identities to work out is non-trivial.

Posted by: Dan Doel on March 23, 2011 7:42 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

If I understand what it does properly, I think pullback-stability is most naturally phrased in type theoretic terms as:

Πx:A+B.(Σa:A.x=inla)+(Σb:B.x=inrb) \Pi x : A + B.\; (\Sigma a:A.\; x = inl\; a) + (\Sigma b:B.\; x = inr\; b)

This is easy to prove. You don’t need any large elims to do it, though you do need dependent elimination when eliminating the coproduct argument xx.

Posted by: Neel Krishnaswami on March 23, 2011 10:33 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Yeah, that seems equivalent. At least, proving that lemma helped me define the second part of the more categorical isomorphism (I was thinking I might need to break out Inspect, and your simplified statement seems similar).

I’ve updated the file to include this. I still haven’t proved the two pieces of the categorical definition are actually inverse. It’s starting to get a little hairier than I appreciate working with only ML-style combinators.

Posted by: Dan Doel on March 23, 2011 12:03 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

This disjointness and stability is looking great. My next question would be, can we extend this to show that coproducts are disjoint and stable for all types, not just for sets? For disjointness I think the part about intersection should be the same, and the part about monicness should say that the induced function

mapinl:Paths X(x,y)Paths X+Y(inlx,inly) map inl \colon Paths_X(x,y) \to Paths_{X+Y}(inl x, inl y)

(and its obvious dual) is an equivalence. (What we’ve got so far is that there exists a map in the other direction, which is of course sufficient for a map between (-1)-types to be an equivalence.)

It’s pretty standard that proving disjointness of constructors requires use of universes or the equivalent.

That’s interesting. But I notice that the “large elimination” isn’t very large: the only output types it gives are \top and \bot. So it seems that all you really need is a type family which includes both \top and \bot. For instance, a subobject classifier ought to suffice. This seems kind of like the categorical facts that a category with coproducts and a terminal object is (finitary) extensive as soon as the single coproduct 1+11+1 is disjoint and stable, and that elementary toposes are always extensive.

Posted by: Mike Shulman on March 27, 2011 4:03 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

This disjointness and stability is looking great. My next question would be, can we extend this to show that coproducts are disjoint and stable for all types, not just for sets?

I fixed the proof of disjointness like you said. For proving the equivalence, I used the definition that Peter LeFanu Lumsdaine mentioned in the HTT3 comments, because it seemed easier. However, I needed to use an even fancier large elimination. Maybe it’s not necessary, but I couldn’t figure out how to do without it.

I’m not so optimistic about my ability to prove stability. I’m already not sure how to prove that the type I have is a pullback in general. More realistically, do you know what I’d have to do to Neel’s lemma to make it homotopically kosher? Would proving that it’s an equivalence between A + B and (Σ A \a → x ≡ inl a) + (Σ B \b → x ≡ inr b) be sufficient?

That’s interesting. But I notice that the “large elimination” isn’t very large: the only output types it gives are ⊤ and ⊥. So it seems that all you really need is a type family which includes both ⊤ and ⊥. For instance, a subobject classifier ought to suffice.

The usual universe U suffices for this, and you could conceivably have an even smaller universe with just those two codes. I don’t think either of those actually acts as a subobject classifier; if I’m not mistaken, to have a classifier, we’d need the theory to be impredicative?

Large elimination is a little stronger than a universe in some ways, I think. I actually flirted with making a universe and using that this time around, because I wanted to define (as the file says):

P : (A B : Set) -> (s : A + B) -> (inl x == s) -> Set
P A B (inl y) eq = foo (bar eq) == eq
P A B (inr _) ()

where () is is the absurd match against obviously empty types. The +-Elim I had wasn’t working for me, because I wanted to do dependent elimination on s to refine it in the identity type. I could achieve that with +-elim and a universe, but then I realized that I didn’t have a code for

(foo (bar eq) == eq)

unless A and B were also coded in the universe (and thus Id (A + B) would have a code …). So, I wouldn’t have a proof for all types, I’d just have a proof schema for however high a universe you wish to write down. Similarly, my proof is only for Agda’s Set, not its Set1 and so on. This could be recitified with universe polymorphism, but I didn’t want to complicate things.

Posted by: Dan Doel on March 27, 2011 12:44 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

The usual universe U suffices for this, and you could conceivably have an even smaller universe with just those two codes. I don’t think either of those actually acts as a subobject classifier; if I’m not mistaken, to have a classifier, we’d need the theory to be impredicative?

Yes, indeed. I was just trying to relate the discussion to things which may be more familiar to the homotopy theorists and topos theorists in the audience, by pointing out that a subobject classifier would be sufficient to assume instead of a universe. I would expect that a small “universe” with just those two codes should be a classifier for complemented subobjects.

Posted by: Mike Shulman on March 28, 2011 6:47 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Would proving that it’s an equivalence between A + B and (Σ A \a → x ≡ inl a) + (Σ B \b → x ≡ inr b) be sufficient?

After thinking about it, I quickly realized this makes no sense. The second part depends on the first, so it doesn’t fit the type for an equivalence.

But, I have another question: if we think about the proposed pullback type…

f : X -> Z
g : Y -> Z

f * g : Type

Values of f * g are of the form:

(x, y, eq)

x : X
y : Y
eq : Id Z (f x) (g y)

So, if Z is not a set, then there are potentially many inhabitants (x, y, eq) even for fixed x and y. Is this a problem, or no?

Posted by: Dan Doel on March 27, 2011 4:18 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Is this a problem, or no?

That’s the behavior we expect for homotopy pullbacks. As an extreme case, if XX and YY are the unit type and ff and gg are identical, corresponding to a point z:Zz\colon Z, then the homotopy pullback is the loop space Ω zZ\Omega_z Z, which is in general quite nontrivial even though XX and YY are trivial.

Posted by: Mike Shulman on March 28, 2011 6:29 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Okay. The file now contains (I think) a proof that the datatype in question is in fact a homotopy pullback. I need to take a break, but perhaps I’ll get to stability later.

Posted by: Dan Doel on March 29, 2011 12:43 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

If I understand what the file says correctly, then I think being a homotopy pullback is more than that. It doesn’t just mean that every homotopy commutative square factors through it up to homotopy, uniquely up to homotopy. It also means that every path between commutative squares factors through, and every path between paths, and so on—in other words, the space of homotopy commutative squares is equivalent to the space of maps into the homotopy pullback. That is, the map

(f×g) X m:XA n:XB x:XPaths C(fmx,gnx) (f\times g)^X \to \sum_{m\colon X\to A} \; \sum_{n\colon X\to B} \; \prod_{x\colon X} Paths_C(f m x, g n x)

defined by h(fh,gh,ϕh) h \mapsto (f \circ h, g \circ h, \phi h) , is an equivalence. Hmm, I guess that may require functional extensionality.

(Homotopy theorists take note: this is an “internal” statement in the logic of the homotopy type theory, which is different from the “external” statement that the type in question is a homotopy pullback relative to the category-of-fibrant-objects homotopy theory on the category of types. I think the latter is basically immediate from the standard construction of homotopy pullbacks in a category of fibrant objects.)

Side note: I wish that in Agda we could use a notation for path-spaces more like the \rightsquigarrow that Andrej Bauer picked for his Coq files. The notation \equiv looks too much like equality for my comfort.

Posted by: Mike Shulman on March 29, 2011 5:32 PM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

If I understand what the file says correctly, then I think being a homotopy pullback is more than that. It doesn’t just mean that every homotopy commutative square factors through it up to homotopy, uniquely up to homotopy.

That’s what I get for staring at the 2-pullback definition trying to figure out what coherence condition I was missing as a premise.

That is, the map … defined by h(fh,gh,ϕh)h&#8614;(f&#8728;h,g&#8728;h,&#981;h), is an equivalence.

Is that all I have to prove? Because believe it or not, that was trivial, since definitional eta works for all the involved types. The file has been updated.

Side note: I wish that in Agda we could use a notation for path-spaces more like the ⇝ that Andrej Bauer picked for his Coq files.

We can. This module is entirely self-contained, so I picked the names. I just don’t really like prefix Id. I switched it to a long squiggly arrow (the short one is to squashed in monospace, I think). That kind of suggest a directionality that isn’t entirely appropriate for these types though, no (unfortunately, the emacs mode I’m using has no long, bidirectional squiggly arrow available)?

Posted by: Dan Doel on March 29, 2011 6:51 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Ah, beautiful! I forgot that Agda has definitional eta.

That kind of suggest a directionality that isn’t entirely appropriate for these types though, no?

Heh – Peter Lumsdaine and I had this argument. I think it is appropriate to suggest a directionality, because a particular element of a path-type does have a direction. It can always be reversed, but reversal is an operation, which produces an element of a different type. And reversal is only an involution up to homotopy.

Posted by: Mike Shulman on March 29, 2011 7:05 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Okay. Another update….

Hopefully I’m learning correctly, and wrote the correct proof from the start this time. I assume stability works like this: we have two homotopy pullback diagrams:

A× DB B A× DC C g h A f D A f D\begin{matrix} A \times_D B & \longrightarrow & B & \,\,\,\,\, & A \times_D C & \longrightarrow & C\\ \downarrow & & \downarrow\mathrlap{g} & & \downarrow & & \downarrow\mathrlap{h} \\ A & \underset{\scriptsize{f}}{\longrightarrow} & D & & A & \underset{f}{\longrightarrow} & D \end{matrix}

There is a morphism factor:(A× DB)+(A× DC)A× D(B+C)factor : (A \times_D B) + (A \times_D C) \to A \times_D (B + C). Stability means it is an equivalence.

Assuming I’ve got that right, my file has a proof. And so coproducts are disjoint and stable under pullback in intensional type theory, up to having to manually write in point-wise equality for functions in quite a few places (and adding the univalence axiom would allow the more categorical statements, due to function extensionality).

Posted by: Dan Doel on March 30, 2011 2:04 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

And so coproducts are disjoint and stable under pullback in intensional type theory

Can you also prove the full statement of universal colimits: that all homotopy colimits are stable under pullback?

Posted by: Urs Schreiber on March 30, 2011 8:09 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Well, we don’t yet know how to formalize the notion of “(,1)(\infty,1)-category” in homotopy type theory. (There are of course many possible definitions of an internal (,1)(\infty,1)-category in an (,1)(\infty,1)-category; the problem is that a priori they all involve specifying an infinite amount of data, so are not directly formalizable in the type theory.) So we can’t yet even write down what an arbitrary homotopy colimit would mean. Nor, actually, do we have enough axioms yet to prove that arbitrary homotopy colimits exist, even if we could define what they would mean. You can see that we are still at an early stage in many ways.

Posted by: Mike Shulman on March 30, 2011 10:24 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Mike> specifying an infinite amount of data …

Could Martin-Lof’s Mathematics of infinity be relevant in any of this?

Posted by: Bas Spitters on March 31, 2011 8:18 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Could Martin-Löf’s Mathematics of infinity be relevant in any of this?

I don’t think so, not precisely.

Of course there are ways to specify an “infinite amount of data” in type theory. We can give a function X\mathbb{N}\to X, which specifies infinitely many elements of XX (where \mathbb{N} is defined inductively). Or we can consider coinductive types. And certainly it seems likely that a solution to the problem referred to will involve one or both of these ideas or similar ones, and a number of us are currently working on that question. It’s just not clear yet exactly how to do it.

Martin-Löf’s Mathematics of Infinity starts off by considering many examples of coinductive objects, so it is related in that sense. But instead of distinguishing inductive from coinductive definitions, it looks to me like he considers the result of adding axioms requiring that the coinductive “infinite” objects already exist in the ordinary inductively defined type. This turns out to give a type-theoretic analogue of nonstandard analysis, which is very interesting! But doesn’t seem to me to have immediate relevance to the problem at hand.

Posted by: Mike Shulman on March 31, 2011 11:01 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

the problem is that a priori they all involve specifying an infinite amount of data, so are not directly formalizable in the type theory

Okay, i see.

Nor, actually, do we have enough axioms yet to prove that arbitrary homotopy colimits exist

How about just homotopy pushouts? Can one prove they exist? Can one show they are stable under homotopy pullback? Can one show the pasting law for homotopy pullbacks and pushouts? Or: do you expect that this can be done?

Posted by: Urs Schreiber on March 31, 2011 7:10 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

So far, in these posts, I’ve been working in intensional type theory with a version of function extensionality. But I haven’t introduced any axioms yet which contradict extensional type theory, so the basic theory still has sound semantics in any locally cartesian closed category. Including inductive type constructors gives us coproducts, at least, and some other things, but as far as I know it doesn’t imply quotients, pushouts, coequalizers, or any colimit of that sort.

Having a subobject classifier is enough to construct quotients of equivalence relations on sets, and thereby colimits in the extensional world of 0-types, but I don’t think it suffices for homotopy colimits of higher types. An exactness axiom should be enough, if we can figure out how to write it down. One can do some things with the univalence axiom too, but it’s not clear to me exactly how far it gets you.

The pasting lemma for homotopy pullbacks, however, I expect would not be difficult.

Posted by: Mike Shulman on March 31, 2011 8:01 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

One can do some things with the univalence axiom too, but it’s not clear to me exactly how far it gets you.

Could you post about what you is possible with the univalence axiom?

My own interest is in smoothly treating “naive constructive reasoning” – i.e., simple algebra and analysis handled in Bishop style. Basically, I do program verification, and a lot of program verification works with only elementary algebra and category theory. But I desperately need support for coequalizers and coinduction to do this cleanly.

I’d be quite happy with an exotic story for big/complex types, as long as the simple stuff looked reasonably familiar (at least to a constructivist).

Posted by: Neel Krishnaswami on April 1, 2011 1:23 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Another nice extreme example is that the homotopy pullback of the diagonal XX×XX\to X\times X with itself is the free loop space of XX.

Posted by: Mike Shulman on March 29, 2011 6:54 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

That’s reassuring. So probably disjointness will be okay.

Posted by: Mike Shulman on March 23, 2011 7:50 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

these mysterious exactness axioms

By the way, I think the idea of these exactness axioms shouldn’t be mysterious to anyone familiar with (,1)(\infty,1)-topoi. We just want an analogous property to the “exactness” part of the (,1)(\infty,1)-Giraud theorem: every internal groupoid is effective. (If I write a Part IV about exactness, then I’ll try to explain that for people not familiar with (,1)(\infty,1)-topoi.) The only mysterious part (currently) is phrasing that formally in the type theory, since an internal groupoid a priori involves an infinite amount of data.

Posted by: Mike Shulman on March 21, 2011 4:36 AM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

If IsContrIsContr plays such an important role here, perhaps IsFutureContrIsFutureContr and IsPastContrIsPastContr (as in directed algebraic topology) will feature in a theory of directed identity types.

Posted by: David Corfield on March 21, 2011 10:39 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

There’s a start on this in Dan Licata’s PhD thesis – he uses a directed interpretation of type (ie, types as 1-categories rather than 1-groupoids) – the idea is that the step to directedness takes you from equivalence to coercibility.

He uses this to describe certain properties of substitution, which is one of the noninvertible operations of interest to logicians. :)

Posted by: Neel Krishnaswami on March 22, 2011 12:02 AM | Permalink | Reply to this

Re: Homotopy Type Theory, II

Awesome! Thanks, I hadn’t seen that yet. I’d been sort of stumbling towards something similar; perhaps the same thing has occurred to other people too. (I think I remember some conversations about this stuff at CMU last year?) Anyway, it looks like Dan Licata has pushed these ideas further, dealing successfully with co- and contra-variance of type dependencies. He assumes an involution () op(-)^{op}, which I wouldn’t want to do in general (since I think there are potentially interesting 2-toposes that lack such an involution), but probably that is not essential.

For the (,)(\infty,\infty)-categorical theory, though, I still dream that we might think of a way to have “directed identity types” with elimination and computation rules analogous to the symmetrical ones.

Posted by: Mike Shulman on March 23, 2011 9:41 PM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

From a homotopy perspective, is natural to call this “squashed” type π 1(Z)\pi_{-1}(Z).

Don’t you mean the (-1)-truncation τ 1(Z)\tau_{\leq -1}(Z) of ZZ?

Posted by: Urs Schreiber on March 21, 2011 1:13 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

How is that different?

Posted by: Mike Shulman on March 21, 2011 6:02 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

How is that different?

“From a homotopy perspective” there is no π 1\pi_{-1}. There is a (1)(-1)-truncation. Generally, the idea of “squashing a type down to an nn-type” is that of nn-truncation, not of forming the nnth homotopy group.

Posted by: Urs Schreiber on March 21, 2011 7:39 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

It’s true that by π 1\pi_{-1} I meant to indicate the (-1)st fundamental groupoid (which is another name for the (-1)st truncation), not the “(-1)st homotopy group.” I’m not even quite sure what the latter would mean. But homotopy groups for n0n\ge 0 do also make perfect sense in a homotopical foundation: π 0\pi_0 is the 0th truncation, and π n\pi_n is the 0th truncation of the nnth loop space.

(If we’re working in the internal language of an (,1)(\infty,1)-topos, then these are of course the “categorical” homotopy groups rather than the “geometric” ones, the latter not being “internal.”)

There’s a bit of a problem that it’s common to write Π n\Pi_n for the groupoid and π n\pi_n for the group, but in type theory, capital Π\Pi means something different! It’s true that τ n\tau_{\le n} is another possibility, and perhaps the best one, although I’m wary of that notation ever since you pointed out that Lurie uses it for two incompatible things.

I guess we could also generalize the Awodey-Bauer notation and write [Z] n[Z]_n, or perhaps [Z] n+2[Z]_{n+2}.

Posted by: Mike Shulman on March 21, 2011 8:04 PM | Permalink | PGP Sig | Reply to this

Re: Homotopy Type Theory, II

There’s a bit of a problem that it’s common to write Π n\Pi_n for the groupoid and π n\pi_n for the group, but in type theory, capital Π\Pi means something different!

But shouldn’t you be typing

  \prod

rendering to

\prod

for the dependent product, instead of

 \Pi

rendering to

Π\Pi

?

It would seem helpful to carefully harmonize notation when making the connection to homotopy theory. For instance I am looking at Coquand’s slide 30 from the conference, and see the assertion/definition

π 1(X,a)=Id Xaa\pi_1(X,a) = Id_X a \; a

Shouldn’t this read instead

Ω aX=Id Xaa\Omega_a X = Id_X a \; a

?

I suppose this is what the warning on slide 32 is meant to refer to. But it seems to me with other notation no warning here would be necessary.

Posted by: Urs Schreiber on March 21, 2011 9:57 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I don’t really like the look of \prod for dependent products; it’s too big and ugly, and I don’t want the indexing variable underneath it, instead of as a subscript, when displayed. (-: Same with \sum and \Sigma.

I think the π 1\pi_1/Ω\Omega issue in Coquand’s slides is separate, though related. I pointed that out to him at the conference and he agreed that it should really be Ω\Omega.

Posted by: Mike Shulman on March 21, 2011 10:03 PM | Permalink | Reply to this

Re: Homotopy Type Theory, II

I don’t really like the look of \prod for dependent products; it’s too big and ugly, and I don’t want the indexing variable underneath it, instead of as a subscript, when displayed.

You can't do this in iTeX, but in TeX you can write \prod\nolimits to get the indexing variable as a subscript even when displayed. (I have \product in my personal set of macros, with this definition.)

Posted by: Toby Bartels on March 23, 2011 7:18 AM | Permalink | Reply to this
Read the post Homotopy Type Theory, IV
Weblog: The n-Category Café
Excerpt: Voevodsky's "univalence axiom" for universes in homotopy type theory, and the equivalent principle of "equivalence induction."
Tracked: April 7, 2011 5:20 AM
Read the post Homotopy Type Theory, V
Weblog: The n-Category Café
Excerpt: What's still missing to make homotopy type theory into a complete internal language for (∞,1)-topoi?
Tracked: April 12, 2011 5:18 AM
Read the post Homotopy Type Theory, VI
Weblog: The n-Category Café
Excerpt: A homotopical extension of the notion of "inductive definition" allows us to construct CW complexes and mimic other constructions from homotopy theory in type theory.
Tracked: April 25, 2011 7:55 AM
Read the post The King of France
Weblog: The n-Category Café
Excerpt: Bringing dependent type theory to philosophy
Tracked: February 1, 2013 3:52 PM

Post a New Comment