[Agda] Proofs for enumerated types
Gregory Crosswhite
gcross at phys.washington.edu
Sat Sep 11 00:01:06 CEST 2010
Hey everyone! I am in the early stages of playing around with agda in
order to get a feel with how to use it.
I have got an enumeration type, Pauli:
data Pauli : Set where
I : Pauli
X : Pauli
Y : Pauli
Z : Pauli
And I have a product on this type:
_⋅_ : Pauli → Pauli → Pauli
_ ⋅ I = I
I ⋅ _ = I
X ⋅ X = I
X ⋅ Y = Z
X ⋅ Z = Y
Y ⋅ X = Z
Y ⋅ Y = I
Y ⋅ Z = X
Z ⋅ X = Y
Z ⋅ Y = X
Z ⋅ Z = I
This product is associative and commutative. In order to prove that it
is commutative, I used brute force:
open import Relation.Binary.PropositionalEquality as PropEq
using (_≡_; _≢_; refl; sym; cong; cong₂)
import Algebra.FunctionProperties as P; open P _≡_
+-comm : Commutative _⋅_
+-comm I I = refl
+-comm I X = refl
+-comm I Y = refl
+-comm I Z = refl
+-comm X I = refl
+-comm X X = refl
+-comm X Y = refl
+-comm X Z = refl
+-comm Y I = refl
+-comm Y X = refl
+-comm Y Y = refl
+-comm Y Z = refl
+-comm Z I = refl
+-comm Z X = refl
+-comm Z Y = refl
+-comm Z Z = refl
However, I feel like there should be a more elegant way of doing this.
Since the type is a set that only contains a finite number of values,
such properties as associativity, commutativity, existence of an inverse
(I), etc. can be proven by performing a brute-force examination of all
the possibilities. There is probably a way to do this somewhere in the
standard libraries, but there is so much there and so many layers of
abstraction that I'm not sure where it is. :-) I saw the Fin type and
something whose type overwhelmed me a bit but which looked like a way
for me to establish that there are only a finite number of values in
Pauli, but I couldn't see how proving that would open up new proof tools
for me within the library.
So do you all have any suggestions? :-) Thanks in advance!
- Greg
More information about the Agda
mailing list