Skip to content

Apartness relation

module apartness-relation where

open import bottom-type
open import equivalence-relation
open import negation
open import sigma-type
open import sum-type
record Apart (A : Set) : Set₁ where
  field
    _#_ : A → A → Set
    irrefl-# : ∀ {x} → x # x → ⊥
    sym-# : ∀ {x y} → x # y → y # x
    comparison-# : ∀ {x y z} → x # z → (x # y) + (y # z)

Apartness関係の否定は同値関係である:

private variable
  A B : Set

¬#-is-Equiv : Apart A → Equiv A
¬#-is-Equiv apart = record
  { _≈_ = λ { x y → ¬ (x # y) }
  ; refl-≈ = λ { x x#x → irrefl-# x#x }
  ; sym-≈ = λ { ¬x#y y#x → ¬x#y (sym-# y#x) }
  ; trans-≈ = trans
  }
  where
    open Apart apart

    trans : ∀ {x y z} → ¬ (x # y) → ¬ (y # z) → ¬ (x # z)
    trans ¬x#y ¬y#z x#z with comparison-# x#z
    ... | (inl x#y) = ¬x#y x#y
    ... | (inr y#z) = ¬y#z y#z
record Complemented : Set₁ where
  constructor complemented

  field
    aff : Set
    ref : Set
    -- law of no contradiction
    lnc : aff → ref → ⊥

open Complemented public

_=>_ : Complemented → Complemented → Set
(A => B) = (A .aff → B .aff) × (B .ref → A .ref)

infix 30 _**_
_**_ : Complemented → Complemented → Complemented
(A ** B) .aff = A .aff × B .aff
(A ** B) .ref = A .ref + B .ref
(A ** B) .lnc = λ where
  (a , _) (inl nota) → lnc A a nota
  (_ , b) (inr notb) → lnc B b notb

infix 30 _&&_
_&&_ : Complemented → Complemented → Complemented
(A && B) .aff = A .aff × B .aff
(A && B) .ref = (A .aff → B .ref) × (B .aff → A .ref)
(A && B) .lnc = λ where
  (a , b) (f , _) → lnc B b (f a)

infix 30 _++_
_++_ : Complemented → Complemented → Complemented
(A ++ B) .aff = A .aff + B .aff
(A ++ B) .ref = A .ref × B .ref
(A ++ B) .lnc = λ where
  (inl a) (nota , _) → lnc A a nota
  (inr b) (_ , notb) → lnc B b notb

infix 20 _==>_
_==>_ : Complemented → Complemented → Complemented
(A ==> B) .aff = A => B
(A ==> B) .ref = A .aff × B .ref
(A ==> B) .lnc = λ where
  (f , _) (a , notb) → lnc B (f a) notb

exist : (X : Set) → (X → Complemented) → Complemented
exist X A .aff = Σ[ x ∈ X ] (A x .aff)
exist X A .ref = ∀ x → A x .ref
exist X A .lnc = λ where
  (x , a) f → lnc (A x) a (f x)

univ : (X : Set) → (X → Complemented) → Complemented
univ X A .aff = ∀ x → A x .aff
univ X A .ref = Σ[ x ∈ X ] (A x .ref)
univ X A .lnc = λ where
  f (x , nota) → lnc (A x) (f x) nota
flipCompl : Complemented → Complemented
flipCompl A = record
  { aff = A .ref
  ; ref = A .aff
  ; lnc = λ nota a → A .lnc a nota
  }
compl : Set → Complemented
compl A = record
  { aff = A
  ; ref = ¬ A
  ; lnc = λ a f → f a
  }

lift-compl : (A → B) → compl A => compl B
lift-compl f = (f , λ { ¬B a → ¬B (f a) })

compl-++ : (compl A ++ compl B) => compl (A + B)
compl-++ .fst A+B  = A+B
compl-++ .snd ¬A+B = (λ a → ¬A+B (inl a)) , (λ b → ¬A+B (inr b))
record ApartedSet : Set₁ where
  field
    X : Set
    equiv : Equiv X
    apart : Apart X

  open Equiv equiv public
  open Apart apart public

  field
    no-contra : ∀ {x y} → x ≈ y → x # y → ⊥

  #-resp-≈ᵣ : ∀ {x y z} → x # y → y ≈ z → x # z
  #-resp-≈ᵣ x#y y≈z with comparison-# x#y
  ... | inl x#z = x#z
  ... | inr z#y = absurd (no-contra y≈z (sym-# z#y))

  #-resp-≈ₗ : ∀ {x y z} → x # y → x ≈ z → z # y
  #-resp-≈ₗ x#y x≈z = sym-# (#-resp-≈ᵣ (sym-# x#y) x≈z)

  setoid : Setoid
  setoid = record { X = X ; equiv = equiv }

  infix 35 _∼_
  _∼_ : X → X → Complemented
  _∼_ x y .aff = x ≈ y
  _∼_ x y .ref = x # y
  _∼_ x y .lnc = no-contra

  infix 35 _≁_
  _≁_ : X → X → Complemented
  x ≁ y = flipCompl (x ∼ y)

ApartedSetに構造が乗ったものから台となる型を取り出すための、便利な記号を定義しておく:

^_ : ∀ {ℓ} {C : ApartedSet → Set ℓ} → Σ ApartedSet C → Set
^_ (S , _) = ApartedSet.X S

型A上の同値関係が決定可能であるとき、A上のapartness relationをその否定として構成できる:

module _ (S : Setoid) where
  open Equiv (Setoid.equiv S)

  ApartOnDiscreteSetoid : (∀ x y → Decidable (x ≈ y)) → Apart (Setoid.X S)
  ApartOnDiscreteSetoid disc = record
    { _#_ = λ x y → ¬ (x ≈ y)
    ; irrefl-# = λ f → f (refl-≈ _)
    ; sym-# = λ f e → f (sym-≈ e)
    ; comparison-# = comp
    }
    where
      comp : ∀ {x y z} → ¬ (x ≈ z) → ¬ (x ≈ y) + ¬ (y ≈ z)
      comp {x = x} {y} {z} f with disc x y
      ... | inl e = inr λ e′ → f (trans-≈ e e′)
      ... | inr f = inl f

  DiscreteSetoid→ApartedSet : (∀ x y → Decidable (x ≈ y)) → ApartedSet
  DiscreteSetoid→ApartedSet disc = record
    { X = Setoid.X S
    ; equiv = Setoid.equiv S
    ; apart = ApartOnDiscreteSetoid disc
    ; no-contra = λ e f → f e
    }