[Agda] Tips for working around proof relevance
James Wood
james.wood.100 at strath.ac.uk
Sun Dec 20 23:16:41 CET 2020
On 20/12/2020 17:04, Jacques Carette wrote:
> The reason for sym-assoc is for definitional equality. This way C.op.op
> is definitionally equal to C. Otherwise, it is merely propositionally
> equal, and this means that some things that normally typecheck in
> category theory no longer do.
The way stdlib is set up, you don't even get propositional equality
without some extra work. With the naïve definition (i.e, the
agda-categories definition without sym-assoc), we get that
op (op C) .assoc f g h = sym (sym (C .assoc f g h)) .
To get a propositional equality from this to C .assoc f g h, we would
need Setoid to give us some propositional equations. We could either
enforce that the equivalence relation is h-prop-valued (probably the
right thing) or add groupoid coherence laws. On top of that, we would
need function extensionality.
In any case, we should at least get an equivalence of categories, though
I'm not sure how useful that is in practice in a non-univalent setting.
In general, I think it's an interesting phenomenon that we can get
ourselves into situations where judgemental equality is the only hope.
The other example I can think of is how you can have a (badly behaved)
category of Sets in plain Agda without using setoids because _∘_ is
judgementally unital and associative.
James
More information about the Agda
mailing list