internlm/Lean-Github huggingface dataset:
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ (arr.swap i j)[first] = arr[first]
Tactic:
apply Vec.get_swap_neq
Proof state after:
case step_ge.ki
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ i

case step_ge.kj
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ j
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge.ki
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ i

case step_ge.kj
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ j
Tactic:
. apply Fin.ne_of_val_ne
  exact Nat.ne_of_lt fi
Proof state after:
case step_ge.kj
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ j
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge.kj
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ j
Tactic:
. apply Fin.ne_of_val_ne
  exact Nat.ne_of_lt fj
Proof state after:
no goals
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge.ki
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ i
Tactic:
apply Fin.ne_of_val_ne
Proof state after:
case step_ge.ki.h
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ ¬↑first = ↑i
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge.ki.h
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ ¬↑first = ↑i
Tactic:
exact Nat.ne_of_lt fi
Proof state after:
no goals
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge.kj
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ first ≠ j
Tactic:
apply Fin.ne_of_val_ne
Proof state after:
case step_ge.kj.h
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ ¬↑first = ↑j
Theorem: partitionImpl.first_eq
Proof state before:
case step_ge.kj.h
α : Type
inst✝ : Ord α
n : Nat
first✝ i✝ j✝ : Fin n
arr : Vec α n
first i j : Fin n
fi✝ : first ≤ i
ij : i ≤ j
fi : first < i
x✝² : ↑first ≤ ↑i - 1
x✝¹ : ¬arr[i] < arr[first]
x✝ : ↑i - 1 ≤ ↑j - 1
ih✝ : (partitionImpl (arr.swap i j) first i.prev j.prev x✝² x✝).snd[first] = (arr.swap i j)[first]
fj : first < j
⊢ ¬↑first = ↑j
Tactic:
exact Nat.ne_of_lt fj
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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
let afterLoop := partitionImpl arr first last last fl (Nat.le_refl _)
Proof state after:
α : 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 ⋯
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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 ⋯
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
let mid := afterLoop.1
Proof state after:
α : 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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
let arr' := afterLoop.2
Proof state after:
α : 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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
have : mid < n := Nat.lt_of_le_of_lt mid.property.2 last.isLt
Proof state after:
α : 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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
let swapped := arr'.swap first ⟨mid, by assumption⟩
Proof state after:
α : 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⟩
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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⟩
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
have : result.1 = mid := by
  rw [←eq]
  unfold partition
  simp [afterLoop]
Proof state after:
α : 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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
have : result.2 = swapped := by
  rw [←eq]
  unfold partition
  simp [afterLoop, dbgTraceIfShared]
Proof state after:
α : 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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
have first_eq : arr'[first] = arr[first] := by
  apply partitionImpl.first_eq
Proof state after:
α : 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]
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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]
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
let inv₀ : partitionImpl.LoopInvariant arr first last last last := by
  apply partitionImpl.LoopInvariant.intro
  . intro k lk kl
    exact (Nat.lt_irrefl k (Nat.lt_trans kl lk)).elim
  . intro k lk kl
    exact (Nat.lt_irrefl k (Nat.lt_of_le_of_lt kl lk)).elim
  . intro ll
    exact (Nat.lt_irrefl last ll).elim
Proof state after:
α : 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) }
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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) }
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
let inv := partitionImpl.loop_invariant arr first last last last fl (Nat.le_refl _) inv₀ afterLoop (by rfl)
Proof state after:
α : 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), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
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)))
p₁ : ∀ (k : Fin n), first ≤ k → ↑k < ↑mid.val → swapped[k] < arr[first]
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]
Tactic:
have p₂ : swapped[mid.val] = arr[first] := by
  have : swapped[mid.val] = arr'[first] := by
    apply Vec.get_swap_right
  rw [this]
  assumption
Proof state after:
α : 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)))
p₁ : ∀ (k : Fin n), first ≤ k → ↑k < ↑mid.val → swapped[k] < arr[first]
p₂ : swapped[mid.val] = arr[first]
⊢ (∀ (k : Fin n), first ≤ k → ↑k < ↑result.fst.val → result.snd[k] < arr[first]) ∧
    result.snd[result.fst.val] = arr[first] ∧
      ∀ (k : Fin n), ↑result.fst.val < ↑k → k ≤ last → ¬result.snd[k] < arr[first]