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 }