Skip to content

関係

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