Physlib.List.takeWhile_orderedInsert
theoremverifiedformalizationimported Lean
Physlib.List.takeWhile_orderedInsert
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open _root_.Physlib.Fin in variable {n : Nat} in lemma Physlib.List.takeWhile_orderedInsert {α : Type} (r : α → α → Prop) [DecidableRel r] [Std.Total r] [IsTrans α r] (a b : α) (hr : ¬ r a b) : (l : List α) → (List.takeWhile (fun c => !decide (r a c)) (List.orderedInsert r b l)).length = (List.takeWhile (fun c => !decide (r a c)) l).length + 1
- Formalizes
- Physlib, `Physlib.List.takeWhile_orderedInsert`
- Lean proof
- By Joseph Tooby-Smith, from github.com/leanprover-community/physlib at
e411c6e89692(Copyright (c) 2024 Joseph Tooby-Smith. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.34.1.Physlib.List.takeWhile_orderedInsert← Physlib.List.takeWhile_orderedInsert (Physlib/Mathematics/ForMathlib/List/InsertionSort.lean:153): verbatim
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Physlib.Fin.involutionNoFixedSetOneFixed point involutions of
Fin n.succ.succfixingf 0 = 1are equivalent to fixed point involutions ofFin n.
- Physlib.Fin.involutionNoFixedSetOneFixed point involutions of
- Used by 1
- FieldStatistic.ofList_eq_prodFieldStatistic.ofList_eq_prod
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen _root_.Physlib.Fin invariable {n : Nat} inlemma Physlib.List.takeWhile_orderedInsert {α : Type} (r : α → α → Prop) [DecidableRel r] [Std.Total r] [IsTrans α r] (a b : α) (hr : ¬ r a b) : (l : List α) → (List.takeWhile (fun c => !decide (r a c)) (List.orderedInsert r b l)).length = (List.takeWhile (fun c => !decide (r a c)) l).length + 1 | [] => by simp [hr] | c :: l => by simp only [List.orderedInsert] by_cases h : r b c · simp [h, hr] · simp only [h, ↓reduceIte] have hl : ¬ r a c := fun hn => h (IsTrans.trans _ _ _ ((Std.Total.total a b).resolve_left hr) hn) simp only [hl, decide_false, Bool.not_false, List.takeWhile_cons_of_pos, List.length_cons, add_left_inj] exact takeWhile_orderedInsert r a b hr l