[Agda] Agda dies trying to prove transitivity
Peter Thiemann
thiemann at informatik.uni-freiburg.de
Thu Jun 4 17:49:00 CEST 2015
Hi all,
I'm looking at a coinductively defined type
data SType' : Set where
Skip : SType'
Semi : ∞ SType' → ∞ SType' → SType'
Case : ∞ SType' → ∞ SType' → SType'
for which I want to establish a non-trivial equivalence relation
data _∼_ : SType' → SType' → Set where
∼-Skip : Skip ∼ Skip
∼-Case : ∀ {s₁ s₁' s₂ s₂'} → ∞ (♭ s₁ ∼ ♭ s₁') → ∞ (♭ s₂ ∼ ♭ s₂') → Case s₁ s₂ ∼ Case s₁' s₂'
∼-Semi : ∀ {s₁ s₁' s₂ s₂'} → ∞ (♭ s₁ ∼ ♭ s₁') → ∞ (♭ s₂ ∼ ♭ s₂') → Semi s₁ s₂ ∼ Semi s₁' s₂'
∼-Semi-Skip-Left-Left : ∀ {s₁ s₂ s₃} → ∞ (♭ s₁ ∼ Skip) → ∞ (♭ s₂ ∼ s₃) → Semi s₁ s₂ ∼ s₃
∼-Semi-Skip-Right-Left : ∀ {s₁ s₂ s₃} → ∞ (♭ s₂ ∼ Skip) → ∞ (♭ s₁ ∼ s₃) → Semi s₁ s₂ ∼ s₃
∼-Semi-Skip-Left-Right : ∀ {s₁ s₂ s₃} → ∞ (♭ s₁ ∼ Skip) → ∞ (♭ s₂ ∼ s₃) → s₃ ∼ Semi s₁ s₂
∼-Semi-Skip-Right-Right : ∀ {s₁ s₂ s₃} → ∞ (♭ s₂ ∼ Skip) → ∞ (♭ s₁ ∼ s₃) → s₃ ∼ Semi s₁ s₂
∼-Semi-Case-Left : ∀ {s₁ s₂ s₃ sl1 sl2 sr}
→ ∞ (♭ sl1 ∼ Semi s₁ s₃) → ∞ (♭ sl2 ∼ Semi s₂ s₃) → ∞ (♭ sr ∼ Case s₁ s₂) → Case sl1 sl2 ∼ Semi sr s₃
∼-Semi-Case-Right : ∀ {s₁ s₂ s₃ sl1 sl2 sr}
→ ∞ (♭ sl1 ∼ Semi s₁ s₃) → ∞ (♭ sl2 ∼ Semi s₂ s₃) → ∞ (♭ sr ∼ Case s₁ s₂) → Semi sr s₃ ∼ Case sl1 sl2
When it comes to proving the equivalence properties, reflexivity and symmetry are straightforward, but for transitivity
I run into problems with Agda. I particular, as soon as I have proved some number of cases, the type checker does not appear to
terminate any more.
Is there something obviously wrong about these definitions?
The full code may be found here: https://gist.github.com/28c0643956315b70c0e6.git
I'm running version 2.3.2.2
-Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20150604/4b0d91bc/attachment.html
More information about the Agda
mailing list