ComparativeRecognizer

formal source

  47
  48/-- A comparative recognizer detects relationships between pairs of configurations.
  49    It maps (c₁, c₂) to a "comparison event" that encodes their relationship. -/
  50structure ComparativeRecognizer (C E : Type*) where
  51  /-- The comparison function -/
  52  compare : C × C → E
  53  /-- Reflexivity: comparing c with itself gives a distinguished "equal" result -/
  54  eq_event : E
  55  /-- Self-comparison yields the equal event -/
  56  compare_self : ∀ c, compare (c, c) = eq_event
  57
  58/-! ## Induced Relations -/
  59
  60variable {E : Type*} [DecidableEq E]
  61
  62/-- The "not greater than" relation induced by a comparative recognizer.
  63    c₁ ≤ c₂ iff comparing them doesn't produce a "greater than" result. -/
  64def notGreaterThan (R : ComparativeRecognizer C E) (gt_events : Set E) (c₁ c₂ : C) : Prop :=
  65  R.compare (c₁, c₂) ∉ gt_events
  66
  67/-- The "equivalent" relation: neither is greater than the other -/
  68def comparativeEquiv (R : ComparativeRecognizer C E) (gt_events : Set E) (c₁ c₂ : C) : Prop :=
  69  notGreaterThan R gt_events c₁ c₂ ∧ notGreaterThan R gt_events c₂ c₁
  70
  71/-! ## Recognition Preorder -/
  72
  73/-- A comparative recognizer induces a preorder when:
  74    1. Self-comparison is "not greater than" (reflexivity)
  75    2. The relation is transitive -/
  76structure InducesPreorder (R : ComparativeRecognizer C E) (gt_events : Set E) : Prop where
  77  /-- The equal event is not a "greater than" event -/
  78  eq_not_gt : R.eq_event ∉ gt_events
  79  /-- Transitivity: c₁ ≤ c₂ and c₂ ≤ c₃ implies c₁ ≤ c₃ -/
  80  trans : ∀ c₁ c₂ c₃, notGreaterThan R gt_events c₁ c₂ →