https://github.com/rolyp/proof-relevant-pi
Tip revision: 64c86002b9c00aad9c04fc38a0e2f5d31d877e75 authored by Roly Perera on 05 October 2016, 21:43:13 UTC
Update README.
Update README.
Tip revision: 64c8600
Ren.agda
-- A renaming as a context morphism.
module Ren where
open import ProofRelevantPiCommon hiding (Involutive)
open import Data.Nat.Properties.Simple
import Relation.Binary.EqReasoning as EqReasoning
open import Name as ᴺ using (Cxt; module Cxt; Name; _+_; zero; shift)
-- Hom-setoid over extensional equivalence.
Ren : Cxt → Cxt → Set
Ren Γ Γ′ = Name Γ → Name Γ′
-- Extend a renaming with an identity mapping.
suc : ∀ {Γ Γ′} → Ren Γ Γ′ → Ren (Γ + 1) (Γ′ + 1)
suc ρ zero = zero
suc ρ (ᴺ.suc x) = ᴺ.suc (ρ x)
push : ∀ {Γ} → Ren Γ (Γ + 1)
push = shift 1
weaken : ∀ {Γ} → Ren Γ (Γ + 1)
weaken zero = zero
weaken (ᴺ.suc x) = ᴺ.suc (weaken x)
infixl 6 _ᴿ+_
_ᴿ+_ : ∀ {Γ Γ′} → Ren Γ Γ′ → ∀ n → Ren (Γ + n) (Γ′ + n)
ρ ᴿ+ zero = ρ
ρ ᴿ+ (ᴺ.suc n) = suc (ρ ᴿ+ n)
-- TODO: define a Functor instance for (ᴿ+ Δ).
+-preserves-id : ∀ {Γ} Δ → (id {A = Name Γ} ᴿ+ Δ) ≃ₑ id
+-preserves-id zero _ = refl
+-preserves-id (ᴺ.suc _) zero = refl
+-preserves-id (ᴺ.suc Δ) (ᴺ.suc x) = cong ᴺ.suc (+-preserves-id Δ x)
+-preserves-≃ₑ : ∀ {Γ Γ′} Δ {ρ σ : Ren Γ Γ′} → ρ ≃ₑ σ → ρ ᴿ+ Δ ≃ₑ σ ᴿ+ Δ
+-preserves-≃ₑ zero ρ≃ₑσ = ρ≃ₑσ
+-preserves-≃ₑ (ᴺ.suc _) _ zero = refl
+-preserves-≃ₑ (ᴺ.suc Δ) ρ≃ₑσ (ᴺ.suc x) = cong ᴺ.suc (+-preserves-≃ₑ Δ ρ≃ₑσ x)
+-preserves-∘ : ∀ {Γ Δ Γ′} Δ′ (ρ : Ren Δ Γ′) (σ : Ren Γ Δ) → (ρ ᴿ+ Δ′) ∘ (σ ᴿ+ Δ′) ≃ₑ (ρ ∘ σ) ᴿ+ Δ′
+-preserves-∘ zero _ _ _ = refl
+-preserves-∘ (ᴺ.suc _) _ _ zero = refl
+-preserves-∘ (ᴺ.suc Δ) ρ σ (ᴺ.suc x) = cong ᴺ.suc (+-preserves-∘ Δ ρ σ x)
-- shift n is a natural transformation between the identity functor and (· ᴿ+ n).
ᴿ+-comm : ∀ {Γ Γ′} n (ρ : Ren Γ Γ′) → (ρ ᴿ+ n) ∘ shift {Γ} n ≃ₑ shift {Γ′} n ∘ ρ
ᴿ+-comm zero _ _ = refl
ᴿ+-comm (ᴺ.suc n) ρ = cong ᴺ.suc ∘ ᴿ+-comm n ρ
-- Functor from renamings.
record Renameable (A : Cxt → Set) : Set where
field
_* : ∀ {Γ Γ′} → Ren Γ Γ′ → A Γ → A Γ′
*-preserves-≃ₑ : ∀ {Γ Γ′} {ρ σ : Ren Γ Γ′} → ρ ≃ₑ σ → ρ * ≃ₑ σ *
*-preserves-id : ∀ {Γ} → id * ≃ₑ id {A = A Γ}
*-preserves-∘ : ∀ {Γ Δ Γ′} {ρ : Ren Δ Γ′} {σ : Ren Γ Δ} → ρ * ∘ σ * ≃ₑ (ρ ∘ σ) *
-- TODO: better names for these.
∘-*₁ : ∀ {Γ Δ Γ′} {ρ : Ren Δ Γ′} {σ : Ren Γ Δ} {ρ′ : Ren Γ Γ′} →
ρ ∘ σ ≃ₑ ρ′ → ρ * ∘ σ * ≃ₑ ρ′ *
∘-*₁ ρ∘σ≃ₑρ′ a = trans (*-preserves-∘ a) (*-preserves-≃ₑ ρ∘σ≃ₑρ′ a)
∘-* : ∀ {Γ Δ Δ′ Γ′} {ρ : Ren Δ Γ′} {σ : Ren Γ Δ} {ρ′ : Ren Δ′ Γ′} {σ′ : Ren Γ Δ′} →
ρ ∘ σ ≃ₑ ρ′ ∘ σ′ → ρ * ∘ σ * ≃ₑ ρ′ * ∘ σ′ *
∘-* ρ∘σ≡ρ′∘σ′ a = trans (∘-*₁ ρ∘σ≡ρ′∘σ′ a) (sym (*-preserves-∘ a))
pop : ∀ {Γ} (x : Name Γ) → Ren (Γ + 1) Γ
pop x zero = x
pop _ (ᴺ.suc y) = y
pop-comm : ∀ {Γ Γ′} (ρ : Ren Γ Γ′) (x : Name Γ) → ρ ∘ pop {Γ} x ≃ₑ pop {Γ′} (ρ x) ∘ suc ρ
pop-comm _ x zero = refl
pop-comm _ x (ᴺ.suc y) = refl
swap : ∀ {Γ} → Ren (Γ + 2) (Γ + 2)
swap zero = ᴺ.suc zero
swap (ᴺ.suc zero) = zero
swap (ᴺ.suc (ᴺ.suc x)) = ᴺ.suc (ᴺ.suc x)
swap-suc-suc : ∀ {Γ Γ′} (ρ : Ren Γ Γ′) → swap {Γ′} ∘ suc (suc ρ) ≃ₑ suc (suc ρ) ∘ swap {Γ}
swap-suc-suc _ zero = refl
swap-suc-suc _ (ᴺ.suc zero) = refl
swap-suc-suc _ (ᴺ.suc (ᴺ.suc _)) = refl
Involutive : ∀ {Γ} → Ren Γ Γ → Set
Involutive ρ = ρ ∘ ρ ≃ₑ id
+-preserves-involutivity : ∀ {Γ} (ρ : Ren Γ Γ) Δ → Involutive ρ → Involutive (ρ ᴿ+ Δ)
+-preserves-involutivity ρ Δ ρ-involutive x =
let open EqReasoning (setoid _) in
begin
(ρ ᴿ+ Δ) ((ρ ᴿ+ Δ) x)
≡⟨ +-preserves-∘ Δ ρ ρ _ ⟩
((ρ ∘ ρ) ᴿ+ Δ) x
≡⟨ +-preserves-≃ₑ Δ ρ-involutive _ ⟩
(id ᴿ+ Δ) x
≡⟨ +-preserves-id Δ _ ⟩
id x
∎
swap-involutive : ∀ {Γ} → Involutive (swap {Γ})
swap-involutive zero = refl
swap-involutive (ᴺ.suc zero) = refl
swap-involutive (ᴺ.suc (ᴺ.suc _)) = refl
swap∘suc-swap∘swap : ∀ {Γ} → swap ∘ suc (swap {Γ}) ∘ swap ≃ₑ suc swap ∘ swap ∘ suc swap
swap∘suc-swap∘swap zero = refl
swap∘suc-swap∘swap (ᴺ.suc zero) = refl
swap∘suc-swap∘swap (ᴺ.suc (ᴺ.suc zero)) = refl
swap∘suc-swap∘swap (ᴺ.suc (ᴺ.suc (ᴺ.suc _))) = refl
-- Additional properties required to prove cofinality of transition residuals.
swap∘suc-push : ∀ {Γ} → push {Γ + 1} ≃ₑ swap ∘ suc push
swap∘suc-push zero = refl
swap∘suc-push (ᴺ.suc _) = refl
swap∘push : ∀ {Γ} → suc (push {Γ}) ≃ₑ swap ∘ push {Γ + 1}
swap∘push zero = refl
swap∘push (ᴺ.suc _) = refl
-- The names of the next two are too similar.
pop∘swap : ∀ {Γ} (y : Name Γ) → suc (pop y) ≃ₑ pop (ᴺ.suc y) ∘ swap
pop∘swap _ zero = refl
pop∘swap _ (ᴺ.suc zero) = refl
pop∘swap _ (ᴺ.suc (ᴺ.suc _)) = refl
pop-swap : ∀ {Γ} → pop ᴺ.zero ∘ swap {Γ} ≃ₑ pop ᴺ.zero
pop-swap zero = refl
pop-swap (ᴺ.suc zero) = refl
pop-swap (ᴺ.suc (ᴺ.suc _)) = refl
pop∘suc-push : ∀ {Γ} (y : Name Γ) → push ∘ (pop y) ≃ₑ pop (ᴺ.suc y) ∘ suc push
pop∘suc-push _ zero = refl
pop∘suc-push _ (ᴺ.suc _) = refl
pop-zero∘suc-push : ∀ {Γ} → pop {Γ + 1} ᴺ.zero ∘ suc push ≃ₑ id
pop-zero∘suc-push zero = refl
pop-zero∘suc-push (ᴺ.suc _) = refl
pop-pop-swap : ∀ {Γ} (x y : Name Γ) → pop x ∘ suc (pop y) ∘ swap ≃ₑ pop y ∘ suc (pop x)
pop-pop-swap _ _ zero = refl
pop-pop-swap _ _ (ᴺ.suc zero) = refl
pop-pop-swap _ _ (ᴺ.suc (ᴺ.suc _)) = refl
suc-pop∘swap : ∀ {Γ} (y : Name Γ) → suc (pop y) ∘ swap ≃ₑ pop (ᴺ.suc y)
suc-pop∘swap _ zero = refl
suc-pop∘swap _ (ᴺ.suc zero) = refl
suc-pop∘swap _ (ᴺ.suc (ᴺ.suc _)) = refl