AFTD Auto-Formalizing Theoretical Domains

move_to_bottom_is_strict_total_order

theoremverified

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.

  1. 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.

    lines 4–6

      refine { toTrichotomous := ?_, toIsStrictOrder := ?_ }
      · refine { trichotomous := ?_ }
        intro a b h1 h2
  2. 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.

    lines 7–11

        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
  3. 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.

    lines 12–16

    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
  4. 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).

    lines 17–22

    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]
  5. 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.

    lines 23–27

        · refine { trans := ?_ }
          intro a b c
          by_cases ha : a = bot_elt
          · intro h
            simp [move_to_bottom, ha] at h
  6. 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.

    lines 28–30

          · by_cases hb : b = bot_elt
            · intro _ h2
              simp [move_to_bottom, hb] at h2
  7. 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.

    lines 31–33

            · by_cases hc : c = bot_elt
              · intro _ _
                simp [move_to_bottom, ha, hc]
  8. 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).

    lines 34–36

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it