agda-stdlib
agda-stdlib copied to clipboard
Adding new reasoning combinators
Fascinating how these next proofs are essentially the
cancelandelim(left and right) combinators inCategories.Morphism.Reasoning!
Originally posted by @JacquesCarette in https://github.com/agda/agda-stdlib/pull/2251#discussion_r1469634123
The point would be that for binary operations for which we have congruence (i.e. everything above Magma), there are additional combinators that we can create. Even more above Semigroup, where we also get associativity, and also Monoid (unital).
So we should get more and more reasoning power as we move up.
Naming:
- Is
cancelactually an instance of aCancellativeproperty? - Is there a more memorable/less generic name than
elimfor the other one?
- No, as
Cancellativehave a different shape andcancel-left:x * y = e -> x * (y * z) = zforea unit. It is a chain of assoc, apply on left, left-unit. (There'scancel-righttoo). -
elim-idwould be slightly better. The comments above the definition of those combinators is
-- Introduce/Elimilate an equivalent-to-identity
-- on left, right or 'in the middle' of something existing