A Formal Proof that the Higher Fundamental Groups are Abelian

Homotopy type theory (HoTT) will have applications for both computer science and math. On the computer science side, applications include using homotopy type theory’s more general notion of equality to make formal verification of software easier. On the mathematical side, applications include using type theoretic proof assistants, like Coq and Agda, to give formal, machine-verified, proofs of mathematical theorems. We’d like to show that HoTT is useful for formalizing homotopy theory and higher-dimensional category theory, and then that the ability to work up-to-equivalence is useful for other parts of math as well.

As a first example of the former, we can prove the well-known result that the higher homotopy groups of a topological space are all abelian.

Given a space A and a distiguished base point base, the fundamental group π1 is the group of loops around the base point. π1 has, as elements, the loops at base—paths from the base point to itself—with the group multiplication given by composition, and the identity element by the identity path. However, to satisfy associativity and unit, the paths must be quotiented by homotopy.

However, the homotopies, or deformations of paths, themselves have some structure, and we can look at the second fundamental group π2, which is the same construction “one level up”: take the base point to be the identity loop at the original base point base, and then look at the homotopies from this loop to itself (again quotiented by higher homotopies).

It turns out that the second fundamental group, and all higher ones obtained by iterating this construction, are abelian. The way we’ll prove this is to show that there are two different notions of composition on them, which have the same unit and satisfy an interchange law, so the result follows from the Eckmann-Hilton argument. What are the two notions of compostion? The first is the multiplication from π2, which is just composition/transitivity of homotopies/deformations. The second uses composition of loops one level down (which explains why the fundamental group is not necessarily abelian), and states that composition preserves deformability. Namely, if you have four loops around base, p q p' q' and a deformation from p to p' and a deformation from q to q', then you can compose these to give a deformation from q ∘ p to q' ∘ p'. Now, take all four loops to be the identity, in which case we have an operation that takes two elements of π2 (i.e. two deformations from the identity loop to itself) and gives back a third (by the unit laws, id ∘ id = id).

Next, we are going to formalize this proof in type theory. In particular, I will use Agda, though the proof could easily be translated to Coq.

Here are the basic definitions:

    
module FundamentalAbelian (A : Set) (base : A) where
    π1El : Set
    π1El = base ≃ base
    π2El : Set
    π2El = _≃_{π1El} Refl Refl 

    _∘_ : π2El → π2El → π2El 
    p ∘ q = trans q p

    _⊙_ : π2El → π2El → π2El 
    a ⊙ b =  resptrans b a

    ⊙-unit-l : (p : π2El) → (Refl ⊙ p) ≃ p
    ⊙-unit-l p = resptrans-unit-r p 

    ⊙-unit-r : (a : π2El) → (a ⊙ Refl) ≃ a
    ⊙-unit-r a = trans (resptrans-unit-l a) (trans-unit-l a) 

    interchange : (a b c d : _) 
                       → ((a ∘ b) ⊙ (c ∘ d)) ≃ ((a ⊙ c)  ∘ (b ⊙ d))
    interchange a b c d = trans-resptrans-ichange  _ _ d _ c _ _ b _ a

We define a module parametrized by a set A (Agda uses the word Set for ‘type’) and a term base of that type: the proof works for any space and base point. The type π1El (the elements of π1) is defined to be the loops at base, represented using the identity type M ≃ N, which is defined in a library. Similarly, the elements of π1 are the loops (at type π1El) at reflexivity. The two notions of composition discussed above are defined in the identity type library, with ∘ defined by transitivity, and ⊙ defined by resptrans–the proof that transitivity respects equivalence.

⊙-unit-l proves the left unit law for ⊙. The way to read this declaration is (1) ⊙-unit-l is a term of type (p : π2El) → (Refl ⊙ p) ≃ p (where (x : A) → B is Agda syntax for a Pi-type), and (2) it is defined to be the term λ p → resptrans-unit-r p. That is, it is implemented by a straightforward application of a lemma in the identity type library. ⊙-unit-r is similar, except it takes two lemmas to prove: the general resp-trans-unit-l states that resptrans Refl a is equal to a composed with proofs that cancel trans - Refl (transitivity with reflexivity on this side is propositionally but not definitionally the identity, for the way I have defined transitivity); however, in this case, these transitivities cancel, because the base point is reflexivity.

The middle-four interchange law states an interaction between the two notions of composition, which is key to the proof below. It is proved using an application of a lemma from the library.

Now, we can give a simple formalization of the Eckmann-Hilton argument, which proves that the two compositions are the same, and abelian:

    same : (a b : π2El) → (a ∘ b) ≃ (a ⊙ b)
    same a b = (( a ∘ b)              ≃〈 resp (λ x → x ∘ b) (sym (⊙-unit-r a)) 〉 
             ((a ⊙ Refl) ∘ b)         ≃〈 resp (λ x → (a ⊙ Refl) ∘ x) (sym (⊙-unit-l b)) 〉 
             ((a ⊙ Refl) ∘ (Refl ⊙ b)) ≃〈 sym (interchange a Refl Refl b) 〉 
             ((a ∘ Refl) ⊙ (Refl ∘ b))  ≃〈 resp (λ x → x ⊙ (Refl ∘ b)) (trans-unit-l a) 〉 
             (a ⊙ (Refl ∘ b))         ≃〈 resp (λ x → a ⊙ x) (trans-unit-r b) 〉 
             (a ⊙ b) 
             ∎)

    abelian : (a b : π2El) → (a ∘ b) ≃ (b ∘ a)
    abelian a b = (a ∘ b)               ≃〈 resp (λ x → x ∘ b) (sym (⊙-unit-l a)) 〉 
                ((Refl ⊙ a) ∘ b)           ≃〈 resp (λ x → (Refl ⊙ a) ∘ x) (sym (⊙-unit-r b)) 〉 
                ((Refl ⊙ a) ∘ (b ⊙ Refl)) ≃〈 interchange Refl b a Refl 〉 
                ((Refl ∘ b) ⊙ (a ∘ Refl))  ≃〈 resp (λ x → x ⊙ (a ∘ Refl)) (trans-unit-r b) 〉 
                (b           ⊙ (a ∘ Refl))  ≃〈 resp (λ x → b ⊙ x) (trans-unit-l a) 〉 
                (b ⊙ a)                     ≃〈 sym (same b a) 〉 
                (b ∘ a) 
                ∎

The proof is exactly the textbook Eckmann-Hilton argument. We use a notational trick to write the proof as a sequence of steps x ≃〈 p 〉y, which is read x is equivalent to y by p. To prove that the compositions are the same, we expand using the unit laws, apply interchange, and then contract. To prove that they are abelian, we expand using the unit laws, apply interchange, and contract, which swaps the order but also swaps the composition; so same gives the result. In the proofs, resp is a general compatibility lemma, which lifts an equation into a context (given by the function in its first argument).

The thing to take away from this post is that, after developing some libraries for identity types, we were able to use a simple, clean transcription of the Eckmann-Hilton argument to give a formal proof of the result. In the next post, I’ll talk about the lemmas we used from the identity type library.

Technical caveat: following the discussion here (if I have understood it correctly; if not please correct me), what this theorem really states is that composition in the loop space is abelian, up to higher homotopies (because the statement of the theorem itself uses the identity type). This is slightly different than stating that the fundamental group is abelian. The difference is that the loop space is itself a whole higher-dimensional space, with “external” higher-dimensional homotopies, whereas the fundamental group theorem talks about the group whose elements are paths quotiented by homotopy. Our theorem statement is like saying that two numbers are congruent mod k, whereas the theorem about fundamental groups is like saying that two elements of Z/kZ are equal. Of course, it’s easy to go between these, but to state the latter version in type theory, we will need a form of quotient types that lets one quotient by higher dimensional structure to obtain a lower-dimensional type.

The code for this post is here, for now, until I make a GitHub repository. Thierry Coquand and Nils Anders Danielsson have a proof here, but it seems to use a different argument than Eckmann-HIlton.

About these ads
This entry was posted in Applications. Bookmark the permalink.

13 Responses to A Formal Proof that the Higher Fundamental Groups are Abelian

  1. Mike Shulman says:

    Nice! I think you understood the discussion about loop spaces correctly. Given that the theorem is really about loop spaces, why not use the homotopically correct notation \Omega^n X rather than \pi_n X?

    I would be surprised if Thierry and Nils’ proof is materially different from the Eckmann-Hilton argument. Glancing at it briefly, it looks about the same but just keeping track of all the “unitor” isomorphisms, although it’d take some time to puzzle out exactly what everything means.

    One day, maybe someone will write a proof assistant that understands higher-dimensional pasting or string diagrams directly. (-:

    • Steve Awodey says:

      The statement for \pi_n X certainly follows from the proof given, and since the higher homotopy groups are more familiar to non-specialists, it seems reasonable to me to state it this way in this forum.

      • Mike Shulman says:

        I just meant that in the Agda file itself, the object defined as “\pi_n” is actually \Omega^n. Certainly, when explaining it to nonspecialists it makes sense to talk about homotopy groups, but in the actual code we can be precise, no?

        • Dan Licata says:

          I basically agree with you, Mike, and in a ‘real’ development I would probably use the loop space notation. Here, I used the fundamental group notation because a couple of people that I explained this to knew about fundamental groups (from an undergrad topology course) but not loop spaces.

          Re: Thierry and Nisse’s proof: from a very cursory glance, I couldn’t find the definition of ‘resptrans’–maybe it’s inlined? That’s what made me think it was a different argument.

        • Steve Awodey says:

          sure.

    • Mike Shulman says:

      It looks to me like rather than proving directly that \Omega^2 X is commutative, Thierry and Niesse prove a bit more abstractly first that given any type equipped with a binary operation that has a 2-sided unit e, the composition of endo-paths of e is commutative. This is a well-known equivalent version of the Eckmann-Hilton theorem. Then they apply that to the endo-paths of the basepoint of a type X, equipped with the composition operation, to deduce that \Omega^2 X is commutative. I think the equivalent of your resptrans may be hiding in their operations called cong and cong2.

      • Dan Licata says:

        Ooh, you’re right. On a slightly longer glance, I see that lc and rc are defined in terms of cong, which is definitely the equivalent of resptrans :)

  2. Steve Awodey says:

    I think one of the most interesting things about these proofs is the way they use a sort of “synthetic” reasoning about path-spaces: rather than treating them as maps from the unit interval and reparameterizing, etc., one uses the the Id-elim rule as a (weak) universal property of the path space itself — what Andrej Bauer has termed “path induction”. This is a proof method that — to my knowledge — is not used in traditional homotopy theory (although it is, to be sure, related to weak factorization system lifting properties).

    It’s use is based on the reading of the Id-type as (some sort of weak) identity relation, generalizing from predicate logic to the constructive setting, where one has to also keep track of “evidence” or proof terms. In fact, the Id-elim rule itself can be recognized as essentially Lawvere’s adjoint rule for equality, but decorated with proof-terms.

    I would expect this (new?) point of view should shed a different light on other constructions in classical homotopy theory as well. Another simple example is the interpretation of fibrations as “predicates” — i.e. families of (proof-relevant) propositions that respect “identity”.

    • Mike Shulman says:

      I agree, to a certain extent. In one of my nCafe posts, I thought of writing something like “in this way the type-theoretic proofs that equality is transitive and symmetric can be identified with the model-category-theoretic proofs that homotopies can be composed and reversed,” but then when I unraveled the proofs, as far as I could tell they were actually different! That surprised me. Of course, it’s not immediately clear that path induction will always work in traditional homotopy theory, since a weak factorization system has to have certain very special properties to model identity types.

      On the other hand, it seems that once we use path induction to prove the basic facts about composition of paths, the Eckmann-Hilton argument is proven in the same way as in homotopy theory.

      • Richard Garner says:

        I think the correct level of generality is: if for a weak factorisation system (L,R) you assume that the L-maps are stable under pullback along the R-maps—as in, e.g., R=Kan fibrations of simplicial sets, or R=Hurewicz fibrations of topological spaces—then the homotopy relation defined in terms of path objects will be symmetric and transitive at any fibrant object, with the same proof as the type-theoretic one.

  3. Pingback: Just Kidding: Understanding Identity Elimination in Homotopy Type Theory | Homotopy Type Theory

  4. Pingback: Another Formal Proof that the Higher Homotopy Groups are Abelian | Homotopy Type Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s