InducesPreorder

formal source

  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
  95  le := notGreaterThan R gt_events
  96  le_refl := preorder_refl R gt_events h
  97  le_trans := fun _ _ _ => h.trans _ _ _
  98
  99/-! ## Recognition Partial Order -/
 100
 101/-- A comparative recognizer induces a partial order when it's also antisymmetric:
 102    c₁ ≤ c₂ and c₂ ≤ c₁ implies c₁ = c₂ -/
 103structure InducesPartialOrder (R : ComparativeRecognizer C E) (gt_events : Set E)
 104    extends InducesPreorder R gt_events : Prop where
 105  /-- Antisymmetry -/
 106  antisymm : ∀ c₁ c₂, notGreaterThan R gt_events c₁ c₂ →