[Agda] `<' reasoning
Nils Anders Danielsson
nad at cse.gu.se
Fri Dec 8 14:58:35 CET 2017
On 2017-12-08 12:14, Sandro Stucki wrote:
> Another solution is to relax the requirements of
> Relation.Binary.PreorderReasoning to allow reasoning about arbitrary
> transitive relations that respect the underlying equality but are not
> necessarily reflexive. Here's a possible implementation:
>
> https://gist.github.com/sstucki/2ce758a6dc62883ecbe54e71c0177fd0
In a proof-relevant setting it can also be nice to avoid inserting extra
steps in proofs. I often use combinators of the following kind:
finally : ∀ {a} {A : Set a} (x y : A) → x ≡ y → x ≡ y
finally _ _ x≡y = x≡y
syntax finally x y x≡y = x ≡⟨ x≡y ⟩∎ y ∎
I also have a library that allows you to mix different relations:
http://www.cse.chalmers.se/~nad/listings/up-to/Equational-reasoning.html
One key piece is the following abstraction of transitivity:
record Transitive {a b p q} {A : Set a} {B : Set b}
(P : A → A → Set p) (Q : A → B → Set q) :
Set (a ⊔ b ⊔ p ⊔ q) where
constructor is-transitive
field
transitive : ∀ {x y z} → P x y → Q y z → Q x z
(I also have one where transitivity goes from P and Q to P.) It is then
up to users of the library to define suitable instances.
--
/NAD
More information about the Agda
mailing list