Skip to content

Group theory in Agda, including a proof of Lagrange's theorem.

License

Notifications You must be signed in to change notification settings

nosewings/agda-group-theory

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

27 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Where's the good stuff?

Look in Algebra.Group.Lagrange. The proof term lagrange of Lagrange's theorem is at the bottom of the file.

Note that even the type of the theorem already contains a nontrivial assumption: the definition of size-of. There are multiple definitions of finiteness in MLTT; indeed, there are multiple non-equivalent ways to define finiteness. The definition under consideration here is first defined in Finite.UList.Core.

Where's the bad stuff?

Everything under Base is pretty boring, and not all of it is strictly necessary. List.One is necessary, but it feels like there should be a better way to accomplish it.

Everything related to finiteness is unfortunate. Especially notable: if B is finite and there is an injection from A to B, we can't prove that A is finite.

Okay, where's the really bad stuff?

Set-partitions are a disaster. In retrospect, this is unsurprising: set-partitions are an inherently set-theoretical concept. But it is hard to imagine how to prove Lagrange's theorem without them. This is a real problem for MLTT: extremely basic combinatorics takes a ridiculous amount of work. Indeed, all the real work in this "proof of Lagrange's theorem" went into a proof that (essentially) the sum of the sizes of the constituents of a set-partition is equal to the size of the original set. The proof term for that fact is in Finite.Partition; but if you want to see some truly horrifying stuff, check out Finite.Partition.Pseudo. Pay particular attention to the type of stupid-lemma (and the accompanying stupid-lemma-lemma). Finite.Partition.Core, while intimidating at first, is comparatively quite nice. Also check out Finite.UList.Partition.

About

Group theory in Agda, including a proof of Lagrange's theorem.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published