関係
module relation where open import apartness-relation open import bottom-type open import equivalence-relation open import negation open import sigma-type open import sum-type
A : ApartedSet上の2項関係を定義する。
BinRel : ApartedSet → Set₁ BinRel A = ApartedSet.X A → ApartedSet.X A → Set record Respect (A : ApartedSet) (R : BinRel A) : Set where open ApartedSet A field resp-≈ₗ : ∀ {x y z} → R x y → x ≈ z → R z y resp-≈ᵣ : ∀ {x y z} → R x y → y ≈ z → R x z module _ (A : ApartedSet) (R : BinRel A) where open ApartedSet A ¬R : BinRel A ¬R x y = ¬ R x y reflexive : Set reflexive = ∀ x → R x x irreflexive : Set irreflexive = ∀ {x y} → R x y → x # y symmetric : Set symmetric = ∀ {x y} → R x y → R y x transitive : Set transitive = ∀ {x y z} → R x y → R y z → R x z comparison : Set comparison = ∀ {x y z} → R x z → R x y + R y z anti-symmetric : Set anti-symmetric = ∀ {x y} → R x y → R y x → x ≈ y #-connected : Set #-connected = ∀ {x y} → x # y → R x y + R y x total : Set total = ∀ {x y} → R x y + R y x ⊥-asymmetric : Set ⊥-asymmetric = ∀ {x y} → R x y → R y x → ⊥
推移律(transitive R)とcomparison ¬Rは互いの否定のようなものだと思える。反射律(reflexive R)とirreflexive ¬Rも同様である。対称律(symmetric R)は自分自身(symmetric ¬R)の否定と思える。反対称律(anti-symmetric R)と#-connected ¬Rも互いの否定と思える。total Rと⊥-asymmetric ¬Rも同様である。
module Residual (A : ApartedSet) where open ApartedSet A _/_ : BinRel A → BinRel A → BinRel A R / S = λ x y → ∀ z → S y z → R x z _\\_ : BinRel A → BinRel A → BinRel A R \\ S = λ x y → ∀ z → R z x → S z y
module Antithetical (A : ApartedSet) (R Q : BinRel A) (H : ∀ {x y} → R x y → Q y x → ⊥) where open ApartedSet A weak-comparison₁ : Set weak-comparison₁ = ∀ {x y z} → Q x y → R z x → R z y -- Q x y |- (R \\ R) x y weak-comparison₂ : Set weak-comparison₂ = ∀ {x y z} → Q x y → R y z → R x z -- Q x y |- (R / R) x y weak-comparison : Set weak-comparison = weak-comparison₁ × weak-comparison₂ -- R is #-anti-symmetric iff Q is #-connected. #-anti-symmetric : Set #-anti-symmetric = ∀ {x y} → x # y → Q x y + Q y x -- R is connected iff Q is anti-symmetric. connected : Set connected = ∀ {x y} → Q x y → Q y x → x ≈ y weakly-total : Set weakly-total = ∀ {x y} → Q x y → R x y weakly-asymmetric : Set weakly-asymmetric = ∀ {x y} → R x y → Q x y -- R is asymmetric iff Q is total asymmetric : Set asymmetric = ∀ {x y} → Q x y + Q y x comparison→weak-comparison₁ : comparison A R → weak-comparison₁ comparison→weak-comparison₁ f Qxy Ryz with f Ryz ... | inl Rzy = Rzy ... | inr Ryx = absurd (H Ryx Qxy) comparison→weak-comparison₂ : comparison A R → weak-comparison₂ comparison→weak-comparison₂ f Qxy Ryz with f Ryz ... | inl Ryx = absurd (H Ryx Qxy) ... | inr Rxz = Rxz total→weakly-total : total A R → weakly-total total→weakly-total f Qxy with f ... | inl Ryx = absurd (H Ryx Qxy) ... | inr Rxy = Rxy asymmetric→weakly-asymmetric : asymmetric → weakly-asymmetric asymmetric→weakly-asymmetric f Rxy with f ... | inl Qyx = absurd (H Rxy Qyx) ... | inr Qxy = Qxy
#がtightでない限り、「#-connectedならばconnected」であるとは限らない。#-anti-symmetricとanti-symmetricについても同様である。
前順序を定義する。
record isPreOrder (A : ApartedSet) (_≤_ : BinRel A) : Set where open ApartedSet A field refl-≤ : reflexive A _≤_ trans-≤ : transitive A _≤_ ≤-resp-≈ : Respect A _≤_ open Respect ≤-resp-≈ public renaming (resp-≈ₗ to ≤-resp-≈ₗ; resp-≈ᵣ to ≤-resp-≈ᵣ) ≈→≤ : ∀ {x y} → x ≈ y → x ≤ y ≈→≤ {x = x} x≈y = ≤-resp-≈ᵣ (refl-≤ x) x≈y record PreOrder (A : ApartedSet) : Set₁ where field _≤_ : BinRel A is-pre-order : isPreOrder A _≤_ _≥_ : BinRel A x ≥ y = y ≤ x
半順序を定義する。
record isPartialOrder (A : ApartedSet) (_≤_ : BinRel A) : Set where open ApartedSet A field is-pre-order : isPreOrder A _≤_ anti-sym-≤ : anti-symmetric A _≤_ record PartialOrder (A : ApartedSet) : Set₁ where field _≤_ : BinRel A is-partial-order : isPartialOrder A _≤_ _≥_ : BinRel A x ≥ y = y ≤ x
module _ (A : ApartedSet) where open ApartedSet A negation-of-irr-comp : (R : BinRel A) → Respect A R → irreflexive A R → comparison A R → isPreOrder A (¬R A R) negation-of-irr-comp R Resp irr comp = record { refl-≤ = λ { x Rxx → irrefl-# (irr Rxx) } ; trans-≤ = λ { ¬Rxy ¬Ryz Rxz → case-+ (comp Rxz) ¬Rxy ¬Ryz } ; ≤-resp-≈ = record { resp-≈ₗ = λ { ¬Rxy x≈z Rzy → ¬Rxy (Respect.resp-≈ₗ Resp Rzy (sym-≈ x≈z)) } ; resp-≈ᵣ = λ { ¬Rxy y≈z Rxz → ¬Rxy (Respect.resp-≈ᵣ Resp Rxz (sym-≈ y≈z)) } } }
record isStrictPreOrder (A : ApartedSet) (_<_ : BinRel A) : Set where open ApartedSet A field irrefl-< : irreflexive A _<_ trans-< : transitive A _<_ <-resp-≈ : Respect A _<_ asym-< : ⊥-asymmetric A _<_ asym-< x<y y<x = irrefl-# (irrefl-< (trans-< x<y y<x)) record StrictPreOrder (A : ApartedSet) : Set₁ where field _<_ : BinRel A is-strict-pre-order : isStrictPreOrder A _<_ _>_ : BinRel A x > y = y < x
record isStrictPartialOrder (A : ApartedSet) (_<_ : BinRel A) : Set where open ApartedSet A field is-strict-pre-order : isStrictPreOrder A _<_ comp-< : comparison A _<_ open isStrictPreOrder is-strict-pre-order public record StrictPartialOrder (A : ApartedSet) : Set₁ where field _<_ : BinRel A is-strict-partial-order : isStrictPartialOrder A _<_ _>_ : BinRel A x > y = y < x
record isPseudoOrder (A : ApartedSet) (_<_ : BinRel A) : Set where open ApartedSet A field is-strict-partial-order : isStrictPartialOrder A _<_ conn-< : #-connected A _<_ open isStrictPartialOrder is-strict-partial-order public record PseudoOrder (A : ApartedSet) : Set₁ where field _<_ : BinRel A is-pseudo-order : isPseudoOrder A _<_ _>_ : BinRel A x > y = y < x
data Trichotomy (A : ApartedSet) (R : StrictPreOrder A) (x y : (ApartedSet.X A)) : Set where Lt : StrictPreOrder._<_ R x y → Trichotomy A R x y Eq : ApartedSet._≈_ A x y → Trichotomy A R x y Gt : StrictPreOrder._>_ R x y → Trichotomy A R x y