Proving Propositional Equality¶
This page attempts to explain some of the techniques used in Idris to prove propositional equalities.
We have seen that definitional equalities can be proved using Refl
since they always normalise to unique values that can be compared directly.
However with propositional equalities we are using symbolic variables they do not always normalise.
So to take the previous example:
plusReducesR : (n:Nat) -> plus n Z = n
In this case plus n Z
does not normalise to n
. Even though both sides are equal we cannot pattern match Refl
.
If the pattern match cannot match for all n
then the way around this is to separately match all possible values of n
. In the case of natural numbers we do this by induction.
So here:
plusReducesR : n = plus n 0
plusReducesR {n = Z} = Refl
plusReducesR {n = (S k)} = let rec = plus_commutes_Z {n=k} in
rewrite rec in Refl
we don’t call Refl
to match on n = plus n 0
forall n
we call it for every number separately. So, in the second line, the pattern matcher knows to substitute Z
for n
in the type being matched. This uses rewrite
which is explained below.
Replace¶
This implements the indiscernability of identicals principle, if two terms are equal then they have the same properties. In other words, if x=y
, then we can substitute y
for x
in any expression. In our proofs we can express this as:
if x=y
then P x = P y
where P
is a pure function representing the property. In the examples below P
is an expression in some variable with a type like this: P: n -> Type
.
So if n
is a natural number variable then P
could be something like 2*n + 3
.
To use this in our proofs there is the following function in the prelude:
||| Perform substitution in a term according to some equality.
replace : {a:_} -> {x:_} -> {y:_} -> {P : a -> Type} -> x = y -> P x -> P y
replace Refl prf = prf
Removing the implicits, if we supply an equality x=y
and a proof of a property of x
(i.e. P x
) then we get a proof of a property of y
(i.e. P y
)
> :t replace
replace : (x = y) -> P x -> P y
So, in the following example, if we supply p1 x
which is a proof that x=2
and the equality x=y
then we get a proof that y=2
.
p1: Nat -> Type
p1 n = (n=2)
testReplace: (x=y) -> (p1 x) -> (p1 y)
testReplace a b = replace a b
Rewrite¶
Similar to replace
above but Idris provides a nicer syntax which makes rewrite
easier to use in examples like plusReducesR
above.
rewrite__impl : (P : a -> Type) -> x = y -> P y -> P x
rewrite__impl p Refl prf = prf
The difference from replace
above is nicer syntax and the property p1
is explicitly supplied and it goes in the opposite direction (input and output reversed).
Example: again we supply p1
which is a proof that x=2
and the equality x=y
then we get a proof that y=2
.
p1: Nat -> Type
p1 x = (x=2)
testRewrite2: (x=y) -> (p1 y) -> (p1 x)
testRewrite2 a b = rewrite a in b
We can think of rewrite doing this:
start with a equation
x=y
and a propertyP: x -> Type
;search
y
inP
;replace all occurrences of
y
withx
inP
.
That is, we are doing a substitution.
Symmetry and Transitivity¶
In addition to reflexivity equality also obeys symmetry and transitivity and these are also included in the prelude:
||| Symmetry of propositional equality
sym : {left:a} -> {right:b} -> left = right -> right = left
sym Refl = Refl
||| Transitivity of propositional equality
trans : {a:x} -> {b:y} -> {c:z} -> a = b -> b = c -> a = c
trans Refl Refl = Refl
Heterogeneous Equality¶
Also included in the prelude:
||| Explicit heterogeneous ("John Major") equality. Use this when Idris
||| incorrectly chooses homogeneous equality for `(=)`.
||| @ a the type of the left side
||| @ b the type of the right side
||| @ x the left side
||| @ y the right side
(~=~) : (x : a) -> (y : b) -> Type
(~=~) x y = (x = y)