[Agda] problem with algebraic hierarchy
mechvel at scico.botik.ru
mechvel at scico.botik.ru
Mon Aug 10 20:14:27 CEST 2020
On 2020-08-10 19:27, a.j.rouvoet wrote:
> 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.
I have provided two sensible examples showing a merit.
Can you provide a sensible example showing a demerit?
A generic discourse, notes, objections can be understood when there are
given examples.
Very often I start to understand of what I intend to tell only after
considering examples.
I expect the same is, more or less, with other authors.
Regards,
--
SM
> 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.
> [..]
> 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
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
More information about the Agda
mailing list