------------------------------------------------------------------------
-- H-levels
------------------------------------------------------------------------

{-# OPTIONS --without-K #-}

-- Partly based on Voevodsky's work on so-called univalent
-- foundations.

open import Equality

module H-level
  {reflexive} (eq :  {a p}  Equality-with-J a p reflexive) where

open Derived-definitions-and-properties eq
import Equality.Decidable-UIP eq as DUIP
open import Logical-equivalence hiding (id; _∘_)
open import Prelude
open import Surjection eq hiding (id; _∘_)

------------------------------------------------------------------------
-- H-levels

-- H-levels ("homotopy levels").

H-level :    {}  Set   Set 
H-level zero    A = Contractible A
H-level (suc n) A = (x y : A)  H-level n (x  y)

-- Some named levels.

Is-proposition :  {}  Set   Set 
Is-proposition = H-level 1

Is-set :  {}  Set   Set 
Is-set = H-level 2

-- Propositions are propositional types.

Proposition : ( : Level)  Set (lsuc )
Proposition _ =  Is-proposition

-- Types that are sets.

SET : ( : Level)  Set (lsuc )
SET _ =  Is-set

-- The underlying type.

Type :  {}  SET   Set 
Type A = proj₁ A

------------------------------------------------------------------------
-- General properties

abstract

  -- H-level is upwards closed in its first argument.

  mono₁ :  {a} {A : Set a} n  H-level n A  H-level (1 + n) A
  mono₁         (suc n) h x y = mono₁ n (h x y)
  mono₁ {A = A} zero    h x y = (trivial x y , irr)
    where
    trivial : (x y : A)  x  y
    trivial x y =
      x        ≡⟨ sym $ proj₂ h x 
      proj₁ h  ≡⟨ proj₂ h y ⟩∎
      y        

    irr :  {x y} (x≡y : x  y)  trivial x y  x≡y
    irr = elim  {x y} x≡y  trivial x y  x≡y)
                x  trans-symˡ (proj₂ h x))

  mono :  {a m n} {A : Set a}  m  n  H-level m A  H-level n A
  mono ≤-refl               = id
  mono (≤-step {n = n} m≤n) = λ h  mono₁ n (mono m≤n h)

  -- If something is contractible given the assumption that it is
  -- inhabited, then it is propositional.

  [inhabited⇒contractible]⇒propositional :
     {a} {A : Set a}  (A  Contractible A)  Is-proposition A
  [inhabited⇒contractible]⇒propositional h x = mono₁ 0 (h x) x

  -- If something has h-level (1 + n) given the assumption that it is
  -- inhabited, then it has h-level (1 + n).

  [inhabited⇒+]⇒+ :
     {a} {A : Set a} n  (A  H-level (1 + n) A)  H-level (1 + n) A
  [inhabited⇒+]⇒+ n h x = h x x

  -- Being propositional is logically equivalent to having at most one
  -- element.

  propositional⇔irrelevant :
     {a} {A : Set a}  Is-proposition A  Proof-irrelevant A
  propositional⇔irrelevant {A} = record
    { to   = λ h x y  proj₁ (h x y)
    ; from = λ irr 
        [inhabited⇒contractible]⇒propositional  x  (x , irr x))
    }

  -- If a propositional type is inhabited, then it is contractible.

  propositional⇒inhabited⇒contractible :
     {a} {A : Set a}  Is-proposition A  A  Contractible A
  propositional⇒inhabited⇒contractible p x =
    (x , _⇔_.to propositional⇔irrelevant p x)

  -- Being a set is logically equivalent to having unique identity
  -- proofs. Note that this means that, assuming that Agda is
  -- consistent, I cannot prove (inside Agda) that there is any type
  -- whose minimal h-level is at least three.

  set⇔UIP :  {a} {A : Set a} 
            Is-set A  Uniqueness-of-identity-proofs A
  set⇔UIP {A = A} = record
    { to   = λ h {x} {y} x≡y x≡y′  proj₁ (h x y x≡y x≡y′)
    ; from = λ UIP x y 
        [inhabited⇒contractible]⇒propositional  x≡y  (x≡y , UIP x≡y))
    }

  -- Types with decidable equality are sets.

  decidable⇒set :  {a} {A : Set a}  Decidable-equality A  Is-set A
  decidable⇒set {A = A} dec =
    _⇔_.from {To = Uniqueness-of-identity-proofs A}
             set⇔UIP (DUIP.decidable⇒UIP dec)

-- H-level n respects (split) surjections.

respects-surjection :
   {a b} {A : Set a} {B : Set b} 
  A  B   n  H-level n A  H-level n B
respects-surjection A↠B zero (x , irr) = (to x , irr′)
  where
  open _↠_ A↠B

  abstract
    irr′ :  y  to x  y
    irr′ = λ y 
      to x         ≡⟨ cong to (irr (from y)) 
      to (from y)  ≡⟨ right-inverse-of y ⟩∎
      y            

respects-surjection A↠B (suc n) h = λ x y 
  respects-surjection (↠-≡ A↠B) n (h (from x) (from y))
  where open _↠_ A↠B