Tom de Jong (adapted from Martin's MGS lecture notes) 18 September 2020 We show that the type of natural numbers enjoys the universal property of a natural numbers object. We generalize https://www.cs.bham.ac.uk/~mhe/HoTT-UF.in-Agda-Lecture-Notes/HoTT-UF-Agda.html#β-is-nno here from nondependent functions to dependent functions. \begin{code} {-# OPTIONS --safe --without-K #-} module Naturals.UniversalProperty where open import MLTT.Spartan open import UF.Base open import UF.Equiv open import UF.FunExt open import UF.Retracts open import UF.Subsingletons β-induction-retract : funext π€β π€ β (Y : β β π€Μ ) (yβ : Y 0) (g : (n : β) β Y n β Y (succ n)) β (Ξ£ h κ (Ξ Y) , (h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n))) β (Ξ£ h κ (Ξ Y) , h οΌ β-induction yβ g) β-induction-retract fe Y yβ g = Ξ£-retract _ _ Ξ³ where Ξ³ : (h : Ξ Y) β (h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n)) β (h οΌ β-induction yβ g) Ξ³ h = (h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n)) ββ¨ i β© (h βΌ β-induction yβ g) ββ¨ ii β© (h οΌ β-induction yβ g) β where ii = β-gives-β (β-sym (β-funext fe h (β-induction yβ g))) i = r , s , Ξ· where r : h βΌ β-induction yβ g β (h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n)) r H = H 0 , (Ξ» n β h (succ n) οΌβ¨ H (succ n) β© β-induction yβ g (succ n) οΌβ¨ refl β© g n (β-induction yβ g n) οΌβ¨ ap (g n) ((H n) β»ΒΉ) β© g n (h n) β) s : (h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n)) β h βΌ β-induction yβ g s (p , K) 0 = p s (p , K) (succ n) = h (succ n) οΌβ¨ K n β© g n (h n) οΌβ¨ ap (g n) (s (p , K) n) β© g n (β-induction yβ g n) οΌβ¨ refl β© β-induction yβ g (succ n) β Ξ· : r β s βΌ id Ξ· (p , K) = r (s (p , K)) οΌβ¨reflβ© (p , Ξ» n β s (p , K) (succ n) β (refl β ap (g n) ((s (p , K) n) β»ΒΉ))) οΌβ¨ Ο β© (p , K) β where Ο = ap (p ,_) (dfunext fe Ο) where Ο : (n : β) β s (p , K) (succ n) β (refl β ap (g n) (s (p , K) n β»ΒΉ)) οΌ K n Ο n = s (p , K) (succ n) β (refl β ap (g n) (s (p , K) n β»ΒΉ)) οΌβ¨reflβ© K n β ap (g n) (s (p , K) n) β (refl β ap (g n) ((s (p , K) n) β»ΒΉ)) οΌβ¨ I β© K n β ap (g n) (s (p , K) n) β ap (g n) ((s (p , K) n) β»ΒΉ) οΌβ¨ II β© K n β (ap (g n) (s (p , K) n) β ap (g n) ((s (p , K) n) β»ΒΉ)) οΌβ¨ III β© K n β (ap (g n) (s (p , K) n) β (ap (g n) (s (p , K) n)) β»ΒΉ) οΌβ¨ IV β© K n β refl οΌβ¨reflβ© K n β where I = ap (K n β ap (g n) (s (p , K) n) β_) (refl-left-neutral {_} {_} {_} {_} {ap (g n) ((s (p , K) n) β»ΒΉ)}) II = βassoc (K n) (ap (g n) (s (p , K) n)) (ap (g n) ((s (p , K) n) β»ΒΉ)) III = ap (Ξ» - β K n β (ap (g n) (s (p , K) n) β -)) ((ap-sym (g n) (s (p , K) n)) β»ΒΉ) IV = ap (K n β_) ((right-inverse (ap (g n) (s (p , K) n))) β»ΒΉ) β-is-nno-dep : funext π€β π€ β (Y : β β π€ Μ ) (yβ : Y 0) (g : (n : β) β Y n β Y (succ n)) β β! h κ (Ξ Y) , ((h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n))) β-is-nno-dep {π€} fe Y yβ g = Ξ³ where Ξ³ : is-singleton (Ξ£ h κ (Ξ Y) , (h 0 οΌ yβ) Γ ((n : β) β h (succ n) οΌ g n (h n))) Ξ³ = retract-of-singleton (β-induction-retract fe Y yβ g) (singleton-types'-are-singletons (β-induction {π€} {Y} yβ g)) \end{code}