book icon indicating copy to clipboard operation
book copied to clipboard

Mention potential simplification of 2.13.1, see HoTT/HoTT#972

Open mikeshulman opened this issue 6 years ago • 4 comments

mikeshulman avatar Dec 19 '18 19:12 mikeshulman

You can show directly by induction that observational equality is an identity system. You don't need Hedberg's theorem or even propositions at all.

EgbertRijke avatar Apr 04 '20 23:04 EgbertRijke

I would expect that to take more space though. Is it equally concise?

mikeshulman avatar Apr 05 '20 15:04 mikeshulman

The entire agda code is just:

Eq-ℕ : ℕ → (ℕ → UU lzero)
Eq-ℕ zero-ℕ zero-ℕ = 𝟙
Eq-ℕ zero-ℕ (succ-ℕ n) = 𝟘
Eq-ℕ (succ-ℕ m) zero-ℕ = 𝟘
Eq-ℕ (succ-ℕ m) (succ-ℕ n) = Eq-ℕ m n

refl-Eq-ℕ : (n : ℕ) → Eq-ℕ n n
refl-Eq-ℕ zero-ℕ = star
refl-Eq-ℕ (succ-ℕ n) = refl-Eq-ℕ n

path-ind-Eq-ℕ :
  {i : Level} (R : (m n : ℕ) → Eq-ℕ m n → UU i)
  ( ρ : (n : ℕ) → R n n (refl-Eq-ℕ n)) →
  ( m n : ℕ) (e : Eq-ℕ m n) → R m n e
path-ind-Eq-ℕ R ρ zero-ℕ zero-ℕ star = ρ zero-ℕ
path-ind-Eq-ℕ R ρ (succ-ℕ m) (succ-ℕ n) e =
  path-ind-Eq-ℕ
    ( λ m n e → R (succ-ℕ m) (succ-ℕ n) e)
    ( λ n → ρ (succ-ℕ n)) m n e

comp-path-ind-Eq-ℕ :
  {i : Level} (R : (m n : ℕ) → Eq-ℕ m n → UU i)
  ( ρ : (n : ℕ) → R n n (refl-Eq-ℕ n)) →
  ( n : ℕ) → Id (path-ind-Eq-ℕ R ρ n n (refl-Eq-ℕ n)) (ρ n)
comp-path-ind-Eq-ℕ R ρ zero-ℕ = refl
comp-path-ind-Eq-ℕ R ρ (succ-ℕ n) =
  comp-path-ind-Eq-ℕ
    ( λ m n e → R (succ-ℕ m) (succ-ℕ n) e)
    ( λ n → ρ (succ-ℕ n)) n

There's nothing going on except induction, so it depends on how much you would want there to be written about the induction steps.

EgbertRijke avatar Apr 05 '20 20:04 EgbertRijke

Aside from this observation, which is fine to ignore, I think that Mike's pull request is good.

EgbertRijke avatar Apr 06 '20 09:04 EgbertRijke