internlm/Lean-Github huggingface dataset:
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
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✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < 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) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
hlk : ¬2 * i + 1 = k
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }]
      (if ↑{ val := 2 * i + 1, isLt := hl✝ } = k then x[↑{ val := i, isLt := hi }]
      else if ↑{ val := i, isLt := hi } = k then x[↑{ val := 2 * i + 1, isLt := hl✝ }] else x[k]) =
    false
Tactic:
simp only [if_neg hlk, if_neg <| Nat.ne_of_lt <| trans (lt_child_left i) hdk.le]
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✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < 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) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
hlk : ¬2 * i + 1 = k
⊢ lt x[2 * i + 1] x[k] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
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✝ :
  ∀
    (hl :
      2 * (2 * i + 1) + 1 < 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) + 1) →
      lt y[2 * i + 1] y[2 * (2 * i + 1) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
k : Nat
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })
hdk : Descendant (2 * i + 1) k
h : y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl✝ })[k]
hlk : ¬2 * i + 1 = k
⊢ lt x[2 * i + 1] x[k] = false
Tactic:
exact heap_left.not_lt_of_descendant k hdk
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_end_left
α : 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
a✝ : lt x[2 * i + 2] x[2 * i + 1] = true
hx : lt x[i] x[2 * i + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact hx
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right
α : 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt y[i] y[2 * i + 1] = false
Tactic:
rewrite [h.get_not_descendant i (fun h => Nat.not_lt_of_le h.le (lt_child_right i))]
Proof state after:
case node_next_right
α : 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[i] y[2 * i + 1] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right
α : 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[i] y[2 * i + 1] = false
Tactic:
rewrite [h.get_not_descendant (2*i+1) (Descendant.sibling_not' i)]
Proof state after:
case node_next_right
α : 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[i]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 1] =
    false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right
α : 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[i]
      (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 1] =
    false
Tactic:
rw [Subarray.getElem_swap_left, Subarray.getElem_swap_ne, hx']
Proof state after:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 1

case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := 2 * i + 2, isLt := hr } ≠ 2 * i + 1
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 1

case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := 2 * i + 2, isLt := hr } ≠ 2 * i + 1
Tactic:
. show i ≠ 2*i+1; exact Nat.ne_of_lt (lt_child_left i)
Proof state after:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := 2 * i + 2, isLt := hr } ≠ 2 * i + 1
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := 2 * i + 2, isLt := hr } ≠ 2 * i + 1
Tactic:
. show 2*i+1+1 ≠ 2*i+1; exact Nat.ne_of_gt .refl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := i, isLt := hi } ≠ 2 * i + 1
Tactic:
show i ≠ 2*i+1
Proof state after:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ i ≠ 2 * i + 1
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ i ≠ 2 * i + 1
Tactic:
exact Nat.ne_of_lt (lt_child_left i)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ ↑{ val := 2 * i + 2, isLt := hr } ≠ 2 * i + 1
Tactic:
show 2*i+1+1 ≠ 2*i+1
Proof state after:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ 2 * i + 1 + 1 ≠ 2 * i + 1
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_next_right.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] = 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✝ :
  ∀
    (hl :
      2 * (2 * i + 2) + 1 < 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) + 1) →
      lt y[2 * i + 2] y[2 * (2 * i + 2) + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ 2 * i + 1 + 1 ≠ 2 * i + 1
Tactic:
exact Nat.ne_of_gt .refl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_end_right
α : 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
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact LawfulLTBRel.ntrans hx hx'
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_odd_next
α : 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[i] x[2 * i + 1] = true
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ 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 + 1] =
    false
Tactic:
rewrite [Subarray.getElem_swap_left, Subarray.getElem_swap_right]
Proof state after:
case node_odd_next
α : 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[i] x[2 * i + 1] = true
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }] x[↑{ val := i, isLt := hi }] = false
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case node_odd_next
α : 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[i] x[2 * i + 1] = true
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[↑{ val := 2 * i + 1, isLt := hl✝ }] x[↑{ val := i, isLt := hi }] = false
Tactic:
exact LawfulLTBRel.asymm hx
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
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
hx : lt x[i] x[2 * i + 1] = false
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact hx
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.not_lt_left
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
inst✝ : LawfulLTBRel lt
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hl' : 2 * i + 1 ≥ Subarray.size x
hl : 2 * i + 1 < Subarray.size x
heap_left : IsHeap lt x (2 * i + 1)
⊢ lt x[i] x[2 * i + 1] = false
Tactic:
exact absurd hl <| Nat.not_lt_of_le hl'
Proof state after:
no goals