notGreaterThan

formal source

  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₂ →
  81                       notGreaterThan R gt_events c₂ c₃ →
  82                       notGreaterThan R gt_events c₁ c₃
  83
  84/-- When a comparative recognizer induces a preorder, we get reflexivity for free -/
  85theorem preorder_refl (R : ComparativeRecognizer C E) (gt_events : Set E)
  86    (h : InducesPreorder R gt_events) (c : C) :
  87    notGreaterThan R gt_events c c := by
  88  unfold notGreaterThan
  89  rw [R.compare_self]
  90  exact h.eq_not_gt
  91
  92/-- The induced preorder relation -/
  93def inducedPreorder (R : ComparativeRecognizer C E) (gt_events : Set E)
  94    (h : InducesPreorder R gt_events) : Preorder C where