move_to_bottom_is_strict_total_order
If r is a strict total order on α, then moving an element bot_elt to the bottom of r yields a strict total order.
Statement
theorem move_to_bottom_is_strict_total_order {α : Type*} (r : α → α → Prop) [IsStrictTotalOrder α r] (bot_elt : α) : IsStrictTotalOrder α (move_to_bottom r bot_elt)
- Source
- folklore
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- move_to_bottomThe relation obtained from a binary relation r on α by moving an element bot_elt to the bottom: bot_elt is not preferred to anything, any…
Read back from the Lean
For any type α, any binary relation r : α → α → Prop that is a strict total order on α ([IsStrictTotalOrder α r]), and any element bot_elt : α, the relation move_to_bottom r bot_elt is also a strict total order on α.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that the modified relation move_to_bottom r bot_elt is a strict total order, the proof verifies trichotomy and the two strict order properties (irreflexivity and transitivity). Trichotomy follows by case analysis on whether elements equal bot_elt: if both do, they are equal; if exactly one does, the relation holds strictly between them, contradicting incomparability; and if neither does, equality follows from the trichotomy of r. Irreflexivity holds because bot_elt is not related to itself by definition, while any other element inherits irreflexivity from r. Transitivity is verified by case-splitting on which of a, b, c equals bot_elt: the cases where a or b equals bot_elt are vacuously true, the case where c equals bot_elt holds by definition, and the remaining case reduces directly to the transitivity of r.
To prove that the modified relation is a strict total order, it suffices to show trichotomy and that it is a strict order; for trichotomy, we assume two elements a and b are incomparable.
A strict total order consists of a trichotomous relation that is also a strict order (irreflexive and transitive). We split the goal into these two obligations. For trichotomy, we introduce elements a, b and assume h1 : ¬move_to_bottom r bot_elt a b and h2 : ¬move_to_bottom r bot_elt b a, with the goal of showing a = b.
refine { toTrichotomous := ?_, toIsStrictOrder := ?_ } · refine { trichotomous := ?_ } intro a b h1 h2
If a = bot_elt, then a = b.
We case-split on whether b = bot_elt. If b = bot_elt, then a = b by transitivity of equality since both equal bot_elt. If b ≠ bot_elt, then by definition of move_to_bottom, move_to_bottom r bot_elt b a evaluates to True (since b ≠ bot_elt and a = bot_elt), which directly contradicts the hypothesis h2.
by_cases ha : a = bot_elt · by_cases hb : b = bot_elt · exact ha.trans hb.symm · have : move_to_bottom r bot_elt b a := by simp [move_to_bottom, ha, hb] exact absurd this h2
If a ≠ bot_elt, then a = b, completing the proof of trichotomy.
Assuming a ≠ bot_elt, we case-split on whether b = bot_elt. If b = bot_elt, then move_to_bottom r bot_elt a b is True by definition, contradicting h1. If b ≠ bot_elt, the condition of each if-branch is false, so using if_false simplifies the hypotheses h1 and h2 to ¬r a b and ¬r b a. By the trichotomy of r (Std.Trichotomous.trichotomous), this implies a = b.
uses
if_false,Std.Trichotomous.trichotomous· by_cases hb : b = bot_elt · have : move_to_bottom r bot_elt a b := by simp [move_to_bottom, ha, hb] exact absurd this h1 · simp only [move_to_bottom, ha, hb, if_false] at h1 h2 exact Std.Trichotomous.trichotomous a b h1 h2
The modified relation is irreflexive: for any element a, ¬move_to_bottom r bot_elt a a holds.
To establish that the relation is a strict order, we must show irreflexivity and transitivity. For irreflexivity, let a be given and case-split on whether a = bot_elt. If a = bot_elt, the relation evaluates to False by the first branch of move_to_bottom. If a ≠ bot_elt, the definition simplifies to r a a, which is false by the irreflexivity of r (Std.Irrefl.irrefl).
uses
Std.Irrefl.irrefl· refine { toIrrefl := ?_, toIsTrans := ?_ } · refine { irrefl := ?_ } intro a by_cases ha : a = bot_elt · simp [move_to_bottom, ha] · simp [move_to_bottom, ha, Std.Irrefl.irrefl a]
For transitivity, if a = bot_elt, the implication holds vacuously.
To establish transitivity, let elements a, b, c be given. Case-splitting on whether a = bot_elt, if a = bot_elt then the premise move_to_bottom r bot_elt a b simplifies to False, making the implication vacuously true.
· refine { trans := ?_ } intro a b c by_cases ha : a = bot_elt · intro h simp [move_to_bottom, ha] at h
If a ≠ bot_elt and b = bot_elt, transitivity holds vacuously.
Assuming b = bot_elt, the second premise move_to_bottom r bot_elt b c simplifies to False by definition, so the implication again holds vacuously.
· by_cases hb : b = bot_elt · intro _ h2 simp [move_to_bottom, hb] at h2
If a, b ≠ bot_elt and c = bot_elt, the conclusion move_to_bottom r bot_elt a c holds.
Assuming c = bot_elt, since a ≠ bot_elt, the conclusion move_to_bottom r bot_elt a c evaluates directly to True by the definition of move_to_bottom.
· by_cases hc : c = bot_elt · intro _ _ simp [move_to_bottom, ha, hc]
If none of a, b, c is bot_elt, transitivity follows from the transitivity of r.
When none of a, b, c equals bot_elt, all conditional branches evaluate to their else-cases via if_false, simplifying the premises and conclusion to r a b, r b c, and r a c. The goal then follows immediately from the transitivity of r (IsTrans.trans).
uses
if_false,IsTrans.trans· intro h1 h2 simp only [move_to_bottom, ha, hb, hc, if_false] at h1 h2 ⊢ exact IsTrans.trans a b c h1 h2
if_false- An if-then-else expression with a false condition simplifies to its else branch: (if False then t else e) = e.
Std.Trichotomous.trichotomous- In a trichotomous relation r, if neither r a b nor r b a holds, then a = b.
Std.Irrefl.irrefl- An irreflexive relation r satisfies ¬r a a for every element a.
IsTrans.trans- A transitive relation r satisfies r a b → r b c → r a c for all elements a, b, c.
- Despite the name `move_to_bottom`, the definition sets `move_to_bottom r bot_elt a b` to `False` when `a = bot_elt` and to `True` when `b = bot_elt` (and `a ≠ bot_elt`). Thus, if `r` is read as strict less-than (<), `bot_elt` is made greater than all other elements; under the dual reading where `r` represents strict greater-than (>), `bot_elt` is at the bottom.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Moving an element to the bottom of a strict total order preserves the strict total order property. -/theorem move_to_bottom_is_strict_total_order {α : Type*} (r : α → α → Prop) [IsStrictTotalOrder α r] (bot_elt : α) : IsStrictTotalOrder α (move_to_bottom r bot_elt) := by refine { toTrichotomous := ?_, toIsStrictOrder := ?_ } · refine { trichotomous := ?_ } intro a b h1 h2 by_cases ha : a = bot_elt · by_cases hb : b = bot_elt · exact ha.trans hb.symm · have : move_to_bottom r bot_elt b a := by simp [move_to_bottom, ha, hb] exact absurd this h2 · by_cases hb : b = bot_elt · have : move_to_bottom r bot_elt a b := by simp [move_to_bottom, ha, hb] exact absurd this h1 · simp only [move_to_bottom, ha, hb, if_false] at h1 h2 exact Std.Trichotomous.trichotomous a b h1 h2 · refine { toIrrefl := ?_, toIsTrans := ?_ } · refine { irrefl := ?_ } intro a by_cases ha : a = bot_elt · simp [move_to_bottom, ha] · simp [move_to_bottom, ha, Std.Irrefl.irrefl a] · refine { trans := ?_ } intro a b c by_cases ha : a = bot_elt · intro h simp [move_to_bottom, ha] at h · by_cases hb : b = bot_elt · intro _ h2 simp [move_to_bottom, hb] at h2 · by_cases hc : c = bot_elt · intro _ _ simp [move_to_bottom, ha, hc] · intro h1 h2 simp only [move_to_bottom, ha, hb, hc, if_false] at h1 h2 ⊢ exact IsTrans.trans a b c h1 h2