Free Groups in Agda
nomeata’s mind shares

I must say that I do like free groups. At least whenever I play around with some theorem provers, I find myself formalizing free groups in them. For Isabelle, my development of free groups is already part of the Archive of Formal Proofs. Now I became interested in the theorem prover/programming language Agda,so I did it there as well. I was curious how well Agda is suited for doing math, and how comfortable with intuitionalistic logic I’d be.

At first I wanted to follow the same path again and tried to define the free group on the set of fully reduced words. This is the natural way in Isabelle, where the existing setup for groups expects you to define the carrier as a subset of an existing type (the type here being lists of generators and their inverses). But I did not get far, and also I had to start using stuff like DecidableEquivalence, an indication that this might not go well with the intuitionalistic logic. So I changed my approach and defined the free group on all words as elements of the group, with a suitable equivalence relation. This allowed me define the free group construction and show its group properties without any smell of classical logic.

The agda files can be found in my darcs repository, and the HTML export can be browsed: Generators.agda defines the sets-of-generators-and-inverses and FreeGroups.agda (parametrized by the Setoid it is defined over) the reduction relation and the group axioms. Here are some observations I (disclaimer: Agda-beginer) made:

• Fun fact: Free groups exist not only in classical logic.
  
• Without any automation as in Isabelle, even simple things get quite complicated. A simple substitution of an equality with subst requires me to specify not only the equality and the term I want it to apply, but also to repeat the common part of the terms. Or when using the associativity of list concatenation, I have to pass all three sublists to the lemma. Maybe I am a bit spoiled by Isabelle, but I’d be worried that this would prevent large proofs.
• The levels are also annoying. Although my theory stays within one level, I have to annotate it everywhere. I’d expect the type inference to figure this out for me.
• Equality reasoning with begin ... ∎ is quite nice and surprisingly well readable.
• Besides the additional work, it is nice to be able to do the proof in almost all detail. There is a limitation, though, as some steps are done automatically (if they happen to occur when evaluating/normalizing a term) and the others, even if similar-looking, are not.
  
• It’d be great if one would be free in the choice of editor, but vim users generally have a hard time in the field of theorem provers.
  

If I were to extend this theory, there are two important facts to be shown: That there is a unique reduced word in every equivalence class (norm_form_uniq), and the universal property of the free group. For the former (started in NormalForm.agda) I’m missing some general lemmas about relations (e.g. that local confluence implies global confluence, and even the reflexive, symmetric, transitive hull is missing in the standard library). For the latter, some general notions such as a group homomorphism need to be developed first.

I planned to compare the two developments, Isabelle and Agda. But as they turned out to show quite things in different orders, this is not really possible any more. One motivation to look at Agda was to see if a dependently typed language frees me from doing lots of set-element-checking (see the “mems” lemma in the Isabelle proof of the Ping-Pong-Lemma). So far I had no such problems, but I did not get far enough yet to actually tell.

Thanks to Helmut Grohne for an educating evening of Agda hacking!