[Agda] How can we define a type of symmetric binary operations
in Agda ?
Andreas Abel
abela at chalmers.se
Tue May 5 11:27:17 CEST 2015
Looks like you want a higher inductive type...
On 05.05.2015 08:27, Dr. ÉRDI Gergő wrote:
> 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
> <mailto: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 <mailto: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 <mailto:andreas.abel at gu.se>
> http://www2.tcs.ifi.lmu.de/~abel/
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se <mailto: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/
More information about the Agda
mailing list