data.ordmap.ordset | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

47b51515

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

af471b9e

bump to nightly-2024-04-25-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

ad7a2212

Diff

@@ -601,7 +601,7 @@ theorem all_node' {P l x r} : @All α P (node' l x r) ↔ All P l ∧ P x ∧ Al
 #print Ordnode.all_node3L /-
 theorem all_node3L {P l x m y r} :
     @All α P (node3L l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r := by
-  simp [node3_l, all_node', and_assoc']
+  simp [node3_l, all_node', and_assoc]
 #align ordnode.all_node3_l Ordnode.all_node3L
 -/
 
@@ -615,14 +615,14 @@ theorem all_node3R {P l x m y r} :
 #print Ordnode.all_node4L /-
 theorem all_node4L {P l x m y r} :
     @All α P (node4L l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r := by
-  cases m <;> simp [node4_l, all_node', all, all_node3_l, and_assoc']
+  cases m <;> simp [node4_l, all_node', all, all_node3_l, and_assoc]
 #align ordnode.all_node4_l Ordnode.all_node4L
 -/
 
 #print Ordnode.all_node4R /-
 theorem all_node4R {P l x m y r} :
     @All α P (node4R l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r := by
-  cases m <;> simp [node4_r, all_node', all, all_node3_r, and_assoc']
+  cases m <;> simp [node4_r, all_node', all, all_node3_r, and_assoc]
 #align ordnode.all_node4_r Ordnode.all_node4R
 -/
 
@@ -634,7 +634,7 @@ theorem all_rotateL {P l x r} : @All α P (rotateL l x r) ↔ All P l ∧ P x 
 
 #print Ordnode.all_rotateR /-
 theorem all_rotateR {P l x r} : @All α P (rotateR l x r) ↔ All P l ∧ P x ∧ All P r := by
-  rw [← all_dual, dual_rotate_r, all_rotate_l] <;> simp [all_dual, and_comm', and_left_comm]
+  rw [← all_dual, dual_rotate_r, all_rotate_l] <;> simp [all_dual, and_comm, and_left_comm]
 #align ordnode.all_rotate_r Ordnode.all_rotateR
 -/
 
@@ -673,7 +673,7 @@ theorem toList_node (s l x r) : toList (@node α s l x r) = toList l ++ x :: toL
 
 #print Ordnode.emem_iff_mem_toList /-
 theorem emem_iff_mem_toList {x : α} {t} : Emem x t ↔ x ∈ toList t := by
-  unfold emem <;> induction t <;> simp [any, *, or_assoc']
+  unfold emem <;> induction t <;> simp [any, *, or_assoc]
 #align ordnode.emem_iff_mem_to_list Ordnode.emem_iff_mem_toList
 -/

af471b9e

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -845,7 +845,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · have : size rrl = 0 ∧ size rrr = 0 :=
           by
           have := balanced_sz_zero.1 hr.1.symm
-          rwa [size, sr.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
+          rwa [size, sr.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
         cases sr.2.2.2.1.size_eq_zero.1 this.1
         cases sr.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : rrs = 1 := sr.2.2.1
@@ -854,7 +854,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · have : size rll = 0 ∧ size rlr = 0 :=
           by
           have := balanced_sz_zero.1 hr.1
-          rwa [size, sr.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
+          rwa [size, sr.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
         cases sr.2.1.2.1.size_eq_zero.1 this.1
         cases sr.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : rls = 1 := sr.2.1.1
@@ -874,7 +874,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · have : size lrl = 0 ∧ size lrr = 0 :=
           by
           have := balanced_sz_zero.1 hl.1.symm
-          rwa [size, sl.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
+          rwa [size, sl.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
         cases sl.2.2.2.1.size_eq_zero.1 this.1
         cases sl.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : lrs = 1 := sl.2.2.1
@@ -883,7 +883,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · have : size lll = 0 ∧ size llr = 0 :=
           by
           have := balanced_sz_zero.1 hl.1
-          rwa [size, sl.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
+          rwa [size, sl.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
         cases sl.2.1.2.1.size_eq_zero.1 this.1
         cases sl.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : lls = 1 := sl.2.1.1
@@ -902,9 +902,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · have rd : delta ≤ size rl + size rr :=
             by
             have := lt_of_le_of_lt (Nat.mul_le_mul_left _ sl.pos) h
-            rwa [sr.1, Nat.lt_succ_iff] at this 
+            rwa [sr.1, Nat.lt_succ_iff] at this
           cases' rl with rls rll rlx rlr
-          · rw [size, zero_add] at rd 
+          · rw [size, zero_add] at rd
             exact absurd (le_trans rd (balanced_sz_zero.1 hr.1.symm)) (by decide)
           cases' rr with rrs rrl rrx rrr
           · exact absurd (le_trans rd (balanced_sz_zero.1 hr.1)) (by decide)
@@ -914,9 +914,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · have ld : delta ≤ size ll + size lr :=
             by
             have := lt_of_le_of_lt (Nat.mul_le_mul_left _ sr.pos) h_1
-            rwa [sl.1, Nat.lt_succ_iff] at this 
+            rwa [sl.1, Nat.lt_succ_iff] at this
           cases' ll with lls lll llx llr
-          · rw [size, zero_add] at ld 
+          · rw [size, zero_add] at ld
             exact absurd (le_trans ld (balanced_sz_zero.1 hl.1.symm)) (by decide)
           cases' lr with lrs lrl lrx lrr
           · exact absurd (le_trans ld (balanced_sz_zero.1 hl.1)) (by decide)
@@ -937,7 +937,7 @@ theorem balanceL_eq_balance {l x r} (sl : Sized l) (sr : Sized r) (H1 : size l =
   · cases' l with ls ll lx lr
     · have : size rl = 0 ∧ size rr = 0 := by
         have := H1 rfl
-        rwa [size, sr.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
+        rwa [size, sr.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
       cases sr.2.1.size_eq_zero.1 this.1
       cases sr.2.2.size_eq_zero.1 this.2
       rw [sr.eq_node']; rfl
@@ -1013,7 +1013,7 @@ theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     @balanceL α l x r = balance' l x r :=
   by
   rw [← balance_eq_balance' hl hr sl sr, balance_l_eq_balance sl sr]
-  · intro l0; rw [l0] at H 
+  · intro l0; rw [l0] at H
     rcases H with (⟨_, ⟨⟨⟩⟩ | ⟨⟨⟩⟩, H⟩ | ⟨r', e, H⟩)
     · exact balanced_sz_zero.1 H.symm
     exact le_trans (raised_iff.1 e).1 (balanced_sz_zero.1 H.symm)
@@ -1124,7 +1124,7 @@ theorem Bounded.dual :
 theorem Bounded.dual_iff {t : Ordnode α} {o₁ o₂} :
     Bounded t o₁ o₂ ↔ @Bounded αᵒᵈ _ (dual t) o₂ o₁ :=
   ⟨Bounded.dual, fun h => by
-    have := bounded.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this ⟩
+    have := bounded.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this⟩
 #align ordnode.bounded.dual_iff Ordnode.Bounded.dual_iff
 -/
 
@@ -1346,7 +1346,7 @@ theorem Valid'.dual : ∀ {t : Ordnode α} {o₁ o₂} (h : Valid' o₁ t o₂),
 #print Ordnode.Valid'.dual_iff /-
 theorem Valid'.dual_iff {t : Ordnode α} {o₁ o₂} : Valid' o₁ t o₂ ↔ @Valid' αᵒᵈ _ o₂ (dual t) o₁ :=
   ⟨Valid'.dual, fun h => by
-    have := valid'.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this ⟩
+    have := valid'.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this⟩
 #align ordnode.valid'.dual_iff Ordnode.Valid'.dual_iff
 -/
 
@@ -1475,16 +1475,16 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
       balanced_sz (size mr) (size r) ∧ balanced_sz (size l + size ml + 1) (size mr + size r + 1)
   exact valid'.node' (hl.node' hm.left this.1) (hm.right.node' hr this.2.1) this.2.2
   rcases H with (⟨l0, m1, r0⟩ | ⟨l0, mr₁, lr₁, lr₂, mr₂⟩)
-  · rw [hm.2.size_eq, Nat.succ_inj, add_eq_zero_iff] at m1 
+  · rw [hm.2.size_eq, Nat.succ_inj, add_eq_zero_iff] at m1
     rw [l0, m1.1, m1.2]; rcases size r with (_ | _ | _) <;> exact by decide
   · cases' Nat.eq_zero_or_pos (size r) with r0 r0
-    · rw [r0] at mr₂ ; cases not_le_of_lt Hm mr₂
-    rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂ 
+    · rw [r0] at mr₂; cases not_le_of_lt Hm mr₂
+    rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂
     by_cases mm : size ml + size mr ≤ 1
     · have r1 :=
         le_antisymm
           ((mul_le_mul_left (by decide)).1 (le_trans mr₁ (Nat.succ_le_succ mm) : _ ≤ ratio * 1)) r0
-      rw [r1, add_assoc] at lr₁ 
+      rw [r1, add_assoc] at lr₁
       have l1 :=
         le_antisymm
           ((mul_le_mul_left (by decide)).1 (le_trans lr₁ (add_le_add_right mm 2) : _ ≤ delta * 1))
@@ -1492,20 +1492,20 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
       rw [l1, r1]
       cases size ml <;> cases size mr
       · exact by decide
-      · rw [zero_add] at mm ; rcases mm with (_ | ⟨⟨⟩⟩)
+      · rw [zero_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
         exact by decide
       · rcases mm with (_ | ⟨⟨⟩⟩); exact by decide
-      · rw [Nat.succ_add] at mm ; rcases mm with (_ | ⟨⟨⟩⟩)
+      · rw [Nat.succ_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
     cases' Nat.eq_zero_or_pos (size ml) with ml0 ml0
-    · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂ 
-      rw [ml0, mm₂] at mm ; cases mm (by decide)
+    · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂
+      rw [ml0, mm₂] at mm; cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 :=
       by
       have := Nat.mul_le_mul_left _ lr₁
-      rw [mul_left_comm, mul_add] at this 
+      rw [mul_left_comm, mul_add] at this
       have := le_trans this (add_le_add_left mr₁ _)
-      rw [← Nat.succ_mul] at this 
+      rw [← Nat.succ_mul] at this
       exact (mul_le_mul_left (by decide)).1 this
     refine' ⟨Or.inr ⟨_, _⟩, Or.inr ⟨_, _⟩, Or.inr ⟨_, _⟩⟩
     · refine' (mul_le_mul_left (by decide)).1 (le_trans this _)
@@ -1549,13 +1549,13 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     (H3 : 2 * size r ≤ 9 * size l + 5 ∨ size r ≤ 3) : Valid' o₁ (@rotateL α l x r) o₂ :=
   by
   cases' r with rs rl rx rr; · cases H2
-  rw [hr.2.size_eq, Nat.lt_succ_iff] at H2 
-  rw [hr.2.size_eq] at H3 
+  rw [hr.2.size_eq, Nat.lt_succ_iff] at H2
+  rw [hr.2.size_eq] at H3
   replace H3 : 2 * (size rl + size rr) ≤ 9 * size l + 3 ∨ size rl + size rr ≤ 2 :=
     H3.imp (@Nat.le_of_add_le_add_right 2 _ _) Nat.le_of_succ_le_succ
   have H3_0 : size l = 0 → size rl + size rr ≤ 2 :=
     by
-    intro l0; rw [l0] at H3 
+    intro l0; rw [l0] at H3
     exact
       (or_iff_right_of_imp fun h => (mul_le_mul_left (by decide)).1 (le_trans h (by decide))).1 H3
   have H3p : size l > 0 → 2 * (size rl + size rr) ≤ 9 * size l + 3 := fun l0 : 1 ≤ size l =>
@@ -1576,7 +1576,7 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
         rw [le_antisymm (balanced_sz_zero.1 this.symm) rr0]
         exact by decide
       have rr1 : size rr = 1 := le_antisymm (ablem rl0 H3) rr0
-      rw [add_comm] at H3 
+      rw [add_comm] at H3
       rw [rr1, show size rl = 1 from le_antisymm (ablem rr0 H3) rl0]
       exact by decide
     replace H3 := H3p l0
@@ -1590,17 +1590,17 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
         le_trans hb₂
           (Nat.mul_le_mul_left _ <| le_trans (Nat.le_add_left _ _) (Nat.le_add_right _ _))
   · cases' Nat.eq_zero_or_pos (size rl) with rl0 rl0
-    · rw [rl0, not_lt, le_zero_iff, Nat.mul_eq_zero] at h 
+    · rw [rl0, not_lt, le_zero_iff, Nat.mul_eq_zero] at h
       replace h := h.resolve_left (by decide)
-      rw [rl0, h, le_zero_iff, Nat.mul_eq_zero] at H2 
-      rw [hr.2.size_eq, rl0, h, H2.resolve_left (by decide)] at H1 
+      rw [rl0, h, le_zero_iff, Nat.mul_eq_zero] at H2
+      rw [hr.2.size_eq, rl0, h, H2.resolve_left (by decide)] at H1
       cases H1 (by decide)
     refine' hl.node4_l hr.left hr.right rl0 _
     cases' Nat.eq_zero_or_pos (size l) with l0 l0
     · replace H3 := H3_0 l0
       cases' Nat.eq_zero_or_pos (size rr) with rr0 rr0
       · have := hr.3.1
-        rw [rr0] at this 
+        rw [rr0] at this
         exact Or.inl ⟨l0, le_antisymm (balanced_sz_zero.1 this) rl0, rr0.symm ▸ zero_le_one⟩
       exact Or.inl ⟨l0, le_antisymm (ablem rr0 <| by rwa [add_comm]) rl0, ablem rl0 H3⟩
     exact
@@ -1643,8 +1643,8 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
   suffices @size α r ≤ 3 * (size l + 1)
     by
     cases' Nat.eq_zero_or_pos (size l) with l0 l0
-    · apply Or.inr; rwa [l0] at this 
-    change 1 ≤ _ at l0 ; apply Or.inl; linarith
+    · apply Or.inr; rwa [l0] at this
+    change 1 ≤ _ at l0; apply Or.inl; linarith
   rcases H2 with (⟨hl, rfl⟩ | ⟨hr, rfl⟩) <;> rcases H1 with (h | ⟨h₁, h₂⟩)
   · exact le_trans (Nat.le_add_left _ _) (le_trans h (Nat.le_add_left _ _))
   ·
@@ -1720,7 +1720,7 @@ theorem Valid'.balanceR_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Va
   by
   rw [valid'.dual_iff, dual_balance_r]
   have := hr.dual.balance_l_aux hl.dual
-  rw [size_dual, size_dual] at this 
+  rw [size_dual, size_dual] at this
   exact this H₁ H₂ H₃
 #align ordnode.valid'.balance_r_aux Ordnode.Valid'.balanceR_aux
 -/
@@ -1740,7 +1740,7 @@ theorem Valid'.eraseMax_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r)
     Valid' o₁ (@eraseMax α (node' l x r)) ↑(findMax' x r) ∧
       size (node' l x r) = size (eraseMax (node' l x r)) + 1 :=
   by
-  have := H.2.eq_node'; rw [this] at H ; clear this
+  have := H.2.eq_node'; rw [this] at H; clear this
   induction' r with rs rl rx rr IHrl IHrr generalizing l x o₁
   · exact ⟨H.left, rfl⟩
   have := H.2.2.2.eq_node'; rw [this] at H ⊢
@@ -1758,7 +1758,7 @@ theorem Valid'.eraseMin_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r)
   by
   have := H.dual.erase_max_aux <;>
     rwa [← dual_node', size_dual, ← dual_erase_min, size_dual, ← valid'.dual_iff, find_max'_dual] at
-      this 
+      this
 #align ordnode.valid'.erase_min_aux Ordnode.Valid'.eraseMin_aux
 -/
 
@@ -1792,7 +1792,7 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
     · exact @find_max'_all _ (fun a => all (· > a) (node rs rl rx rr)) lx lr sep.2.1 sep.2.2
     · rw [size_balance_r v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
     · refine' Or.inl ⟨_, Or.inr e, _⟩
-      rwa [hl.2.eq_node'] at bal 
+      rwa [hl.2.eq_node'] at bal
   · rw [split_min_eq, glue]
     cases' valid'.erase_min_aux hr with v e
     suffices H
@@ -1806,7 +1806,7 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
           (sep.imp fun y hy => hy.2.1)
     · rw [size_balance_l hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
     · refine' Or.inr ⟨_, Or.inr e, _⟩
-      rwa [hr.2.eq_node'] at bal 
+      rwa [hr.2.eq_node'] at bal
 #align ordnode.valid'.glue_aux Ordnode.Valid'.glue_aux
 -/
 
@@ -1830,8 +1830,8 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
     (h : delta * ls < rs) (v : Valid' o₁ t ↑rx) (e : size t = ls + size rl) :
     Valid' o₁ (balanceL t rx rr) o₂ ∧ size (balanceL t rx rr) = ls + rs :=
   by
-  rw [hl.2.1] at e 
-  rw [hl.2.1, hr.2.1, delta] at h 
+  rw [hl.2.1] at e
+  rw [hl.2.1, hr.2.1, delta] at h
   rcases hr.3.1 with (H | ⟨hr₁, hr₂⟩); · linarith
   suffices H₂; suffices H₁
   refine' ⟨valid'.balance_l_aux v hr.right H₁ H₂ _, _⟩
@@ -1862,7 +1862,7 @@ theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid'
   · cases' IHlr hl.right (hr.of_gt hl.1.2.to_nil sep.2.1) sep.2.2 with v e
     have := valid'.merge_aux₁ hr.dual hl.dual h_1 v.dual
     rw [size_dual, add_comm, size_dual, ← dual_balance_r, ← valid'.dual_iff, size_dual,
-      add_comm rs] at this 
+      add_comm rs] at this
     exact this e
   · refine' valid'.glue_aux hl hr sep (Or.inr ⟨not_lt.1 h_1, not_lt.1 h⟩)
 #align ordnode.valid'.merge_aux Ordnode.Valid'.merge_aux
@@ -2037,9 +2037,9 @@ theorem size_erase_of_mem [@DecidableRel α (· ≤ ·)] {x : α} {t a₁ a₂}
   · have t_ih_l' := t_ih_l h.left
     have t_ih_r' := t_ih_r h.right
     clear t_ih_l t_ih_r
-    unfold Membership.Mem mem at h_mem 
+    unfold Membership.Mem mem at h_mem
     unfold erase
-    cases cmpLE x t_x <;> simp [mem._match_1] at h_mem  <;> simp [erase._match_1]
+    cases cmpLE x t_x <;> simp [mem._match_1] at h_mem <;> simp [erase._match_1]
     · have t_ih_l := t_ih_l' h_mem
       clear t_ih_l' t_ih_r'
       have t_l_h := valid'.erase_aux x h.left
@@ -2181,7 +2181,7 @@ instance mem.decidable (x : α) (s : Ordset α) : Decidable (x ∈ s) :=
 #print Ordset.pos_size_of_mem /-
 theorem pos_size_of_mem {x : α} {t : Ordset α} (h_mem : x ∈ t) : 0 < size t :=
   by
-  simp [Membership.Mem, mem] at h_mem 
+  simp [Membership.Mem, mem] at h_mem
   apply Ordnode.pos_size_of_mem t.property.sz h_mem
 #align ordset.pos_size_of_mem Ordset.pos_size_of_mem
 -/

af471b9e

bump to nightly-2024-01-13-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

31733180

Diff

@@ -1475,7 +1475,7 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
       balanced_sz (size mr) (size r) ∧ balanced_sz (size l + size ml + 1) (size mr + size r + 1)
   exact valid'.node' (hl.node' hm.left this.1) (hm.right.node' hr this.2.1) this.2.2
   rcases H with (⟨l0, m1, r0⟩ | ⟨l0, mr₁, lr₁, lr₂, mr₂⟩)
-  · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1 
+  · rw [hm.2.size_eq, Nat.succ_inj, add_eq_zero_iff] at m1 
     rw [l0, m1.1, m1.2]; rcases size r with (_ | _ | _) <;> exact by decide
   · cases' Nat.eq_zero_or_pos (size r) with r0 r0
     · rw [r0] at mr₂ ; cases not_le_of_lt Hm mr₂

af471b9e

bump to nightly-2023-11-05-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

acc3325f

Diff

@@ -231,7 +231,7 @@ theorem balancedSz_zero {l : ℕ} : BalancedSz l 0 ↔ l ≤ 1 := by
 theorem balancedSz_up {l r₁ r₂ : ℕ} (h₁ : r₁ ≤ r₂) (h₂ : l + r₂ ≤ 1 ∨ r₂ ≤ delta * l)
     (H : BalancedSz l r₁) : BalancedSz l r₂ :=
   by
-  refine' or_iff_not_imp_left.2 fun h => _
+  refine' Classical.or_iff_not_imp_left.2 fun h => _
   refine' ⟨_, h₂.resolve_left h⟩
   cases H
   · cases r₂

af471b9e

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
-import Mathbin.Data.Ordmap.Ordnode
-import Mathbin.Algebra.Order.Ring.Defs
-import Mathbin.Data.Nat.Dist
+import Data.Ordmap.Ordnode
+import Algebra.Order.Ring.Defs
+import Data.Nat.Dist
 import Mathbin.Tactic.Linarith.Default
 
 #align_import data.ordmap.ordset from "leanprover-community/mathlib"@"af471b9e3ce868f296626d33189b4ce730fa4c00"

af471b9e

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.ordmap.ordset
-! leanprover-community/mathlib commit af471b9e3ce868f296626d33189b4ce730fa4c00
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Ordmap.Ordnode
 import Mathbin.Algebra.Order.Ring.Defs
 import Mathbin.Data.Nat.Dist
 import Mathbin.Tactic.Linarith.Default
 
+#align_import data.ordmap.ordset from "leanprover-community/mathlib"@"af471b9e3ce868f296626d33189b4ce730fa4c00"
+
 /-!
 # Verification of the `ordnode α` datatype

af471b9e

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -804,6 +804,7 @@ theorem merge_nil_right (t : Ordnode α) : merge nil t = t :=
 #align ordnode.merge_nil_right Ordnode.merge_nil_right
 -/
 
+#print Ordnode.merge_node /-
 @[simp]
 theorem merge_node {ls ll lx lr rs rl rx rr} :
     merge (@node α ls ll lx lr) (node rs rl rx rr) =
@@ -813,6 +814,7 @@ theorem merge_node {ls ll lx lr rs rl rx rr} :
         else glue (node ls ll lx lr) (node rs rl rx rr) :=
   rfl
 #align ordnode.merge_node Ordnode.merge_node
+-/
 
 /-! ### `insert` -/

af471b9e

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.ordmap.ordset
-! leanprover-community/mathlib commit 47b51515e69f59bca5cf34ef456e6000fe205a69
+! leanprover-community/mathlib commit af471b9e3ce868f296626d33189b4ce730fa4c00
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Tactic.Linarith.Default
 /-!
 # Verification of the `ordnode α` datatype
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file proves the correctness of the operations in `data.ordmap.ordnode`.
 The public facing version is the type `ordset α`, which is a wrapper around
 `ordnode α` which includes the correctness invariant of the type, and it exposes
@@ -77,14 +80,18 @@ namespace Ordnode
 /-! ### delta and ratio -/
 
 
+#print Ordnode.not_le_delta /-
 theorem not_le_delta {s} (H : 1 ≤ s) : ¬s ≤ delta * 0 :=
   not_le_of_gt H
 #align ordnode.not_le_delta Ordnode.not_le_delta
+-/
 
+#print Ordnode.delta_lt_false /-
 theorem delta_lt_false {a b : ℕ} (h₁ : delta * a < b) (h₂ : delta * b < a) : False :=
   not_le_of_lt (lt_trans ((mul_lt_mul_left (by decide)).2 h₁) h₂) <| by
     simpa [mul_assoc] using Nat.mul_le_mul_right a (by decide : 1 ≤ delta * delta)
 #align ordnode.delta_lt_false Ordnode.delta_lt_false
+-/
 
 /-! ### `singleton` -/
 
@@ -92,35 +99,46 @@ theorem delta_lt_false {a b : ℕ} (h₁ : delta * a < b) (h₂ : delta * b < a)
 /-! ### `size` and `empty` -/
 
 
+#print Ordnode.realSize /-
 /-- O(n). Computes the actual number of elements in the set, ignoring the cached `size` field. -/
 def realSize : Ordnode α → ℕ
   | nil => 0
   | node _ l _ r => real_size l + real_size r + 1
 #align ordnode.real_size Ordnode.realSize
+-/
 
 /-! ### `sized` -/
 
 
+#print Ordnode.Sized /-
 /-- The `sized` property asserts that all the `size` fields in nodes match the actual size of the
 respective subtrees. -/
 def Sized : Ordnode α → Prop
   | nil => True
   | node s l _ r => s = size l + size r + 1 ∧ sized l ∧ sized r
 #align ordnode.sized Ordnode.Sized
+-/
 
+#print Ordnode.Sized.node' /-
 theorem Sized.node' {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (node' l x r) :=
   ⟨rfl, hl, hr⟩
 #align ordnode.sized.node' Ordnode.Sized.node'
+-/
 
+#print Ordnode.Sized.eq_node' /-
 theorem Sized.eq_node' {s l x r} (h : @Sized α (node s l x r)) : node s l x r = node' l x r := by
   rw [h.1] <;> rfl
 #align ordnode.sized.eq_node' Ordnode.Sized.eq_node'
+-/
 
+#print Ordnode.Sized.size_eq /-
 theorem Sized.size_eq {s l x r} (H : Sized (@node α s l x r)) :
     size (@node α s l x r) = size l + size r + 1 :=
   H.1
 #align ordnode.sized.size_eq Ordnode.Sized.size_eq
+-/
 
+#print Ordnode.Sized.induction /-
 @[elab_as_elim]
 theorem Sized.induction {t} (hl : @Sized α t) {C : Ordnode α → Prop} (H0 : C nil)
     (H1 : ∀ l x r, C l → C r → C (node' l x r)) : C t :=
@@ -129,66 +147,90 @@ theorem Sized.induction {t} (hl : @Sized α t) {C : Ordnode α → Prop} (H0 : C
   rw [hl.eq_node']
   exact H1 _ _ _ (t_ih_l hl.2.1) (t_ih_r hl.2.2)
 #align ordnode.sized.induction Ordnode.Sized.induction
+-/
 
+#print Ordnode.size_eq_realSize /-
 theorem size_eq_realSize : ∀ {t : Ordnode α}, Sized t → size t = realSize t
   | nil, _ => rfl
   | node s l x r, ⟨h₁, h₂, h₃⟩ => by
     rw [size, h₁, size_eq_real_size h₂, size_eq_real_size h₃] <;> rfl
 #align ordnode.size_eq_real_size Ordnode.size_eq_realSize
+-/
 
+#print Ordnode.Sized.size_eq_zero /-
 @[simp]
 theorem Sized.size_eq_zero {t : Ordnode α} (ht : Sized t) : size t = 0 ↔ t = nil := by
   cases t <;> [simp; simp [ht.1]]
 #align ordnode.sized.size_eq_zero Ordnode.Sized.size_eq_zero
+-/
 
+#print Ordnode.Sized.pos /-
 theorem Sized.pos {s l x r} (h : Sized (@node α s l x r)) : 0 < s := by
   rw [h.1] <;> apply Nat.le_add_left
 #align ordnode.sized.pos Ordnode.Sized.pos
+-/
 
 /-! `dual` -/
 
 
+#print Ordnode.dual_dual /-
 theorem dual_dual : ∀ t : Ordnode α, dual (dual t) = t
   | nil => rfl
   | node s l x r => by rw [dual, dual, dual_dual, dual_dual]
 #align ordnode.dual_dual Ordnode.dual_dual
+-/
 
+#print Ordnode.size_dual /-
 @[simp]
 theorem size_dual (t : Ordnode α) : size (dual t) = size t := by cases t <;> rfl
 #align ordnode.size_dual Ordnode.size_dual
+-/
 
 /-! `balanced` -/
 
 
+#print Ordnode.BalancedSz /-
 /-- The `balanced_sz l r` asserts that a hypothetical tree with children of sizes `l` and `r` is
 balanced: either `l ≤ δ * r` and `r ≤ δ * r`, or the tree is trivial with a singleton on one side
 and nothing on the other. -/
 def BalancedSz (l r : ℕ) : Prop :=
   l + r ≤ 1 ∨ l ≤ delta * r ∧ r ≤ delta * l
 #align ordnode.balanced_sz Ordnode.BalancedSz
+-/
 
+#print Ordnode.BalancedSz.dec /-
 instance BalancedSz.dec : DecidableRel BalancedSz := fun l r => Or.decidable
 #align ordnode.balanced_sz.dec Ordnode.BalancedSz.dec
+-/
 
+#print Ordnode.Balanced /-
 /-- The `balanced t` asserts that the tree `t` satisfies the balance invariants
 (at every level). -/
 def Balanced : Ordnode α → Prop
   | nil => True
   | node _ l _ r => BalancedSz (size l) (size r) ∧ Balanced l ∧ Balanced r
 #align ordnode.balanced Ordnode.Balanced
+-/
 
+#print Ordnode.Balanced.dec /-
 instance Balanced.dec : DecidablePred (@Balanced α)
   | t => by induction t <;> unfold Balanced <;> skip <;> infer_instance
 #align ordnode.balanced.dec Ordnode.Balanced.dec
+-/
 
+#print Ordnode.BalancedSz.symm /-
 theorem BalancedSz.symm {l r : ℕ} : BalancedSz l r → BalancedSz r l :=
   Or.imp (by rw [add_comm] <;> exact id) And.symm
 #align ordnode.balanced_sz.symm Ordnode.BalancedSz.symm
+-/
 
+#print Ordnode.balancedSz_zero /-
 theorem balancedSz_zero {l : ℕ} : BalancedSz l 0 ↔ l ≤ 1 := by
   simp (config := { contextual := true }) [balanced_sz]
 #align ordnode.balanced_sz_zero Ordnode.balancedSz_zero
+-/
 
+#print Ordnode.balancedSz_up /-
 theorem balancedSz_up {l r₁ r₂ : ℕ} (h₁ : r₁ ≤ r₂) (h₂ : l + r₂ ≤ 1 ∨ r₂ ≤ delta * l)
     (H : BalancedSz l r₁) : BalancedSz l r₂ :=
   by
@@ -200,44 +242,58 @@ theorem balancedSz_up {l r₁ r₂ : ℕ} (h₁ : r₁ ≤ r₂) (h₂ : l + r
     · exact le_trans (le_trans (Nat.le_add_right _ _) H) (Nat.le_add_left 1 _)
   · exact le_trans H.1 (Nat.mul_le_mul_left _ h₁)
 #align ordnode.balanced_sz_up Ordnode.balancedSz_up
+-/
 
+#print Ordnode.balancedSz_down /-
 theorem balancedSz_down {l r₁ r₂ : ℕ} (h₁ : r₁ ≤ r₂) (h₂ : l + r₂ ≤ 1 ∨ l ≤ delta * r₁)
     (H : BalancedSz l r₂) : BalancedSz l r₁ :=
   have : l + r₂ ≤ 1 → BalancedSz l r₁ := fun H => Or.inl (le_trans (Nat.add_le_add_left h₁ _) H)
   Or.cases_on H this fun H => Or.cases_on h₂ this fun h₂ => Or.inr ⟨h₂, le_trans h₁ H.2⟩
 #align ordnode.balanced_sz_down Ordnode.balancedSz_down
+-/
 
+#print Ordnode.Balanced.dual /-
 theorem Balanced.dual : ∀ {t : Ordnode α}, Balanced t → Balanced (dual t)
   | nil, h => ⟨⟩
   | node s l x r, ⟨b, bl, br⟩ => ⟨by rw [size_dual, size_dual] <;> exact b.symm, br.dual, bl.dual⟩
 #align ordnode.balanced.dual Ordnode.Balanced.dual
+-/
 
 /-! ### `rotate` and `balance` -/
 
 
+#print Ordnode.node3L /-
 /-- Build a tree from three nodes, left associated (ignores the invariants). -/
 def node3L (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) : Ordnode α :=
   node' (node' l x m) y r
 #align ordnode.node3_l Ordnode.node3L
+-/
 
+#print Ordnode.node3R /-
 /-- Build a tree from three nodes, right associated (ignores the invariants). -/
 def node3R (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) : Ordnode α :=
   node' l x (node' m y r)
 #align ordnode.node3_r Ordnode.node3R
+-/
 
+#print Ordnode.node4L /-
 /-- Build a tree from three nodes, with `a () b -> (a ()) b` and `a (b c) d -> ((a b) (c d))`. -/
 def node4L : Ordnode α → α → Ordnode α → α → Ordnode α → Ordnode α
   | l, x, node _ ml y mr, z, r => node' (node' l x ml) y (node' mr z r)
   | l, x, nil, z, r => node3L l x nil z r
 #align ordnode.node4_l Ordnode.node4L
+-/
 
+#print Ordnode.node4R /-
 -- should not happen
 /-- Build a tree from three nodes, with `a () b -> a (() b)` and `a (b c) d -> ((a b) (c d))`. -/
 def node4R : Ordnode α → α → Ordnode α → α → Ordnode α → Ordnode α
   | l, x, node _ ml y mr, z, r => node' (node' l x ml) y (node' mr z r)
   | l, x, nil, z, r => node3R l x nil z r
 #align ordnode.node4_r Ordnode.node4R
+-/
 
+#print Ordnode.rotateL /-
 -- should not happen
 /-- Concatenate two nodes, performing a left rotation `x (y z) -> ((x y) z)`
 if balance is upset. -/
@@ -245,7 +301,9 @@ def rotateL : Ordnode α → α → Ordnode α → Ordnode α
   | l, x, node _ m y r => if size m < ratio * size r then node3L l x m y r else node4L l x m y r
   | l, x, nil => node' l x nil
 #align ordnode.rotate_l Ordnode.rotateL
+-/
 
+#print Ordnode.rotateR /-
 -- should not happen
 /-- Concatenate two nodes, performing a right rotation `(x y) z -> (x (y z))`
 if balance is upset. -/
@@ -253,7 +311,9 @@ def rotateR : Ordnode α → α → Ordnode α → Ordnode α
   | node _ l x m, y, r => if size m < ratio * size l then node3R l x m y r else node4R l x m y r
   | nil, y, r => node' nil y r
 #align ordnode.rotate_r Ordnode.rotateR
+-/
 
+#print Ordnode.balanceL' /-
 -- should not happen
 /-- A left balance operation. This will rebalance a concatenation, assuming the original nodes are
 not too far from balanced. -/
@@ -261,14 +321,18 @@ def balanceL' (l : Ordnode α) (x : α) (r : Ordnode α) : Ordnode α :=
   if size l + size r ≤ 1 then node' l x r
   else if size l > delta * size r then rotateR l x r else node' l x r
 #align ordnode.balance_l' Ordnode.balanceL'
+-/
 
+#print Ordnode.balanceR' /-
 /-- A right balance operation. This will rebalance a concatenation, assuming the original nodes are
 not too far from balanced. -/
 def balanceR' (l : Ordnode α) (x : α) (r : Ordnode α) : Ordnode α :=
   if size l + size r ≤ 1 then node' l x r
   else if size r > delta * size l then rotateL l x r else node' l x r
 #align ordnode.balance_r' Ordnode.balanceR'
+-/
 
+#print Ordnode.balance' /-
 /-- The full balance operation. This is the same as `balance`, but with less manual inlining.
 It is somewhat easier to work with this version in proofs. -/
 def balance' (l : Ordnode α) (x : α) (r : Ordnode α) : Ordnode α :=
@@ -277,49 +341,67 @@ def balance' (l : Ordnode α) (x : α) (r : Ordnode α) : Ordnode α :=
     if size r > delta * size l then rotateL l x r
     else if size l > delta * size r then rotateR l x r else node' l x r
 #align ordnode.balance' Ordnode.balance'
+-/
 
+#print Ordnode.dual_node' /-
 theorem dual_node' (l : Ordnode α) (x : α) (r : Ordnode α) :
     dual (node' l x r) = node' (dual r) x (dual l) := by simp [node', add_comm]
 #align ordnode.dual_node' Ordnode.dual_node'
+-/
 
+#print Ordnode.dual_node3L /-
 theorem dual_node3L (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) :
     dual (node3L l x m y r) = node3R (dual r) y (dual m) x (dual l) := by
   simp [node3_l, node3_r, dual_node']
 #align ordnode.dual_node3_l Ordnode.dual_node3L
+-/
 
+#print Ordnode.dual_node3R /-
 theorem dual_node3R (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) :
     dual (node3R l x m y r) = node3L (dual r) y (dual m) x (dual l) := by
   simp [node3_l, node3_r, dual_node']
 #align ordnode.dual_node3_r Ordnode.dual_node3R
+-/
 
+#print Ordnode.dual_node4L /-
 theorem dual_node4L (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) :
     dual (node4L l x m y r) = node4R (dual r) y (dual m) x (dual l) := by
   cases m <;> simp [node4_l, node4_r, dual_node3_l, dual_node']
 #align ordnode.dual_node4_l Ordnode.dual_node4L
+-/
 
+#print Ordnode.dual_node4R /-
 theorem dual_node4R (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) :
     dual (node4R l x m y r) = node4L (dual r) y (dual m) x (dual l) := by
   cases m <;> simp [node4_l, node4_r, dual_node3_r, dual_node']
 #align ordnode.dual_node4_r Ordnode.dual_node4R
+-/
 
+#print Ordnode.dual_rotateL /-
 theorem dual_rotateL (l : Ordnode α) (x : α) (r : Ordnode α) :
     dual (rotateL l x r) = rotateR (dual r) x (dual l) := by
   cases r <;> simp [rotate_l, rotate_r, dual_node'] <;> split_ifs <;>
     simp [dual_node3_l, dual_node4_l]
 #align ordnode.dual_rotate_l Ordnode.dual_rotateL
+-/
 
+#print Ordnode.dual_rotateR /-
 theorem dual_rotateR (l : Ordnode α) (x : α) (r : Ordnode α) :
     dual (rotateR l x r) = rotateL (dual r) x (dual l) := by
   rw [← dual_dual (rotate_l _ _ _), dual_rotate_l, dual_dual, dual_dual]
 #align ordnode.dual_rotate_r Ordnode.dual_rotateR
+-/
 
+#print Ordnode.dual_balance' /-
 theorem dual_balance' (l : Ordnode α) (x : α) (r : Ordnode α) :
     dual (balance' l x r) = balance' (dual r) x (dual l) :=
   by
   simp [balance', add_comm]; split_ifs <;> simp [dual_node', dual_rotate_l, dual_rotate_r]
   cases delta_lt_false h_1 h_2
 #align ordnode.dual_balance' Ordnode.dual_balance'
+-/
 
+#print Ordnode.dual_balanceL /-
 theorem dual_balanceL (l : Ordnode α) (x : α) (r : Ordnode α) :
     dual (balanceL l x r) = balanceR (dual r) x (dual l) :=
   by
@@ -336,35 +418,49 @@ theorem dual_balanceL (l : Ordnode α) (x : α) (r : Ordnode α) :
     dsimp only [dual]
     split_ifs <;> simp [h, add_comm]
 #align ordnode.dual_balance_l Ordnode.dual_balanceL
+-/
 
+#print Ordnode.dual_balanceR /-
 theorem dual_balanceR (l : Ordnode α) (x : α) (r : Ordnode α) :
     dual (balanceR l x r) = balanceL (dual r) x (dual l) := by
   rw [← dual_dual (balance_l _ _ _), dual_balance_l, dual_dual, dual_dual]
 #align ordnode.dual_balance_r Ordnode.dual_balanceR
+-/
 
+#print Ordnode.Sized.node3L /-
 theorem Sized.node3L {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r) :
     Sized (node3L l x m y r) :=
   (hl.node' hm).node' hr
 #align ordnode.sized.node3_l Ordnode.Sized.node3L
+-/
 
+#print Ordnode.Sized.node3R /-
 theorem Sized.node3R {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r) :
     Sized (node3R l x m y r) :=
   hl.node' (hm.node' hr)
 #align ordnode.sized.node3_r Ordnode.Sized.node3R
+-/
 
+#print Ordnode.Sized.node4L /-
 theorem Sized.node4L {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r) :
     Sized (node4L l x m y r) := by
   cases m <;> [exact (hl.node' hm).node' hr; exact (hl.node' hm.2.1).node' (hm.2.2.node' hr)]
 #align ordnode.sized.node4_l Ordnode.Sized.node4L
+-/
 
+#print Ordnode.node3L_size /-
 theorem node3L_size {l x m y r} : size (@node3L α l x m y r) = size l + size m + size r + 2 := by
   dsimp [node3_l, node', size] <;> rw [add_right_comm _ 1]
 #align ordnode.node3_l_size Ordnode.node3L_size
+-/
 
+#print Ordnode.node3R_size /-
 theorem node3R_size {l x m y r} : size (@node3R α l x m y r) = size l + size m + size r + 2 := by
   dsimp [node3_r, node', size] <;> rw [← add_assoc, ← add_assoc]
 #align ordnode.node3_r_size Ordnode.node3R_size
+-/
 
+#print Ordnode.node4L_size /-
 theorem node4L_size {l x m y r} (hm : Sized m) :
     size (@node4L α l x m y r) = size l + size m + size r + 2 := by
   cases m <;> simp [node4_l, node3_l, node', add_comm, add_left_comm] <;> [skip;
@@ -372,16 +468,22 @@ theorem node4L_size {l x m y r} (hm : Sized m) :
       rw [← add_assoc, ← bit0] <;>
     simp [add_comm, add_left_comm]
 #align ordnode.node4_l_size Ordnode.node4L_size
+-/
 
+#print Ordnode.Sized.dual /-
 theorem Sized.dual : ∀ {t : Ordnode α} (h : Sized t), Sized (dual t)
   | nil, h => ⟨⟩
   | node s l x r, ⟨rfl, sl, sr⟩ => ⟨by simp [size_dual, add_comm], sized.dual sr, sized.dual sl⟩
 #align ordnode.sized.dual Ordnode.Sized.dual
+-/
 
+#print Ordnode.Sized.dual_iff /-
 theorem Sized.dual_iff {t : Ordnode α} : Sized (dual t) ↔ Sized t :=
   ⟨fun h => by rw [← dual_dual t] <;> exact h.dual, Sized.dual⟩
 #align ordnode.sized.dual_iff Ordnode.Sized.dual_iff
+-/
 
+#print Ordnode.Sized.rotateL /-
 theorem Sized.rotateL {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (rotateL l x r) :=
   by
   cases r; · exact hl.node' hr
@@ -389,22 +491,30 @@ theorem Sized.rotateL {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (rotateL
   · exact hl.node3_l hr.2.1 hr.2.2
   · exact hl.node4_l hr.2.1 hr.2.2
 #align ordnode.sized.rotate_l Ordnode.Sized.rotateL
+-/
 
+#print Ordnode.Sized.rotateR /-
 theorem Sized.rotateR {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (rotateR l x r) :=
   Sized.dual_iff.1 <| by rw [dual_rotate_r] <;> exact hr.dual.rotate_l hl.dual
 #align ordnode.sized.rotate_r Ordnode.Sized.rotateR
+-/
 
+#print Ordnode.Sized.rotateL_size /-
 theorem Sized.rotateL_size {l x r} (hm : Sized r) : size (@rotateL α l x r) = size l + size r + 1 :=
   by
   cases r <;> simp [rotate_l]
   simp [size, hm.1, add_comm, add_left_comm]; rw [← add_assoc, ← bit0]; simp
   split_ifs <;> simp [node3_l_size, node4_l_size hm.2.1, add_comm, add_left_comm]
 #align ordnode.sized.rotate_l_size Ordnode.Sized.rotateL_size
+-/
 
+#print Ordnode.Sized.rotateR_size /-
 theorem Sized.rotateR_size {l x r} (hl : Sized l) : size (@rotateR α l x r) = size l + size r + 1 :=
   by rw [← size_dual, dual_rotate_r, hl.dual.rotate_l_size, size_dual, size_dual, add_comm (size l)]
 #align ordnode.sized.rotate_r_size Ordnode.Sized.rotateR_size
+-/
 
+#print Ordnode.Sized.balance' /-
 theorem Sized.balance' {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (balance' l x r) :=
   by
   unfold balance'; split_ifs
@@ -413,7 +523,9 @@ theorem Sized.balance' {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (balanc
   · exact hl.rotate_r hr
   · exact hl.node' hr
 #align ordnode.sized.balance' Ordnode.Sized.balance'
+-/
 
+#print Ordnode.size_balance' /-
 theorem size_balance' {l x r} (hl : @Sized α l) (hr : Sized r) :
     size (@balance' α l x r) = size l + size r + 1 :=
   by
@@ -423,88 +535,122 @@ theorem size_balance' {l x r} (hl : @Sized α l) (hr : Sized r) :
   · exact hl.rotate_r_size
   · rfl
 #align ordnode.size_balance' Ordnode.size_balance'
+-/
 
 /-! ## `all`, `any`, `emem`, `amem` -/
 
 
+#print Ordnode.All.imp /-
 theorem All.imp {P Q : α → Prop} (H : ∀ a, P a → Q a) : ∀ {t}, All P t → All Q t
   | nil, h => ⟨⟩
   | node _ l x r, ⟨h₁, h₂, h₃⟩ => ⟨h₁.imp, H _ h₂, h₃.imp⟩
 #align ordnode.all.imp Ordnode.All.imp
+-/
 
+#print Ordnode.Any.imp /-
 theorem Any.imp {P Q : α → Prop} (H : ∀ a, P a → Q a) : ∀ {t}, Any P t → Any Q t
   | nil => id
   | node _ l x r => Or.imp any.imp <| Or.imp (H _) any.imp
 #align ordnode.any.imp Ordnode.Any.imp
+-/
 
+#print Ordnode.all_singleton /-
 theorem all_singleton {P : α → Prop} {x : α} : All P (singleton x) ↔ P x :=
   ⟨fun h => h.2.1, fun h => ⟨⟨⟩, h, ⟨⟩⟩⟩
 #align ordnode.all_singleton Ordnode.all_singleton
+-/
 
+#print Ordnode.any_singleton /-
 theorem any_singleton {P : α → Prop} {x : α} : Any P (singleton x) ↔ P x :=
   ⟨by rintro (⟨⟨⟩⟩ | h | ⟨⟨⟩⟩) <;> exact h, fun h => Or.inr (Or.inl h)⟩
 #align ordnode.any_singleton Ordnode.any_singleton
+-/
 
+#print Ordnode.all_dual /-
 theorem all_dual {P : α → Prop} : ∀ {t : Ordnode α}, All P (dual t) ↔ All P t
   | nil => Iff.rfl
   | node s l x r =>
     ⟨fun ⟨hr, hx, hl⟩ => ⟨all_dual.1 hl, hx, all_dual.1 hr⟩, fun ⟨hl, hx, hr⟩ =>
       ⟨all_dual.2 hr, hx, all_dual.2 hl⟩⟩
 #align ordnode.all_dual Ordnode.all_dual
+-/
 
+#print Ordnode.all_iff_forall /-
 theorem all_iff_forall {P : α → Prop} : ∀ {t}, All P t ↔ ∀ x, Emem x t → P x
   | nil => (iff_true_intro <| by rintro _ ⟨⟩).symm
   | node _ l x r => by simp [all, emem, all_iff_forall, any, or_imp, forall_and]
 #align ordnode.all_iff_forall Ordnode.all_iff_forall
+-/
 
+#print Ordnode.any_iff_exists /-
 theorem any_iff_exists {P : α → Prop} : ∀ {t}, Any P t ↔ ∃ x, Emem x t ∧ P x
   | nil => ⟨by rintro ⟨⟩, by rintro ⟨_, ⟨⟩, _⟩⟩
   | node _ l x r => by simp [any, emem, any_iff_exists, or_and_right, exists_or]
 #align ordnode.any_iff_exists Ordnode.any_iff_exists
+-/
 
+#print Ordnode.emem_iff_all /-
 theorem emem_iff_all {x : α} {t} : Emem x t ↔ ∀ P, All P t → P x :=
   ⟨fun h P al => all_iff_forall.1 al _ h, fun H => H _ <| all_iff_forall.2 fun _ => id⟩
 #align ordnode.emem_iff_all Ordnode.emem_iff_all
+-/
 
+#print Ordnode.all_node' /-
 theorem all_node' {P l x r} : @All α P (node' l x r) ↔ All P l ∧ P x ∧ All P r :=
   Iff.rfl
 #align ordnode.all_node' Ordnode.all_node'
+-/
 
+#print Ordnode.all_node3L /-
 theorem all_node3L {P l x m y r} :
     @All α P (node3L l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r := by
   simp [node3_l, all_node', and_assoc']
 #align ordnode.all_node3_l Ordnode.all_node3L
+-/
 
+#print Ordnode.all_node3R /-
 theorem all_node3R {P l x m y r} :
     @All α P (node3R l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r :=
   Iff.rfl
 #align ordnode.all_node3_r Ordnode.all_node3R
+-/
 
+#print Ordnode.all_node4L /-
 theorem all_node4L {P l x m y r} :
     @All α P (node4L l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r := by
   cases m <;> simp [node4_l, all_node', all, all_node3_l, and_assoc']
 #align ordnode.all_node4_l Ordnode.all_node4L
+-/
 
+#print Ordnode.all_node4R /-
 theorem all_node4R {P l x m y r} :
     @All α P (node4R l x m y r) ↔ All P l ∧ P x ∧ All P m ∧ P y ∧ All P r := by
   cases m <;> simp [node4_r, all_node', all, all_node3_r, and_assoc']
 #align ordnode.all_node4_r Ordnode.all_node4R
+-/
 
+#print Ordnode.all_rotateL /-
 theorem all_rotateL {P l x r} : @All α P (rotateL l x r) ↔ All P l ∧ P x ∧ All P r := by
   cases r <;> simp [rotate_l, all_node'] <;> split_ifs <;> simp [all_node3_l, all_node4_l, all]
 #align ordnode.all_rotate_l Ordnode.all_rotateL
+-/
 
+#print Ordnode.all_rotateR /-
 theorem all_rotateR {P l x r} : @All α P (rotateR l x r) ↔ All P l ∧ P x ∧ All P r := by
   rw [← all_dual, dual_rotate_r, all_rotate_l] <;> simp [all_dual, and_comm', and_left_comm]
 #align ordnode.all_rotate_r Ordnode.all_rotateR
+-/
 
+#print Ordnode.all_balance' /-
 theorem all_balance' {P l x r} : @All α P (balance' l x r) ↔ All P l ∧ P x ∧ All P r := by
   rw [balance'] <;> split_ifs <;> simp [all_node', all_rotate_l, all_rotate_r]
 #align ordnode.all_balance' Ordnode.all_balance'
+-/
 
 /-! ### `to_list` -/
 
 
+#print Ordnode.foldr_cons_eq_toList /-
 theorem foldr_cons_eq_toList : ∀ (t : Ordnode α) (r : List α), t.foldr List.cons r = toList t ++ r
   | nil, r => rfl
   | node _ l x r, r' => by
@@ -512,99 +658,132 @@ theorem foldr_cons_eq_toList : ∀ (t : Ordnode α) (r : List α), t.foldr List.
         List.append_assoc, ← foldr_cons_eq_to_list] <;>
       rfl
 #align ordnode.foldr_cons_eq_to_list Ordnode.foldr_cons_eq_toList
+-/
 
+#print Ordnode.toList_nil /-
 @[simp]
 theorem toList_nil : toList (@nil α) = [] :=
   rfl
 #align ordnode.to_list_nil Ordnode.toList_nil
+-/
 
+#print Ordnode.toList_node /-
 @[simp]
 theorem toList_node (s l x r) : toList (@node α s l x r) = toList l ++ x :: toList r := by
   rw [to_list, foldr, foldr_cons_eq_to_list] <;> rfl
 #align ordnode.to_list_node Ordnode.toList_node
+-/
 
+#print Ordnode.emem_iff_mem_toList /-
 theorem emem_iff_mem_toList {x : α} {t} : Emem x t ↔ x ∈ toList t := by
   unfold emem <;> induction t <;> simp [any, *, or_assoc']
 #align ordnode.emem_iff_mem_to_list Ordnode.emem_iff_mem_toList
+-/
 
-theorem length_to_list' : ∀ t : Ordnode α, (toList t).length = t.realSize
+#print Ordnode.length_toList' /-
+theorem length_toList' : ∀ t : Ordnode α, (toList t).length = t.realSize
   | nil => rfl
   | node _ l _ r => by
     rw [to_list_node, List.length_append, List.length_cons, length_to_list', length_to_list'] <;>
       rfl
-#align ordnode.length_to_list' Ordnode.length_to_list'
+#align ordnode.length_to_list' Ordnode.length_toList'
+-/
 
+#print Ordnode.length_toList /-
 theorem length_toList {t : Ordnode α} (h : Sized t) : (toList t).length = t.size := by
   rw [length_to_list', size_eq_real_size h]
 #align ordnode.length_to_list Ordnode.length_toList
+-/
 
+#print Ordnode.equiv_iff /-
 theorem equiv_iff {t₁ t₂ : Ordnode α} (h₁ : Sized t₁) (h₂ : Sized t₂) :
     Equiv t₁ t₂ ↔ toList t₁ = toList t₂ :=
   and_iff_right_of_imp fun h => by rw [← length_to_list h₁, h, length_to_list h₂]
 #align ordnode.equiv_iff Ordnode.equiv_iff
+-/
 
 /-! ### `mem` -/
 
 
+#print Ordnode.pos_size_of_mem /-
 theorem pos_size_of_mem [LE α] [@DecidableRel α (· ≤ ·)] {x : α} {t : Ordnode α} (h : Sized t)
     (h_mem : x ∈ t) : 0 < size t := by cases t; · contradiction; · simp [h.1]
 #align ordnode.pos_size_of_mem Ordnode.pos_size_of_mem
+-/
 
 /-! ### `(find/erase/split)_(min/max)` -/
 
 
+#print Ordnode.findMin'_dual /-
 theorem findMin'_dual : ∀ (t) (x : α), findMin' (dual t) x = findMax' x t
   | nil, x => rfl
   | node _ l x r, _ => find_min'_dual r x
 #align ordnode.find_min'_dual Ordnode.findMin'_dual
+-/
 
+#print Ordnode.findMax'_dual /-
 theorem findMax'_dual (t) (x : α) : findMax' x (dual t) = findMin' t x := by
   rw [← find_min'_dual, dual_dual]
 #align ordnode.find_max'_dual Ordnode.findMax'_dual
+-/
 
+#print Ordnode.findMin_dual /-
 theorem findMin_dual : ∀ t : Ordnode α, findMin (dual t) = findMax t
   | nil => rfl
   | node _ l x r => congr_arg some <| findMin'_dual _ _
 #align ordnode.find_min_dual Ordnode.findMin_dual
+-/
 
+#print Ordnode.findMax_dual /-
 theorem findMax_dual (t : Ordnode α) : findMax (dual t) = findMin t := by
   rw [← find_min_dual, dual_dual]
 #align ordnode.find_max_dual Ordnode.findMax_dual
+-/
 
+#print Ordnode.dual_eraseMin /-
 theorem dual_eraseMin : ∀ t : Ordnode α, dual (eraseMin t) = eraseMax (dual t)
   | nil => rfl
   | node _ nil x r => rfl
   | node _ (l@(node _ _ _ _)) x r => by
     rw [erase_min, dual_balance_r, dual_erase_min, dual, dual, dual, erase_max]
 #align ordnode.dual_erase_min Ordnode.dual_eraseMin
+-/
 
+#print Ordnode.dual_eraseMax /-
 theorem dual_eraseMax (t : Ordnode α) : dual (eraseMax t) = eraseMin (dual t) := by
   rw [← dual_dual (erase_min _), dual_erase_min, dual_dual]
 #align ordnode.dual_erase_max Ordnode.dual_eraseMax
+-/
 
-theorem split_min_eq :
-    ∀ (s l) (x : α) (r), splitMin' l x r = (findMin' l x, eraseMin (node s l x r))
+#print Ordnode.splitMin_eq /-
+theorem splitMin_eq : ∀ (s l) (x : α) (r), splitMin' l x r = (findMin' l x, eraseMin (node s l x r))
   | _, nil, x, r => rfl
   | _, node ls ll lx lr, x, r => by rw [split_min', split_min_eq, split_min', find_min', erase_min]
-#align ordnode.split_min_eq Ordnode.split_min_eq
+#align ordnode.split_min_eq Ordnode.splitMin_eq
+-/
 
-theorem split_max_eq :
-    ∀ (s l) (x : α) (r), splitMax' l x r = (eraseMax (node s l x r), findMax' x r)
+#print Ordnode.splitMax_eq /-
+theorem splitMax_eq : ∀ (s l) (x : α) (r), splitMax' l x r = (eraseMax (node s l x r), findMax' x r)
   | _, l, x, nil => rfl
   | _, l, x, node ls ll lx lr => by rw [split_max', split_max_eq, split_max', find_max', erase_max]
-#align ordnode.split_max_eq Ordnode.split_max_eq
+#align ordnode.split_max_eq Ordnode.splitMax_eq
+-/
 
+#print Ordnode.findMin'_all /-
 @[elab_as_elim]
 theorem findMin'_all {P : α → Prop} : ∀ (t) (x : α), All P t → P x → P (findMin' t x)
   | nil, x, h, hx => hx
   | node _ ll lx lr, x, ⟨h₁, h₂, h₃⟩, hx => find_min'_all _ _ h₁ h₂
 #align ordnode.find_min'_all Ordnode.findMin'_all
+-/
 
+#print Ordnode.findMax'_all /-
 @[elab_as_elim]
 theorem findMax'_all {P : α → Prop} : ∀ (x : α) (t), P x → All P t → P (findMax' x t)
   | x, nil, hx, h => hx
   | x, node _ ll lx lr, hx, ⟨h₁, h₂, h₃⟩ => find_max'_all _ _ h₂ h₃
 #align ordnode.find_max'_all Ordnode.findMax'_all
+-/
 
 /-! ### `glue` -/
 
@@ -612,14 +791,18 @@ theorem findMax'_all {P : α → Prop} : ∀ (x : α) (t), P x → All P t → P
 /-! ### `merge` -/
 
 
+#print Ordnode.merge_nil_left /-
 @[simp]
 theorem merge_nil_left (t : Ordnode α) : merge t nil = t := by cases t <;> rfl
 #align ordnode.merge_nil_left Ordnode.merge_nil_left
+-/
 
+#print Ordnode.merge_nil_right /-
 @[simp]
 theorem merge_nil_right (t : Ordnode α) : merge nil t = t :=
   rfl
 #align ordnode.merge_nil_right Ordnode.merge_nil_right
+-/
 
 @[simp]
 theorem merge_node {ls ll lx lr rs rl rx rr} :
@@ -634,6 +817,7 @@ theorem merge_node {ls ll lx lr rs rl rx rr} :
 /-! ### `insert` -/
 
 
+#print Ordnode.dual_insert /-
 theorem dual_insert [Preorder α] [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (x : α) :
     ∀ t : Ordnode α, dual (Ordnode.insert x t) = @Ordnode.insert αᵒᵈ _ _ x (dual t)
   | nil => rfl
@@ -643,10 +827,12 @@ theorem dual_insert [Preorder α] [IsTotal α (· ≤ ·)] [@DecidableRel α (·
     cases cmpLE x y <;>
       simp [Ordering.swap, Ordnode.insert, dual_balance_l, dual_balance_r, dual_insert]
 #align ordnode.dual_insert Ordnode.dual_insert
+-/
 
 /-! ### `balance` properties -/
 
 
+#print Ordnode.balance_eq_balance' /-
 theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l)
     (sr : Sized r) : @balance α l x r = balance' l x r :=
   by
@@ -741,7 +927,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · simp [node']
       · exact not_le_of_gt (add_le_add sl.pos sr.pos : 2 ≤ ls + rs)
 #align ordnode.balance_eq_balance' Ordnode.balance_eq_balance'
+-/
 
+#print Ordnode.balanceL_eq_balance /-
 theorem balanceL_eq_balance {l x r} (sl : Sized l) (sr : Sized r) (H1 : size l = 0 → size r ≤ 1)
     (H2 : 1 ≤ size l → 1 ≤ size r → size r ≤ delta * size l) : @balanceL α l x r = balance l x r :=
   by
@@ -757,12 +945,16 @@ theorem balanceL_eq_balance {l x r} (sl : Sized l) (sr : Sized r) (H1 : size l =
     · replace H2 : ¬rs > delta * ls := not_lt_of_le (H2 sl.pos sr.pos)
       simp [balance_l, balance, H2] <;> split_ifs <;> simp [add_comm]
 #align ordnode.balance_l_eq_balance Ordnode.balanceL_eq_balance
+-/
 
+#print Ordnode.Raised /-
 /-- `raised n m` means `m` is either equal or one up from `n`. -/
 def Raised (n m : ℕ) : Prop :=
   m = n ∨ m = n + 1
 #align ordnode.raised Ordnode.Raised
+-/
 
+#print Ordnode.raised_iff /-
 theorem raised_iff {n m} : Raised n m ↔ n ≤ m ∧ m ≤ n + 1 :=
   by
   constructor; rintro (rfl | rfl)
@@ -773,26 +965,36 @@ theorem raised_iff {n m} : Raised n m ↔ n ≤ m ∧ m ≤ n + 1 :=
     · exact Or.inl rfl
     · exact Or.inr (le_antisymm h₂ h₁)
 #align ordnode.raised_iff Ordnode.raised_iff
+-/
 
+#print Ordnode.Raised.dist_le /-
 theorem Raised.dist_le {n m} (H : Raised n m) : Nat.dist n m ≤ 1 := by
   cases' raised_iff.1 H with H1 H2 <;> rwa [Nat.dist_eq_sub_of_le H1, tsub_le_iff_left]
 #align ordnode.raised.dist_le Ordnode.Raised.dist_le
+-/
 
+#print Ordnode.Raised.dist_le' /-
 theorem Raised.dist_le' {n m} (H : Raised n m) : Nat.dist m n ≤ 1 := by
   rw [Nat.dist_comm] <;> exact H.dist_le
 #align ordnode.raised.dist_le' Ordnode.Raised.dist_le'
+-/
 
+#print Ordnode.Raised.add_left /-
 theorem Raised.add_left (k) {n m} (H : Raised n m) : Raised (k + n) (k + m) :=
   by
   rcases H with (rfl | rfl)
   · exact Or.inl rfl
   · exact Or.inr rfl
 #align ordnode.raised.add_left Ordnode.Raised.add_left
+-/
 
+#print Ordnode.Raised.add_right /-
 theorem Raised.add_right (k) {n m} (H : Raised n m) : Raised (n + k) (m + k) := by
   rw [add_comm, add_comm m] <;> exact H.add_left _
 #align ordnode.raised.add_right Ordnode.Raised.add_right
+-/
 
+#print Ordnode.Raised.right /-
 theorem Raised.right {l x₁ x₂ r₁ r₂} (H : Raised (size r₁) (size r₂)) :
     Raised (size (@node' α l x₁ r₁)) (size (@node' α l x₂ r₂)) :=
   by
@@ -801,7 +1003,9 @@ theorem Raised.right {l x₁ x₂ r₁ r₂} (H : Raised (size r₁) (size r₂)
   · exact Or.inl rfl
   · exact Or.inr rfl
 #align ordnode.raised.right Ordnode.Raised.right
+-/
 
+#print Ordnode.balanceL_eq_balance' /-
 theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l)
     (sr : Sized r)
     (H :
@@ -821,7 +1025,9 @@ theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     · cases raised_iff.1 e; unfold delta; linarith
     · exact le_trans (raised_iff.1 e).1 H₂
 #align ordnode.balance_l_eq_balance' Ordnode.balanceL_eq_balance'
+-/
 
+#print Ordnode.balance_sz_dual /-
 theorem balance_sz_dual {l r}
     (H :
       (∃ l', Raised (@size α l) l' ∧ BalancedSz l' (@size α r)) ∨
@@ -834,7 +1040,9 @@ theorem balance_sz_dual {l r}
     H.symm.imp (Exists.imp fun _ => And.imp_right balanced_sz.symm)
       (Exists.imp fun _ => And.imp_right balanced_sz.symm)
 #align ordnode.balance_sz_dual Ordnode.balance_sz_dual
+-/
 
+#print Ordnode.size_balanceL /-
 theorem size_balanceL {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l) (sr : Sized r)
     (H :
       (∃ l', Raised l' (size l) ∧ BalancedSz l' (size r)) ∨
@@ -842,7 +1050,9 @@ theorem size_balanceL {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l)
     size (@balanceL α l x r) = size l + size r + 1 := by
   rw [balance_l_eq_balance' hl hr sl sr H, size_balance' sl sr]
 #align ordnode.size_balance_l Ordnode.size_balanceL
+-/
 
+#print Ordnode.all_balanceL /-
 theorem all_balanceL {P l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l) (sr : Sized r)
     (H :
       (∃ l', Raised l' (size l) ∧ BalancedSz l' (size r)) ∨
@@ -850,7 +1060,9 @@ theorem all_balanceL {P l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l
     All P (@balanceL α l x r) ↔ All P l ∧ P x ∧ All P r := by
   rw [balance_l_eq_balance' hl hr sl sr H, all_balance']
 #align ordnode.all_balance_l Ordnode.all_balanceL
+-/
 
+#print Ordnode.balanceR_eq_balance' /-
 theorem balanceR_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l)
     (sr : Sized r)
     (H :
@@ -861,7 +1073,9 @@ theorem balanceR_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     balance_l_eq_balance' hr.dual hl.dual sr.dual sl.dual (balance_sz_dual H), ← dual_balance',
     dual_dual]
 #align ordnode.balance_r_eq_balance' Ordnode.balanceR_eq_balance'
+-/
 
+#print Ordnode.size_balanceR /-
 theorem size_balanceR {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l) (sr : Sized r)
     (H :
       (∃ l', Raised (size l) l' ∧ BalancedSz l' (size r)) ∨
@@ -869,7 +1083,9 @@ theorem size_balanceR {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l)
     size (@balanceR α l x r) = size l + size r + 1 := by
   rw [balance_r_eq_balance' hl hr sl sr H, size_balance' sl sr]
 #align ordnode.size_balance_r Ordnode.size_balanceR
+-/
 
+#print Ordnode.all_balanceR /-
 theorem all_balanceR {P l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l) (sr : Sized r)
     (H :
       (∃ l', Raised (size l) l' ∧ BalancedSz l' (size r)) ∨
@@ -877,6 +1093,7 @@ theorem all_balanceR {P l x r} (hl : Balanced l) (hr : Balanced r) (sl : Sized l
     All P (@balanceR α l x r) ↔ All P l ∧ P x ∧ All P r := by
   rw [balance_r_eq_balance' hl hr sl sr H, all_balance']
 #align ordnode.all_balance_r Ordnode.all_balanceR
+-/
 
 /-! ### `bounded` -/
 
@@ -885,6 +1102,7 @@ section
 
 variable [Preorder α]
 
+#print Ordnode.Bounded /-
 /-- `bounded t lo hi` says that every element `x ∈ t` is in the range `lo < x < hi`, and also this
 property holds recursively in subtrees, making the full tree a BST. The bounds can be set to
 `lo = ⊥` and `hi = ⊤` if we care only about the internal ordering constraints. -/
@@ -893,97 +1111,130 @@ def Bounded : Ordnode α → WithBot α → WithTop α → Prop
   | nil, _, _ => True
   | node _ l x r, o₁, o₂ => bounded l o₁ ↑x ∧ bounded r (↑x) o₂
 #align ordnode.bounded Ordnode.Bounded
+-/
 
+#print Ordnode.Bounded.dual /-
 theorem Bounded.dual :
     ∀ {t : Ordnode α} {o₁ o₂} (h : Bounded t o₁ o₂), @Bounded αᵒᵈ _ (dual t) o₂ o₁
   | nil, o₁, o₂, h => by cases o₁ <;> cases o₂ <;> try trivial <;> exact h
   | node s l x r, _, _, ⟨ol, Or⟩ => ⟨Or.dual, ol.dual⟩
 #align ordnode.bounded.dual Ordnode.Bounded.dual
+-/
 
+#print Ordnode.Bounded.dual_iff /-
 theorem Bounded.dual_iff {t : Ordnode α} {o₁ o₂} :
     Bounded t o₁ o₂ ↔ @Bounded αᵒᵈ _ (dual t) o₂ o₁ :=
   ⟨Bounded.dual, fun h => by
     have := bounded.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this ⟩
 #align ordnode.bounded.dual_iff Ordnode.Bounded.dual_iff
+-/
 
+#print Ordnode.Bounded.weak_left /-
 theorem Bounded.weak_left : ∀ {t : Ordnode α} {o₁ o₂}, Bounded t o₁ o₂ → Bounded t ⊥ o₂
   | nil, o₁, o₂, h => by cases o₂ <;> try trivial <;> exact h
   | node s l x r, _, _, ⟨ol, Or⟩ => ⟨ol.weak_left, Or⟩
 #align ordnode.bounded.weak_left Ordnode.Bounded.weak_left
+-/
 
+#print Ordnode.Bounded.weak_right /-
 theorem Bounded.weak_right : ∀ {t : Ordnode α} {o₁ o₂}, Bounded t o₁ o₂ → Bounded t o₁ ⊤
   | nil, o₁, o₂, h => by cases o₁ <;> try trivial <;> exact h
   | node s l x r, _, _, ⟨ol, Or⟩ => ⟨ol, Or.weak_right⟩
 #align ordnode.bounded.weak_right Ordnode.Bounded.weak_right
+-/
 
+#print Ordnode.Bounded.weak /-
 theorem Bounded.weak {t : Ordnode α} {o₁ o₂} (h : Bounded t o₁ o₂) : Bounded t ⊥ ⊤ :=
   h.weak_left.weak_right
 #align ordnode.bounded.weak Ordnode.Bounded.weak
+-/
 
+#print Ordnode.Bounded.mono_left /-
 theorem Bounded.mono_left {x y : α} (xy : x ≤ y) :
     ∀ {t : Ordnode α} {o}, Bounded t (↑y) o → Bounded t (↑x) o
   | nil, none, h => ⟨⟩
   | nil, some z, h => lt_of_le_of_lt xy h
   | node s l z r, o, ⟨ol, Or⟩ => ⟨ol.mono_left, Or⟩
 #align ordnode.bounded.mono_left Ordnode.Bounded.mono_left
+-/
 
+#print Ordnode.Bounded.mono_right /-
 theorem Bounded.mono_right {x y : α} (xy : x ≤ y) :
     ∀ {t : Ordnode α} {o}, Bounded t o ↑x → Bounded t o ↑y
   | nil, none, h => ⟨⟩
   | nil, some z, h => lt_of_lt_of_le h xy
   | node s l z r, o, ⟨ol, Or⟩ => ⟨ol, Or.mono_right⟩
 #align ordnode.bounded.mono_right Ordnode.Bounded.mono_right
+-/
 
+#print Ordnode.Bounded.to_lt /-
 theorem Bounded.to_lt : ∀ {t : Ordnode α} {x y : α}, Bounded t x y → x < y
   | nil, x, y, h => h
   | node _ l y r, x, z, ⟨h₁, h₂⟩ => lt_trans h₁.to_lt h₂.to_lt
 #align ordnode.bounded.to_lt Ordnode.Bounded.to_lt
+-/
 
+#print Ordnode.Bounded.to_nil /-
 theorem Bounded.to_nil {t : Ordnode α} : ∀ {o₁ o₂}, Bounded t o₁ o₂ → Bounded nil o₁ o₂
   | none, _, h => ⟨⟩
   | some _, none, h => ⟨⟩
   | some x, some y, h => h.to_lt
 #align ordnode.bounded.to_nil Ordnode.Bounded.to_nil
+-/
 
+#print Ordnode.Bounded.trans_left /-
 theorem Bounded.trans_left {t₁ t₂ : Ordnode α} {x : α} :
     ∀ {o₁ o₂}, Bounded t₁ o₁ ↑x → Bounded t₂ (↑x) o₂ → Bounded t₂ o₁ o₂
   | none, o₂, h₁, h₂ => h₂.weak_left
   | some y, o₂, h₁, h₂ => h₂.mono_left (le_of_lt h₁.to_lt)
 #align ordnode.bounded.trans_left Ordnode.Bounded.trans_left
+-/
 
+#print Ordnode.Bounded.trans_right /-
 theorem Bounded.trans_right {t₁ t₂ : Ordnode α} {x : α} :
     ∀ {o₁ o₂}, Bounded t₁ o₁ ↑x → Bounded t₂ (↑x) o₂ → Bounded t₁ o₁ o₂
   | o₁, none, h₁, h₂ => h₁.weak_right
   | o₁, some y, h₁, h₂ => h₁.mono_right (le_of_lt h₂.to_lt)
 #align ordnode.bounded.trans_right Ordnode.Bounded.trans_right
+-/
 
+#print Ordnode.Bounded.mem_lt /-
 theorem Bounded.mem_lt : ∀ {t o} {x : α}, Bounded t o ↑x → All (· < x) t
   | nil, o, x, _ => ⟨⟩
   | node _ l y r, o, x, ⟨h₁, h₂⟩ =>
     ⟨h₁.mem_lt.imp fun z h => lt_trans h h₂.to_lt, h₂.to_lt, h₂.mem_lt⟩
 #align ordnode.bounded.mem_lt Ordnode.Bounded.mem_lt
+-/
 
+#print Ordnode.Bounded.mem_gt /-
 theorem Bounded.mem_gt : ∀ {t o} {x : α}, Bounded t (↑x) o → All (· > x) t
   | nil, o, x, _ => ⟨⟩
   | node _ l y r, o, x, ⟨h₁, h₂⟩ => ⟨h₁.mem_gt, h₁.to_lt, h₂.mem_gt.imp fun z => lt_trans h₁.to_lt⟩
 #align ordnode.bounded.mem_gt Ordnode.Bounded.mem_gt
+-/
 
+#print Ordnode.Bounded.of_lt /-
 theorem Bounded.of_lt :
     ∀ {t o₁ o₂} {x : α}, Bounded t o₁ o₂ → Bounded nil o₁ ↑x → All (· < x) t → Bounded t o₁ ↑x
   | nil, o₁, o₂, x, _, hn, _ => hn
   | node _ l y r, o₁, o₂, x, ⟨h₁, h₂⟩, hn, ⟨al₁, al₂, al₃⟩ => ⟨h₁, h₂.of_lt al₂ al₃⟩
 #align ordnode.bounded.of_lt Ordnode.Bounded.of_lt
+-/
 
+#print Ordnode.Bounded.of_gt /-
 theorem Bounded.of_gt :
     ∀ {t o₁ o₂} {x : α}, Bounded t o₁ o₂ → Bounded nil (↑x) o₂ → All (· > x) t → Bounded t (↑x) o₂
   | nil, o₁, o₂, x, _, hn, _ => hn
   | node _ l y r, o₁, o₂, x, ⟨h₁, h₂⟩, hn, ⟨al₁, al₂, al₃⟩ => ⟨h₁.of_gt al₂ al₁, h₂⟩
 #align ordnode.bounded.of_gt Ordnode.Bounded.of_gt
+-/
 
+#print Ordnode.Bounded.to_sep /-
 theorem Bounded.to_sep {t₁ t₂ o₁ o₂} {x : α} (h₁ : Bounded t₁ o₁ ↑x) (h₂ : Bounded t₂ (↑x) o₂) :
     t₁.all fun y => t₂.all fun z : α => y < z :=
   h₁.mem_lt.imp fun y yx => h₂.mem_gt.imp fun z xz => lt_trans yx xz
 #align ordnode.bounded.to_sep Ordnode.Bounded.to_sep
+-/
 
 end
 
@@ -994,6 +1245,7 @@ section
 
 variable [Preorder α]
 
+#print Ordnode.Valid' /-
 /-- The validity predicate for an `ordnode` subtree. This asserts that the `size` fields are
 correct, the tree is balanced, and the elements of the tree are organized according to the
 ordering. This version of `valid` also puts all elements in the tree in the interval `(lo, hi)`. -/
@@ -1002,62 +1254,86 @@ structure Valid' (lo : WithBot α) (t : Ordnode α) (hi : WithTop α) : Prop whe
   sz : t.Sized
   bal : t.Balanced
 #align ordnode.valid' Ordnode.Valid'
+-/
 
+#print Ordnode.Valid /-
 /-- The validity predicate for an `ordnode` subtree. This asserts that the `size` fields are
 correct, the tree is balanced, and the elements of the tree are organized according to the
 ordering. -/
 def Valid (t : Ordnode α) : Prop :=
   Valid' ⊥ t ⊤
 #align ordnode.valid Ordnode.Valid
+-/
 
+#print Ordnode.Valid'.mono_left /-
 theorem Valid'.mono_left {x y : α} (xy : x ≤ y) {t : Ordnode α} {o} (h : Valid' (↑y) t o) :
     Valid' (↑x) t o :=
   ⟨h.1.mono_left xy, h.2, h.3⟩
 #align ordnode.valid'.mono_left Ordnode.Valid'.mono_left
+-/
 
+#print Ordnode.Valid'.mono_right /-
 theorem Valid'.mono_right {x y : α} (xy : x ≤ y) {t : Ordnode α} {o} (h : Valid' o t ↑x) :
     Valid' o t ↑y :=
   ⟨h.1.mono_right xy, h.2, h.3⟩
 #align ordnode.valid'.mono_right Ordnode.Valid'.mono_right
+-/
 
+#print Ordnode.Valid'.trans_left /-
 theorem Valid'.trans_left {t₁ t₂ : Ordnode α} {x : α} {o₁ o₂} (h : Bounded t₁ o₁ ↑x)
     (H : Valid' (↑x) t₂ o₂) : Valid' o₁ t₂ o₂ :=
   ⟨h.trans_left H.1, H.2, H.3⟩
 #align ordnode.valid'.trans_left Ordnode.Valid'.trans_left
+-/
 
+#print Ordnode.Valid'.trans_right /-
 theorem Valid'.trans_right {t₁ t₂ : Ordnode α} {x : α} {o₁ o₂} (H : Valid' o₁ t₁ ↑x)
     (h : Bounded t₂ (↑x) o₂) : Valid' o₁ t₁ o₂ :=
   ⟨H.1.trans_right h, H.2, H.3⟩
 #align ordnode.valid'.trans_right Ordnode.Valid'.trans_right
+-/
 
+#print Ordnode.Valid'.of_lt /-
 theorem Valid'.of_lt {t : Ordnode α} {x : α} {o₁ o₂} (H : Valid' o₁ t o₂) (h₁ : Bounded nil o₁ ↑x)
     (h₂ : All (· < x) t) : Valid' o₁ t ↑x :=
   ⟨H.1.of_lt h₁ h₂, H.2, H.3⟩
 #align ordnode.valid'.of_lt Ordnode.Valid'.of_lt
+-/
 
+#print Ordnode.Valid'.of_gt /-
 theorem Valid'.of_gt {t : Ordnode α} {x : α} {o₁ o₂} (H : Valid' o₁ t o₂) (h₁ : Bounded nil (↑x) o₂)
     (h₂ : All (· > x) t) : Valid' (↑x) t o₂ :=
   ⟨H.1.of_gt h₁ h₂, H.2, H.3⟩
 #align ordnode.valid'.of_gt Ordnode.Valid'.of_gt
+-/
 
+#print Ordnode.Valid'.valid /-
 theorem Valid'.valid {t o₁ o₂} (h : @Valid' α _ o₁ t o₂) : Valid t :=
   ⟨h.1.weak, h.2, h.3⟩
 #align ordnode.valid'.valid Ordnode.Valid'.valid
+-/
 
+#print Ordnode.valid'_nil /-
 theorem valid'_nil {o₁ o₂} (h : Bounded nil o₁ o₂) : Valid' o₁ (@nil α) o₂ :=
   ⟨h, ⟨⟩, ⟨⟩⟩
 #align ordnode.valid'_nil Ordnode.valid'_nil
+-/
 
+#print Ordnode.valid_nil /-
 theorem valid_nil : Valid (@nil α) :=
   valid'_nil ⟨⟩
 #align ordnode.valid_nil Ordnode.valid_nil
+-/
 
+#print Ordnode.Valid'.node /-
 theorem Valid'.node {s l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H : BalancedSz (size l) (size r)) (hs : s = size l + size r + 1) :
     Valid' o₁ (@node α s l x r) o₂ :=
   ⟨⟨hl.1, hr.1⟩, ⟨hs, hl.2, hr.2⟩, ⟨H, hl.3, hr.3⟩⟩
 #align ordnode.valid'.node Ordnode.Valid'.node
+-/
 
+#print Ordnode.Valid'.dual /-
 theorem Valid'.dual : ∀ {t : Ordnode α} {o₁ o₂} (h : Valid' o₁ t o₂), @Valid' αᵒᵈ _ o₂ (dual t) o₁
   | nil, o₁, o₂, h => valid'_nil h.1.dual
   | node s l x r, o₁, o₂, ⟨⟨ol, Or⟩, ⟨rfl, sl, sr⟩, ⟨b, bl, br⟩⟩ =>
@@ -1066,86 +1342,124 @@ theorem Valid'.dual : ∀ {t : Ordnode α} {o₁ o₂} (h : Valid' o₁ t o₂),
     ⟨⟨or', ol'⟩, ⟨by simp [size_dual, add_comm], sr', sl'⟩,
       ⟨by rw [size_dual, size_dual] <;> exact b.symm, br', bl'⟩⟩
 #align ordnode.valid'.dual Ordnode.Valid'.dual
+-/
 
+#print Ordnode.Valid'.dual_iff /-
 theorem Valid'.dual_iff {t : Ordnode α} {o₁ o₂} : Valid' o₁ t o₂ ↔ @Valid' αᵒᵈ _ o₂ (dual t) o₁ :=
   ⟨Valid'.dual, fun h => by
     have := valid'.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this ⟩
 #align ordnode.valid'.dual_iff Ordnode.Valid'.dual_iff
+-/
 
+#print Ordnode.Valid.dual /-
 theorem Valid.dual {t : Ordnode α} : Valid t → @Valid αᵒᵈ _ (dual t) :=
   Valid'.dual
 #align ordnode.valid.dual Ordnode.Valid.dual
+-/
 
+#print Ordnode.Valid.dual_iff /-
 theorem Valid.dual_iff {t : Ordnode α} : Valid t ↔ @Valid αᵒᵈ _ (dual t) :=
   Valid'.dual_iff
 #align ordnode.valid.dual_iff Ordnode.Valid.dual_iff
+-/
 
+#print Ordnode.Valid'.left /-
 theorem Valid'.left {s l x r o₁ o₂} (H : Valid' o₁ (@node α s l x r) o₂) : Valid' o₁ l x :=
   ⟨H.1.1, H.2.2.1, H.3.2.1⟩
 #align ordnode.valid'.left Ordnode.Valid'.left
+-/
 
+#print Ordnode.Valid'.right /-
 theorem Valid'.right {s l x r o₁ o₂} (H : Valid' o₁ (@node α s l x r) o₂) : Valid' (↑x) r o₂ :=
   ⟨H.1.2, H.2.2.2, H.3.2.2⟩
 #align ordnode.valid'.right Ordnode.Valid'.right
+-/
 
+#print Ordnode.Valid.left /-
 theorem Valid.left {s l x r} (H : Valid (@node α s l x r)) : Valid l :=
   H.left.valid
 #align ordnode.valid.left Ordnode.Valid.left
+-/
 
+#print Ordnode.Valid.right /-
 theorem Valid.right {s l x r} (H : Valid (@node α s l x r)) : Valid r :=
   H.right.valid
 #align ordnode.valid.right Ordnode.Valid.right
+-/
 
+#print Ordnode.Valid.size_eq /-
 theorem Valid.size_eq {s l x r} (H : Valid (@node α s l x r)) :
     size (@node α s l x r) = size l + size r + 1 :=
   H.2.1
 #align ordnode.valid.size_eq Ordnode.Valid.size_eq
+-/
 
+#print Ordnode.Valid'.node' /-
 theorem Valid'.node' {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H : BalancedSz (size l) (size r)) : Valid' o₁ (@node' α l x r) o₂ :=
   hl.node hr H rfl
 #align ordnode.valid'.node' Ordnode.Valid'.node'
+-/
 
+#print Ordnode.valid'_singleton /-
 theorem valid'_singleton {x : α} {o₁ o₂} (h₁ : Bounded nil o₁ ↑x) (h₂ : Bounded nil (↑x) o₂) :
     Valid' o₁ (singleton x : Ordnode α) o₂ :=
   (valid'_nil h₁).node (valid'_nil h₂) (Or.inl zero_le_one) rfl
 #align ordnode.valid'_singleton Ordnode.valid'_singleton
+-/
 
+#print Ordnode.valid_singleton /-
 theorem valid_singleton {x : α} : Valid (singleton x : Ordnode α) :=
   valid'_singleton ⟨⟩ ⟨⟩
 #align ordnode.valid_singleton Ordnode.valid_singleton
+-/
 
+#print Ordnode.Valid'.node3L /-
 theorem Valid'.node3L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Valid' (↑x) m ↑y)
     (hr : Valid' (↑y) r o₂) (H1 : BalancedSz (size l) (size m))
     (H2 : BalancedSz (size l + size m + 1) (size r)) : Valid' o₁ (@node3L α l x m y r) o₂ :=
   (hl.node' hm H1).node' hr H2
 #align ordnode.valid'.node3_l Ordnode.Valid'.node3L
+-/
 
+#print Ordnode.Valid'.node3R /-
 theorem Valid'.node3R {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Valid' (↑x) m ↑y)
     (hr : Valid' (↑y) r o₂) (H1 : BalancedSz (size l) (size m + size r + 1))
     (H2 : BalancedSz (size m) (size r)) : Valid' o₁ (@node3R α l x m y r) o₂ :=
   hl.node' (hm.node' hr H2) H1
 #align ordnode.valid'.node3_r Ordnode.Valid'.node3R
+-/
 
-theorem Valid'.node4_l_lemma₁ {a b c d : ℕ} (lr₂ : 3 * (b + c + 1 + d) ≤ 16 * a + 9)
+#print Ordnode.Valid'.node4L_lemma₁ /-
+theorem Valid'.node4L_lemma₁ {a b c d : ℕ} (lr₂ : 3 * (b + c + 1 + d) ≤ 16 * a + 9)
     (mr₂ : b + c + 1 ≤ 3 * d) (mm₁ : b ≤ 3 * c) : b < 3 * a + 1 := by linarith
-#align ordnode.valid'.node4_l_lemma₁ Ordnode.Valid'.node4_l_lemma₁
+#align ordnode.valid'.node4_l_lemma₁ Ordnode.Valid'.node4L_lemma₁
+-/
 
-theorem Valid'.node4_l_lemma₂ {b c d : ℕ} (mr₂ : b + c + 1 ≤ 3 * d) : c ≤ 3 * d := by linarith
-#align ordnode.valid'.node4_l_lemma₂ Ordnode.Valid'.node4_l_lemma₂
+#print Ordnode.Valid'.node4L_lemma₂ /-
+theorem Valid'.node4L_lemma₂ {b c d : ℕ} (mr₂ : b + c + 1 ≤ 3 * d) : c ≤ 3 * d := by linarith
+#align ordnode.valid'.node4_l_lemma₂ Ordnode.Valid'.node4L_lemma₂
+-/
 
-theorem Valid'.node4_l_lemma₃ {b c d : ℕ} (mr₁ : 2 * d ≤ b + c + 1) (mm₁ : b ≤ 3 * c) : d ≤ 3 * c :=
+#print Ordnode.Valid'.node4L_lemma₃ /-
+theorem Valid'.node4L_lemma₃ {b c d : ℕ} (mr₁ : 2 * d ≤ b + c + 1) (mm₁ : b ≤ 3 * c) : d ≤ 3 * c :=
   by linarith
-#align ordnode.valid'.node4_l_lemma₃ Ordnode.Valid'.node4_l_lemma₃
+#align ordnode.valid'.node4_l_lemma₃ Ordnode.Valid'.node4L_lemma₃
+-/
 
-theorem Valid'.node4_l_lemma₄ {a b c d : ℕ} (lr₁ : 3 * a ≤ b + c + 1 + d) (mr₂ : b + c + 1 ≤ 3 * d)
+#print Ordnode.Valid'.node4L_lemma₄ /-
+theorem Valid'.node4L_lemma₄ {a b c d : ℕ} (lr₁ : 3 * a ≤ b + c + 1 + d) (mr₂ : b + c + 1 ≤ 3 * d)
     (mm₁ : b ≤ 3 * c) : a + b + 1 ≤ 3 * (c + d + 1) := by linarith
-#align ordnode.valid'.node4_l_lemma₄ Ordnode.Valid'.node4_l_lemma₄
+#align ordnode.valid'.node4_l_lemma₄ Ordnode.Valid'.node4L_lemma₄
+-/
 
-theorem Valid'.node4_l_lemma₅ {a b c d : ℕ} (lr₂ : 3 * (b + c + 1 + d) ≤ 16 * a + 9)
+#print Ordnode.Valid'.node4L_lemma₅ /-
+theorem Valid'.node4L_lemma₅ {a b c d : ℕ} (lr₂ : 3 * (b + c + 1 + d) ≤ 16 * a + 9)
     (mr₁ : 2 * d ≤ b + c + 1) (mm₂ : c ≤ 3 * b) : c + d + 1 ≤ 3 * (a + b + 1) := by linarith
-#align ordnode.valid'.node4_l_lemma₅ Ordnode.Valid'.node4_l_lemma₅
+#align ordnode.valid'.node4_l_lemma₅ Ordnode.Valid'.node4L_lemma₅
+-/
 
+#print Ordnode.Valid'.node4L /-
 theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Valid' (↑x) m ↑y)
     (hr : Valid' (↑y) r o₂) (Hm : 0 < size m)
     (H :
@@ -1205,23 +1519,32 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
     · exact valid'.node4_l_lemma₄ lr₁ mr₂ mm₁
     · exact valid'.node4_l_lemma₅ lr₂ mr₁ mm₂
 #align ordnode.valid'.node4_l Ordnode.Valid'.node4L
+-/
 
-theorem Valid'.rotate_l_lemma₁ {a b c : ℕ} (H2 : 3 * a ≤ b + c) (hb₂ : c ≤ 3 * b) : a ≤ 3 * b := by
+#print Ordnode.Valid'.rotateL_lemma₁ /-
+theorem Valid'.rotateL_lemma₁ {a b c : ℕ} (H2 : 3 * a ≤ b + c) (hb₂ : c ≤ 3 * b) : a ≤ 3 * b := by
   linarith
-#align ordnode.valid'.rotate_l_lemma₁ Ordnode.Valid'.rotate_l_lemma₁
+#align ordnode.valid'.rotate_l_lemma₁ Ordnode.Valid'.rotateL_lemma₁
+-/
 
-theorem Valid'.rotate_l_lemma₂ {a b c : ℕ} (H3 : 2 * (b + c) ≤ 9 * a + 3) (h : b < 2 * c) :
+#print Ordnode.Valid'.rotateL_lemma₂ /-
+theorem Valid'.rotateL_lemma₂ {a b c : ℕ} (H3 : 2 * (b + c) ≤ 9 * a + 3) (h : b < 2 * c) :
     b < 3 * a + 1 := by linarith
-#align ordnode.valid'.rotate_l_lemma₂ Ordnode.Valid'.rotate_l_lemma₂
-
-theorem Valid'.rotate_l_lemma₃ {a b c : ℕ} (H2 : 3 * a ≤ b + c) (h : b < 2 * c) : a + b < 3 * c :=
-  by linarith
-#align ordnode.valid'.rotate_l_lemma₃ Ordnode.Valid'.rotate_l_lemma₃
+#align ordnode.valid'.rotate_l_lemma₂ Ordnode.Valid'.rotateL_lemma₂
+-/
 
-theorem Valid'.rotate_l_lemma₄ {a b : ℕ} (H3 : 2 * b ≤ 9 * a + 3) : 3 * b ≤ 16 * a + 9 := by
+#print Ordnode.Valid'.rotateL_lemma₃ /-
+theorem Valid'.rotateL_lemma₃ {a b c : ℕ} (H2 : 3 * a ≤ b + c) (h : b < 2 * c) : a + b < 3 * c := by
   linarith
-#align ordnode.valid'.rotate_l_lemma₄ Ordnode.Valid'.rotate_l_lemma₄
+#align ordnode.valid'.rotate_l_lemma₃ Ordnode.Valid'.rotateL_lemma₃
+-/
+
+#print Ordnode.Valid'.rotateL_lemma₄ /-
+theorem Valid'.rotateL_lemma₄ {a b : ℕ} (H3 : 2 * b ≤ 9 * a + 3) : 3 * b ≤ 16 * a + 9 := by linarith
+#align ordnode.valid'.rotate_l_lemma₄ Ordnode.Valid'.rotateL_lemma₄
+-/
 
+#print Ordnode.Valid'.rotateL /-
 theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H1 : ¬size l + size r ≤ 1) (H2 : delta * size l < size r)
     (H3 : 2 * size r ≤ 9 * size l + 5 ∨ size r ≤ 3) : Valid' o₁ (@rotateL α l x r) o₂ :=
@@ -1284,7 +1607,9 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     exact
       Or.inr ⟨l0, not_lt.1 h, H2, valid'.rotate_l_lemma₄ (H3p l0), (hr.3.1.resolve_left (hlp l0)).1⟩
 #align ordnode.valid'.rotate_l Ordnode.Valid'.rotateL
+-/
 
+#print Ordnode.Valid'.rotateR /-
 theorem Valid'.rotateR {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H1 : ¬size l + size r ≤ 1) (H2 : delta * size r < size l)
     (H3 : 2 * size l ≤ 9 * size r + 5 ∨ size l ≤ 3) : Valid' o₁ (@rotateR α l x r) o₂ :=
@@ -1296,7 +1621,9 @@ theorem Valid'.rotateR {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
   · rwa [size_dual, size_dual]
   · rwa [size_dual, size_dual]
 #align ordnode.valid'.rotate_r Ordnode.Valid'.rotateR
+-/
 
+#print Ordnode.Valid'.balance'_aux /-
 theorem Valid'.balance'_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H₁ : 2 * @size α r ≤ 9 * size l + 5 ∨ size r ≤ 3)
     (H₂ : 2 * @size α l ≤ 9 * size r + 5 ∨ size l ≤ 3) : Valid' o₁ (@balance' α l x r) o₂ :=
@@ -1307,7 +1634,9 @@ theorem Valid'.balance'_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Va
   · exact hl.rotate_r hr h h_2 H₂
   · exact hl.node' hr (Or.inr ⟨not_lt.1 h_2, not_lt.1 h_1⟩)
 #align ordnode.valid'.balance'_aux Ordnode.Valid'.balance'_aux
+-/
 
+#print Ordnode.Valid'.balance'_lemma /-
 theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
     (H2 : Nat.dist (@size α l) l' ≤ 1 ∧ size r = r' ∨ Nat.dist (size r) r' ≤ 1 ∧ size l = l') :
     2 * @size α r ≤ 9 * size l + 5 ∨ size r ≤ 3 :=
@@ -1330,7 +1659,9 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
   · rw [Nat.mul_succ]
     exact le_trans (Nat.dist_tri_right' _ _) (add_le_add h₂ (le_trans hr (by decide)))
 #align ordnode.valid'.balance'_lemma Ordnode.Valid'.balance'_lemma
+-/
 
+#print Ordnode.Valid'.balance' /-
 theorem Valid'.balance' {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H :
       ∃ l' r',
@@ -1340,7 +1671,9 @@ theorem Valid'.balance' {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
   let ⟨l', r', H1, H2⟩ := H
   Valid'.balance'_aux hl hr (Valid'.balance'_lemma H1 H2) (Valid'.balance'_lemma H1.symm H2.symm)
 #align ordnode.valid'.balance' Ordnode.Valid'.balance'
+-/
 
+#print Ordnode.Valid'.balance /-
 theorem Valid'.balance {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H :
       ∃ l' r',
@@ -1349,7 +1682,9 @@ theorem Valid'.balance {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     Valid' o₁ (@balance α l x r) o₂ := by
   rw [balance_eq_balance' hl.3 hr.3 hl.2 hr.2] <;> exact hl.balance' hr H
 #align ordnode.valid'.balance Ordnode.Valid'.balance
+-/
 
+#print Ordnode.Valid'.balanceL_aux /-
 theorem Valid'.balanceL_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H₁ : size l = 0 → size r ≤ 1) (H₂ : 1 ≤ size l → 1 ≤ size r → size r ≤ delta * size l)
     (H₃ : 2 * @size α l ≤ 9 * size r + 5 ∨ size l ≤ 3) : Valid' o₁ (@balanceL α l x r) o₂ :=
@@ -1362,7 +1697,9 @@ theorem Valid'.balanceL_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Va
   · rw [l0]; exact le_trans (Nat.mul_le_mul_left _ (H₁ l0)) (by decide)
   replace H₂ : _ ≤ 3 * _ := H₂ l0 r0; linarith
 #align ordnode.valid'.balance_l_aux Ordnode.Valid'.balanceL_aux
+-/
 
+#print Ordnode.Valid'.balanceL /-
 theorem Valid'.balanceL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H :
       (∃ l', Raised l' (size l) ∧ BalancedSz l' (size r)) ∨
@@ -1375,7 +1712,9 @@ theorem Valid'.balanceL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
   · exact ⟨_, _, H, Or.inl ⟨e.dist_le', rfl⟩⟩
   · exact ⟨_, _, H, Or.inr ⟨e.dist_le, rfl⟩⟩
 #align ordnode.valid'.balance_l Ordnode.Valid'.balanceL
+-/
 
+#print Ordnode.Valid'.balanceR_aux /-
 theorem Valid'.balanceR_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H₁ : size r = 0 → size l ≤ 1) (H₂ : 1 ≤ size r → 1 ≤ size l → size l ≤ delta * size r)
     (H₃ : 2 * @size α r ≤ 9 * size l + 5 ∨ size r ≤ 3) : Valid' o₁ (@balanceR α l x r) o₂ :=
@@ -1385,7 +1724,9 @@ theorem Valid'.balanceR_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Va
   rw [size_dual, size_dual] at this 
   exact this H₁ H₂ H₃
 #align ordnode.valid'.balance_r_aux Ordnode.Valid'.balanceR_aux
+-/
 
+#print Ordnode.Valid'.balanceR /-
 theorem Valid'.balanceR {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid' (↑x) r o₂)
     (H :
       (∃ l', Raised (size l) l' ∧ BalancedSz l' (size r)) ∨
@@ -1393,7 +1734,9 @@ theorem Valid'.balanceR {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     Valid' o₁ (@balanceR α l x r) o₂ := by
   rw [valid'.dual_iff, dual_balance_r] <;> exact hr.dual.balance_l hl.dual (balance_sz_dual H)
 #align ordnode.valid'.balance_r Ordnode.Valid'.balanceR
+-/
 
+#print Ordnode.Valid'.eraseMax_aux /-
 theorem Valid'.eraseMax_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r) o₂) :
     Valid' o₁ (@eraseMax α (node' l x r)) ↑(findMax' x r) ∧
       size (node' l x r) = size (eraseMax (node' l x r)) + 1 :=
@@ -1407,7 +1750,9 @@ theorem Valid'.eraseMax_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r)
   rw [erase_max, size_balance_l H.3.2.1 h.3 H.2.2.1 h.2 (Or.inr ⟨_, Or.inr e, H.3.1⟩)]
   rw [size, e]; rfl
 #align ordnode.valid'.erase_max_aux Ordnode.Valid'.eraseMax_aux
+-/
 
+#print Ordnode.Valid'.eraseMin_aux /-
 theorem Valid'.eraseMin_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r) o₂) :
     Valid' (↑(findMin' l x)) (@eraseMin α (node' l x r)) o₂ ∧
       size (node' l x r) = size (eraseMin (node' l x r)) + 1 :=
@@ -1416,16 +1761,22 @@ theorem Valid'.eraseMin_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r)
     rwa [← dual_node', size_dual, ← dual_erase_min, size_dual, ← valid'.dual_iff, find_max'_dual] at
       this 
 #align ordnode.valid'.erase_min_aux Ordnode.Valid'.eraseMin_aux
+-/
 
+#print Ordnode.eraseMin.valid /-
 theorem eraseMin.valid : ∀ {t} (h : @Valid α _ t), Valid (eraseMin t)
   | nil, _ => valid_nil
   | node _ l x r, h => by rw [h.2.eq_node'] <;> exact h.erase_min_aux.1.valid
 #align ordnode.erase_min.valid Ordnode.eraseMin.valid
+-/
 
+#print Ordnode.eraseMax.valid /-
 theorem eraseMax.valid {t} (h : @Valid α _ t) : Valid (eraseMax t) := by
   rw [valid.dual_iff, dual_erase_max] <;> exact erase_min.valid h.dual
 #align ordnode.erase_max.valid Ordnode.eraseMax.valid
+-/
 
+#print Ordnode.Valid'.glue_aux /-
 theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o₁ r o₂)
     (sep : l.all fun x => r.all fun y => x < y) (bal : BalancedSz (size l) (size r)) :
     Valid' o₁ (@glue α l r) o₂ ∧ size (glue l r) = size l + size r :=
@@ -1458,17 +1809,23 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
     · refine' Or.inr ⟨_, Or.inr e, _⟩
       rwa [hr.2.eq_node'] at bal 
 #align ordnode.valid'.glue_aux Ordnode.Valid'.glue_aux
+-/
 
+#print Ordnode.Valid'.glue /-
 theorem Valid'.glue {l x r o₁ o₂} (hl : Valid' o₁ l ↑(x : α)) (hr : Valid' (↑x) r o₂) :
     BalancedSz (size l) (size r) →
       Valid' o₁ (@glue α l r) o₂ ∧ size (@glue α l r) = size l + size r :=
   Valid'.glue_aux (hl.trans_right hr.1) (hr.trans_left hl.1) (hl.1.to_sep hr.1)
 #align ordnode.valid'.glue Ordnode.Valid'.glue
+-/
 
+#print Ordnode.Valid'.merge_lemma /-
 theorem Valid'.merge_lemma {a b c : ℕ} (h₁ : 3 * a < b + c + 1) (h₂ : b ≤ 3 * c) :
     2 * (a + b) ≤ 9 * c + 5 := by linarith
 #align ordnode.valid'.merge_lemma Ordnode.Valid'.merge_lemma
+-/
 
+#print Ordnode.Valid'.merge_aux₁ /-
 theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
     (hl : Valid' o₁ (@node α ls ll lx lr) o₂) (hr : Valid' o₁ (node rs rl rx rr) o₂)
     (h : delta * ls < rs) (v : Valid' o₁ t ↑rx) (e : size t = ls + size rl) :
@@ -1486,7 +1843,9 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
   · rw [e, add_right_comm]; rintro ⟨⟩
   · intro _ h₁; rw [e]; unfold delta at hr₂ ⊢; linarith
 #align ordnode.valid'.merge_aux₁ Ordnode.Valid'.merge_aux₁
+-/
 
+#print Ordnode.Valid'.merge_aux /-
 theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o₁ r o₂)
     (sep : l.all fun x => r.all fun y => x < y) :
     Valid' o₁ (@merge α l r) o₂ ∧ size (merge l r) = size l + size r :=
@@ -1508,12 +1867,16 @@ theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid'
     exact this e
   · refine' valid'.glue_aux hl hr sep (Or.inr ⟨not_lt.1 h_1, not_lt.1 h⟩)
 #align ordnode.valid'.merge_aux Ordnode.Valid'.merge_aux
+-/
 
+#print Ordnode.Valid.merge /-
 theorem Valid.merge {l r} (hl : Valid l) (hr : Valid r)
     (sep : l.all fun x => r.all fun y => x < y) : Valid (@merge α l r) :=
   (Valid'.merge_aux hl hr sep).1
 #align ordnode.valid.merge Ordnode.Valid.merge
+-/
 
+#print Ordnode.insertWith.valid_aux /-
 theorem insertWith.valid_aux [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (f : α → α) (x : α)
     (hf : ∀ y, x ≤ y ∧ y ≤ x → x ≤ f y ∧ f y ≤ x) :
     ∀ {t o₁ o₂},
@@ -1544,12 +1907,16 @@ theorem insertWith.valid_aux [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤
         refine' (e.add_left _).add_right _
       · exact Or.inr ⟨_, e, h.3.1⟩
 #align ordnode.insert_with.valid_aux Ordnode.insertWith.valid_aux
+-/
 
+#print Ordnode.insertWith.valid /-
 theorem insertWith.valid [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (f : α → α) (x : α)
     (hf : ∀ y, x ≤ y ∧ y ≤ x → x ≤ f y ∧ f y ≤ x) {t} (h : Valid t) : Valid (insertWith f x t) :=
   (insertWith.valid_aux _ _ hf h ⟨⟩ ⟨⟩).1
 #align ordnode.insert_with.valid Ordnode.insertWith.valid
+-/
 
+#print Ordnode.insert_eq_insertWith /-
 theorem insert_eq_insertWith [@DecidableRel α (· ≤ ·)] (x : α) :
     ∀ t, Ordnode.insert x t = insertWith (fun _ => x) x t
   | nil => rfl
@@ -1557,12 +1924,16 @@ theorem insert_eq_insertWith [@DecidableRel α (· ≤ ·)] (x : α) :
     unfold Ordnode.insert insert_with <;> cases cmpLE x y <;> unfold Ordnode.insert insert_with <;>
       simp [insert_eq_insert_with]
 #align ordnode.insert_eq_insert_with Ordnode.insert_eq_insertWith
+-/
 
+#print Ordnode.insert.valid /-
 theorem insert.valid [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (x : α) {t} (h : Valid t) :
     Valid (Ordnode.insert x t) := by
   rw [insert_eq_insert_with] <;> exact insert_with.valid _ _ (fun _ _ => ⟨le_rfl, le_rfl⟩) h
 #align ordnode.insert.valid Ordnode.insert.valid
+-/
 
+#print Ordnode.insert'_eq_insertWith /-
 theorem insert'_eq_insertWith [@DecidableRel α (· ≤ ·)] (x : α) :
     ∀ t, insert' x t = insertWith id x t
   | nil => rfl
@@ -1570,12 +1941,16 @@ theorem insert'_eq_insertWith [@DecidableRel α (· ≤ ·)] (x : α) :
     unfold insert' insert_with <;> cases cmpLE x y <;> unfold insert' insert_with <;>
       simp [insert'_eq_insert_with]
 #align ordnode.insert'_eq_insert_with Ordnode.insert'_eq_insertWith
+-/
 
+#print Ordnode.insert'.valid /-
 theorem insert'.valid [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (x : α) {t} (h : Valid t) :
     Valid (insert' x t) := by
   rw [insert'_eq_insert_with] <;> exact insert_with.valid _ _ (fun _ => id) h
 #align ordnode.insert'.valid Ordnode.insert'.valid
+-/
 
+#print Ordnode.Valid'.map_aux /-
 theorem Valid'.map_aux {β} [Preorder β] {f : α → β} (f_strict_mono : StrictMono f) {t a₁ a₂}
     (h : Valid' a₁ t a₂) :
     Valid' (Option.map f a₁) (map f t) (Option.map f a₂) ∧ (map f t).size = t.size :=
@@ -1603,12 +1978,16 @@ theorem Valid'.map_aux {β} [Preorder β] {f : α → β} (f_strict_mono : Stric
       · exact t_l_valid.bal
       · exact t_r_valid.bal
 #align ordnode.valid'.map_aux Ordnode.Valid'.map_aux
+-/
 
+#print Ordnode.map.valid /-
 theorem map.valid {β} [Preorder β] {f : α → β} (f_strict_mono : StrictMono f) {t} (h : Valid t) :
     Valid (map f t) :=
   (Valid'.map_aux f_strict_mono h).1
 #align ordnode.map.valid Ordnode.map.valid
+-/
 
+#print Ordnode.Valid'.erase_aux /-
 theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (h : Valid' a₁ t a₂) :
     Valid' a₁ (erase x t) a₂ ∧ Raised (erase x t).size t.size :=
   by
@@ -1642,11 +2021,15 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
         exact t_r_size
       · right; exists t_r.size; exact And.intro t_r_size h.bal.1
 #align ordnode.valid'.erase_aux Ordnode.Valid'.erase_aux
+-/
 
+#print Ordnode.erase.valid /-
 theorem erase.valid [@DecidableRel α (· ≤ ·)] (x : α) {t} (h : Valid t) : Valid (erase x t) :=
   (Valid'.erase_aux x h).1
 #align ordnode.erase.valid Ordnode.erase.valid
+-/
 
+#print Ordnode.size_erase_of_mem /-
 theorem size_erase_of_mem [@DecidableRel α (· ≤ ·)] {x : α} {t a₁ a₂} (h : Valid' a₁ t a₂)
     (h_mem : x ∈ t) : size (erase x t) = size t - 1 :=
   by
@@ -1680,11 +2063,13 @@ theorem size_erase_of_mem [@DecidableRel α (· ≤ ·)] {x : α} {t a₁ a₂}
       cases' t_r.size with t_r_size; · cases h_pos_t_r_size
       simp [Nat.succ_add, Nat.add_succ]
 #align ordnode.size_erase_of_mem Ordnode.size_erase_of_mem
+-/
 
 end
 
 end Ordnode
 
+#print Ordset /-
 /-- An `ordset α` is a finite set of values, represented as a tree. The operations on this type
 maintain that the tree is balanced and correctly stores subtree sizes at each level. The
 correctness property of the tree is baked into the type, so all operations on this type are correct
@@ -1692,6 +2077,7 @@ by construction. -/
 def Ordset (α : Type _) [Preorder α] :=
   { t : Ordnode α // t.valid }
 #align ordset Ordset
+-/
 
 namespace Ordset
 
@@ -1699,20 +2085,26 @@ open Ordnode
 
 variable [Preorder α]
 
+#print Ordset.nil /-
 /-- O(1). The empty set. -/
 def nil : Ordset α :=
   ⟨nil, ⟨⟩, ⟨⟩, ⟨⟩⟩
 #align ordset.nil Ordset.nil
+-/
 
+#print Ordset.size /-
 /-- O(1). Get the size of the set. -/
 def size (s : Ordset α) : ℕ :=
   s.1.size
 #align ordset.size Ordset.size
+-/
 
+#print Ordset.singleton /-
 /-- O(1). Construct a singleton set containing value `a`. -/
 protected def singleton (a : α) : Ordset α :=
   ⟨singleton a, valid_singleton⟩
 #align ordset.singleton Ordset.singleton
+-/
 
 instance : EmptyCollection (Ordset α) :=
   ⟨nil⟩
@@ -1723,74 +2115,94 @@ instance : Inhabited (Ordset α) :=
 instance : Singleton α (Ordset α) :=
   ⟨Ordset.singleton⟩
 
+#print Ordset.Empty /-
 /-- O(1). Is the set empty? -/
 def Empty (s : Ordset α) : Prop :=
   s = ∅
 #align ordset.empty Ordset.Empty
+-/
 
+#print Ordset.empty_iff /-
 theorem empty_iff {s : Ordset α} : s = ∅ ↔ s.1.Empty :=
   ⟨fun h => by cases h <;> exact rfl, fun h => by cases s <;> cases s_val <;> [exact rfl; cases h]⟩
 #align ordset.empty_iff Ordset.empty_iff
+-/
 
 instance : DecidablePred (@Empty α _) := fun s => decidable_of_iff' _ empty_iff
 
+#print Ordset.insert /-
 /-- O(log n). Insert an element into the set, preserving balance and the BST property.
   If an equivalent element is already in the set, this replaces it. -/
 protected def insert [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (x : α) (s : Ordset α) :
     Ordset α :=
   ⟨Ordnode.insert x s.1, insert.valid _ s.2⟩
 #align ordset.insert Ordset.insert
+-/
 
 instance [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] : Insert α (Ordset α) :=
   ⟨Ordset.insert⟩
 
+#print Ordset.insert' /-
 /-- O(log n). Insert an element into the set, preserving balance and the BST property.
   If an equivalent element is already in the set, the set is returned as is. -/
 def insert' [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (x : α) (s : Ordset α) : Ordset α :=
   ⟨insert' x s.1, insert'.valid _ s.2⟩
 #align ordset.insert' Ordset.insert'
+-/
 
 section
 
 variable [@DecidableRel α (· ≤ ·)]
 
+#print Ordset.mem /-
 /-- O(log n). Does the set contain the element `x`? That is,
   is there an element that is equivalent to `x` in the order? -/
 def mem (x : α) (s : Ordset α) : Bool :=
   x ∈ s.val
 #align ordset.mem Ordset.mem
+-/
 
+#print Ordset.find /-
 /-- O(log n). Retrieve an element in the set that is equivalent to `x` in the order,
   if it exists. -/
 def find (x : α) (s : Ordset α) : Option α :=
   Ordnode.find x s.val
 #align ordset.find Ordset.find
+-/
 
 instance : Membership α (Ordset α) :=
   ⟨fun x s => mem x s⟩
 
+#print Ordset.mem.decidable /-
 instance mem.decidable (x : α) (s : Ordset α) : Decidable (x ∈ s) :=
   Bool.decidableEq _ _
 #align ordset.mem.decidable Ordset.mem.decidable
+-/
 
+#print Ordset.pos_size_of_mem /-
 theorem pos_size_of_mem {x : α} {t : Ordset α} (h_mem : x ∈ t) : 0 < size t :=
   by
   simp [Membership.Mem, mem] at h_mem 
   apply Ordnode.pos_size_of_mem t.property.sz h_mem
 #align ordset.pos_size_of_mem Ordset.pos_size_of_mem
+-/
 
 end
 
+#print Ordset.erase /-
 /-- O(log n). Remove an element from the set equivalent to `x`. Does nothing if there
 is no such element. -/
 def erase [@DecidableRel α (· ≤ ·)] (x : α) (s : Ordset α) : Ordset α :=
   ⟨Ordnode.erase x s.val, Ordnode.erase.valid x s.property⟩
 #align ordset.erase Ordset.erase
+-/
 
+#print Ordset.map /-
 /-- O(n). Map a function across a tree, without changing the structure. -/
 def map {β} [Preorder β] (f : α → β) (f_strict_mono : StrictMono f) (s : Ordset α) : Ordset β :=
   ⟨Ordnode.map f s.val, Ordnode.map.valid f_strict_mono s.property⟩
 #align ordset.map Ordset.map
+-/
 
 end Ordset

47b51515

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -138,7 +138,7 @@ theorem size_eq_realSize : ∀ {t : Ordnode α}, Sized t → size t = realSize t
 
 @[simp]
 theorem Sized.size_eq_zero {t : Ordnode α} (ht : Sized t) : size t = 0 ↔ t = nil := by
-  cases t <;> [simp;simp [ht.1]]
+  cases t <;> [simp; simp [ht.1]]
 #align ordnode.sized.size_eq_zero Ordnode.Sized.size_eq_zero
 
 theorem Sized.pos {s l x r} (h : Sized (@node α s l x r)) : 0 < s := by
@@ -354,7 +354,7 @@ theorem Sized.node3R {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r
 
 theorem Sized.node4L {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r) :
     Sized (node4L l x m y r) := by
-  cases m <;> [exact (hl.node' hm).node' hr;exact (hl.node' hm.2.1).node' (hm.2.2.node' hr)]
+  cases m <;> [exact (hl.node' hm).node' hr; exact (hl.node' hm.2.1).node' (hm.2.2.node' hr)]
 #align ordnode.sized.node4_l Ordnode.Sized.node4L
 
 theorem node3L_size {l x m y r} : size (@node3L α l x m y r) = size l + size m + size r + 2 := by
@@ -367,8 +367,8 @@ theorem node3R_size {l x m y r} : size (@node3R α l x m y r) = size l + size m
 
 theorem node4L_size {l x m y r} (hm : Sized m) :
     size (@node4L α l x m y r) = size l + size m + size r + 2 := by
-  cases m <;> simp [node4_l, node3_l, node', add_comm, add_left_comm] <;>
-        [skip;simp [size, hm.1]] <;>
+  cases m <;> simp [node4_l, node3_l, node', add_comm, add_left_comm] <;> [skip;
+        simp [size, hm.1]] <;>
       rw [← add_assoc, ← bit0] <;>
     simp [add_comm, add_left_comm]
 #align ordnode.node4_l_size Ordnode.node4L_size
@@ -653,14 +653,14 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
   cases' l with ls ll lx lr
   · cases' r with rs rl rx rr
     · rfl
-    · rw [sr.eq_node'] at hr⊢
+    · rw [sr.eq_node'] at hr ⊢
       cases' rl with rls rll rlx rlr <;> cases' rr with rrs rrl rrx rrr <;>
         dsimp [balance, balance']
       · rfl
       · have : size rrl = 0 ∧ size rrr = 0 :=
           by
           have := balanced_sz_zero.1 hr.1.symm
-          rwa [size, sr.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sr.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
         cases sr.2.2.2.1.size_eq_zero.1 this.1
         cases sr.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : rrs = 1 := sr.2.2.1
@@ -669,7 +669,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · have : size rll = 0 ∧ size rlr = 0 :=
           by
           have := balanced_sz_zero.1 hr.1
-          rwa [size, sr.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sr.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
         cases sr.2.1.2.1.size_eq_zero.1 this.1
         cases sr.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : rls = 1 := sr.2.1.1
@@ -682,14 +682,14 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · exact by decide
         · exact not_le_of_gt (Nat.succ_lt_succ (add_pos sr.2.1.Pos sr.2.2.Pos))
   · cases' r with rs rl rx rr
-    · rw [sl.eq_node'] at hl⊢
+    · rw [sl.eq_node'] at hl ⊢
       cases' ll with lls lll llx llr <;> cases' lr with lrs lrl lrx lrr <;>
         dsimp [balance, balance']
       · rfl
       · have : size lrl = 0 ∧ size lrr = 0 :=
           by
           have := balanced_sz_zero.1 hl.1.symm
-          rwa [size, sl.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sl.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
         cases sl.2.2.2.1.size_eq_zero.1 this.1
         cases sl.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : lrs = 1 := sl.2.2.1
@@ -698,7 +698,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · have : size lll = 0 ∧ size llr = 0 :=
           by
           have := balanced_sz_zero.1 hl.1
-          rwa [size, sl.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sl.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
         cases sl.2.1.2.1.size_eq_zero.1 this.1
         cases sl.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : lls = 1 := sl.2.1.1
@@ -717,9 +717,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · have rd : delta ≤ size rl + size rr :=
             by
             have := lt_of_le_of_lt (Nat.mul_le_mul_left _ sl.pos) h
-            rwa [sr.1, Nat.lt_succ_iff] at this
+            rwa [sr.1, Nat.lt_succ_iff] at this 
           cases' rl with rls rll rlx rlr
-          · rw [size, zero_add] at rd
+          · rw [size, zero_add] at rd 
             exact absurd (le_trans rd (balanced_sz_zero.1 hr.1.symm)) (by decide)
           cases' rr with rrs rrl rrx rrr
           · exact absurd (le_trans rd (balanced_sz_zero.1 hr.1)) (by decide)
@@ -729,9 +729,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · have ld : delta ≤ size ll + size lr :=
             by
             have := lt_of_le_of_lt (Nat.mul_le_mul_left _ sr.pos) h_1
-            rwa [sl.1, Nat.lt_succ_iff] at this
+            rwa [sl.1, Nat.lt_succ_iff] at this 
           cases' ll with lls lll llx llr
-          · rw [size, zero_add] at ld
+          · rw [size, zero_add] at ld 
             exact absurd (le_trans ld (balanced_sz_zero.1 hl.1.symm)) (by decide)
           cases' lr with lrs lrl lrx lrr
           · exact absurd (le_trans ld (balanced_sz_zero.1 hl.1)) (by decide)
@@ -750,7 +750,7 @@ theorem balanceL_eq_balance {l x r} (sl : Sized l) (sr : Sized r) (H1 : size l =
   · cases' l with ls ll lx lr
     · have : size rl = 0 ∧ size rr = 0 := by
         have := H1 rfl
-        rwa [size, sr.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+        rwa [size, sr.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this 
       cases sr.2.1.size_eq_zero.1 this.1
       cases sr.2.2.size_eq_zero.1 this.2
       rw [sr.eq_node']; rfl
@@ -796,7 +796,7 @@ theorem Raised.add_right (k) {n m} (H : Raised n m) : Raised (n + k) (m + k) :=
 theorem Raised.right {l x₁ x₂ r₁ r₂} (H : Raised (size r₁) (size r₂)) :
     Raised (size (@node' α l x₁ r₁)) (size (@node' α l x₂ r₂)) :=
   by
-  dsimp [node', size]; generalize size r₂ = m at H⊢
+  dsimp [node', size]; generalize size r₂ = m at H ⊢
   rcases H with (rfl | rfl)
   · exact Or.inl rfl
   · exact Or.inr rfl
@@ -810,7 +810,7 @@ theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     @balanceL α l x r = balance' l x r :=
   by
   rw [← balance_eq_balance' hl hr sl sr, balance_l_eq_balance sl sr]
-  · intro l0; rw [l0] at H
+  · intro l0; rw [l0] at H 
     rcases H with (⟨_, ⟨⟨⟩⟩ | ⟨⟨⟩⟩, H⟩ | ⟨r', e, H⟩)
     · exact balanced_sz_zero.1 H.symm
     exact le_trans (raised_iff.1 e).1 (balanced_sz_zero.1 H.symm)
@@ -903,7 +903,7 @@ theorem Bounded.dual :
 theorem Bounded.dual_iff {t : Ordnode α} {o₁ o₂} :
     Bounded t o₁ o₂ ↔ @Bounded αᵒᵈ _ (dual t) o₂ o₁ :=
   ⟨Bounded.dual, fun h => by
-    have := bounded.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this⟩
+    have := bounded.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this ⟩
 #align ordnode.bounded.dual_iff Ordnode.Bounded.dual_iff
 
 theorem Bounded.weak_left : ∀ {t : Ordnode α} {o₁ o₂}, Bounded t o₁ o₂ → Bounded t ⊥ o₂
@@ -1069,7 +1069,7 @@ theorem Valid'.dual : ∀ {t : Ordnode α} {o₁ o₂} (h : Valid' o₁ t o₂),
 
 theorem Valid'.dual_iff {t : Ordnode α} {o₁ o₂} : Valid' o₁ t o₂ ↔ @Valid' αᵒᵈ _ o₂ (dual t) o₁ :=
   ⟨Valid'.dual, fun h => by
-    have := valid'.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this⟩
+    have := valid'.dual h <;> rwa [dual_dual, OrderDual.Preorder.dual_dual] at this ⟩
 #align ordnode.valid'.dual_iff Ordnode.Valid'.dual_iff
 
 theorem Valid.dual {t : Ordnode α} : Valid t → @Valid αᵒᵈ _ (dual t) :=
@@ -1162,16 +1162,16 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
       balanced_sz (size mr) (size r) ∧ balanced_sz (size l + size ml + 1) (size mr + size r + 1)
   exact valid'.node' (hl.node' hm.left this.1) (hm.right.node' hr this.2.1) this.2.2
   rcases H with (⟨l0, m1, r0⟩ | ⟨l0, mr₁, lr₁, lr₂, mr₂⟩)
-  · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1
+  · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1 
     rw [l0, m1.1, m1.2]; rcases size r with (_ | _ | _) <;> exact by decide
   · cases' Nat.eq_zero_or_pos (size r) with r0 r0
-    · rw [r0] at mr₂; cases not_le_of_lt Hm mr₂
-    rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂
+    · rw [r0] at mr₂ ; cases not_le_of_lt Hm mr₂
+    rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂ 
     by_cases mm : size ml + size mr ≤ 1
     · have r1 :=
         le_antisymm
           ((mul_le_mul_left (by decide)).1 (le_trans mr₁ (Nat.succ_le_succ mm) : _ ≤ ratio * 1)) r0
-      rw [r1, add_assoc] at lr₁
+      rw [r1, add_assoc] at lr₁ 
       have l1 :=
         le_antisymm
           ((mul_le_mul_left (by decide)).1 (le_trans lr₁ (add_le_add_right mm 2) : _ ≤ delta * 1))
@@ -1179,20 +1179,20 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
       rw [l1, r1]
       cases size ml <;> cases size mr
       · exact by decide
-      · rw [zero_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
+      · rw [zero_add] at mm ; rcases mm with (_ | ⟨⟨⟩⟩)
         exact by decide
       · rcases mm with (_ | ⟨⟨⟩⟩); exact by decide
-      · rw [Nat.succ_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
+      · rw [Nat.succ_add] at mm ; rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
     cases' Nat.eq_zero_or_pos (size ml) with ml0 ml0
-    · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂
-      rw [ml0, mm₂] at mm; cases mm (by decide)
+    · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂ 
+      rw [ml0, mm₂] at mm ; cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 :=
       by
       have := Nat.mul_le_mul_left _ lr₁
-      rw [mul_left_comm, mul_add] at this
+      rw [mul_left_comm, mul_add] at this 
       have := le_trans this (add_le_add_left mr₁ _)
-      rw [← Nat.succ_mul] at this
+      rw [← Nat.succ_mul] at this 
       exact (mul_le_mul_left (by decide)).1 this
     refine' ⟨Or.inr ⟨_, _⟩, Or.inr ⟨_, _⟩, Or.inr ⟨_, _⟩⟩
     · refine' (mul_le_mul_left (by decide)).1 (le_trans this _)
@@ -1227,18 +1227,18 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     (H3 : 2 * size r ≤ 9 * size l + 5 ∨ size r ≤ 3) : Valid' o₁ (@rotateL α l x r) o₂ :=
   by
   cases' r with rs rl rx rr; · cases H2
-  rw [hr.2.size_eq, Nat.lt_succ_iff] at H2
-  rw [hr.2.size_eq] at H3
+  rw [hr.2.size_eq, Nat.lt_succ_iff] at H2 
+  rw [hr.2.size_eq] at H3 
   replace H3 : 2 * (size rl + size rr) ≤ 9 * size l + 3 ∨ size rl + size rr ≤ 2 :=
     H3.imp (@Nat.le_of_add_le_add_right 2 _ _) Nat.le_of_succ_le_succ
   have H3_0 : size l = 0 → size rl + size rr ≤ 2 :=
     by
-    intro l0; rw [l0] at H3
+    intro l0; rw [l0] at H3 
     exact
       (or_iff_right_of_imp fun h => (mul_le_mul_left (by decide)).1 (le_trans h (by decide))).1 H3
   have H3p : size l > 0 → 2 * (size rl + size rr) ≤ 9 * size l + 3 := fun l0 : 1 ≤ size l =>
     (or_iff_left_of_imp <| by intro <;> linarith).1 H3
-  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros ; linarith
+  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros; linarith
   have hlp : size l > 0 → ¬size rl + size rr ≤ 1 := fun l0 hb =>
     absurd (le_trans (le_trans (Nat.mul_le_mul_left _ l0) H2) hb) (by decide)
   rw [rotate_l]; split_ifs
@@ -1250,11 +1250,11 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     · rw [l0]; replace H3 := H3_0 l0
       have := hr.3.1
       cases' Nat.eq_zero_or_pos (size rl) with rl0 rl0
-      · rw [rl0] at this⊢
+      · rw [rl0] at this ⊢
         rw [le_antisymm (balanced_sz_zero.1 this.symm) rr0]
         exact by decide
       have rr1 : size rr = 1 := le_antisymm (ablem rl0 H3) rr0
-      rw [add_comm] at H3
+      rw [add_comm] at H3 
       rw [rr1, show size rl = 1 from le_antisymm (ablem rr0 H3) rl0]
       exact by decide
     replace H3 := H3p l0
@@ -1268,17 +1268,17 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
         le_trans hb₂
           (Nat.mul_le_mul_left _ <| le_trans (Nat.le_add_left _ _) (Nat.le_add_right _ _))
   · cases' Nat.eq_zero_or_pos (size rl) with rl0 rl0
-    · rw [rl0, not_lt, le_zero_iff, Nat.mul_eq_zero] at h
+    · rw [rl0, not_lt, le_zero_iff, Nat.mul_eq_zero] at h 
       replace h := h.resolve_left (by decide)
-      rw [rl0, h, le_zero_iff, Nat.mul_eq_zero] at H2
-      rw [hr.2.size_eq, rl0, h, H2.resolve_left (by decide)] at H1
+      rw [rl0, h, le_zero_iff, Nat.mul_eq_zero] at H2 
+      rw [hr.2.size_eq, rl0, h, H2.resolve_left (by decide)] at H1 
       cases H1 (by decide)
     refine' hl.node4_l hr.left hr.right rl0 _
     cases' Nat.eq_zero_or_pos (size l) with l0 l0
     · replace H3 := H3_0 l0
       cases' Nat.eq_zero_or_pos (size rr) with rr0 rr0
       · have := hr.3.1
-        rw [rr0] at this
+        rw [rr0] at this 
         exact Or.inl ⟨l0, le_antisymm (balanced_sz_zero.1 this) rl0, rr0.symm ▸ zero_le_one⟩
       exact Or.inl ⟨l0, le_antisymm (ablem rr0 <| by rwa [add_comm]) rl0, ablem rl0 H3⟩
     exact
@@ -1315,8 +1315,8 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
   suffices @size α r ≤ 3 * (size l + 1)
     by
     cases' Nat.eq_zero_or_pos (size l) with l0 l0
-    · apply Or.inr; rwa [l0] at this
-    change 1 ≤ _ at l0; apply Or.inl; linarith
+    · apply Or.inr; rwa [l0] at this 
+    change 1 ≤ _ at l0 ; apply Or.inl; linarith
   rcases H2 with (⟨hl, rfl⟩ | ⟨hr, rfl⟩) <;> rcases H1 with (h | ⟨h₁, h₂⟩)
   · exact le_trans (Nat.le_add_left _ _) (le_trans h (Nat.le_add_left _ _))
   ·
@@ -1382,7 +1382,7 @@ theorem Valid'.balanceR_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Va
   by
   rw [valid'.dual_iff, dual_balance_r]
   have := hr.dual.balance_l_aux hl.dual
-  rw [size_dual, size_dual] at this
+  rw [size_dual, size_dual] at this 
   exact this H₁ H₂ H₃
 #align ordnode.valid'.balance_r_aux Ordnode.Valid'.balanceR_aux
 
@@ -1398,10 +1398,10 @@ theorem Valid'.eraseMax_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r)
     Valid' o₁ (@eraseMax α (node' l x r)) ↑(findMax' x r) ∧
       size (node' l x r) = size (eraseMax (node' l x r)) + 1 :=
   by
-  have := H.2.eq_node'; rw [this] at H; clear this
+  have := H.2.eq_node'; rw [this] at H ; clear this
   induction' r with rs rl rx rr IHrl IHrr generalizing l x o₁
   · exact ⟨H.left, rfl⟩
-  have := H.2.2.2.eq_node'; rw [this] at H⊢
+  have := H.2.2.2.eq_node'; rw [this] at H ⊢
   rcases IHrr H.right with ⟨h, e⟩
   refine' ⟨valid'.balance_l H.left h (Or.inr ⟨_, Or.inr e, H.3.1⟩), _⟩
   rw [erase_max, size_balance_l H.3.2.1 h.3 H.2.2.1 h.2 (Or.inr ⟨_, Or.inr e, H.3.1⟩)]
@@ -1414,7 +1414,7 @@ theorem Valid'.eraseMin_aux {s l x r o₁ o₂} (H : Valid' o₁ (node s l x r)
   by
   have := H.dual.erase_max_aux <;>
     rwa [← dual_node', size_dual, ← dual_erase_min, size_dual, ← valid'.dual_iff, find_max'_dual] at
-      this
+      this 
 #align ordnode.valid'.erase_min_aux Ordnode.Valid'.eraseMin_aux
 
 theorem eraseMin.valid : ∀ {t} (h : @Valid α _ t), Valid (eraseMin t)
@@ -1442,7 +1442,7 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
     · exact @find_max'_all _ (fun a => all (· > a) (node rs rl rx rr)) lx lr sep.2.1 sep.2.2
     · rw [size_balance_r v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
     · refine' Or.inl ⟨_, Or.inr e, _⟩
-      rwa [hl.2.eq_node'] at bal
+      rwa [hl.2.eq_node'] at bal 
   · rw [split_min_eq, glue]
     cases' valid'.erase_min_aux hr with v e
     suffices H
@@ -1456,7 +1456,7 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
           (sep.imp fun y hy => hy.2.1)
     · rw [size_balance_l hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
     · refine' Or.inr ⟨_, Or.inr e, _⟩
-      rwa [hr.2.eq_node'] at bal
+      rwa [hr.2.eq_node'] at bal 
 #align ordnode.valid'.glue_aux Ordnode.Valid'.glue_aux
 
 theorem Valid'.glue {l x r o₁ o₂} (hl : Valid' o₁ l ↑(x : α)) (hr : Valid' (↑x) r o₂) :
@@ -1474,8 +1474,8 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
     (h : delta * ls < rs) (v : Valid' o₁ t ↑rx) (e : size t = ls + size rl) :
     Valid' o₁ (balanceL t rx rr) o₂ ∧ size (balanceL t rx rr) = ls + rs :=
   by
-  rw [hl.2.1] at e
-  rw [hl.2.1, hr.2.1, delta] at h
+  rw [hl.2.1] at e 
+  rw [hl.2.1, hr.2.1, delta] at h 
   rcases hr.3.1 with (H | ⟨hr₁, hr₂⟩); · linarith
   suffices H₂; suffices H₁
   refine' ⟨valid'.balance_l_aux v hr.right H₁ H₂ _, _⟩
@@ -1484,7 +1484,7 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
       size_balance' v.2 hr.2.2.2, e, hl.2.1, hr.2.1]
     simp [add_comm, add_left_comm]
   · rw [e, add_right_comm]; rintro ⟨⟩
-  · intro _ h₁; rw [e]; unfold delta at hr₂⊢; linarith
+  · intro _ h₁; rw [e]; unfold delta at hr₂ ⊢; linarith
 #align ordnode.valid'.merge_aux₁ Ordnode.Valid'.merge_aux₁
 
 theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o₁ r o₂)
@@ -1504,7 +1504,7 @@ theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid'
   · cases' IHlr hl.right (hr.of_gt hl.1.2.to_nil sep.2.1) sep.2.2 with v e
     have := valid'.merge_aux₁ hr.dual hl.dual h_1 v.dual
     rw [size_dual, add_comm, size_dual, ← dual_balance_r, ← valid'.dual_iff, size_dual,
-      add_comm rs] at this
+      add_comm rs] at this 
     exact this e
   · refine' valid'.glue_aux hl hr sep (Or.inr ⟨not_lt.1 h_1, not_lt.1 h⟩)
 #align ordnode.valid'.merge_aux Ordnode.Valid'.merge_aux
@@ -1655,9 +1655,9 @@ theorem size_erase_of_mem [@DecidableRel α (· ≤ ·)] {x : α} {t a₁ a₂}
   · have t_ih_l' := t_ih_l h.left
     have t_ih_r' := t_ih_r h.right
     clear t_ih_l t_ih_r
-    unfold Membership.Mem mem at h_mem
+    unfold Membership.Mem mem at h_mem 
     unfold erase
-    cases cmpLE x t_x <;> simp [mem._match_1] at h_mem <;> simp [erase._match_1]
+    cases cmpLE x t_x <;> simp [mem._match_1] at h_mem  <;> simp [erase._match_1]
     · have t_ih_l := t_ih_l' h_mem
       clear t_ih_l' t_ih_r'
       have t_l_h := valid'.erase_aux x h.left
@@ -1729,7 +1729,7 @@ def Empty (s : Ordset α) : Prop :=
 #align ordset.empty Ordset.Empty
 
 theorem empty_iff {s : Ordset α} : s = ∅ ↔ s.1.Empty :=
-  ⟨fun h => by cases h <;> exact rfl, fun h => by cases s <;> cases s_val <;> [exact rfl;cases h]⟩
+  ⟨fun h => by cases h <;> exact rfl, fun h => by cases s <;> cases s_val <;> [exact rfl; cases h]⟩
 #align ordset.empty_iff Ordset.empty_iff
 
 instance : DecidablePred (@Empty α _) := fun s => decidable_of_iff' _ empty_iff
@@ -1775,7 +1775,7 @@ instance mem.decidable (x : α) (s : Ordset α) : Decidable (x ∈ s) :=
 
 theorem pos_size_of_mem {x : α} {t : Ordset α} (h_mem : x ∈ t) : 0 < size t :=
   by
-  simp [Membership.Mem, mem] at h_mem
+  simp [Membership.Mem, mem] at h_mem 
   apply Ordnode.pos_size_of_mem t.property.sz h_mem
 #align ordset.pos_size_of_mem Ordset.pos_size_of_mem

47b51515

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -325,17 +325,13 @@ theorem dual_balanceL (l : Ordnode α) (x : α) (r : Ordnode α) :
   by
   unfold balance_l balance_r
   cases' r with rs rl rx rr
-  · cases' l with ls ll lx lr
-    · rfl
+  · cases' l with ls ll lx lr; · rfl
     cases' ll with lls lll llx llr <;> cases' lr with lrs lrl lrx lrr <;> dsimp only [dual] <;>
       try rfl
     split_ifs <;> repeat' simp [h, add_comm]
-  · cases' l with ls ll lx lr
-    · rfl
+  · cases' l with ls ll lx lr; · rfl
     dsimp only [dual]
-    split_ifs
-    swap
-    · simp [add_comm]
+    split_ifs; swap; · simp [add_comm]
     cases' ll with lls lll llx llr <;> cases' lr with lrs lrl lrx lrr <;> try rfl
     dsimp only [dual]
     split_ifs <;> simp [h, add_comm]
@@ -551,10 +547,7 @@ theorem equiv_iff {t₁ t₂ : Ordnode α} (h₁ : Sized t₁) (h₂ : Sized t
 
 
 theorem pos_size_of_mem [LE α] [@DecidableRel α (· ≤ ·)] {x : α} {t : Ordnode α} (h : Sized t)
-    (h_mem : x ∈ t) : 0 < size t := by
-  cases t
-  · contradiction
-  · simp [h.1]
+    (h_mem : x ∈ t) : 0 < size t := by cases t; · contradiction; · simp [h.1]
 #align ordnode.pos_size_of_mem Ordnode.pos_size_of_mem
 
 /-! ### `(find/erase/split)_(min/max)` -/
@@ -671,8 +664,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sr.2.2.2.1.size_eq_zero.1 this.1
         cases sr.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : rrs = 1 := sr.2.2.1
-        rw [if_neg, if_pos, rotate_l, if_pos]
-        · rfl
+        rw [if_neg, if_pos, rotate_l, if_pos]; · rfl
         all_goals exact by decide
       · have : size rll = 0 ∧ size rlr = 0 :=
           by
@@ -681,11 +673,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sr.2.1.2.1.size_eq_zero.1 this.1
         cases sr.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : rls = 1 := sr.2.1.1
-        rw [if_neg, if_pos, rotate_l, if_neg]
-        · rfl
+        rw [if_neg, if_pos, rotate_l, if_neg]; · rfl
         all_goals exact by decide
-      · symm
-        rw [zero_add, if_neg, if_pos, rotate_l]
+      · symm; rw [zero_add, if_neg, if_pos, rotate_l]
         · split_ifs
           · simp [node3_l, node', add_comm, add_left_comm]
           · simp [node4_l, node', sr.2.1.1, add_comm, add_left_comm]
@@ -703,8 +693,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sl.2.2.2.1.size_eq_zero.1 this.1
         cases sl.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : lrs = 1 := sl.2.2.1
-        rw [if_neg, if_neg, if_pos, rotate_r, if_neg]
-        · rfl
+        rw [if_neg, if_neg, if_pos, rotate_r, if_neg]; · rfl
         all_goals exact by decide
       · have : size lll = 0 ∧ size llr = 0 :=
           by
@@ -713,11 +702,9 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sl.2.1.2.1.size_eq_zero.1 this.1
         cases sl.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : lls = 1 := sl.2.1.1
-        rw [if_neg, if_neg, if_pos, rotate_r, if_pos]
-        · rfl
+        rw [if_neg, if_neg, if_pos, rotate_r, if_pos]; · rfl
         all_goals exact by decide
-      · symm
-        rw [if_neg, if_neg, if_pos, rotate_r]
+      · symm; rw [if_neg, if_neg, if_pos, rotate_r]
         · split_ifs
           · simp [node3_r, node', add_comm, add_left_comm]
           · simp [node4_r, node', sl.2.2.1, add_comm, add_left_comm]
@@ -725,8 +712,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         · exact by decide
         · exact not_le_of_gt (Nat.succ_lt_succ (add_pos sl.2.1.Pos sl.2.2.Pos))
     · simp [balance, balance']
-      symm
-      rw [if_neg]
+      symm; rw [if_neg]
       · split_ifs
         · have rd : delta ≤ size rl + size rr :=
             by
@@ -737,8 +723,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
             exact absurd (le_trans rd (balanced_sz_zero.1 hr.1.symm)) (by decide)
           cases' rr with rrs rrl rrx rrr
           · exact absurd (le_trans rd (balanced_sz_zero.1 hr.1)) (by decide)
-          dsimp [rotate_l]
-          split_ifs
+          dsimp [rotate_l]; split_ifs
           · simp [node3_l, node', sr.1, add_comm, add_left_comm]
           · simp [node4_l, node', sr.1, sr.2.1.1, add_comm, add_left_comm]
         · have ld : delta ≤ size ll + size lr :=
@@ -750,8 +735,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
             exact absurd (le_trans ld (balanced_sz_zero.1 hl.1.symm)) (by decide)
           cases' lr with lrs lrl lrx lrr
           · exact absurd (le_trans ld (balanced_sz_zero.1 hl.1)) (by decide)
-          dsimp [rotate_r]
-          split_ifs
+          dsimp [rotate_r]; split_ifs
           · simp [node3_r, node', sl.1, add_comm, add_left_comm]
           · simp [node4_r, node', sl.1, sl.2.2.1, add_comm, add_left_comm]
         · simp [node']
@@ -769,8 +753,7 @@ theorem balanceL_eq_balance {l x r} (sl : Sized l) (sr : Sized r) (H1 : size l =
         rwa [size, sr.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
       cases sr.2.1.size_eq_zero.1 this.1
       cases sr.2.2.size_eq_zero.1 this.2
-      rw [sr.eq_node']
-      rfl
+      rw [sr.eq_node']; rfl
     · replace H2 : ¬rs > delta * ls := not_lt_of_le (H2 sl.pos sr.pos)
       simp [balance_l, balance, H2] <;> split_ifs <;> simp [add_comm]
 #align ordnode.balance_l_eq_balance Ordnode.balanceL_eq_balance
@@ -827,8 +810,7 @@ theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     @balanceL α l x r = balance' l x r :=
   by
   rw [← balance_eq_balance' hl hr sl sr, balance_l_eq_balance sl sr]
-  · intro l0
-    rw [l0] at H
+  · intro l0; rw [l0] at H
     rcases H with (⟨_, ⟨⟨⟩⟩ | ⟨⟨⟩⟩, H⟩ | ⟨r', e, H⟩)
     · exact balanced_sz_zero.1 H.symm
     exact le_trans (raised_iff.1 e).1 (balanced_sz_zero.1 H.symm)
@@ -836,9 +818,7 @@ theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     rcases H with (⟨l', e, H | ⟨H₁, H₂⟩⟩ | ⟨r', e, H | ⟨H₁, H₂⟩⟩)
     · exact le_trans (le_trans (Nat.le_add_left _ _) H) (mul_pos (by decide) l1 : (0 : ℕ) < _)
     · exact le_trans H₂ (Nat.mul_le_mul_left _ (raised_iff.1 e).1)
-    · cases raised_iff.1 e
-      unfold delta
-      linarith
+    · cases raised_iff.1 e; unfold delta; linarith
     · exact le_trans (raised_iff.1 e).1 H₂
 #align ordnode.balance_l_eq_balance' Ordnode.balanceL_eq_balance'
 
@@ -1183,11 +1163,9 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
   exact valid'.node' (hl.node' hm.left this.1) (hm.right.node' hr this.2.1) this.2.2
   rcases H with (⟨l0, m1, r0⟩ | ⟨l0, mr₁, lr₁, lr₂, mr₂⟩)
   · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1
-    rw [l0, m1.1, m1.2]
-    rcases size r with (_ | _ | _) <;> exact by decide
+    rw [l0, m1.1, m1.2]; rcases size r with (_ | _ | _) <;> exact by decide
   · cases' Nat.eq_zero_or_pos (size r) with r0 r0
-    · rw [r0] at mr₂
-      cases not_le_of_lt Hm mr₂
+    · rw [r0] at mr₂; cases not_le_of_lt Hm mr₂
     rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂
     by_cases mm : size ml + size mr ≤ 1
     · have r1 :=
@@ -1201,18 +1179,14 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
       rw [l1, r1]
       cases size ml <;> cases size mr
       · exact by decide
-      · rw [zero_add] at mm
-        rcases mm with (_ | ⟨⟨⟩⟩)
-        exact by decide
-      · rcases mm with (_ | ⟨⟨⟩⟩)
+      · rw [zero_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
         exact by decide
-      · rw [Nat.succ_add] at mm
-        rcases mm with (_ | ⟨⟨⟩⟩)
+      · rcases mm with (_ | ⟨⟨⟩⟩); exact by decide
+      · rw [Nat.succ_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
     cases' Nat.eq_zero_or_pos (size ml) with ml0 ml0
     · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂
-      rw [ml0, mm₂] at mm
-      cases mm (by decide)
+      rw [ml0, mm₂] at mm; cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 :=
       by
       have := Nat.mul_le_mul_left _ lr₁
@@ -1252,35 +1226,28 @@ theorem Valid'.rotateL {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Valid'
     (H1 : ¬size l + size r ≤ 1) (H2 : delta * size l < size r)
     (H3 : 2 * size r ≤ 9 * size l + 5 ∨ size r ≤ 3) : Valid' o₁ (@rotateL α l x r) o₂ :=
   by
-  cases' r with rs rl rx rr
-  · cases H2
+  cases' r with rs rl rx rr; · cases H2
   rw [hr.2.size_eq, Nat.lt_succ_iff] at H2
   rw [hr.2.size_eq] at H3
   replace H3 : 2 * (size rl + size rr) ≤ 9 * size l + 3 ∨ size rl + size rr ≤ 2 :=
     H3.imp (@Nat.le_of_add_le_add_right 2 _ _) Nat.le_of_succ_le_succ
   have H3_0 : size l = 0 → size rl + size rr ≤ 2 :=
     by
-    intro l0
-    rw [l0] at H3
+    intro l0; rw [l0] at H3
     exact
       (or_iff_right_of_imp fun h => (mul_le_mul_left (by decide)).1 (le_trans h (by decide))).1 H3
   have H3p : size l > 0 → 2 * (size rl + size rr) ≤ 9 * size l + 3 := fun l0 : 1 ≤ size l =>
     (or_iff_left_of_imp <| by intro <;> linarith).1 H3
-  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 :=
-    by
-    intros
-    linarith
+  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros ; linarith
   have hlp : size l > 0 → ¬size rl + size rr ≤ 1 := fun l0 hb =>
     absurd (le_trans (le_trans (Nat.mul_le_mul_left _ l0) H2) hb) (by decide)
-  rw [rotate_l]
-  split_ifs
+  rw [rotate_l]; split_ifs
   · have rr0 : size rr > 0 :=
       (mul_lt_mul_left (by decide)).1 (lt_of_le_of_lt (Nat.zero_le _) h : ratio * 0 < _)
     suffices balanced_sz (size l) (size rl) ∧ balanced_sz (size l + size rl + 1) (size rr) by
       exact hl.node3_l hr.left hr.right this.1 this.2
     cases' Nat.eq_zero_or_pos (size l) with l0 l0
-    · rw [l0]
-      replace H3 := H3_0 l0
+    · rw [l0]; replace H3 := H3_0 l0
       have := hr.3.1
       cases' Nat.eq_zero_or_pos (size rl) with rl0 rl0
       · rw [rl0] at this⊢
@@ -1348,11 +1315,8 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
   suffices @size α r ≤ 3 * (size l + 1)
     by
     cases' Nat.eq_zero_or_pos (size l) with l0 l0
-    · apply Or.inr
-      rwa [l0] at this
-    change 1 ≤ _ at l0
-    apply Or.inl
-    linarith
+    · apply Or.inr; rwa [l0] at this
+    change 1 ≤ _ at l0; apply Or.inl; linarith
   rcases H2 with (⟨hl, rfl⟩ | ⟨hr, rfl⟩) <;> rcases H1 with (h | ⟨h₁, h₂⟩)
   · exact le_trans (Nat.le_add_left _ _) (le_trans h (Nat.le_add_left _ _))
   ·
@@ -1393,11 +1357,9 @@ theorem Valid'.balanceL_aux {l x r o₁ o₂} (hl : Valid' o₁ l ↑x) (hr : Va
   rw [balance_l_eq_balance hl.2 hr.2 H₁ H₂, balance_eq_balance' hl.3 hr.3 hl.2 hr.2]
   refine' hl.balance'_aux hr (Or.inl _) H₃
   cases' Nat.eq_zero_or_pos (size r) with r0 r0
-  · rw [r0]
-    exact Nat.zero_le _
+  · rw [r0]; exact Nat.zero_le _
   cases' Nat.eq_zero_or_pos (size l) with l0 l0
-  · rw [l0]
-    exact le_trans (Nat.mul_le_mul_left _ (H₁ l0)) (by decide)
+  · rw [l0]; exact le_trans (Nat.mul_le_mul_left _ (H₁ l0)) (by decide)
   replace H₂ : _ ≤ 3 * _ := H₂ l0 r0; linarith
 #align ordnode.valid'.balance_l_aux Ordnode.Valid'.balanceL_aux
 
@@ -1478,8 +1440,7 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
     · refine' find_max'_all lx lr hl.1.2.to_nil (sep.2.2.imp _)
       exact fun x h => hr.1.2.to_nil.mono_left (le_of_lt h.2.1)
     · exact @find_max'_all _ (fun a => all (· > a) (node rs rl rx rr)) lx lr sep.2.1 sep.2.2
-    · rw [size_balance_r v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]
-      rfl
+    · rw [size_balance_r v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
     · refine' Or.inl ⟨_, Or.inr e, _⟩
       rwa [hl.2.eq_node'] at bal
   · rw [split_min_eq, glue]
@@ -1493,8 +1454,7 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
         @find_min'_all _ (fun a => all (· < a) (node ls ll lx lr)) rl rx
           (all_iff_forall.2 fun x hx => sep.imp fun y hy => all_iff_forall.1 hy.1 _ hx)
           (sep.imp fun y hy => hy.2.1)
-    · rw [size_balance_l hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]
-      rfl
+    · rw [size_balance_l hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
     · refine' Or.inr ⟨_, Or.inr e, _⟩
       rwa [hr.2.eq_node'] at bal
 #align ordnode.valid'.glue_aux Ordnode.Valid'.glue_aux
@@ -1519,17 +1479,12 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
   rcases hr.3.1 with (H | ⟨hr₁, hr₂⟩); · linarith
   suffices H₂; suffices H₁
   refine' ⟨valid'.balance_l_aux v hr.right H₁ H₂ _, _⟩
-  · rw [e]
-    exact Or.inl (valid'.merge_lemma h hr₁)
+  · rw [e]; exact Or.inl (valid'.merge_lemma h hr₁)
   · rw [balance_l_eq_balance v.2 hr.2.2.2 H₁ H₂, balance_eq_balance' v.3 hr.3.2.2 v.2 hr.2.2.2,
       size_balance' v.2 hr.2.2.2, e, hl.2.1, hr.2.1]
     simp [add_comm, add_left_comm]
-  · rw [e, add_right_comm]
-    rintro ⟨⟩
-  · intro _ h₁
-    rw [e]
-    unfold delta at hr₂⊢
-    linarith
+  · rw [e, add_right_comm]; rintro ⟨⟩
+  · intro _ h₁; rw [e]; unfold delta at hr₂⊢; linarith
 #align ordnode.valid'.merge_aux₁ Ordnode.Valid'.merge_aux₁
 
 theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o₁ r o₂)
@@ -1626,12 +1581,9 @@ theorem Valid'.map_aux {β} [Preorder β] {f : α → β} (f_strict_mono : Stric
     Valid' (Option.map f a₁) (map f t) (Option.map f a₂) ∧ (map f t).size = t.size :=
   by
   induction t generalizing a₁ a₂
-  · simp [map]
-    apply valid'_nil
-    cases a₁
-    · trivial
-    cases a₂
-    · trivial
+  · simp [map]; apply valid'_nil
+    cases a₁; · trivial
+    cases a₂; · trivial
     simp [bounded]
     exact f_strict_mono h.ord
   · have t_ih_l' := t_ih_l h.left
@@ -1643,13 +1595,11 @@ theorem Valid'.map_aux {β} [Preorder β] {f : α → β} (f_strict_mono : Stric
     constructor
     · exact And.intro t_l_valid.ord t_r_valid.ord
     · repeat' constructor
-      · rw [t_l_size, t_r_size]
-        exact h.sz.1
+      · rw [t_l_size, t_r_size]; exact h.sz.1
       · exact t_l_valid.sz
       · exact t_r_valid.sz
     · repeat' constructor
-      · rw [t_l_size, t_r_size]
-        exact h.bal.1
+      · rw [t_l_size, t_r_size]; exact h.bal.1
       · exact t_l_valid.bal
       · exact t_r_valid.bal
 #align ordnode.valid'.map_aux Ordnode.Valid'.map_aux
@@ -1663,8 +1613,7 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
     Valid' a₁ (erase x t) a₂ ∧ Raised (erase x t).size t.size :=
   by
   induction t generalizing a₁ a₂
-  · simp [erase, raised]
-    exact h
+  · simp [erase, raised]; exact h
   · simp [erase]
     have t_ih_l' := t_ih_l h.left
     have t_ih_r' := t_ih_r h.right
@@ -1678,15 +1627,12 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
       · rw [size_balance_r t_l_valid.bal h.right.bal t_l_valid.sz h.right.sz h_balanceable]
         repeat' apply raised.add_right
         exact t_l_size
-      · left
-        exists t_l.size
-        exact And.intro t_l_size h.bal.1
+      · left; exists t_l.size; exact And.intro t_l_size h.bal.1
     · have h_glue := valid'.glue h.left h.right h.bal.1
       cases' h_glue with h_glue_valid h_glue_sized
       constructor
       · exact h_glue_valid
-      · right
-        rw [h_glue_sized]
+      · right; rw [h_glue_sized]
     · suffices h_balanceable
       constructor
       · exact valid'.balance_l h.left t_r_valid h_balanceable
@@ -1694,9 +1640,7 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
         apply raised.add_right
         apply raised.add_left
         exact t_r_size
-      · right
-        exists t_r.size
-        exact And.intro t_r_size h.bal.1
+      · right; exists t_r.size; exact And.intro t_r_size h.bal.1
 #align ordnode.valid'.erase_aux Ordnode.Valid'.erase_aux
 
 theorem erase.valid [@DecidableRel α (· ≤ ·)] (x : α) {t} (h : Valid t) : Valid (erase x t) :=
@@ -1722,11 +1666,9 @@ theorem size_erase_of_mem [@DecidableRel α (· ≤ ·)] {x : α} {t a₁ a₂}
           (Or.inl (Exists.intro t_l.size (And.intro t_l_size h.bal.1)))]
       rw [t_ih_l, h.sz.1]
       have h_pos_t_l_size := pos_size_of_mem h.left.sz h_mem
-      cases' t_l.size with t_l_size
-      · cases h_pos_t_l_size
+      cases' t_l.size with t_l_size; · cases h_pos_t_l_size
       simp [Nat.succ_add]
-    · rw [(valid'.glue h.left h.right h.bal.1).2, h.sz.1]
-      rfl
+    · rw [(valid'.glue h.left h.right h.bal.1).2, h.sz.1]; rfl
     · have t_ih_r := t_ih_r' h_mem
       clear t_ih_l' t_ih_r'
       have t_r_h := valid'.erase_aux x h.right
@@ -1735,8 +1677,7 @@ theorem size_erase_of_mem [@DecidableRel α (· ≤ ·)] {x : α} {t a₁ a₂}
           (Or.inr (Exists.intro t_r.size (And.intro t_r_size h.bal.1)))]
       rw [t_ih_r, h.sz.1]
       have h_pos_t_r_size := pos_size_of_mem h.right.sz h_mem
-      cases' t_r.size with t_r_size
-      · cases h_pos_t_r_size
+      cases' t_r.size with t_r_size; · cases h_pos_t_r_size
       simp [Nat.succ_add, Nat.add_succ]
 #align ordnode.size_erase_of_mem Ordnode.size_erase_of_mem

47b51515

bump to nightly-2023-05-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b

fbc7b476

Diff

@@ -138,7 +138,7 @@ theorem size_eq_realSize : ∀ {t : Ordnode α}, Sized t → size t = realSize t
 
 @[simp]
 theorem Sized.size_eq_zero {t : Ordnode α} (ht : Sized t) : size t = 0 ↔ t = nil := by
-  cases t <;> [simp, simp [ht.1]]
+  cases t <;> [simp;simp [ht.1]]
 #align ordnode.sized.size_eq_zero Ordnode.Sized.size_eq_zero
 
 theorem Sized.pos {s l x r} (h : Sized (@node α s l x r)) : 0 < s := by
@@ -358,7 +358,7 @@ theorem Sized.node3R {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r
 
 theorem Sized.node4L {l x m y r} (hl : @Sized α l) (hm : Sized m) (hr : Sized r) :
     Sized (node4L l x m y r) := by
-  cases m <;> [exact (hl.node' hm).node' hr, exact (hl.node' hm.2.1).node' (hm.2.2.node' hr)]
+  cases m <;> [exact (hl.node' hm).node' hr;exact (hl.node' hm.2.1).node' (hm.2.2.node' hr)]
 #align ordnode.sized.node4_l Ordnode.Sized.node4L
 
 theorem node3L_size {l x m y r} : size (@node3L α l x m y r) = size l + size m + size r + 2 := by
@@ -371,8 +371,8 @@ theorem node3R_size {l x m y r} : size (@node3R α l x m y r) = size l + size m
 
 theorem node4L_size {l x m y r} (hm : Sized m) :
     size (@node4L α l x m y r) = size l + size m + size r + 2 := by
-  cases m <;> simp [node4_l, node3_l, node', add_comm, add_left_comm] <;> [skip,
-        simp [size, hm.1]] <;>
+  cases m <;> simp [node4_l, node3_l, node', add_comm, add_left_comm] <;>
+        [skip;simp [size, hm.1]] <;>
       rw [← add_assoc, ← bit0] <;>
     simp [add_comm, add_left_comm]
 #align ordnode.node4_l_size Ordnode.node4L_size
@@ -1788,7 +1788,7 @@ def Empty (s : Ordset α) : Prop :=
 #align ordset.empty Ordset.Empty
 
 theorem empty_iff {s : Ordset α} : s = ∅ ↔ s.1.Empty :=
-  ⟨fun h => by cases h <;> exact rfl, fun h => by cases s <;> cases s_val <;> [exact rfl, cases h]⟩
+  ⟨fun h => by cases h <;> exact rfl, fun h => by cases s <;> cases s_val <;> [exact rfl;cases h]⟩
 #align ordset.empty_iff Ordset.empty_iff
 
 instance : DecidablePred (@Empty α _) := fun s => decidable_of_iff' _ empty_iff

47b51515

bump to nightly-2023-04-12-20

mathlib commit https://github.com/leanprover-community/mathlib/commit/039ef89bef6e58b32b62898dd48e9d1a4312bb65

0809e5be

Diff

@@ -174,11 +174,11 @@ instance BalancedSz.dec : DecidableRel BalancedSz := fun l r => Or.decidable
 (at every level). -/
 def Balanced : Ordnode α → Prop
   | nil => True
-  | node _ l _ r => BalancedSz (size l) (size r) ∧ balanced l ∧ balanced r
+  | node _ l _ r => BalancedSz (size l) (size r) ∧ Balanced l ∧ Balanced r
 #align ordnode.balanced Ordnode.Balanced
 
 instance Balanced.dec : DecidablePred (@Balanced α)
-  | t => by induction t <;> unfold balanced <;> skip <;> infer_instance
+  | t => by induction t <;> unfold Balanced <;> skip <;> infer_instance
 #align ordnode.balanced.dec Ordnode.Balanced.dec
 
 theorem BalancedSz.symm {l r : ℕ} : BalancedSz l r → BalancedSz r l :=

47b51515

bump to nightly-2023-03-11-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212

cd44fb92

Diff

@@ -1210,7 +1210,7 @@ theorem Valid'.node4L {l x m y r o₁ o₂} (hl : Valid' o₁ l ↑x) (hm : Vali
         rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
     cases' Nat.eq_zero_or_pos (size ml) with ml0 ml0
-    · rw [ml0, mul_zero, le_zero_iff] at mm₂
+    · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂
       rw [ml0, mm₂] at mm
       cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 :=

47b51515

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

47b51515

chore: adapt to multiple goal linter 1 (#12338)

A PR accompanying #12339.

Zulip discussion

45f93f3f

Diff

@@ -784,9 +784,10 @@ def Raised (n m : ℕ) : Prop :=
 #align ordnode.raised Ordnode.Raised
 
 theorem raised_iff {n m} : Raised n m ↔ n ≤ m ∧ m ≤ n + 1 := by
-  constructor; rintro (rfl | rfl)
-  · exact ⟨le_rfl, Nat.le_succ _⟩
-  · exact ⟨Nat.le_succ _, le_rfl⟩
+  constructor
+  · rintro (rfl | rfl)
+    · exact ⟨le_rfl, Nat.le_succ _⟩
+    · exact ⟨Nat.le_succ _, le_rfl⟩
   · rintro ⟨h₁, h₂⟩
     rcases eq_or_lt_of_le h₁ with (rfl | h₁)
     · exact Or.inl rfl
@@ -1427,30 +1428,30 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
   cases' r with rs rl rx rr; · exact ⟨hl, rfl⟩
   dsimp [glue]; split_ifs
   · rw [splitMax_eq]
-    cases' Valid'.eraseMax_aux hl with v e
-    suffices H : _ by
-      refine' ⟨Valid'.balanceR v (hr.of_gt _ _) H, _⟩
-      · refine' findMax'_all (P := fun a : α => Bounded nil (a : WithTop α) o₂)
-          lx lr hl.1.2.to_nil (sep.2.2.imp _)
-        exact fun x h => hr.1.2.to_nil.mono_left (le_of_lt h.2.1)
-      · exact @findMax'_all _ (fun a => All (· > a) (.node rs rl rx rr)) lx lr sep.2.1 sep.2.2
-      · rw [size_balanceR v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
-    refine' Or.inl ⟨_, Or.inr e, _⟩
-    rwa [hl.2.eq_node'] at bal
+    · cases' Valid'.eraseMax_aux hl with v e
+      suffices H : _ by
+        refine' ⟨Valid'.balanceR v (hr.of_gt _ _) H, _⟩
+        · refine' findMax'_all (P := fun a : α => Bounded nil (a : WithTop α) o₂)
+            lx lr hl.1.2.to_nil (sep.2.2.imp _)
+          exact fun x h => hr.1.2.to_nil.mono_left (le_of_lt h.2.1)
+        · exact @findMax'_all _ (fun a => All (· > a) (.node rs rl rx rr)) lx lr sep.2.1 sep.2.2
+        · rw [size_balanceR v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
+      refine' Or.inl ⟨_, Or.inr e, _⟩
+      rwa [hl.2.eq_node'] at bal
   · rw [splitMin_eq]
-    cases' Valid'.eraseMin_aux hr with v e
-    suffices H : _ by
-      refine' ⟨Valid'.balanceL (hl.of_lt _ _) v H, _⟩
-      · refine' @findMin'_all (P := fun a : α => Bounded nil o₁ (a : WithBot α))
-          rl rx (sep.2.1.1.imp _) hr.1.1.to_nil
-        exact fun y h => hl.1.1.to_nil.mono_right (le_of_lt h)
-      · exact
-          @findMin'_all _ (fun a => All (· < a) (.node ls ll lx lr)) rl rx
-            (all_iff_forall.2 fun x hx => sep.imp fun y hy => all_iff_forall.1 hy.1 _ hx)
-            (sep.imp fun y hy => hy.2.1)
-      · rw [size_balanceL hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
-    refine' Or.inr ⟨_, Or.inr e, _⟩
-    rwa [hr.2.eq_node'] at bal
+    · cases' Valid'.eraseMin_aux hr with v e
+      suffices H : _ by
+        refine' ⟨Valid'.balanceL (hl.of_lt _ _) v H, _⟩
+        · refine' @findMin'_all (P := fun a : α => Bounded nil o₁ (a : WithBot α))
+            rl rx (sep.2.1.1.imp _) hr.1.1.to_nil
+          exact fun y h => hl.1.1.to_nil.mono_right (le_of_lt h)
+        · exact
+            @findMin'_all _ (fun a => All (· < a) (.node ls ll lx lr)) rl rx
+              (all_iff_forall.2 fun x hx => sep.imp fun y hy => all_iff_forall.1 hy.1 _ hx)
+              (sep.imp fun y hy => hy.2.1)
+        · rw [size_balanceL hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
+      refine' Or.inr ⟨_, Or.inr e, _⟩
+      rwa [hr.2.eq_node'] at bal
 #align ordnode.valid'.glue_aux Ordnode.Valid'.glue_aux
 
 theorem Valid'.glue {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : Valid' x r o₂) :

47b51515

chore: remove unnecessary cdots (#12417)

These · are scoping when there is a single active goal.

These were found using a modification of the linter at #12339.

5450e922

Diff

@@ -1478,7 +1478,7 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
           size_balance' v.2 hr.2.2.2, e, hl.2.1, hr.2.1]
         abel
     · rw [e, add_right_comm]; rintro ⟨⟩
-  · intro _ _; rw [e]; unfold delta at hr₂ ⊢; omega
+  intro _ _; rw [e]; unfold delta at hr₂ ⊢; omega
 #align ordnode.valid'.merge_aux₁ Ordnode.Valid'.merge_aux₁
 
 theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o₁ r o₂)
@@ -1527,14 +1527,14 @@ theorem insertWith.valid_aux [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤
         refine' ⟨vl.balanceL h.right H, _⟩
         rw [size_balanceL vl.3 h.3.2.2 vl.2 h.2.2.2 H, h.2.size_eq]
         exact (e.add_right _).add_right _
-      · exact Or.inl ⟨_, e, h.3.1⟩
+      exact Or.inl ⟨_, e, h.3.1⟩
     · have : y < x := lt_of_le_not_le ((total_of (· ≤ ·) _ _).resolve_left h_1) h_1
       rcases insertWith.valid_aux f x hf h.right this br with ⟨vr, e⟩
       suffices H : _ by
         refine' ⟨h.left.balanceR vr H, _⟩
         rw [size_balanceR h.3.2.1 vr.3 h.2.2.1 vr.2 H, h.2.size_eq]
         exact (e.add_left _).add_right _
-      · exact Or.inr ⟨_, e, h.3.1⟩
+      exact Or.inr ⟨_, e, h.3.1⟩
 #align ordnode.insert_with.valid_aux Ordnode.insertWith.valid_aux
 
 theorem insertWith.valid [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤ ·)] (f : α → α) (x : α)
@@ -1621,7 +1621,7 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
         · rw [size_balanceR t_l_valid.bal h.right.bal t_l_valid.sz h.right.sz h_balanceable]
           repeat apply Raised.add_right
           exact t_l_size
-      · left; exists t_l.size; exact And.intro t_l_size h.bal.1
+      left; exists t_l.size; exact And.intro t_l_size h.bal.1
     · have h_glue := Valid'.glue h.left h.right h.bal.1
       cases' h_glue with h_glue_valid h_glue_sized
       constructor
@@ -1634,7 +1634,7 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
           apply Raised.add_right
           apply Raised.add_left
           exact t_r_size
-      · right; exists t_r.size; exact And.intro t_r_size h.bal.1
+      right; exists t_r.size; exact And.intro t_r_size h.bal.1
 #align ordnode.valid'.erase_aux Ordnode.Valid'.erase_aux
 
 theorem erase.valid [@DecidableRel α (· ≤ ·)] (x : α) {t} (h : Valid t) : Valid (erase x t) :=

47b51515

chore: refactor to avoid importing Ring for Group topics (#11913)

This is a far from a complete success at the PR title, but it makes a fair bit of progress, and then guards this with appropriate assert_not_exists Ring statements.

It also breaks apart the Mathlib.GroupTheory.Subsemigroup.[Center|Centralizer] files, to pull the Set.center and Set.centralizer declarations into their own files not depending on Subsemigroup.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

8e052acc

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
 import Mathlib.Algebra.Order.Ring.Defs
-import Mathlib.Algebra.Ring.Int
+import Mathlib.Algebra.Group.Int
 import Mathlib.Data.Nat.Dist
 import Mathlib.Data.Nat.Units
 import Mathlib.Data.Ordmap.Ordnode

47b51515

chore: Split Data.{Nat,Int}{.Order}.Basic in group vs ring instances (#11924)

Scatter the content of Data.Nat.Basic across:

Data.Nat.Defs for the lemmas having no dependencies
Algebra.Group.Nat for the monoid instances and the few miscellaneous lemmas needing them.
Algebra.Ring.Nat for the semiring instance and the few miscellaneous lemmas following it.

Similarly, scatter

Data.Int.Basic across Data.Int.Defs, Algebra.Group.Int, Algebra.Ring.Int
Data.Nat.Order.Basic across Data.Nat.Defs, Algebra.Order.Group.Nat, Algebra.Order.Ring.Nat
Data.Int.Order.Basic across Data.Int.Defs, Algebra.Order.Group.Int, Algebra.Order.Ring.Int

Also move a few lemmas from Data.Nat.Order.Lemmas to Data.Nat.Defs.

Before pre_11924

After post_11924

47062a71

Diff

@@ -4,8 +4,9 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
 import Mathlib.Algebra.Order.Ring.Defs
-import Mathlib.Data.Int.Basic
+import Mathlib.Algebra.Ring.Int
 import Mathlib.Data.Nat.Dist
+import Mathlib.Data.Nat.Units
 import Mathlib.Data.Ordmap.Ordnode
 import Mathlib.Tactic.Abel
 import Mathlib.Tactic.Linarith

47b51515

chore: remove @[eqns] on Ordnode.rotateR/L (#11649)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

c59421a2

Diff

@@ -255,6 +255,10 @@ def rotateL : Ordnode α → α → Ordnode α → Ordnode α
   | l, x, nil => node' l x nil
 #align ordnode.rotate_l Ordnode.rotateL
 
+-- Adaptation note:
+-- During the port we marked these lemmas with `@[eqns]` to emulate the old Lean 3 behaviour.
+-- See https://github.com/leanprover-community/mathlib4/issues/11647
+
 theorem rotateL_node (l : Ordnode α) (x : α) (sz : ℕ) (m : Ordnode α) (y : α) (r : Ordnode α) :
     rotateL l x (node sz m y r) =
       if size m < ratio * size r then node3L l x m y r else node4L l x m y r :=
@@ -263,8 +267,6 @@ theorem rotateL_node (l : Ordnode α) (x : α) (sz : ℕ) (m : Ordnode α) (y :
 theorem rotateL_nil (l : Ordnode α) (x : α) : rotateL l x nil = node' l x nil :=
   rfl
 
-attribute [eqns rotateL_node rotateL_nil] rotateL
-
 -- should not happen
 /-- Concatenate two nodes, performing a right rotation `(x y) z -> (x (y z))`
 if balance is upset. -/
@@ -273,6 +275,10 @@ def rotateR : Ordnode α → α → Ordnode α → Ordnode α
   | nil, y, r => node' nil y r
 #align ordnode.rotate_r Ordnode.rotateR
 
+-- Adaptation note:
+-- During the port we marked these lemmas with `@[eqns]` to emulate the old Lean 3 behaviour.
+-- See https://github.com/leanprover-community/mathlib4/issues/11647
+
 theorem rotateR_node (sz : ℕ) (l : Ordnode α) (x : α) (m : Ordnode α) (y : α) (r : Ordnode α) :
     rotateR (node sz l x m) y r =
       if size m < ratio * size l then node3R l x m y r else node4R l x m y r :=
@@ -281,8 +287,6 @@ theorem rotateR_node (sz : ℕ) (l : Ordnode α) (x : α) (m : Ordnode α) (y :
 theorem rotateR_nil (y : α) (r : Ordnode α) : rotateR nil y r = node' nil y r :=
   rfl
 
-  attribute [eqns rotateR_node rotateR_nil] rotateR
-
 -- should not happen
 /-- A left balance operation. This will rebalance a concatenation, assuming the original nodes are
 not too far from balanced. -/
@@ -409,7 +413,7 @@ theorem Sized.dual_iff {t : Ordnode α} : Sized (.dual t) ↔ Sized t :=
 
 theorem Sized.rotateL {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (rotateL l x r) := by
   cases r; · exact hl.node' hr
-  rw [Ordnode.rotateL]; split_ifs
+  rw [Ordnode.rotateL_node]; split_ifs
   · exact hl.node3L hr.2.1 hr.2.2
   · exact hl.node4L hr.2.1 hr.2.2
 #align ordnode.sized.rotate_l Ordnode.Sized.rotateL
@@ -684,7 +688,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sr.2.2.2.1.size_eq_zero.1 this.1
         cases sr.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : rrs = 1 := sr.2.2.1
-        rw [if_neg, if_pos, rotateL, if_pos]; · rfl
+        rw [if_neg, if_pos, rotateL_node, if_pos]; · rfl
         all_goals dsimp only [size]; decide
       · have : size rll = 0 ∧ size rlr = 0 := by
           have := balancedSz_zero.1 hr.1
@@ -692,7 +696,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sr.2.1.2.1.size_eq_zero.1 this.1
         cases sr.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : rls = 1 := sr.2.1.1
-        rw [if_neg, if_pos, rotateL, if_neg]; · rfl
+        rw [if_neg, if_pos, rotateL_node, if_neg]; · rfl
         all_goals dsimp only [size]; decide
       · symm; rw [zero_add, if_neg, if_pos, rotateL]
         · dsimp only [size_node]; split_ifs
@@ -711,7 +715,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sl.2.2.2.1.size_eq_zero.1 this.1
         cases sl.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : lrs = 1 := sl.2.2.1
-        rw [if_neg, if_neg, if_pos, rotateR, if_neg]; · rfl
+        rw [if_neg, if_neg, if_pos, rotateR_node, if_neg]; · rfl
         all_goals dsimp only [size]; decide
       · have : size lll = 0 ∧ size llr = 0 := by
           have := balancedSz_zero.1 hl.1
@@ -719,7 +723,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         cases sl.2.1.2.1.size_eq_zero.1 this.1
         cases sl.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : lls = 1 := sl.2.1.1
-        rw [if_neg, if_neg, if_pos, rotateR, if_pos]; · rfl
+        rw [if_neg, if_neg, if_pos, rotateR_node, if_pos]; · rfl
         all_goals dsimp only [size]; decide
       · symm; rw [if_neg, if_neg, if_pos, rotateR]
         · dsimp only [size_node]; split_ifs
@@ -1248,7 +1252,7 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
   have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by omega
   have hlp : size l > 0 → ¬size rl + size rr ≤ 1 := fun l0 hb =>
     absurd (le_trans (le_trans (Nat.mul_le_mul_left _ l0) H2) hb) (by decide)
-  rw [Ordnode.rotateL]; split_ifs with h
+  rw [Ordnode.rotateL_node]; split_ifs with h
   · have rr0 : size rr > 0 :=
       (mul_lt_mul_left (by decide)).1 (lt_of_le_of_lt (Nat.zero_le _) h : ratio * 0 < _)
     suffices BalancedSz (size l) (size rl) ∧ BalancedSz (size l + size rl + 1) (size rr) by

47b51515

chore: rm @[eqns] in Ordmap (#11645)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

c1056b03

Diff

@@ -808,7 +808,7 @@ theorem Raised.add_right (k) {n m} (H : Raised n m) : Raised (n + k) (m + k) :=
 
 theorem Raised.right {l x₁ x₂ r₁ r₂} (H : Raised (size r₁) (size r₂)) :
     Raised (size (@node' α l x₁ r₁)) (size (@node' α l x₂ r₂)) := by
-  rw [node', size, size]; generalize size r₂ = m at H ⊢
+  rw [node', size_node, size_node]; generalize size r₂ = m at H ⊢
   rcases H with (rfl | rfl)
   · exact Or.inl rfl
   · exact Or.inr rfl
@@ -1395,7 +1395,7 @@ theorem Valid'.eraseMax_aux {s l x r o₁ o₂} (H : Valid' o₁ (.node s l x r)
   rcases IHrr H.right with ⟨h, e⟩
   refine' ⟨Valid'.balanceL H.left h (Or.inr ⟨_, Or.inr e, H.3.1⟩), _⟩
   rw [eraseMax, size_balanceL H.3.2.1 h.3 H.2.2.1 h.2 (Or.inr ⟨_, Or.inr e, H.3.1⟩)]
-  rw [size, e]; rfl
+  rw [size_node, e]; rfl
 #align ordnode.valid'.erase_max_aux Ordnode.Valid'.eraseMax_aux
 
 theorem Valid'.eraseMin_aux {s l} {x : α} {r o₁ o₂} (H : Valid' o₁ (.node s l x r) o₂) :

47b51515

chore: Move pow_lt_pow_succ to Algebra.Order.WithZero (#11507)

These lemmas can be defined earlier, ridding us of an import in Algebra.GroupPower.Order

d0257020

Diff

@@ -3,12 +3,12 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
-import Mathlib.Data.Ordmap.Ordnode
 import Mathlib.Algebra.Order.Ring.Defs
-import Mathlib.Data.Nat.Dist
 import Mathlib.Data.Int.Basic
-import Mathlib.Tactic.Linarith
+import Mathlib.Data.Nat.Dist
+import Mathlib.Data.Ordmap.Ordnode
 import Mathlib.Tactic.Abel
+import Mathlib.Tactic.Linarith
 
 #align_import data.ordmap.ordset from "leanprover-community/mathlib"@"47b51515e69f59bca5cf34ef456e6000fe205a69"
 
@@ -680,7 +680,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · rfl
       · have : size rrl = 0 ∧ size rrr = 0 := by
           have := balancedSz_zero.1 hr.1.symm
-          rwa [size, sr.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sr.2.2.1, Nat.succ_le_succ_iff, Nat.le_zero, add_eq_zero_iff] at this
         cases sr.2.2.2.1.size_eq_zero.1 this.1
         cases sr.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : rrs = 1 := sr.2.2.1
@@ -688,7 +688,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         all_goals dsimp only [size]; decide
       · have : size rll = 0 ∧ size rlr = 0 := by
           have := balancedSz_zero.1 hr.1
-          rwa [size, sr.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sr.2.1.1, Nat.succ_le_succ_iff, Nat.le_zero, add_eq_zero_iff] at this
         cases sr.2.1.2.1.size_eq_zero.1 this.1
         cases sr.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : rls = 1 := sr.2.1.1
@@ -707,7 +707,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
       · rfl
       · have : size lrl = 0 ∧ size lrr = 0 := by
           have := balancedSz_zero.1 hl.1.symm
-          rwa [size, sl.2.2.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sl.2.2.1, Nat.succ_le_succ_iff, Nat.le_zero, add_eq_zero_iff] at this
         cases sl.2.2.2.1.size_eq_zero.1 this.1
         cases sl.2.2.2.2.size_eq_zero.1 this.2
         obtain rfl : lrs = 1 := sl.2.2.1
@@ -715,7 +715,7 @@ theorem balance_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : Si
         all_goals dsimp only [size]; decide
       · have : size lll = 0 ∧ size llr = 0 := by
           have := balancedSz_zero.1 hl.1
-          rwa [size, sl.2.1.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+          rwa [size, sl.2.1.1, Nat.succ_le_succ_iff, Nat.le_zero, add_eq_zero_iff] at this
         cases sl.2.1.2.1.size_eq_zero.1 this.1
         cases sl.2.1.2.2.size_eq_zero.1 this.2
         obtain rfl : lls = 1 := sl.2.1.1
@@ -765,7 +765,7 @@ theorem balanceL_eq_balance {l x r} (sl : Sized l) (sr : Sized r) (H1 : size l =
   · cases' l with ls ll lx lr
     · have : size rl = 0 ∧ size rr = 0 := by
         have := H1 rfl
-        rwa [size, sr.1, Nat.succ_le_succ_iff, le_zero_iff, add_eq_zero_iff] at this
+        rwa [size, sr.1, Nat.succ_le_succ_iff, Nat.le_zero, add_eq_zero_iff] at this
       cases sr.2.1.size_eq_zero.1 this.1
       cases sr.2.2.size_eq_zero.1 this.2
       rw [sr.eq_node']; rfl
@@ -1195,7 +1195,7 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
       · rw [Nat.succ_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
     rcases Nat.eq_zero_or_pos (size ml) with ml0 | ml0
-    · rw [ml0, mul_zero, le_zero_iff] at mm₂
+    · rw [ml0, mul_zero, Nat.le_zero] at mm₂
       rw [ml0, mm₂] at mm; cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 := by
       have := Nat.mul_le_mul_left ratio lr₁
@@ -1274,9 +1274,9 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
         le_trans hb₂
           (Nat.mul_le_mul_left _ <| le_trans (Nat.le_add_left _ _) (Nat.le_add_right _ _))
   · rcases Nat.eq_zero_or_pos (size rl) with rl0 | rl0
-    · rw [rl0, not_lt, le_zero_iff, Nat.mul_eq_zero] at h
+    · rw [rl0, not_lt, Nat.le_zero, Nat.mul_eq_zero] at h
       replace h := h.resolve_left (by decide)
-      erw [rl0, h, le_zero_iff, Nat.mul_eq_zero] at H2
+      erw [rl0, h, Nat.le_zero, Nat.mul_eq_zero] at H2
       rw [hr.2.size_eq, rl0, h, H2.resolve_left (by decide)] at H1
       cases H1 (by decide)
     refine' hl.node4L hr.left hr.right rl0 _

47b51515

chore: remove useless tactics (#11333)

The removal of some pointless tactics flagged by #11308.

ee18bf38

Diff

@@ -395,7 +395,7 @@ theorem node3R_size {l x m y r} : size (@node3R α l x m y r) = size l + size m
 
 theorem node4L_size {l x m y r} (hm : Sized m) :
     size (@node4L α l x m y r) = size l + size m + size r + 2 := by
-  cases m <;> simp [node4L, node3L, node'] <;> [skip; simp [size, hm.1]] <;> abel
+  cases m <;> simp [node4L, node3L, node'] <;> [abel; (simp [size, hm.1]; abel)]
 #align ordnode.node4_l_size Ordnode.node4L_size
 
 theorem Sized.dual : ∀ {t : Ordnode α}, Sized t → Sized (dual t)

47b51515

chore: move Mathlib to v4.7.0-rc1 (#11162)

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

fa48894a

Diff

@@ -1776,7 +1776,7 @@ instance mem.decidable (x : α) (s : Ordset α) : Decidable (x ∈ s) :=
 
 theorem pos_size_of_mem {x : α} {t : Ordset α} (h_mem : x ∈ t) : 0 < size t := by
   simp? [Membership.mem, mem] at h_mem says
-    simp only [Membership.mem, mem, Bool.decide_coe] at h_mem
+    simp only [Membership.mem, mem, Bool.decide_eq_true] at h_mem
   apply Ordnode.pos_size_of_mem t.property.sz h_mem
 #align ordset.pos_size_of_mem Ordset.pos_size_of_mem

47b51515

refactor: optimize proofs with omega (#11093)

I ran tryAtEachStep on all files under Mathlib to find all locations where omega succeeds. For each that was a linarith without an only, I tried replacing it with omega, and I verified that elaboration time got smaller. (In almost all cases, there was a noticeable speedup.) I also replaced some slow aesops along the way.

37bc4aba

Diff

@@ -829,7 +829,7 @@ theorem balanceL_eq_balance' {l x r} (hl : Balanced l) (hr : Balanced r) (sl : S
     rcases H with (⟨l', e, H | ⟨_, H₂⟩⟩ | ⟨r', e, H | ⟨_, H₂⟩⟩)
     · exact le_trans (le_trans (Nat.le_add_left _ _) H) (mul_pos (by decide) l1 : (0 : ℕ) < _)
     · exact le_trans H₂ (Nat.mul_le_mul_left _ (raised_iff.1 e).1)
-    · cases raised_iff.1 e; unfold delta; linarith
+    · cases raised_iff.1 e; unfold delta; omega
     · exact le_trans (raised_iff.1 e).1 H₂
 #align ordnode.balance_l_eq_balance' Ordnode.balanceL_eq_balance'
 
@@ -1139,22 +1139,22 @@ theorem Valid'.node3R {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
 #align ordnode.valid'.node3_r Ordnode.Valid'.node3R
 
 theorem Valid'.node4L_lemma₁ {a b c d : ℕ} (lr₂ : 3 * (b + c + 1 + d) ≤ 16 * a + 9)
-    (mr₂ : b + c + 1 ≤ 3 * d) (mm₁ : b ≤ 3 * c) : b < 3 * a + 1 := by linarith
+    (mr₂ : b + c + 1 ≤ 3 * d) (mm₁ : b ≤ 3 * c) : b < 3 * a + 1 := by omega
 #align ordnode.valid'.node4_l_lemma₁ Ordnode.Valid'.node4L_lemma₁
 
-theorem Valid'.node4L_lemma₂ {b c d : ℕ} (mr₂ : b + c + 1 ≤ 3 * d) : c ≤ 3 * d := by linarith
+theorem Valid'.node4L_lemma₂ {b c d : ℕ} (mr₂ : b + c + 1 ≤ 3 * d) : c ≤ 3 * d := by omega
 #align ordnode.valid'.node4_l_lemma₂ Ordnode.Valid'.node4L_lemma₂
 
 theorem Valid'.node4L_lemma₃ {b c d : ℕ} (mr₁ : 2 * d ≤ b + c + 1) (mm₁ : b ≤ 3 * c) : d ≤ 3 * c :=
-  by linarith
+  by omega
 #align ordnode.valid'.node4_l_lemma₃ Ordnode.Valid'.node4L_lemma₃
 
 theorem Valid'.node4L_lemma₄ {a b c d : ℕ} (lr₁ : 3 * a ≤ b + c + 1 + d) (mr₂ : b + c + 1 ≤ 3 * d)
-    (mm₁ : b ≤ 3 * c) : a + b + 1 ≤ 3 * (c + d + 1) := by linarith
+    (mm₁ : b ≤ 3 * c) : a + b + 1 ≤ 3 * (c + d + 1) := by omega
 #align ordnode.valid'.node4_l_lemma₄ Ordnode.Valid'.node4L_lemma₄
 
 theorem Valid'.node4L_lemma₅ {a b c d : ℕ} (lr₂ : 3 * (b + c + 1 + d) ≤ 16 * a + 9)
-    (mr₁ : 2 * d ≤ b + c + 1) (mm₂ : c ≤ 3 * b) : c + d + 1 ≤ 3 * (a + b + 1) := by linarith
+    (mr₁ : 2 * d ≤ b + c + 1) (mm₂ : c ≤ 3 * b) : c + d + 1 ≤ 3 * (a + b + 1) := by omega
 #align ordnode.valid'.node4_l_lemma₅ Ordnode.Valid'.node4L_lemma₅
 
 theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hm : Valid' x m y)
@@ -1173,7 +1173,7 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
   rcases H with (⟨l0, m1, r0⟩ | ⟨l0, mr₁, lr₁, lr₂, mr₂⟩)
   · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1
     rw [l0, m1.1, m1.2]; revert r0; rcases size r with (_ | _ | _) <;>
-      [decide; decide; (intro r0; unfold BalancedSz delta; linarith)]
+      [decide; decide; (intro r0; unfold BalancedSz delta; omega)]
   · rcases Nat.eq_zero_or_pos (size r) with r0 | r0
     · rw [r0] at mr₂; cases not_le_of_lt Hm mr₂
     rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂
@@ -1216,19 +1216,19 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
 #align ordnode.valid'.node4_l Ordnode.Valid'.node4L
 
 theorem Valid'.rotateL_lemma₁ {a b c : ℕ} (H2 : 3 * a ≤ b + c) (hb₂ : c ≤ 3 * b) : a ≤ 3 * b := by
-  linarith
+  omega
 #align ordnode.valid'.rotate_l_lemma₁ Ordnode.Valid'.rotateL_lemma₁
 
 theorem Valid'.rotateL_lemma₂ {a b c : ℕ} (H3 : 2 * (b + c) ≤ 9 * a + 3) (h : b < 2 * c) :
-    b < 3 * a + 1 := by linarith
+    b < 3 * a + 1 := by omega
 #align ordnode.valid'.rotate_l_lemma₂ Ordnode.Valid'.rotateL_lemma₂
 
 theorem Valid'.rotateL_lemma₃ {a b c : ℕ} (H2 : 3 * a ≤ b + c) (h : b < 2 * c) : a + b < 3 * c :=
-  by linarith
+  by omega
 #align ordnode.valid'.rotate_l_lemma₃ Ordnode.Valid'.rotateL_lemma₃
 
 theorem Valid'.rotateL_lemma₄ {a b : ℕ} (H3 : 2 * b ≤ 9 * a + 3) : 3 * b ≤ 16 * a + 9 := by
-  linarith
+  omega
 #align ordnode.valid'.rotate_l_lemma₄ Ordnode.Valid'.rotateL_lemma₄
 
 theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : Valid' x r o₂)
@@ -1244,8 +1244,8 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
     exact
       (or_iff_right_of_imp fun h => (mul_le_mul_left (by decide)).1 (le_trans h (by decide))).1 H3
   have H3p : size l > 0 → 2 * (size rl + size rr) ≤ 9 * size l + 3 := fun l0 : 1 ≤ size l =>
-    (or_iff_left_of_imp <| by intro; linarith).1 H3
-  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros; linarith
+    (or_iff_left_of_imp <| by omega).1 H3
+  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by omega
   have hlp : size l > 0 → ¬size rl + size rr ≤ 1 := fun l0 hb =>
     absurd (le_trans (le_trans (Nat.mul_le_mul_left _ l0) H2) hb) (by decide)
   rw [Ordnode.rotateL]; split_ifs with h
@@ -1318,7 +1318,7 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
   suffices @size α r ≤ 3 * (size l + 1) by
     rcases Nat.eq_zero_or_pos (size l) with l0 | l0
     · apply Or.inr; rwa [l0] at this
-    change 1 ≤ _ at l0; apply Or.inl; linarith
+    change 1 ≤ _ at l0; apply Or.inl; omega
   rcases H2 with (⟨hl, rfl⟩ | ⟨hr, rfl⟩) <;> rcases H1 with (h | ⟨_, h₂⟩)
   · exact le_trans (Nat.le_add_left _ _) (le_trans h (Nat.le_add_left _ _))
   · exact
@@ -1326,7 +1326,7 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
         (Nat.mul_le_mul_left _ <| le_trans (Nat.dist_tri_right _ _) (Nat.add_le_add_left hl _))
   · exact
       le_trans (Nat.dist_tri_left' _ _)
-        (le_trans (add_le_add hr (le_trans (Nat.le_add_left _ _) h)) (by linarith))
+        (le_trans (add_le_add hr (le_trans (Nat.le_add_left _ _) h)) (by omega))
   · rw [Nat.mul_succ]
     exact le_trans (Nat.dist_tri_right' _ _) (add_le_add h₂ (le_trans hr (by decide)))
 #align ordnode.valid'.balance'_lemma Ordnode.Valid'.balance'_lemma
@@ -1355,7 +1355,7 @@ theorem Valid'.balanceL_aux {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (h
   · rw [r0]; exact Nat.zero_le _
   rcases Nat.eq_zero_or_pos (size l) with l0 | l0
   · rw [l0]; exact le_trans (Nat.mul_le_mul_left _ (H₁ l0)) (by decide)
-  replace H₂ : _ ≤ 3 * _ := H₂ l0 r0; linarith
+  replace H₂ : _ ≤ 3 * _ := H₂ l0 r0; omega
 #align ordnode.valid'.balance_l_aux Ordnode.Valid'.balanceL_aux
 
 theorem Valid'.balanceL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : Valid' x r o₂)
@@ -1455,7 +1455,7 @@ theorem Valid'.glue {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : Vali
 #align ordnode.valid'.glue Ordnode.Valid'.glue
 
 theorem Valid'.merge_lemma {a b c : ℕ} (h₁ : 3 * a < b + c + 1) (h₂ : b ≤ 3 * c) :
-    2 * (a + b) ≤ 9 * c + 5 := by linarith
+    2 * (a + b) ≤ 9 * c + 5 := by omega
 #align ordnode.valid'.merge_lemma Ordnode.Valid'.merge_lemma
 
 theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
@@ -1464,7 +1464,7 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
     Valid' o₁ (.balanceL t rx rr) o₂ ∧ size (.balanceL t rx rr) = ls + rs := by
   rw [hl.2.1] at e
   rw [hl.2.1, hr.2.1, delta] at h
-  rcases hr.3.1 with (H | ⟨hr₁, hr₂⟩); · linarith
+  rcases hr.3.1 with (H | ⟨hr₁, hr₂⟩); · omega
   suffices H₂ : _ by
     suffices H₁ : _ by
       refine' ⟨Valid'.balanceL_aux v hr.right H₁ H₂ _, _⟩
@@ -1473,7 +1473,7 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
           size_balance' v.2 hr.2.2.2, e, hl.2.1, hr.2.1]
         abel
     · rw [e, add_right_comm]; rintro ⟨⟩
-  · intro _ _; rw [e]; unfold delta at hr₂ ⊢; linarith
+  · intro _ _; rw [e]; unfold delta at hr₂ ⊢; omega
 #align ordnode.valid'.merge_aux₁ Ordnode.Valid'.merge_aux₁
 
 theorem Valid'.merge_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o₁ r o₂)

47b51515

chore: remove terminal, terminal refines (#10762)

I replaced a few "terminal" refine/refine's with exact.

The strategy was very simple-minded: essentially any refine whose following line had smaller indentation got replaced by exact and then I cleaned up the mess.

This PR certainly leaves some further terminal refines, but maybe the current change is beneficial.

ea36aa7d

Diff

@@ -1521,14 +1521,14 @@ theorem insertWith.valid_aux [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤
       suffices H : _ by
         refine' ⟨vl.balanceL h.right H, _⟩
         rw [size_balanceL vl.3 h.3.2.2 vl.2 h.2.2.2 H, h.2.size_eq]
-        refine' (e.add_right _).add_right _
+        exact (e.add_right _).add_right _
       · exact Or.inl ⟨_, e, h.3.1⟩
     · have : y < x := lt_of_le_not_le ((total_of (· ≤ ·) _ _).resolve_left h_1) h_1
       rcases insertWith.valid_aux f x hf h.right this br with ⟨vr, e⟩
       suffices H : _ by
         refine' ⟨h.left.balanceR vr H, _⟩
         rw [size_balanceR h.3.2.1 vr.3 h.2.2.1 vr.2 H, h.2.size_eq]
-        refine' (e.add_left _).add_right _
+        exact (e.add_left _).add_right _
       · exact Or.inr ⟨_, e, h.3.1⟩
 #align ordnode.insert_with.valid_aux Ordnode.insertWith.valid_aux

47b51515

feat: add lake exe shake to CI (#9751)

depends on: #9830
depends on: #9772
depends on: #9996

This checks files for unused imports. The output here is piped through gh-problem-matcher-wrap so that it will show up as annotations.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

056cc4b2

Diff

@@ -6,6 +6,7 @@ Authors: Mario Carneiro
 import Mathlib.Data.Ordmap.Ordnode
 import Mathlib.Algebra.Order.Ring.Defs
 import Mathlib.Data.Nat.Dist
+import Mathlib.Data.Int.Basic
 import Mathlib.Tactic.Linarith
 import Mathlib.Tactic.Abel

47b51515

chore: remove uses of cases' (#9171)

I literally went through and regex'd some uses of cases', replacing them with rcases; this is meant to be a low effort PR as I hope that tools can do this in the future.

rcases is an easier replacement than cases, though with better tools we could in future do a second pass converting simple rcases added here (and existing ones) to cases.

3fca282c

Diff

@@ -1173,7 +1173,7 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
   · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1
     rw [l0, m1.1, m1.2]; revert r0; rcases size r with (_ | _ | _) <;>
       [decide; decide; (intro r0; unfold BalancedSz delta; linarith)]
-  · cases' Nat.eq_zero_or_pos (size r) with r0 r0
+  · rcases Nat.eq_zero_or_pos (size r) with r0 | r0
     · rw [r0] at mr₂; cases not_le_of_lt Hm mr₂
     rw [hm.2.size_eq] at lr₁ lr₂ mr₁ mr₂
     by_cases mm : size ml + size mr ≤ 1
@@ -1193,7 +1193,7 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
       · rcases mm with (_ | ⟨⟨⟩⟩); decide
       · rw [Nat.succ_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
-    cases' Nat.eq_zero_or_pos (size ml) with ml0 ml0
+    rcases Nat.eq_zero_or_pos (size ml) with ml0 | ml0
     · rw [ml0, mul_zero, le_zero_iff] at mm₂
       rw [ml0, mm₂] at mm; cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 := by
@@ -1252,10 +1252,10 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
       (mul_lt_mul_left (by decide)).1 (lt_of_le_of_lt (Nat.zero_le _) h : ratio * 0 < _)
     suffices BalancedSz (size l) (size rl) ∧ BalancedSz (size l + size rl + 1) (size rr) by
       exact hl.node3L hr.left hr.right this.1 this.2
-    cases' Nat.eq_zero_or_pos (size l) with l0 l0
+    rcases Nat.eq_zero_or_pos (size l) with l0 | l0
     · rw [l0]; replace H3 := H3_0 l0
       have := hr.3.1
-      cases' Nat.eq_zero_or_pos (size rl) with rl0 rl0
+      rcases Nat.eq_zero_or_pos (size rl) with rl0 | rl0
       · rw [rl0] at this ⊢
         rw [le_antisymm (balancedSz_zero.1 this.symm) rr0]
         decide
@@ -1272,16 +1272,16 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
     · exact
         le_trans hb₂
           (Nat.mul_le_mul_left _ <| le_trans (Nat.le_add_left _ _) (Nat.le_add_right _ _))
-  · cases' Nat.eq_zero_or_pos (size rl) with rl0 rl0
+  · rcases Nat.eq_zero_or_pos (size rl) with rl0 | rl0
     · rw [rl0, not_lt, le_zero_iff, Nat.mul_eq_zero] at h
       replace h := h.resolve_left (by decide)
       erw [rl0, h, le_zero_iff, Nat.mul_eq_zero] at H2
       rw [hr.2.size_eq, rl0, h, H2.resolve_left (by decide)] at H1
       cases H1 (by decide)
     refine' hl.node4L hr.left hr.right rl0 _
-    cases' Nat.eq_zero_or_pos (size l) with l0 l0
+    rcases Nat.eq_zero_or_pos (size l) with l0 | l0
     · replace H3 := H3_0 l0
-      cases' Nat.eq_zero_or_pos (size rr) with rr0 rr0
+      rcases Nat.eq_zero_or_pos (size rr) with rr0 | rr0
       · have := hr.3.1
         rw [rr0] at this
         exact Or.inl ⟨l0, le_antisymm (balancedSz_zero.1 this) rl0, rr0.symm ▸ zero_le_one⟩
@@ -1315,7 +1315,7 @@ theorem Valid'.balance'_lemma {α l l' r r'} (H1 : BalancedSz l' r')
     (H2 : Nat.dist (@size α l) l' ≤ 1 ∧ size r = r' ∨ Nat.dist (size r) r' ≤ 1 ∧ size l = l') :
     2 * @size α r ≤ 9 * size l + 5 ∨ size r ≤ 3 := by
   suffices @size α r ≤ 3 * (size l + 1) by
-    cases' Nat.eq_zero_or_pos (size l) with l0 l0
+    rcases Nat.eq_zero_or_pos (size l) with l0 | l0
     · apply Or.inr; rwa [l0] at this
     change 1 ≤ _ at l0; apply Or.inl; linarith
   rcases H2 with (⟨hl, rfl⟩ | ⟨hr, rfl⟩) <;> rcases H1 with (h | ⟨_, h₂⟩)
@@ -1350,9 +1350,9 @@ theorem Valid'.balanceL_aux {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (h
     (H₃ : 2 * @size α l ≤ 9 * size r + 5 ∨ size l ≤ 3) : Valid' o₁ (@balanceL α l x r) o₂ := by
   rw [balanceL_eq_balance hl.2 hr.2 H₁ H₂, balance_eq_balance' hl.3 hr.3 hl.2 hr.2]
   refine' hl.balance'_aux hr (Or.inl _) H₃
-  cases' Nat.eq_zero_or_pos (size r) with r0 r0
+  rcases Nat.eq_zero_or_pos (size r) with r0 | r0
   · rw [r0]; exact Nat.zero_le _
-  cases' Nat.eq_zero_or_pos (size l) with l0 l0
+  rcases Nat.eq_zero_or_pos (size l) with l0 | l0
   · rw [l0]; exact le_trans (Nat.mul_le_mul_left _ (H₁ l0)) (by decide)
   replace H₂ : _ ≤ 3 * _ := H₂ l0 r0; linarith
 #align ordnode.valid'.balance_l_aux Ordnode.Valid'.balanceL_aux

47b51515

chore: Remove nonterminal simp at (#7795)

Removes nonterminal uses of simp at. Replaces most of these with instances of simp? ... says.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

4160b2aa

Diff

@@ -1774,7 +1774,8 @@ instance mem.decidable (x : α) (s : Ordset α) : Decidable (x ∈ s) :=
 #align ordset.mem.decidable Ordset.mem.decidable
 
 theorem pos_size_of_mem {x : α} {t : Ordset α} (h_mem : x ∈ t) : 0 < size t := by
-  simp [Membership.mem, mem] at h_mem
+  simp? [Membership.mem, mem] at h_mem says
+    simp only [Membership.mem, mem, Bool.decide_coe] at h_mem
   apply Ordnode.pos_size_of_mem t.property.sz h_mem
 #align ordset.pos_size_of_mem Ordset.pos_size_of_mem

47b51515

chore: bump toolchain to v4.3.0-rc1 (#8051)

This incorporates changes from

#7845
#7847
#7853
#7872 (was never actually made to work, but the diffs in nightly-testing are unexciting: we need to fully qualify a few names)

They can all be closed when this is merged.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

1ff3bf34

Diff

@@ -408,7 +408,7 @@ theorem Sized.dual_iff {t : Ordnode α} : Sized (.dual t) ↔ Sized t :=
 
 theorem Sized.rotateL {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (rotateL l x r) := by
   cases r; · exact hl.node' hr
-  rw [rotateL]; split_ifs
+  rw [Ordnode.rotateL]; split_ifs
   · exact hl.node3L hr.2.1 hr.2.2
   · exact hl.node4L hr.2.1 hr.2.2
 #align ordnode.sized.rotate_l Ordnode.Sized.rotateL
@@ -1247,7 +1247,7 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
   have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros; linarith
   have hlp : size l > 0 → ¬size rl + size rr ≤ 1 := fun l0 hb =>
     absurd (le_trans (le_trans (Nat.mul_le_mul_left _ l0) H2) hb) (by decide)
-  rw [rotateL]; split_ifs with h
+  rw [Ordnode.rotateL]; split_ifs with h
   · have rr0 : size rr > 0 :=
       (mul_lt_mul_left (by decide)).1 (lt_of_le_of_lt (Nat.zero_le _) h : ratio * 0 < _)
     suffices BalancedSz (size l) (size rl) ∧ BalancedSz (size l + size rl + 1) (size rr) by

47b51515

chore: remove nonterminal simp (#7580)

Removes nonterminal simps on lines looking like simp [...]

6fc8e6ec

Diff

@@ -420,7 +420,7 @@ theorem Sized.rotateR {l x r} (hl : @Sized α l) (hr : Sized r) : Sized (rotateR
 theorem Sized.rotateL_size {l x r} (hm : Sized r) :
     size (@Ordnode.rotateL α l x r) = size l + size r + 1 := by
   cases r <;> simp [Ordnode.rotateL]
-  simp [size, hm.1]
+  simp only [hm.1]
   split_ifs <;> simp [node3L_size, node4L_size hm.2.1] <;> abel
 #align ordnode.sized.rotate_l_size Ordnode.Sized.rotateL_size
 
@@ -1568,7 +1568,7 @@ theorem Valid'.map_aux {β} [Preorder β] {f : α → β} (f_strict_mono : Stric
     simp [map]; apply valid'_nil
     cases a₁; · trivial
     cases a₂; · trivial
-    simp [Bounded]
+    simp only [Bounded]
     exact f_strict_mono h.ord
   | node _ _ _ _ t_ih_l t_ih_r =>
     have t_ih_l' := t_ih_l h.left
@@ -1576,7 +1576,7 @@ theorem Valid'.map_aux {β} [Preorder β] {f : α → β} (f_strict_mono : Stric
     clear t_ih_l t_ih_r
     cases' t_ih_l' with t_l_valid t_l_size
     cases' t_ih_r' with t_r_valid t_r_size
-    simp [map]
+    simp only [map, size_node, and_true]
     constructor
     · exact And.intro t_l_valid.ord t_r_valid.ord
     · constructor
@@ -1602,7 +1602,7 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
   | nil =>
     simp [erase, Raised]; exact h
   | node _ t_l t_x t_r t_ih_l t_ih_r =>
-    simp [erase]
+    simp only [erase, size_node]
     have t_ih_l' := t_ih_l h.left
     have t_ih_r' := t_ih_r h.right
     clear t_ih_l t_ih_r

47b51515

chore: avoid lean3 style have/suffices (#6964)

Many proofs use the "stream of consciousness" style from Lean 3, rather than have ... := or suffices ... from/by.

This PR updates a fraction of these to the preferred Lean 4 style.

I think a good goal would be to delete the "deferred" versions of have, suffices, and let at the bottom of Mathlib.Tactic.Have

(Anyone who would like to contribute more cleanup is welcome to push directly to this branch.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

bdc47f68

Diff

@@ -1165,10 +1165,10 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
               3 * (size m + size r) ≤ 16 * size l + 9 ∧ size m ≤ delta * size r) :
     Valid' o₁ (@node4L α l x m y r) o₂ := by
   cases' m with s ml z mr; · cases Hm
-  suffices :
+  suffices
     BalancedSz (size l) (size ml) ∧
-      BalancedSz (size mr) (size r) ∧ BalancedSz (size l + size ml + 1) (size mr + size r + 1)
-  exact Valid'.node' (hl.node' hm.left this.1) (hm.right.node' hr this.2.1) this.2.2
+      BalancedSz (size mr) (size r) ∧ BalancedSz (size l + size ml + 1) (size mr + size r + 1) from
+    Valid'.node' (hl.node' hm.left this.1) (hm.right.node' hr this.2.1) this.2.2
   rcases H with (⟨l0, m1, r0⟩ | ⟨l0, mr₁, lr₁, lr₂, mr₂⟩)
   · rw [hm.2.size_eq, Nat.succ_inj', add_eq_zero_iff] at m1
     rw [l0, m1.1, m1.2]; revert r0; rcases size r with (_ | _ | _) <;>
@@ -1422,29 +1422,29 @@ theorem Valid'.glue_aux {l r o₁ o₂} (hl : Valid' o₁ l o₂) (hr : Valid' o
   dsimp [glue]; split_ifs
   · rw [splitMax_eq]
     cases' Valid'.eraseMax_aux hl with v e
-    suffices H
-    refine' ⟨Valid'.balanceR v (hr.of_gt _ _) H, _⟩
-    · refine' findMax'_all (P := fun a : α => Bounded nil (a : WithTop α) o₂)
-        lx lr hl.1.2.to_nil (sep.2.2.imp _)
-      exact fun x h => hr.1.2.to_nil.mono_left (le_of_lt h.2.1)
-    · exact @findMax'_all _ (fun a => All (· > a) (.node rs rl rx rr)) lx lr sep.2.1 sep.2.2
-    · rw [size_balanceR v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
-    · refine' Or.inl ⟨_, Or.inr e, _⟩
-      rwa [hl.2.eq_node'] at bal
+    suffices H : _ by
+      refine' ⟨Valid'.balanceR v (hr.of_gt _ _) H, _⟩
+      · refine' findMax'_all (P := fun a : α => Bounded nil (a : WithTop α) o₂)
+          lx lr hl.1.2.to_nil (sep.2.2.imp _)
+        exact fun x h => hr.1.2.to_nil.mono_left (le_of_lt h.2.1)
+      · exact @findMax'_all _ (fun a => All (· > a) (.node rs rl rx rr)) lx lr sep.2.1 sep.2.2
+      · rw [size_balanceR v.3 hr.3 v.2 hr.2 H, add_right_comm, ← e, hl.2.1]; rfl
+    refine' Or.inl ⟨_, Or.inr e, _⟩
+    rwa [hl.2.eq_node'] at bal
   · rw [splitMin_eq]
     cases' Valid'.eraseMin_aux hr with v e
-    suffices H
-    refine' ⟨Valid'.balanceL (hl.of_lt _ _) v H, _⟩
-    · refine' @findMin'_all (P := fun a : α => Bounded nil o₁ (a : WithBot α))
-        rl rx (sep.2.1.1.imp _) hr.1.1.to_nil
-      exact fun y h => hl.1.1.to_nil.mono_right (le_of_lt h)
-    · exact
-        @findMin'_all _ (fun a => All (· < a) (.node ls ll lx lr)) rl rx
-          (all_iff_forall.2 fun x hx => sep.imp fun y hy => all_iff_forall.1 hy.1 _ hx)
-          (sep.imp fun y hy => hy.2.1)
-    · rw [size_balanceL hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
-    · refine' Or.inr ⟨_, Or.inr e, _⟩
-      rwa [hr.2.eq_node'] at bal
+    suffices H : _ by
+      refine' ⟨Valid'.balanceL (hl.of_lt _ _) v H, _⟩
+      · refine' @findMin'_all (P := fun a : α => Bounded nil o₁ (a : WithBot α))
+          rl rx (sep.2.1.1.imp _) hr.1.1.to_nil
+        exact fun y h => hl.1.1.to_nil.mono_right (le_of_lt h)
+      · exact
+          @findMin'_all _ (fun a => All (· < a) (.node ls ll lx lr)) rl rx
+            (all_iff_forall.2 fun x hx => sep.imp fun y hy => all_iff_forall.1 hy.1 _ hx)
+            (sep.imp fun y hy => hy.2.1)
+      · rw [size_balanceL hl.3 v.3 hl.2 v.2 H, add_assoc, ← e, hr.2.1]; rfl
+    refine' Or.inr ⟨_, Or.inr e, _⟩
+    rwa [hr.2.eq_node'] at bal
 #align ordnode.valid'.glue_aux Ordnode.Valid'.glue_aux
 
 theorem Valid'.glue {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : Valid' x r o₂) :
@@ -1464,13 +1464,14 @@ theorem Valid'.merge_aux₁ {o₁ o₂ ls ll lx lr rs rl rx rr t}
   rw [hl.2.1] at e
   rw [hl.2.1, hr.2.1, delta] at h
   rcases hr.3.1 with (H | ⟨hr₁, hr₂⟩); · linarith
-  suffices H₂; suffices H₁
-  refine' ⟨Valid'.balanceL_aux v hr.right H₁ H₂ _, _⟩
-  · rw [e]; exact Or.inl (Valid'.merge_lemma h hr₁)
-  · rw [balanceL_eq_balance v.2 hr.2.2.2 H₁ H₂, balance_eq_balance' v.3 hr.3.2.2 v.2 hr.2.2.2,
-      size_balance' v.2 hr.2.2.2, e, hl.2.1, hr.2.1]
-    abel
-  · rw [e, add_right_comm]; rintro ⟨⟩
+  suffices H₂ : _ by
+    suffices H₁ : _ by
+      refine' ⟨Valid'.balanceL_aux v hr.right H₁ H₂ _, _⟩
+      · rw [e]; exact Or.inl (Valid'.merge_lemma h hr₁)
+      · rw [balanceL_eq_balance v.2 hr.2.2.2 H₁ H₂, balance_eq_balance' v.3 hr.3.2.2 v.2 hr.2.2.2,
+          size_balance' v.2 hr.2.2.2, e, hl.2.1, hr.2.1]
+        abel
+    · rw [e, add_right_comm]; rintro ⟨⟩
   · intro _ _; rw [e]; unfold delta at hr₂ ⊢; linarith
 #align ordnode.valid'.merge_aux₁ Ordnode.Valid'.merge_aux₁
 
@@ -1516,15 +1517,15 @@ theorem insertWith.valid_aux [IsTotal α (· ≤ ·)] [@DecidableRel α (· ≤
       refine'
         ⟨⟨⟨lx.mono_right (le_trans h_2 xf), xr.mono_left (le_trans fx h_1)⟩, hs, hb⟩, Or.inl rfl⟩
     · rcases insertWith.valid_aux f x hf h.left bl (lt_of_le_not_le h_1 h_2) with ⟨vl, e⟩
-      suffices H
-      · refine' ⟨vl.balanceL h.right H, _⟩
+      suffices H : _ by
+        refine' ⟨vl.balanceL h.right H, _⟩
         rw [size_balanceL vl.3 h.3.2.2 vl.2 h.2.2.2 H, h.2.size_eq]
         refine' (e.add_right _).add_right _
       · exact Or.inl ⟨_, e, h.3.1⟩
     · have : y < x := lt_of_le_not_le ((total_of (· ≤ ·) _ _).resolve_left h_1) h_1
       rcases insertWith.valid_aux f x hf h.right this br with ⟨vr, e⟩
-      suffices H
-      · refine' ⟨h.left.balanceR vr H, _⟩
+      suffices H : _ by
+        refine' ⟨h.left.balanceR vr H, _⟩
         rw [size_balanceR h.3.2.1 vr.3 h.2.2.1 vr.2 H, h.2.size_eq]
         refine' (e.add_left _).add_right _
       · exact Or.inr ⟨_, e, h.3.1⟩
@@ -1608,25 +1609,25 @@ theorem Valid'.erase_aux [@DecidableRel α (· ≤ ·)] (x : α) {t a₁ a₂} (
     cases' t_ih_l' with t_l_valid t_l_size
     cases' t_ih_r' with t_r_valid t_r_size
     cases cmpLE x t_x <;> rw [h.sz.1]
-    · suffices h_balanceable
-      constructor
-      · exact Valid'.balanceR t_l_valid h.right h_balanceable
-      · rw [size_balanceR t_l_valid.bal h.right.bal t_l_valid.sz h.right.sz h_balanceable]
-        repeat apply Raised.add_right
-        exact t_l_size
+    · suffices h_balanceable : _ by
+        constructor
+        · exact Valid'.balanceR t_l_valid h.right h_balanceable
+        · rw [size_balanceR t_l_valid.bal h.right.bal t_l_valid.sz h.right.sz h_balanceable]
+          repeat apply Raised.add_right
+          exact t_l_size
       · left; exists t_l.size; exact And.intro t_l_size h.bal.1
     · have h_glue := Valid'.glue h.left h.right h.bal.1
       cases' h_glue with h_glue_valid h_glue_sized
       constructor
       · exact h_glue_valid
       · right; rw [h_glue_sized]
-    · suffices h_balanceable
-      constructor
-      · exact Valid'.balanceL h.left t_r_valid h_balanceable
-      · rw [size_balanceL h.left.bal t_r_valid.bal h.left.sz t_r_valid.sz h_balanceable]
-        apply Raised.add_right
-        apply Raised.add_left
-        exact t_r_size
+    · suffices h_balanceable : _ by
+        constructor
+        · exact Valid'.balanceL h.left t_r_valid h_balanceable
+        · rw [size_balanceL h.left.bal t_r_valid.bal h.left.sz t_r_valid.sz h_balanceable]
+          apply Raised.add_right
+          apply Raised.add_left
+          exact t_r_size
       · right; exists t_r.size; exact And.intro t_r_size h.bal.1
 #align ordnode.valid'.erase_aux Ordnode.Valid'.erase_aux

47b51515

feat: add some symm attributes throughout the library (#6708)

Also add a couple of refl and trans attributes

20d6b8e6

Diff

@@ -187,6 +187,7 @@ instance Balanced.dec : DecidablePred (@Balanced α)
     infer_instance
 #align ordnode.balanced.dec Ordnode.Balanced.dec
 
+@[symm]
 theorem BalancedSz.symm {l r : ℕ} : BalancedSz l r → BalancedSz r l :=
   Or.imp (by rw [add_comm]; exact id) And.symm
 #align ordnode.balanced_sz.symm Ordnode.BalancedSz.symm

47b51515

chore: drop MulZeroClass. in mul_zero/zero_mul (#6682)

Search&replace MulZeroClass.mul_zero -> mul_zero, MulZeroClass.zero_mul -> zero_mul.

These were introduced by Mathport, as the full name of mul_zero is actually MulZeroClass.mul_zero (it's exported with the short name).

277dea95

Diff

@@ -1193,7 +1193,7 @@ theorem Valid'.node4L {l} {x : α} {m} {y : α} {r o₁ o₂} (hl : Valid' o₁
       · rw [Nat.succ_add] at mm; rcases mm with (_ | ⟨⟨⟩⟩)
     rcases hm.3.1.resolve_left mm with ⟨mm₁, mm₂⟩
     cases' Nat.eq_zero_or_pos (size ml) with ml0 ml0
-    · rw [ml0, MulZeroClass.mul_zero, le_zero_iff] at mm₂
+    · rw [ml0, mul_zero, le_zero_iff] at mm₂
       rw [ml0, mm₂] at mm; cases mm (by decide)
     have : 2 * size l ≤ size ml + size mr + 1 := by
       have := Nat.mul_le_mul_left ratio lr₁

47b51515

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -68,7 +68,7 @@ ordered map, ordered set, data structure, verified programming
 -/
 
 
-variable {α : Type _}
+variable {α : Type*}
 
 namespace Ordnode
 
@@ -1678,7 +1678,7 @@ end Ordnode
 maintain that the tree is balanced and correctly stores subtree sizes at each level. The
 correctness property of the tree is baked into the type, so all operations on this type are correct
 by construction. -/
-def Ordset (α : Type _) [Preorder α] :=
+def Ordset (α : Type*) [Preorder α] :=
   { t : Ordnode α // t.Valid }
 #align ordset Ordset

47b51515

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.ordmap.ordset
-! leanprover-community/mathlib commit 47b51515e69f59bca5cf34ef456e6000fe205a69
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Ordmap.Ordnode
 import Mathlib.Algebra.Order.Ring.Defs
@@ -14,6 +9,8 @@ import Mathlib.Data.Nat.Dist
 import Mathlib.Tactic.Linarith
 import Mathlib.Tactic.Abel
 
+#align_import data.ordmap.ordset from "leanprover-community/mathlib"@"47b51515e69f59bca5cf34ef456e6000fe205a69"
+
 /-!
 # Verification of the `Ordnode α` datatype

47b51515

chore: cleanup whitespace (#5988)

Grepping for [^ .:{-] [^ :] and reviewing the results. Once I started I couldn't stop. :-)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

12343aa5

Diff

@@ -1341,7 +1341,7 @@ theorem Valid'.balance' {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr :
 #align ordnode.valid'.balance' Ordnode.Valid'.balance'
 
 theorem Valid'.balance {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : Valid' x r o₂)
-    (H : ∃ l' r',  BalancedSz l' r' ∧
+    (H : ∃ l' r', BalancedSz l' r' ∧
           (Nat.dist (size l) l' ≤ 1 ∧ size r = r' ∨ Nat.dist (size r) r' ≤ 1 ∧ size l = l')) :
     Valid' o₁ (@balance α l x r) o₂ := by
   rw [balance_eq_balance' hl.3 hr.3 hl.2 hr.2]; exact hl.balance' hr H

47b51515

chore: remove occurrences of semicolon after space (#5713)

This is the second half of the changes originally in #5699, removing all occurrences of ; after a space and implementing a linter rule to enforce it.

In most cases this 2-character substring has a space after it, so the following command was run first:

find . -type f -name "*.lean" -exec sed -i -E 's/ ; /; /g' {} \;

The remaining cases were few enough in number that they were done manually.

c795bd35

Diff

@@ -1246,7 +1246,7 @@ theorem Valid'.rotateL {l} {x : α} {r o₁ o₂} (hl : Valid' o₁ l x) (hr : V
       (or_iff_right_of_imp fun h => (mul_le_mul_left (by decide)).1 (le_trans h (by decide))).1 H3
   have H3p : size l > 0 → 2 * (size rl + size rr) ≤ 9 * size l + 3 := fun l0 : 1 ≤ size l =>
     (or_iff_left_of_imp <| by intro; linarith).1 H3
-  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros ; linarith
+  have ablem : ∀ {a b : ℕ}, 1 ≤ a → a + b ≤ 2 → b ≤ 1 := by intros; linarith
   have hlp : size l > 0 → ¬size rl + size rr ≤ 1 := fun l0 hb =>
     absurd (le_trans (le_trans (Nat.mul_le_mul_left _ l0) H2) hb) (by decide)
   rw [rotateL]; split_ifs with h

47b51515

feat: port Data.Ordmap.Ordset (#4541)

2afe8cb1

`data.ordmap.ordset` ⟷ `Mathlib.Data.Ordmap.Ordset`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 1 + 74

data.ordmap.ordset ⟷ Mathlib.Data.Ordmap.Ordset

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 1 + 74

`data.ordmap.ordset` ⟷ `Mathlib.Data.Ordmap.Ordset`