Martin Escardo 2011.

(Totally separated types moved to the module TotallySeparated January
2018, and extended.)


{-# OPTIONS --without-K --exact-split --safe #-}

module DiscreteAndSeparated where

open import UF
open import DecidableAndDetachable

isolated :  {U} {X : U ̇}  X  U ̇
isolated x =  y  decidable(x  y)

discrete :  {U}  U ̇  U ̇
discrete X = (x : X)  isolated x


A simple example:


open import Two

𝟚-discrete : discrete 𝟚
𝟚-discrete   = inl refl
𝟚-discrete   = inr ())
𝟚-discrete   = inr ())
𝟚-discrete   = inl refl


General properties:


discrete-is-cotransitive :  {U} {X : U ̇}
                          discrete X  {x y z : X}  x  y   x  z  +  z  y
discrete-is-cotransitive d {x} {y} {z} φ = f(d x z)
  f : x  z  +  x  z  x  z  +  z  y
  f (inl r) = inr  s  φ(r  s)) 
  f (inr γ) = inl γ 

retract-discrete-discrete :  {U} {V} {X : U ̇} {Y : V ̇}
                          retract Y Of X  discrete X  discrete Y
retract-discrete-discrete (f , (s , φ)) d y y' = g (d (s y) (s y'))
  g : decidable (s y  s y')  decidable (y  y')
  g (inl p) = inl ((φ y) ⁻¹  ap f p  φ y')
  g (inr u) = inr (contrapositive (ap s) u)

𝟚-retract-of-discrete :  {U} {X : U ̇} {x₀ x₁ : X}  x₀  x₁  discrete X  retract 𝟚 Of X
𝟚-retract-of-discrete {U} {X} {x₀} {x₁} ne d = r , (s , rs)
  r : X  𝟚
  r = pr₁ (characteristic-function (d x₀))
  φ : (x : X)  (r x    x₀  x) × (r x    ¬ (x₀  x))
  φ = pr₂ (characteristic-function (d x₀))
  s : 𝟚  X
  s  = x₀
  s  = x₁
  rs : (n : 𝟚)  r (s n)  n
  rs  = Lemma[b≢₁→b≡₀]  p  pr₂ (φ x₀) p refl)
  rs  = Lemma[b≢₀→b≡₁] λ p  𝟘-elim (ne (pr₁ (φ x₁) p))

Separated types form an exponential ideal, assuming
extensionality. More generally:


separated :  {U}  U ̇  U ̇
separated X = (x y : X)  ¬¬(x  y)  x  y

separated-ideal :  {U V}  FunExt U V  {X : U ̇} {Y : X  V ̇}
                ((x : X)  separated(Y x))  separated(Π Y)
separated-ideal fe s f g h = funext fe lemma𝟚
  lemma₀ : f  g   x  f x  g x
  lemma₀ r x = ap  h  h x) r

  lemma₁ :  x  ¬¬(f x  g x)
  lemma₁ = DNU(¬¬-functor lemma₀ h)

  lemma𝟚 :  x  f x  g x
  lemma𝟚 x =  s x (f x) (g x) (lemma₁ x) 

discrete-is-separated :  {U} {X : U ̇}  discrete X  separated X
discrete-is-separated d x y = ¬¬-elim(d x y)

𝟚-separated : separated 𝟚
𝟚-separated = discrete-is-separated 𝟚-discrete

subtype-of-separated-is-separated :  {U V} {X : U ̇} {Y : V ̇} (m : X  Y)
                                   left-cancellable m  separated Y  separated X
subtype-of-separated-is-separated {U} {V} {X} m i s x x' e = i (s (m x) (m x') (¬¬-functor (ap m) e))


The following is an apartness relation when Y is separated, but we
define it without this assumption. (Are all types separated? See


infix 21 _♯_

_♯_ :  {U V} {X : U ̇}  {Y : X  V ̇}  (f g : (x : X)  Y x)  U  V ̇
f  g = Σ \x  f x  g x

apart-is-different :  {U V} {X : U ̇} {Y : X  V ̇}
                    {f g : (x : X)  Y x}  f  g  f  g
apart-is-different (x , φ) r = φ (ap  h  h x) r)

apart-is-symmetric :  {U V} {X : U ̇}  {Y : X  V ̇}
                    {f g : (x : X)  Y x}  f  g  g  f
apart-is-symmetric (x , φ)  = (x , (φ  _⁻¹)) 

apart-is-cotransitive :  {U V} {X : U ̇}  {Y : X  V ̇}
                      ((x : X)  discrete(Y x)) 
                      (f g h : (x : X)  Y x)
                      f  g  f  h  +  h  g
apart-is-cotransitive d f g h (x , φ)  = lemma₁(lemma₀ φ)
  lemma₀ : f x  g x  f x  h x  +  h x  g x
  lemma₀ = discrete-is-cotransitive (d x)

  lemma₁ : f x  h x  +  h x  g x  f  h  +  h  g
  lemma₁ (inl γ) = inl (x , γ)
  lemma₁ (inr δ) = inr (x , δ)


We now consider two cases which render the apartness relation ♯ tight,
assuming extensionality:


tight :  {U V} {X : U ̇}  FunExt U V  {Y : X  V ̇}
       ((x : X)  separated(Y x))
       (f g : (x : X)  Y x)
       ¬(f  g)  f  g
tight fe s f g h = funext fe lemma₁
  lemma₀ :  x  ¬¬(f x  g x)
  lemma₀ = not-exists-implies-forall-not h

  lemma₁ :  x  f x  g x
  lemma₁ x = (s x (f x) (g x)) (lemma₀ x)

tight' :  {U V} {X : U ̇}  FunExt U V  {Y : X  V ̇}
        ((x : X)  discrete(Y x))  (f g : (x : X)  Y x)  ¬(f  g)  f  g
tight' fe d = tight fe  x  discrete-is-separated(d x)) 


What about sums? The special case they reduce to binary products is


binary-product-separated :  {U V} {X : U ̇} {Y : V ̇}
                          separated X  separated Y  separated(X × Y)
binary-product-separated s t (x , y) (x' , y') φ = 
 lemma(lemma₀ φ)(lemma₁ φ) 
  lemma₀ : ¬¬((x , y)  (x' , y'))  x  x'
  lemma₀ = (s x x')  ¬¬-functor(ap pr₁)

  lemma₁ : ¬¬((x , y)  (x' , y'))  y  y'
  lemma₁ = (t y y')  ¬¬-functor(ap pr₂)

  lemma : x  x'  y  y'  (x , y)  (x' , y')
  lemma = ap₂ (_,_)  


This proof doesn't work for general dependent sums, because, among
other things, (ap π₁) doesn't make sense in that case.  A different
special case is also easy:


binary-sum-separated :  {U V} {X : U ̇} {Y : V ̇}
                      separated X  separated Y  separated(X + Y)
binary-sum-separated {U} {V} {X} {Y} s t (inl x) (inl x') = lemma 
  claim : inl x  inl x'  x  x'
  claim = ap p
   where p : X + Y  X
         p(inl u) = u
         p(inr v) = x

  lemma : ¬¬(inl x  inl x')  inl x  inl x'
  lemma = (ap inl)  (s x x')  ¬¬-functor claim
binary-sum-separated s t (inl x) (inr y) =  λ φ  𝟘-elim(φ sum-disjoint )  
binary-sum-separated s t (inr y) (inl x)  = λ φ  𝟘-elim(φ(sum-disjoint  _⁻¹)) 
binary-sum-separated {U} {V} {X} {Y} s t (inr y) (inr y') = lemma 
  claim : inr y  inr y'  y  y'
  claim = ap q
   where q : X + Y  Y
         q(inl u) = y
         q(inr v) = v

  lemma : ¬¬(inr y  inr y')  inr y  inr y'
  lemma = (ap inr)  (t y y')  ¬¬-functor claim

false-true-density' : PropExt U₀   {U} {X : U ̇}
                    separated X
                    (f : Prop  X)  f false  f true  constant f
false-true-density' pe s f r p q = g p  (g q)⁻¹
    a :  p  ¬¬(f p  f true)
    a p t = no-truth-values-other-than-false-or-true pe (p , (b , c))
        b : p  false
        b u = t (ap f u  r)
        c : p  true
        c u = t (ap f u)
    g :  p  f p  f true
    g p = s (f p) (f true) (a p)