[Agda] How can we define a type of symmetric binary operations in Agda ?

Dr. ÉRDI Gergő gergo at erdi.hu
Tue May 5 08:27:12 CEST 2015


What about creating them such that they are symmetric by construction? If
we had quotient types, one could easily make an "unordered pair" type, and
make unary relations over that.

Are there any useful tricks to do something similar in Agda?
On May 1, 2015 3:07 PM, "Andreas Abel" <abela at chalmers.se> wrote:

> You can create a record with two fields, one is your binary operation, the
> other the proof of symmetry.
>
> record SymBinOp : Set where
>   field
>     _⊙_ : BinaryOperation
>     proof-of-symmetry : ∀ x y → x ⊙ y == y ⊙ x
>
> That's it!
>
> On 30.04.2015 17:35, Sergey Kirgizov wrote:
>
>> Hello,
>>
>> I don't  understand how  we can  define in Agda  a type  of "Symmetric
>> Binary Relation". Can you help me?
>> Imagine I have something like:
>>
>> =======================================================
>>
>> {-
>>    At first we reaname  Set
>>
>> {-
>>    First, we define a polymorphic idenity
>> -}
>> data _==_ {A : 𝓤} (a : A) : A → 𝓤 where
>>    definition-of-idenity : a == a
>> infix 30 _==_
>>
>> {-
>>   Next we define the finite set Ω = {A,B,C}
>> -}
>> data Ω : 𝓤 where
>>    A B C : Ω
>>
>> {-
>>   We add a type "Binary operation"
>> -}
>> BinaryOperation = Ω → Ω → Ω
>>
>> {-
>>   I can actually define an example of Binary operation.
>> -}
>> _⊙_ : BinaryOperation
>> x ⊙ x' = A
>> infix 40 _⊙_
>>
>> {-
>>   And then I can proove that ⊙ is Symmetric
>> -}
>> proof-of-symmetry : ∀ x y → x ⊙ y == y ⊙ x
>> proof-of-symmetry = λ x y → definition-of-idenity
>>
>>
>> ========================================================
>>
>> How we  can define a  type "Symmetric Binary Operation"?   Having this
>> type we will be able to define ⊙ as
>>
>> _⊙_ : SymmetricBinaryOperation
>> x ⊙ y = A
>>
>> and proof that ⊙ is symmetric will no be required.
>>
>>
>> Best regards,
>> Sergey
>> _______________________________________________
>> Agda mailing list
>> Agda at lists.chalmers.se
>> https://lists.chalmers.se/mailman/listinfo/agda
>>
>>
>
> --
> Andreas Abel  <><      Du bist der geliebte Mensch.
>
> Department of Computer Science and Engineering
> Chalmers and Gothenburg University, Sweden
>
> andreas.abel at gu.se
> http://www2.tcs.ifi.lmu.de/~abel/
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20150505/90095d46/attachment.html


More information about the Agda mailing list