From fd8eed040d6c567f85c9f7509bce60c6ed1c4cce Mon Sep 17 00:00:00 2001 From: Chloe Brown Date: Thu, 7 Jul 2022 22:20:39 +0100 Subject: Prove alpha equivalence is transitive. --- src/Data/Type/Properties.agda | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/src/Data/Type/Properties.agda b/src/Data/Type/Properties.agda index 28667fa..16f6d8e 100644 --- a/src/Data/Type/Properties.agda +++ b/src/Data/Type/Properties.agda @@ -252,3 +252,13 @@ free-≈ (all {α} {A} {β} {B} A≈B) = begin ≈-sym unit = unit ≈-sym (bin A≈C B≈D) = bin (≈-sym A≈C) (≈-sym B≈D) ≈-sym (all A≈B) = all (λ γ∉∀β∙B γ∉∀α∙A → ≈-sym (A≈B γ∉∀α∙A γ∉∀β∙B)) + +≈-trans : Transitive _≈_ +≈-trans (var α) (var .α) = var α +≈-trans unit unit = unit +≈-trans (bin A≈B A₁≈B₁) (bin B≈C B₁≈C₁) = + bin (≈-trans A≈B B≈C) (≈-trans A₁≈B₁ B₁≈C₁) +≈-trans (all A≈B) (all B≈C) = + all (λ δ∉∀α∙A δ∉∀γ∙C → + ≈-trans (A≈B δ∉∀α∙A (P.subst (_ ∉_) (free-≈ (all A≈B)) δ∉∀α∙A)) + (B≈C (P.subst (_ ∉_) (sym (free-≈ (all B≈C))) δ∉∀γ∙C) δ∉∀γ∙C)) -- cgit v1.2.3