internlm/Lean-Github huggingface dataset:
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
case node_next_left x i y hi hl _ hx' hx h _ =>
  rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_left i))]
  rewrite [h.get_not_descendant (2*i+2) (Descendant.sibling_not i)]
  rw [Subarray.getElem_swap_left, Subarray.getElem_swap_ne, LawfulLTBRel.asymm hx']
  . show i ≠ 2*i+2; exact Nat.ne_of_lt (lt_child_right i)
  . show 2*i+1 ≠ 2*i+1+1; exact Nat.ne_of_lt .refl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi✝ : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
case node_end_left x i _ _ _ hx' hx =>
  exact LawfulLTBRel.ntrans hx <| LawfulLTBRel.asymm hx'
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
case node_next_right x i y hi hl _ hx' hx h _ =>
  rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_right i))]
  have ⟨k,hk,hdk,h⟩ := h.exists_get_descendant (2*i+2) hr (.refl _)
  rewrite [Subarray.getElem_swap_left, h, Subarray.getElem_swap]
  if hrk : 2*i+2 = k then
    simp only [if_pos hrk]; exact LawfulLTBRel.asymm hx
  else
    simp only [if_neg hrk, if_neg <| Nat.ne_of_lt <| trans (lt_child_right i) hdk.le]
    exact heap_right.not_lt_of_descendant k hdk
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
case node_end_right x i hi _ _ hx' hx =>
  exact hx
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl' : 2 * i + 1 ≥ Subarray.size x
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
case leaf x i hl' =>
  exact absurd hr <| Nat.not_lt_of_le <| trans hl' (2*i+1).le_succ
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case node_odd_end
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x : Subarray α
i : Nat
y x✝ : Subarray α
i✝ : Nat
hi✝ : i✝ < Subarray.size x✝
hl✝ : 2 * i✝ + 1 < Subarray.size x✝
a✝¹ : 2 * i✝ + 2 ≥ Subarray.size x✝
a✝ : lt x✝[i✝] x✝[2 * i✝ + 1] = false
hr : 2 * i✝ + 2 < Subarray.size x✝
heap_right : IsHeap lt x✝ (2 * i✝ + 2)
⊢ lt x✝[i✝] x✝[2 * i✝ + 2] = false
Tactic:
exact absurd hr <| Nat.not_lt_of_le ‹_›
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_left i))]
Proof state after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i] y[2 * i + 2] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i] y[2 * i + 2] = false
Tactic:
rewrite [h.get_not_descendant (2*i+2) (Descendant.sibling_not i)]
Proof state after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 2] =
    false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[i]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 2] =
    false
Tactic:
rw [Subarray.getElem_swap_left, Subarray.getElem_swap_ne, LawfulLTBRel.asymm hx']
Proof state after:
case hik
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 2

case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case hik
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 2

case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Tactic:
. show i ≠ 2*i+2; exact Nat.ne_of_lt (lt_child_right i)
Proof state after:
case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Tactic:
. show 2*i+1 ≠ 2*i+1+1; exact Nat.ne_of_lt .refl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case hik
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 2
Tactic:
show i ≠ 2*i+2
Proof state after:
case hik
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ i ≠ 2 * i + 2
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case hik
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ i ≠ 2 * i + 2
Tactic:
exact Nat.ne_of_lt (lt_child_right i)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ 2 * i + 2
Tactic:
show 2*i+1 ≠ 2*i+1+1
Proof state after:
case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ 2 * i + 1 ≠ 2 * i + 1 + 1
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 1) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * (2 * i + 1) + 2) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ 2 * i + 1 ≠ 2 * i + 1 + 1
Tactic:
exact Nat.ne_of_lt .refl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi✝ : i < Subarray.size x
hl✝ : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt x[i] x[2 * i + 2] = false
Tactic:
exact LawfulLTBRel.ntrans hx <| LawfulLTBRel.asymm hx'
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_right
Proof state before:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt y[i] y[2 * i + 2] = false
Tactic:
rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_right i))]
Proof state after:
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr✝ : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = true
h : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * i + 2) y
a_ih✝ :
  ∀
    (hr :
      2 * (2 * i + 2) + 2 < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })),
    IsHeap lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ }) (2 * (2 * i + 2) + 2) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 2] = false
hr : 2 * i + 2 < Subarray.size x
heap_right : IsHeap lt x (2 * i + 2)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr✝ })[i] y[2 * i + 2] = false