[Agda] problem with algebraic hierarchy

a.j.rouvoet a.j.rouvoet at gmail.com
Mon Aug 10 18:27:18 CEST 2020


Dear Sergei,

The problem you encounter is wellknown under the name 'the (un)bundling 
problem':
i.e., the problem of choosing which fields should be parameters, and 
which should be fields.
The problem is hard, in the sense that every permutation you can think 
of has applications.
The Agda standard library chooses to do what most other languages have 
done previously: i.e., provide a unbundled IsStructure, and a bundled 
Structure.

The variation you propose has merits, but equally many demerits. Until 
we can dynamically bundle/unbundle, I don't think there is much to be 
said for a particular different variation.
There has been some recent attention for this language feature by 
various people and the Arend proof assistant.

Cheers,

Arjen

On 8/10/20 6:04 PM, mechvel at scico.botik.ru wrote:
> We wrote the following to GitHub for the library:
>
> mechvel
> -------
> I wonder: how to express in Agda-2.6.1 + lib-1.3 the following discourse?
> Let R and U be semirings having the same additive monoid 
> (+-commutativeMonoid).
> Denote * and *' the multiplication operators in R and U respectively,
> 1# and e the unities in R and U respectively. Prove in Agda that
>
> for all x in R  it holds  (1# + 1#) * x ≈ (e + e) *' x     -- (I)
>
> And let us assume that the lemma 2*as+ : ∀ x → (1# + 1#) * x ≈ x + x
> is proved in the module OfSemiring parameterized by Semiring
> (it is proved simply in 2-4 steps).
> Mathematically, the statement (I) has sense.
> And its proof is simple: the left hand side equals x + x by the laws 
> of R;
> the right hand side equals x + x by the laws of U, and this is the same
> element of their common Carrier.
> The matter is not in the proof itself, it is in finding a valid 
> formulation
> of the theorem (I) in Agda.
> Can anybody, please, demonstrate?
>
>
> Matthew Daggitt
> ---------------
>> This is not a question for the standard library.
>> Best to ask this on the mailing list.
>
>
> No, it is for the standard library.
> But let it be, I write to the Agda list.
>
> For example, if the library was organized in a different way, the 
> following code would work:
>
> -----------------------------------------
> theorem : ∀ {α α≈} (S : Setoid α α≈) (+cMon : CommutativeMonoid S)
>                                      (*Mon  : Monoid S)
>                                      (*'Mon : Monoid S)
>                    (R : Semiring S +cMon *Mon) (U : Semiring S +cMon 
> *Mon) →
>                    let open Semiring R
>                        open Semiring U using ()
>                                        renaming (_*_ to _*'_; 1# to e)
>                    in
>                    (x : Carrier) → (1# + 1#) * x ≈ (e + e) *' x
>
> theorem S R +cMon *Mon *'Mon R U x =
>     begin
>       (1# + 1#) * x  ≈⟨ OfSemiring.2*as+ R x ⟩
>       x + x          ≈⟨ sym (OfSemiring.2*as+ U x) ⟩
>       (e + e) *' x
>     ∎
> ------------------------------------------
>
> Here Magma, Semigroup, Monoid, CommutativeMonoid  have an argument of 
> the Setoid type.
> Semiring has arguments (S : Setoid _ _), (+M : CommutativeMonoid S),
> (*M : Monoid S).
>
> Also this solves the problem of a common setoid for +-magma and 
> *-magma in a semiring
> (of what we wrote earlier).
>
> I do not say that everything is all right there.
> But generally, it has sense to think of experimental libraries that 
> reorganize the
> algebraic part, of different ways to transfer the domain parameters.
>
> The first step may be setting (S : Setoid) as an argument as above.
> This will improve much, without spoiling anything.
> But I am not sure that this will be sufficient.
>
> Regards,
>
> ------
> Sergei
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda


More information about the Agda mailing list