[GOAL]
α : Type uu
r : α → α → Prop
a : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p : l₁ ~ l₂
s₁ : Sorted r l₁
s₂ : Sorted r l₂
⊢ l₁ = l₂
[PROOFSTEP]
induction' s₁ with a l₁ h₁ s₁ IH generalizing l₂
[GOAL]
case nil
α : Type uu
r : α → α → Prop
a : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂✝ : List α
p✝ : l₁ ~ l₂✝
s₂✝ : Sorted r l₂✝
l₂ : List α
p : [] ~ l₂
s₂ : Sorted r l₂
⊢ [] = l₂
[PROOFSTEP]
exact p.nil_eq
[GOAL]
case cons
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁✝ l₂✝ : List α
p✝ : l₁✝ ~ l₂✝
s₂✝ : Sorted r l₂✝
a : α
l₁ : List α
h₁ : ∀ (a' : α), a' ∈ l₁ → r a a'
s₁ : Pairwise r l₁
IH : ∀ {l₂ : List α}, l₁ ~ l₂ → Sorted r l₂ → l₁ = l₂
l₂ : List α
p : a :: l₁ ~ l₂
s₂ : Sorted r l₂
⊢ a :: l₁ = l₂
[PROOFSTEP]
have : a ∈ l₂ := p.subset (mem_cons_self _ _)
[GOAL]
case cons
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁✝ l₂✝ : List α
p✝ : l₁✝ ~ l₂✝
s₂✝ : Sorted r l₂✝
a : α
l₁ : List α
h₁ : ∀ (a' : α), a' ∈ l₁ → r a a'
s₁ : Pairwise r l₁
IH : ∀ {l₂ : List α}, l₁ ~ l₂ → Sorted r l₂ → l₁ = l₂
l₂ : List α
p : a :: l₁ ~ l₂
s₂ : Sorted r l₂
this : a ∈ l₂
⊢ a :: l₁ = l₂
[PROOFSTEP]
rcases mem_split this with ⟨u₂, v₂, rfl⟩
[GOAL]
case cons.intro.intro
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁✝ l₂ : List α
p✝ : l₁✝ ~ l₂
s₂✝ : Sorted r l₂
a : α
l₁ : List α
h₁ : ∀ (a' : α), a' ∈ l₁ → r a a'
s₁ : Pairwise r l₁
IH : ∀ {l₂ : List α}, l₁ ~ l₂ → Sorted r l₂ → l₁ = l₂
u₂ v₂ : List α
p : a :: l₁ ~ u₂ ++ a :: v₂
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
⊢ a :: l₁ = u₂ ++ a :: v₂
[PROOFSTEP]
have p' := (perm_cons a).1 (p.trans perm_middle)
[GOAL]
case cons.intro.intro
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁✝ l₂ : List α
p✝ : l₁✝ ~ l₂
s₂✝ : Sorted r l₂
a : α
l₁ : List α
h₁ : ∀ (a' : α), a' ∈ l₁ → r a a'
s₁ : Pairwise r l₁
IH : ∀ {l₂ : List α}, l₁ ~ l₂ → Sorted r l₂ → l₁ = l₂
u₂ v₂ : List α
p : a :: l₁ ~ u₂ ++ a :: v₂
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
p' : l₁ ~ u₂ ++ v₂
⊢ a :: l₁ = u₂ ++ a :: v₂
[PROOFSTEP]
obtain rfl := IH p' (s₂.sublist <| by simp)
[GOAL]
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁✝ l₂ : List α
p✝ : l₁✝ ~ l₂
s₂✝ : Sorted r l₂
a : α
l₁ : List α
h₁ : ∀ (a' : α), a' ∈ l₁ → r a a'
s₁ : Pairwise r l₁
IH : ∀ {l₂ : List α}, l₁ ~ l₂ → Sorted r l₂ → l₁ = l₂
u₂ v₂ : List α
p : a :: l₁ ~ u₂ ++ a :: v₂
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
p' : l₁ ~ u₂ ++ v₂
⊢ u₂ ++ v₂ <+ u₂ ++ a :: v₂
[PROOFSTEP]
simp
[GOAL]
case cons.intro.intro
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
⊢ a :: (u₂ ++ v₂) = u₂ ++ a :: v₂
[PROOFSTEP]
change a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂)
[GOAL]
case cons.intro.intro
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
⊢ a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂)
[PROOFSTEP]
rw [← append_assoc]
[GOAL]
case cons.intro.intro
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
⊢ a :: u₂ ++ v₂ = u₂ ++ [a] ++ v₂
[PROOFSTEP]
congr
[GOAL]
case cons.intro.intro.e_a
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
⊢ a :: u₂ = u₂ ++ [a]
[PROOFSTEP]
have : ∀ (x : α) (_ : x ∈ u₂), x = a := fun x m =>
  antisymm ((pairwise_append.1 s₂).2.2 _ m a (mem_cons_self _ _)) (h₁ _ (by simp [m]))
[GOAL]
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
x : α
m : x ∈ u₂
⊢ x ∈ u₂ ++ v₂
[PROOFSTEP]
simp [m]
[GOAL]
case cons.intro.intro.e_a
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ a :: u₂ = u₂ ++ [a]
[PROOFSTEP]
rw [(@eq_replicate _ a (length u₂ + 1) (a :: u₂)).2, (@eq_replicate _ a (length u₂ + 1) (u₂ ++ [a])).2]
[GOAL]
case cons.intro.intro.e_a
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ length (u₂ ++ [a]) = length u₂ + 1 ∧ ∀ (b : α), b ∈ u₂ ++ [a] → b = a
[PROOFSTEP]
constructor
[GOAL]
case cons.intro.intro.e_a
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ length (a :: u₂) = length u₂ + 1 ∧ ∀ (b : α), b ∈ a :: u₂ → b = a
[PROOFSTEP]
constructor
[GOAL]
case cons.intro.intro.e_a.left
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ length (u₂ ++ [a]) = length u₂ + 1
[PROOFSTEP]
simp [iff_true_intro this, or_comm]
[GOAL]
case cons.intro.intro.e_a.right
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ ∀ (b : α), b ∈ u₂ ++ [a] → b = a
[PROOFSTEP]
simp [iff_true_intro this, or_comm]
[GOAL]
case cons.intro.intro.e_a.left
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ length (a :: u₂) = length u₂ + 1
[PROOFSTEP]
simp [iff_true_intro this, or_comm]
[GOAL]
case cons.intro.intro.e_a.right
α : Type uu
r : α → α → Prop
a✝ : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p✝ : l₁ ~ l₂
s₂✝ : Sorted r l₂
a : α
u₂ v₂ : List α
s₂ : Sorted r (u₂ ++ a :: v₂)
this✝ : a ∈ u₂ ++ a :: v₂
h₁ : ∀ (a' : α), a' ∈ u₂ ++ v₂ → r a a'
s₁ : Pairwise r (u₂ ++ v₂)
IH : ∀ {l₂ : List α}, u₂ ++ v₂ ~ l₂ → Sorted r l₂ → u₂ ++ v₂ = l₂
p : a :: (u₂ ++ v₂) ~ u₂ ++ a :: v₂
p' : u₂ ++ v₂ ~ u₂ ++ v₂
this : ∀ (x : α), x ∈ u₂ → x = a
⊢ ∀ (b : α), b ∈ a :: u₂ → b = a
[PROOFSTEP]
simp [iff_true_intro this, or_comm]
[GOAL]
α : Type uu
r : α → α → Prop
a : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p : l₁ <+~ l₂
s₁ : Sorted r l₁
s₂ : Sorted r l₂
⊢ l₁ <+ l₂
[PROOFSTEP]
let ⟨_, h, h'⟩ := p
[GOAL]
α : Type uu
r : α → α → Prop
a : α
l : List α
inst✝ : IsAntisymm α r
l₁ l₂ : List α
p : l₁ <+~ l₂
s₁ : Sorted r l₁
s₂ : Sorted r l₂
w✝ : List α
h : w✝ ~ l₁
h' : w✝ <+ l₂
⊢ l₁ <+ l₂
[PROOFSTEP]
rwa [← eq_of_perm_of_sorted h (s₂.sublist h') s₁]
[GOAL]
α : Type uu
r : α → α → Prop
a✝ : α
l✝ : List α
inst✝ : IsRefl α r
l : List α
h : Sorted r l
a b : Fin (length l)
hab : a ≤ b
⊢ r (get l a) (get l b)
[PROOFSTEP]
rcases hab.eq_or_lt with (rfl | hlt)
[GOAL]
case inl
α : Type uu
r : α → α → Prop
a✝ : α
l✝ : List α
inst✝ : IsRefl α r
l : List α
h : Sorted r l
a : Fin (length l)
hab : a ≤ a
⊢ r (get l a) (get l a)
case inr
α : Type uu
r : α → α → Prop
a✝ : α
l✝ : List α
inst✝ : IsRefl α r
l : List α
h : Sorted r l
a b : Fin (length l)
hab : a ≤ b
hlt : a < b
⊢ r (get l a) (get l b)
[PROOFSTEP]
exacts [refl _, h.rel_get_of_lt hlt]
[GOAL]
α : Type uu
r : α → α → Prop
a : α
l✝ l : List α
h : Sorted r l
k : ℕ
x y : α
hx : x ∈ take k l
hy : y ∈ drop k l
⊢ r x y
[PROOFSTEP]
obtain ⟨⟨iy, hiy⟩, rfl⟩ := get_of_mem hy
[GOAL]
case intro.mk
α : Type uu
r : α → α → Prop
a : α
l✝ l : List α
h : Sorted r l
k : ℕ
x : α
hx : x ∈ take k l
iy : ℕ
hiy : iy < length (drop k l)
hy : get (drop k l) { val := iy, isLt := hiy } ∈ drop k l
⊢ r x (get (drop k l) { val := iy, isLt := hiy })
[PROOFSTEP]
obtain ⟨⟨ix, hix⟩, rfl⟩ := get_of_mem hx
[GOAL]
case intro.mk.intro.mk
α : Type uu
r : α → α → Prop
a : α
l✝ l : List α
h : Sorted r l
k iy : ℕ
hiy : iy < length (drop k l)
hy : get (drop k l) { val := iy, isLt := hiy } ∈ drop k l
ix : ℕ
hix : ix < length (take k l)
hx : get (take k l) { val := ix, isLt := hix } ∈ take k l
⊢ r (get (take k l) { val := ix, isLt := hix }) (get (drop k l) { val := iy, isLt := hiy })
[PROOFSTEP]
rw [get_take', get_drop']
[GOAL]
case intro.mk.intro.mk
α : Type uu
r : α → α → Prop
a : α
l✝ l : List α
h : Sorted r l
k iy : ℕ
hiy : iy < length (drop k l)
hy : get (drop k l) { val := iy, isLt := hiy } ∈ drop k l
ix : ℕ
hix : ix < length (take k l)
hx : get (take k l) { val := ix, isLt := hix } ∈ take k l
⊢ r (get l { val := ↑{ val := ix, isLt := hix }, isLt := (_ : ↑{ val := ix, isLt := hix } < length l) })
    (get l { val := k + ↑{ val := iy, isLt := hiy }, isLt := (_ : k + ↑{ val := iy, isLt := hiy } < length l) })
[PROOFSTEP]
rw [length_take] at hix 
[GOAL]
case intro.mk.intro.mk
α : Type uu
r : α → α → Prop
a : α
l✝ l : List α
h : Sorted r l
k iy : ℕ
hiy : iy < length (drop k l)
hy : get (drop k l) { val := iy, isLt := hiy } ∈ drop k l
ix : ℕ
hix✝ : ix < length (take k l)
hix : ix < min k (length l)
hx : get (take k l) { val := ix, isLt := hix✝ } ∈ take k l
⊢ r (get l { val := ↑{ val := ix, isLt := hix✝ }, isLt := (_ : ↑{ val := ix, isLt := hix✝ } < length l) })
    (get l { val := k + ↑{ val := iy, isLt := hiy }, isLt := (_ : k + ↑{ val := iy, isLt := hiy } < length l) })
[PROOFSTEP]
exact h.rel_nthLe_of_lt _ _ (ix.lt_add_right _ _ (lt_min_iff.mp hix).left)
[GOAL]
n : ℕ
α : Type uu
inst✝ : Preorder α
f : Fin n → α
r : α → α → Prop
⊢ Sorted r (ofFn f) ↔ ((fun x x_1 => x < x_1) ⇒ r) f f
[PROOFSTEP]
simp_rw [Sorted, pairwise_iff_get, get_ofFn, Relator.LiftFun]
[GOAL]
n : ℕ
α : Type uu
inst✝ : Preorder α
f : Fin n → α
r : α → α → Prop
⊢ (∀ (i j : Fin (length (ofFn f))),
      i < j → r (f (↑(Fin.castIso (_ : length (ofFn f) = n)) i)) (f (↑(Fin.castIso (_ : length (ofFn f) = n)) j))) ↔
    ∀ ⦃a b : Fin n⦄, a < b → r (f a) (f b)
[PROOFSTEP]
exact Iff.symm (Fin.castIso _).surjective.forall₂
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
hd : α
tl : List α
a : α
⊢ length (orderedInsert r a (hd :: tl)) = length (hd :: tl) + 1
[PROOFSTEP]
dsimp [orderedInsert]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
hd : α
tl : List α
a : α
⊢ length (if r a hd then a :: hd :: tl else hd :: orderedInsert r a tl) = Nat.succ (length tl) + 1
[PROOFSTEP]
split_ifs
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
hd : α
tl : List α
a : α
h✝ : r a hd
⊢ length (a :: hd :: tl) = Nat.succ (length tl) + 1
[PROOFSTEP]
simp [orderedInsert_length tl]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
hd : α
tl : List α
a : α
h✝ : ¬r a hd
⊢ length (hd :: orderedInsert r a tl) = Nat.succ (length tl) + 1
[PROOFSTEP]
simp [orderedInsert_length tl]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
⊢ orderedInsert r a (b :: l) =
    takeWhile (fun b => decide ¬r a b) (b :: l) ++ a :: dropWhile (fun b => decide ¬r a b) (b :: l)
[PROOFSTEP]
dsimp only [orderedInsert]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
⊢ (if r a b then a :: b :: l else b :: orderedInsert r a l) =
    takeWhile (fun b => decide ¬r a b) (b :: l) ++ a :: dropWhile (fun b => decide ¬r a b) (b :: l)
[PROOFSTEP]
split_ifs with h
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
h : r a b
⊢ a :: b :: l = takeWhile (fun b => decide ¬r a b) (b :: l) ++ a :: dropWhile (fun b => decide ¬r a b) (b :: l)
[PROOFSTEP]
simp [takeWhile, dropWhile, *, orderedInsert_eq_take_drop a l]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
h : ¬r a b
⊢ b :: orderedInsert r a l =
    takeWhile (fun b => decide ¬r a b) (b :: l) ++ a :: dropWhile (fun b => decide ¬r a b) (b :: l)
[PROOFSTEP]
simp [takeWhile, dropWhile, *, orderedInsert_eq_take_drop a l]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
⊢ orderedInsert r a (b :: l) ~ a :: b :: l
[PROOFSTEP]
by_cases h : a ≼ b
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
h : r a b
⊢ orderedInsert r a (b :: l) ~ a :: b :: l
[PROOFSTEP]
simp [orderedInsert, h]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
h : ¬r a b
⊢ orderedInsert r a (b :: l) ~ a :: b :: l
[PROOFSTEP]
simpa [orderedInsert, h] using ((perm_orderedInsert a l).cons _).trans (Perm.swap _ _ _)
[GOAL]
α : Type uu
r : α → α → Prop
inst✝¹ : DecidableRel r
inst✝ : DecidableEq α
L : List α
a b : α
⊢ count a (orderedInsert r b L) = count a L + if a = b then 1 else 0
[PROOFSTEP]
rw [(L.perm_orderedInsert r b).count_eq, count_cons]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝¹ : DecidableRel r
inst✝ : DecidableEq α
L : List α
a b : α
⊢ (if a = b then Nat.succ (count a L) else count a L) = count a L + if a = b then 1 else 0
[PROOFSTEP]
split_ifs
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝¹ : DecidableRel r
inst✝ : DecidableEq α
L : List α
a b : α
h✝ : a = b
⊢ Nat.succ (count a L) = count a L + 1
[PROOFSTEP]
simp only [Nat.succ_eq_add_one, add_zero]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝¹ : DecidableRel r
inst✝ : DecidableEq α
L : List α
a b : α
h✝ : ¬a = b
⊢ count a L = count a L + 0
[PROOFSTEP]
simp only [Nat.succ_eq_add_one, add_zero]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
b : α
l : List α
⊢ insertionSort r (b :: l) ~ b :: l
[PROOFSTEP]
simpa [insertionSort] using (perm_orderedInsert _ _ _).trans ((perm_insertionSort l).cons b)
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
h : Sorted r (a :: b :: l)
⊢ insertionSort r (a :: b :: l) = a :: b :: l
[PROOFSTEP]
rw [insertionSort, Sorted.insertionSort_eq, orderedInsert, if_pos]
[GOAL]
case hc
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
h : Sorted r (a :: b :: l)
⊢ r a b
α : Type uu r : α → α → Prop inst✝ : DecidableRel r a b : α l : List α h : Sorted r (a :: b :: l) ⊢ Sorted r (b :: l)
[PROOFSTEP]
exacts [rel_of_sorted_cons h _ (mem_cons_self _ _), h.tail]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
⊢ Sorted r (List.orderedInsert r a (b :: l))
[PROOFSTEP]
by_cases h' : a ≼ b
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : r a b
⊢ Sorted r (List.orderedInsert r a (b :: l))
[PROOFSTEP]
rw [List.orderedInsert, if_pos h', sorted_cons]
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : r a b
⊢ (∀ (b_1 : α), b_1 ∈ b :: l → r a b_1) ∧ Sorted r (b :: l)
[PROOFSTEP]
exact ⟨forall_mem_cons.2 ⟨h', fun c hc => _root_.trans h' (rel_of_sorted_cons h _ hc)⟩, h⟩
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
⊢ Sorted r (List.orderedInsert r a (b :: l))
[PROOFSTEP]
suffices ∀ b' : α, b' ∈ List.orderedInsert r a l → r b b' by simpa [orderedInsert, h', h.of_cons.orderedInsert a l]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
this : ∀ (b' : α), b' ∈ List.orderedInsert r a l → r b b'
⊢ Sorted r (List.orderedInsert r a (b :: l))
[PROOFSTEP]
simpa [orderedInsert, h', h.of_cons.orderedInsert a l]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
⊢ ∀ (b' : α), b' ∈ List.orderedInsert r a l → r b b'
[PROOFSTEP]
intro b' bm
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
b' : α
bm : b' ∈ List.orderedInsert r a l
⊢ r b b'
[PROOFSTEP]
cases' show b' = a ∨ b' ∈ l by simpa using (perm_orderedInsert _ _ _).subset bm with be bm
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
b' : α
bm : b' ∈ List.orderedInsert r a l
⊢ b' = a ∨ b' ∈ l
[PROOFSTEP]
simpa using (perm_orderedInsert _ _ _).subset bm
[GOAL]
case neg.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
b' : α
bm : b' ∈ List.orderedInsert r a l
be : b' = a
⊢ r b b'
[PROOFSTEP]
subst b'
[GOAL]
case neg.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
bm : a ∈ List.orderedInsert r a l
⊢ r b a
[PROOFSTEP]
exact (total_of r _ _).resolve_left h'
[GOAL]
case neg.inr
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
h : Sorted r (b :: l)
h' : ¬r a b
b' : α
bm✝ : b' ∈ List.orderedInsert r a l
bm : b' ∈ l
⊢ r b b'
[PROOFSTEP]
exact rel_of_sorted_cons h _ bm
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁ l₂ : List α
h : split l = (l₁, l₂)
⊢ split (a :: l) = (a :: l₂, l₁)
[PROOFSTEP]
rw [split, h]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁' l₂' : List α
h : split (a :: l) = (l₁', l₂')
⊢ length l₁' ≤ length (a :: l) ∧ length l₂' ≤ length (a :: l)
[PROOFSTEP]
cases' e : split l with l₁ l₂
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁' l₂' : List α
h : split (a :: l) = (l₁', l₂')
l₁ l₂ : List α
e : split l = (l₁, l₂)
⊢ length l₁' ≤ length (a :: l) ∧ length l₂' ≤ length (a :: l)
[PROOFSTEP]
injection (split_cons_of_eq _ e).symm.trans h
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁' l₂' : List α
h : split (a :: l) = (l₁', l₂')
l₁ l₂ : List α
e : split l = (l₁, l₂)
fst_eq✝ : a :: l₂ = l₁'
snd_eq✝ : l₁ = l₂'
⊢ length l₁' ≤ length (a :: l) ∧ length l₂' ≤ length (a :: l)
[PROOFSTEP]
substs l₁' l₂'
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁ l₂ : List α
e : split l = (l₁, l₂)
h : split (a :: l) = (a :: l₂, l₁)
⊢ length (a :: l₂) ≤ length (a :: l) ∧ length l₁ ≤ length (a :: l)
[PROOFSTEP]
cases' length_split_le e with h₁ h₂
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁ l₂ : List α
e : split l = (l₁, l₂)
h : split (a :: l) = (a :: l₂, l₁)
h₁ : length l₁ ≤ length l
h₂ : length l₂ ≤ length l
⊢ length (a :: l₂) ≤ length (a :: l) ∧ length l₁ ≤ length (a :: l)
[PROOFSTEP]
exact ⟨Nat.succ_le_succ h₂, Nat.le_succ_of_le h₁⟩
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
h : split (a :: b :: l) = (l₁, l₂)
⊢ length l₁ < length (a :: b :: l) ∧ length l₂ < length (a :: b :: l)
[PROOFSTEP]
cases' e : split l with l₁' l₂'
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
h : split (a :: b :: l) = (l₁, l₂)
l₁' l₂' : List α
e : split l = (l₁', l₂')
⊢ length l₁ < length (a :: b :: l) ∧ length l₂ < length (a :: b :: l)
[PROOFSTEP]
injection (split_cons_of_eq _ (split_cons_of_eq _ e)).symm.trans h
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
h : split (a :: b :: l) = (l₁, l₂)
l₁' l₂' : List α
e : split l = (l₁', l₂')
fst_eq✝ : a :: l₁' = l₁
snd_eq✝ : b :: l₂' = l₂
⊢ length l₁ < length (a :: b :: l) ∧ length l₂ < length (a :: b :: l)
[PROOFSTEP]
substs l₁ l₂
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁' l₂' : List α
e : split l = (l₁', l₂')
h : split (a :: b :: l) = (a :: l₁', b :: l₂')
⊢ length (a :: l₁') < length (a :: b :: l) ∧ length (b :: l₂') < length (a :: b :: l)
[PROOFSTEP]
cases' length_split_le e with h₁ h₂
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁' l₂' : List α
e : split l = (l₁', l₂')
h : split (a :: b :: l) = (a :: l₁', b :: l₂')
h₁ : length l₁' ≤ length l
h₂ : length l₂' ≤ length l
⊢ length (a :: l₁') < length (a :: b :: l) ∧ length (b :: l₂') < length (a :: b :: l)
[PROOFSTEP]
exact ⟨Nat.succ_le_succ (Nat.succ_le_succ h₁), Nat.succ_le_succ (Nat.succ_le_succ h₂)⟩
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁' l₂' : List α
h : split (a :: l) = (l₁', l₂')
⊢ a :: l ~ l₁' ++ l₂'
[PROOFSTEP]
cases' e : split l with l₁ l₂
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁' l₂' : List α
h : split (a :: l) = (l₁', l₂')
l₁ l₂ : List α
e : split l = (l₁, l₂)
⊢ a :: l ~ l₁' ++ l₂'
[PROOFSTEP]
injection (split_cons_of_eq _ e).symm.trans h
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁' l₂' : List α
h : split (a :: l) = (l₁', l₂')
l₁ l₂ : List α
e : split l = (l₁, l₂)
fst_eq✝ : a :: l₂ = l₁'
snd_eq✝ : l₁ = l₂'
⊢ a :: l ~ l₁' ++ l₂'
[PROOFSTEP]
substs l₁' l₂'
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l l₁ l₂ : List α
e : split l = (l₁, l₂)
h : split (a :: l) = (a :: l₂, l₁)
⊢ a :: l ~ a :: l₂ ++ l₁
[PROOFSTEP]
exact ((perm_split e).trans perm_append_comm).cons a
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
⊢ List α
[PROOFSTEP]
let ls := (split (a :: b :: l))
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
ls : List α × List α := split (a :: b :: l)
⊢ List α
[PROOFSTEP]
have e : split (a :: b :: l) = ⟨ls.1, ls.2⟩ := rfl
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
ls : List α × List α := split (a :: b :: l)
e : split (a :: b :: l) = (ls.fst, ls.snd)
⊢ List α
[PROOFSTEP]
have h := length_split_lt e
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
ls : List α × List α := split (a :: b :: l)
e : split (a :: b :: l) = (ls.fst, ls.snd)
h : length ls.fst < length (a :: b :: l) ∧ length ls.snd < length (a :: b :: l)
⊢ List α
[PROOFSTEP]
have := h.1
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
ls : List α × List α := split (a :: b :: l)
e : split (a :: b :: l) = (ls.fst, ls.snd)
h : length ls.fst < length (a :: b :: l) ∧ length ls.snd < length (a :: b :: l)
this : length ls.fst < length (a :: b :: l)
⊢ List α
[PROOFSTEP]
have := h.2
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
ls : List α × List α := split (a :: b :: l)
e : split (a :: b :: l) = (ls.fst, ls.snd)
h : length ls.fst < length (a :: b :: l) ∧ length ls.snd < length (a :: b :: l)
this✝ : length ls.fst < length (a :: b :: l)
this : length ls.snd < length (a :: b :: l)
⊢ List α
[PROOFSTEP]
exact merge r (mergeSort ls.1) (mergeSort ls.2)
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
h : split (a :: b :: l) = (l₁, l₂)
⊢ mergeSort r (a :: b :: l) = merge r (mergeSort r l₁) (mergeSort r l₂)
[PROOFSTEP]
simp only [mergeSort, h]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
⊢ merge r [] [] ~ [] ++ []
[PROOFSTEP]
simp [merge]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
b : α
l' : List α
⊢ merge r [] (b :: l') ~ [] ++ b :: l'
[PROOFSTEP]
simp [merge]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l : List α
⊢ merge r (a :: l) [] ~ a :: l ++ []
[PROOFSTEP]
simp [merge]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l : List α
b : α
l' : List α
⊢ merge r (a :: l) (b :: l') ~ a :: l ++ b :: l'
[PROOFSTEP]
by_cases h : a ≼ b
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l : List α
b : α
l' : List α
h : r a b
⊢ merge r (a :: l) (b :: l') ~ a :: l ++ b :: l'
[PROOFSTEP]
simpa [merge, h] using perm_merge _ _
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l : List α
b : α
l' : List α
h : ¬r a b
⊢ merge r (a :: l) (b :: l') ~ a :: l ++ b :: l'
[PROOFSTEP]
suffices b :: merge r (a :: l) l' ~ a :: (l ++ b :: l') by simpa [merge, h]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l : List α
b : α
l' : List α
h : ¬r a b
this : b :: merge r (a :: l) l' ~ a :: (l ++ b :: l')
⊢ merge r (a :: l) (b :: l') ~ a :: l ++ b :: l'
[PROOFSTEP]
simpa [merge, h]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
l : List α
b : α
l' : List α
h : ¬r a b
⊢ b :: merge r (a :: l) l' ~ a :: (l ++ b :: l')
[PROOFSTEP]
exact ((perm_merge _ _).cons _).trans ((swap _ _ _).trans (perm_middle.symm.cons _))
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
⊢ mergeSort r [] ~ []
[PROOFSTEP]
simp [mergeSort]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
⊢ mergeSort r [a] ~ [a]
[PROOFSTEP]
simp [mergeSort]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l : List α
⊢ mergeSort r (a :: b :: l) ~ a :: b :: l
[PROOFSTEP]
cases' e : split (a :: b :: l) with l₁ l₂
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
⊢ mergeSort r (a :: b :: l) ~ a :: b :: l
[PROOFSTEP]
cases' length_split_lt e with h₁ h₂
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ mergeSort r (a :: b :: l) ~ a :: b :: l
[PROOFSTEP]
rw [mergeSort_cons_cons r e]
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ merge r (mergeSort r l₁) (mergeSort r l₂) ~ a :: b :: l
[PROOFSTEP]
apply (perm_merge r _ _).trans
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ mergeSort r l₁ ++ mergeSort r l₂ ~ a :: b :: l
[PROOFSTEP]
exact ((perm_mergeSort l₁).append (perm_mergeSort l₂)).trans (perm_split e).symm
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
x✝¹ x✝ : Sorted r []
⊢ Sorted r (List.merge r [] [])
[PROOFSTEP]
simp [List.merge]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
b : α
l' : List α
x✝ : Sorted r []
h₂ : Sorted r (b :: l')
⊢ Sorted r (List.merge r [] (b :: l'))
[PROOFSTEP]
simpa [List.merge] using h₂
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
h₁ : Sorted r (a :: l)
x✝ : Sorted r []
⊢ Sorted r (List.merge r (a :: l) [])
[PROOFSTEP]
simpa [List.merge] using h₁
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
⊢ Sorted r (List.merge r (a :: l) (b :: l'))
[PROOFSTEP]
by_cases h : a ≼ b
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
⊢ Sorted r (List.merge r (a :: l) (b :: l'))
[PROOFSTEP]
suffices ∀ (b' : α) (_ : b' ∈ List.merge r l (b :: l')), r a b' by simpa [List.merge, h, h₁.of_cons.merge h₂]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
this : ∀ (b' : α), b' ∈ List.merge r l (b :: l') → r a b'
⊢ Sorted r (List.merge r (a :: l) (b :: l'))
[PROOFSTEP]
simpa [List.merge, h, h₁.of_cons.merge h₂]
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
⊢ ∀ (b' : α), b' ∈ List.merge r l (b :: l') → r a b'
[PROOFSTEP]
intro b' bm
[GOAL]
case pos
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
b' : α
bm : b' ∈ List.merge r l (b :: l')
⊢ r a b'
[PROOFSTEP]
rcases show b' = b ∨ b' ∈ l ∨ b' ∈ l' by simpa [or_left_comm] using (perm_merge _ _ _).subset bm with (be | bl | bl')
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
b' : α
bm : b' ∈ List.merge r l (b :: l')
⊢ b' = b ∨ b' ∈ l ∨ b' ∈ l'
[PROOFSTEP]
simpa [or_left_comm] using (perm_merge _ _ _).subset bm
[GOAL]
case pos.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
b' : α
bm : b' ∈ List.merge r l (b :: l')
be : b' = b
⊢ r a b'
[PROOFSTEP]
subst b'
[GOAL]
case pos.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
bm : b ∈ List.merge r l (b :: l')
⊢ r a b
[PROOFSTEP]
assumption
[GOAL]
case pos.inr.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
b' : α
bm : b' ∈ List.merge r l (b :: l')
bl : b' ∈ l
⊢ r a b'
[PROOFSTEP]
exact rel_of_sorted_cons h₁ _ bl
[GOAL]
case pos.inr.inr
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : r a b
b' : α
bm : b' ∈ List.merge r l (b :: l')
bl' : b' ∈ l'
⊢ r a b'
[PROOFSTEP]
exact _root_.trans h (rel_of_sorted_cons h₂ _ bl')
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
⊢ Sorted r (List.merge r (a :: l) (b :: l'))
[PROOFSTEP]
suffices ∀ (b' : α) (_ : b' ∈ List.merge r (a :: l) l'), r b b' by simpa [List.merge, h, h₁.merge h₂.of_cons]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
this : ∀ (b' : α), b' ∈ List.merge r (a :: l) l' → r b b'
⊢ Sorted r (List.merge r (a :: l) (b :: l'))
[PROOFSTEP]
simpa [List.merge, h, h₁.merge h₂.of_cons]
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
⊢ ∀ (b' : α), b' ∈ List.merge r (a :: l) l' → r b b'
[PROOFSTEP]
intro b' bm
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
⊢ r b b'
[PROOFSTEP]
have ba : b ≼ a := (total_of r _ _).resolve_left h
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
ba : r b a
⊢ r b b'
[PROOFSTEP]
have : b' = a ∨ b' ∈ l ∨ b' ∈ l' := by simpa using (perm_merge _ _ _).subset bm
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
ba : r b a
⊢ b' = a ∨ b' ∈ l ∨ b' ∈ l'
[PROOFSTEP]
simpa using (perm_merge _ _ _).subset bm
[GOAL]
case neg
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
ba : r b a
this : b' = a ∨ b' ∈ l ∨ b' ∈ l'
⊢ r b b'
[PROOFSTEP]
rcases this with (be | bl | bl')
[GOAL]
case neg.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
ba : r b a
be : b' = a
⊢ r b b'
[PROOFSTEP]
subst b'
[GOAL]
case neg.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
ba : r b a
bm : a ∈ List.merge r (a :: l) l'
⊢ r b a
[PROOFSTEP]
assumption
[GOAL]
case neg.inr.inl
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
ba : r b a
bl : b' ∈ l
⊢ r b b'
[PROOFSTEP]
exact _root_.trans ba (rel_of_sorted_cons h₁ _ bl)
[GOAL]
case neg.inr.inr
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
l : List α
b : α
l' : List α
h₁ : Sorted r (a :: l)
h₂ : Sorted r (b :: l')
h : ¬r a b
b' : α
bm : b' ∈ List.merge r (a :: l) l'
ba : r b a
bl' : b' ∈ l'
⊢ r b b'
[PROOFSTEP]
exact rel_of_sorted_cons h₂ _ bl'
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
⊢ Sorted r (mergeSort r [])
[PROOFSTEP]
simp [mergeSort]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a : α
⊢ Sorted r (mergeSort r [a])
[PROOFSTEP]
simp [mergeSort]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l : List α
⊢ Sorted r (mergeSort r (a :: b :: l))
[PROOFSTEP]
cases' e : split (a :: b :: l) with l₁ l₂
[GOAL]
case mk
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
⊢ Sorted r (mergeSort r (a :: b :: l))
[PROOFSTEP]
cases' length_split_lt e with h₁ h₂
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ Sorted r (mergeSort r (a :: b :: l))
[PROOFSTEP]
rw [mergeSort_cons_cons r e]
[GOAL]
case mk.intro
α : Type uu
r : α → α → Prop
inst✝² : DecidableRel r
inst✝¹ : IsTotal α r
inst✝ : IsTrans α r
a b : α
l l₁ l₂ : List α
e : split (a :: b :: l) = (l₁, l₂)
h₁ : length l₁ < length (a :: b :: l)
h₂ : length l₂ < length (a :: b :: l)
⊢ Sorted r (merge r (mergeSort r l₁) (mergeSort r l₂))
[PROOFSTEP]
exact (sorted_mergeSort l₁).merge (sorted_mergeSort l₂)
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
⊢ mergeSort r [] = []
[PROOFSTEP]
rw [List.mergeSort]
[GOAL]
α : Type uu
r : α → α → Prop
inst✝ : DecidableRel r
a : α
⊢ mergeSort r [a] = [a]
[PROOFSTEP]
rw [List.mergeSort]
