internlm/Lean-Github huggingface dataset:
Theorem: partition.partition
Proof state before:
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝¹ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝¹⟩
this✝ : result.fst = mid
this : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
⊢ partitionImpl arr first last last fl ⋯ = afterLoop
Tactic:
rfl
Proof state after:
no goals
Theorem: partition.partition
Proof state before:
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝¹ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝¹⟩
this✝ : result.fst = mid
this : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk : first ≤ k
km : ↑k < ↑mid.val
⊢ swapped[k] < arr[first]
Tactic:
cases Nat.eq_or_lt_of_le fk with
| inl fk =>
  have : swapped[k] = swapped[first] := by
    simp [Fin.eq_of_val_eq fk]
  rw [this]
  have : swapped[first] = arr'[mid.val] := by
    apply Vec.get_swap_left
  rw [this, ←first_eq]
  exact inv.3 (Fin.eq_of_val_eq fk ▸ km)
| inr fk =>
  have : swapped[k] = arr'[k] := by
    apply Vec.get_swap_neq
    . apply Fin.ne_of_val_ne
      exact Nat.ne_of_gt fk
    . apply Fin.ne_of_val_ne
      exact Nat.ne_of_lt km
  rw [this, ←first_eq]
  exact inv.1 k fk km
Proof state after:
no goals
Theorem: partition.partition
Proof state before:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝¹ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝¹⟩
this✝ : result.fst = mid
this : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
⊢ swapped[k] < arr[first]
Tactic:
have : swapped[k] = swapped[first] := by
  simp [Fin.eq_of_val_eq fk]
Proof state after:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this : swapped[k] = swapped[first]
⊢ swapped[k] < arr[first]
Theorem: partition.partition
Proof state before:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this : swapped[k] = swapped[first]
⊢ swapped[k] < arr[first]
Tactic:
rw [this]
Proof state after:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this : swapped[k] = swapped[first]
⊢ swapped[first] < arr[first]
Theorem: partition.partition
Proof state before:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this : swapped[k] = swapped[first]
⊢ swapped[first] < arr[first]
Tactic:
have : swapped[first] = arr'[mid.val] := by
  apply Vec.get_swap_left
Proof state after:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝³ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝³⟩
this✝² : result.fst = mid
this✝¹ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this✝ : swapped[k] = swapped[first]
this : swapped[first] = arr'[mid.val]
⊢ swapped[first] < arr[first]
Theorem: partition.partition
Proof state before:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝³ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝³⟩
this✝² : result.fst = mid
this✝¹ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this✝ : swapped[k] = swapped[first]
this : swapped[first] = arr'[mid.val]
⊢ swapped[first] < arr[first]
Tactic:
rw [this, ←first_eq]
Proof state after:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝³ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝³⟩
this✝² : result.fst = mid
this✝¹ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this✝ : swapped[k] = swapped[first]
this : swapped[first] = arr'[mid.val]
⊢ arr'[mid.val] < arr'[first]
Theorem: partition.partition
Proof state before:
case inl
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝³ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝³⟩
this✝² : result.fst = mid
this✝¹ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this✝ : swapped[k] = swapped[first]
this : swapped[first] = arr'[mid.val]
⊢ arr'[mid.val] < arr'[first]
Tactic:
exact inv.3 (Fin.eq_of_val_eq fk ▸ km)
Proof state after:
no goals
Theorem: partition.partition
Proof state before:
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝¹ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝¹⟩
this✝ : result.fst = mid
this : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
⊢ swapped[k] = swapped[first]
Tactic:
simp [Fin.eq_of_val_eq fk]
Proof state after:
no goals
Theorem: partition.partition
Proof state before:
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first = ↑k
this : swapped[k] = swapped[first]
⊢ swapped[first] = arr'[mid.val]
Tactic:
apply Vec.get_swap_left
Proof state after:
no goals
Theorem: partition.partition
Proof state before:
case inr
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝¹ : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝¹⟩
this✝ : result.fst = mid
this : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first < ↑k
⊢ swapped[k] < arr[first]
Tactic:
have : swapped[k] = arr'[k] := by
  apply Vec.get_swap_neq
  . apply Fin.ne_of_val_ne
    exact Nat.ne_of_gt fk
  . apply Fin.ne_of_val_ne
    exact Nat.ne_of_lt km
Proof state after:
case inr
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first < ↑k
this : swapped[k] = arr'[k]
⊢ swapped[k] < arr[first]
Theorem: partition.partition
Proof state before:
case inr
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first < ↑k
this : swapped[k] = arr'[k]
⊢ swapped[k] < arr[first]
Tactic:
rw [this, ←first_eq]
Proof state after:
case inr
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first < ↑k
this : swapped[k] = arr'[k]
⊢ arr'[k] < arr'[first]
Theorem: partition.partition
Proof state before:
case inr
α : Type
inst✝ : Ord α
n : Nat
arr : Vec α n
first last : Fin n
fl : first ≤ last
result : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n
eq : _root_.partition arr first last fl = result
afterLoop : { mid // first ≤ mid ∧ mid ≤ last } × Vec α n := partitionImpl arr first last last fl ⋯
mid : { mid // first ≤ mid ∧ mid ≤ last } := afterLoop.fst
arr' : Vec α n := afterLoop.snd
this✝² : ↑mid.val < n
swapped : Vec α n := arr'.swap first ⟨↑mid.val, this✝²⟩
this✝¹ : result.fst = mid
this✝ : result.snd = swapped
first_eq : arr'[first] = arr[first]
inv₀ : partitionImpl.LoopInvariant arr first last last last :=
  { inv₁ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_trans kl lk)),
    inv₂ := fun k lk kl => False.elim (Nat.lt_irrefl (↑k) (Nat.lt_of_le_of_lt kl lk)),
    inv₃ := fun ll => False.elim (Nat.lt_irrefl (↑last) ll) }
inv : partitionImpl.LoopInvariant afterLoop.snd first first ⟨↑afterLoop.fst.val, ⋯⟩ last :=
  partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl ↑last) inv₀ afterLoop
    (Eq.refl (partitionImpl arr first last last fl (Nat.le_refl ↑last)))
k : Fin n
fk✝ : first ≤ k
km : ↑k < ↑mid.val
fk : ↑first < ↑k
this : swapped[k] = arr'[k]
⊢ arr'[k] < arr'[first]
Tactic:
exact inv.1 k fk km
Proof state after:
no goals