internlm/Lean-Github huggingface dataset:
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
h : heapifyDown.OpSpec lt x i y
k : Nat
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ y[k] = x[k]
Tactic:
induction h <;> try rfl
Proof state after:
case node_next_left
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = true
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 1] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ }) (2 * i✝ + 1) y✝
a_ih✝ :
  ∀ {hk : k < Subarray.size y✝},
    ¬Descendant (2 * i✝ + 1) k →
      y✝[k] = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ })[k]
hk : k < Subarray.size y✝
hdesc : ¬Descendant i✝ k
⊢ y✝[k] = x✝[k]

case node_next_right
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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✝
a✝² : lt x✝[2 * i✝ + 2] x✝[2 * i✝ + 1] = false
a✝¹ : lt x✝[i✝] x✝[2 * i✝ + 2] = true
a✝ :
  heapifyDown.OpSpec lt (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ }) (2 * i✝ + 2) y✝
a_ih✝ :
  ∀ {hk : k < Subarray.size y✝},
    ¬Descendant (2 * i✝ + 2) k →
      y✝[k] = (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 2, isLt := hr✝ })[k]
hk : k < Subarray.size y✝
hdesc : ¬Descendant i✝ k
⊢ y✝[k] = x✝[k]

case node_odd_next
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
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] = true
hk : k < Subarray.size (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ })
hdesc : ¬Descendant i✝ k
⊢ (Subarray.swap x✝ { val := i✝, isLt := hi✝ } { val := 2 * i✝ + 1, isLt := hl✝ })[k] = x✝[k]
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ y[k] = x[k]
Tactic:
case node_next_left x i y hi hl hr hx' hx _ IH =>
  rewrite [@IH hk fun h => hdesc (Descendant.trans (.child_left i) h)]
  apply Subarray.getElem_swap_ne <;> (dsimp; intro hik; cases hik)
  . exact hdesc (.refl _)
  . exact hdesc (.child_left _)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 2) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ y[k] = x[k]
Tactic:
case node_next_right x i y hi hl hr hx' hx _ IH =>
  rewrite [@IH hk fun h => hdesc (Descendant.trans (.child_right i) h)]
  apply Subarray.getElem_swap_ne <;> (dsimp; intro hik; cases hik)
  . exact hdesc (.refl _)
  . exact hdesc (.child_right _)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
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
hk : k < Subarray.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })
hdesc : ¬Descendant i k
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k] = x[k]
Tactic:
case node_odd_next x i hi hl hr hx =>
  apply Subarray.getElem_swap_ne <;> (dsimp; intro hik; cases hik)
  . exact hdesc (.refl _)
  . exact hdesc (.child_left _)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case leaf
α : Type u
lt : α → α → Bool
x : Subarray α
i : Nat
y : Subarray α
k : Nat
x✝ : Subarray α
i✝ : Nat
a✝ : 2 * i✝ + 1 ≥ Subarray.size x✝
hk : k < Subarray.size x✝
hdesc : ¬Descendant i✝ k
⊢ x✝[k] = x✝[k]
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ y[k] = x[k]
Tactic:
rewrite [@IH hk fun h => hdesc (Descendant.trans (.child_left i) h)]
Proof state after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k] = x[k]
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k] = x[k]
Tactic:
apply Subarray.getElem_swap_ne <;> (dsimp; intro hik; cases hik)
Proof state after:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk : k < Subarray.size y
hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * k + 1) k → y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[k]
hdesc : ¬Descendant k k
⊢ False

case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : 2 * i + 1 < Subarray.size y},
    ¬Descendant (2 * i + 1) (2 * i + 1) →
      y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 1]
hk : 2 * i + 1 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 1)
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk : k < Subarray.size y
hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * k + 1) k → y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[k]
hdesc : ¬Descendant k k
⊢ False

case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : 2 * i + 1 < Subarray.size y},
    ¬Descendant (2 * i + 1) (2 * i + 1) →
      y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 1]
hk : 2 * i + 1 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 1)
⊢ False
Tactic:
. exact hdesc (.refl _)
Proof state after:
case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : 2 * i + 1 < Subarray.size y},
    ¬Descendant (2 * i + 1) (2 * i + 1) →
      y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 1]
hk : 2 * i + 1 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 1)
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : 2 * i + 1 < Subarray.size y},
    ¬Descendant (2 * i + 1) (2 * i + 1) →
      y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 1]
hk : 2 * i + 1 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 1)
⊢ False
Tactic:
. exact hdesc (.child_left _)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ ↑{ val := 2 * i + 1, isLt := hl } ≠ k
Tactic:
dsimp
Proof state after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ ¬2 * i + 1 = k
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ ¬2 * i + 1 = k
Tactic:
intro hik
Proof state after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
hik : 2 * i + 1 = k
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 1) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
hik : 2 * i + 1 = k
⊢ False
Tactic:
cases hik
Proof state after:
case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : 2 * i + 1 < Subarray.size y},
    ¬Descendant (2 * i + 1) (2 * i + 1) →
      y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 1]
hk : 2 * i + 1 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 1)
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk : k < Subarray.size y
hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = true
hx : lt x[k] x[2 * k + 1] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl }) (2 * k + 1) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * k + 1) k → y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 1, isLt := hl })[k]
hdesc : ¬Descendant k k
⊢ False
Tactic:
exact hdesc (.refl _)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }) (2 * i + 1) y
IH :
  ∀ {hk : 2 * i + 1 < Subarray.size y},
    ¬Descendant (2 * i + 1) (2 * i + 1) →
      y[2 * i + 1] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl })[2 * i + 1]
hk : 2 * i + 1 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 1)
⊢ False
Tactic:
exact hdesc (.child_left _)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 2) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ y[k] = x[k]
Tactic:
rewrite [@IH hk fun h => hdesc (Descendant.trans (.child_right i) h)]
Proof state after:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 2) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[k] = x[k]
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * i + 2) k → y[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[k]
hk : k < Subarray.size y
hdesc : ¬Descendant i k
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[k] = x[k]
Tactic:
apply Subarray.getElem_swap_ne <;> (dsimp; intro hik; cases hik)
Proof state after:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk : k < Subarray.size y
hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = false
hx : lt x[k] x[2 * k + 2] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr }) (2 * k + 2) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * k + 2) k → y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })[k]
hdesc : ¬Descendant k k
⊢ False

case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : 2 * i + 2 < Subarray.size y},
    ¬Descendant (2 * i + 2) (2 * i + 2) →
      y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
hk : 2 * i + 2 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 2)
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i : Nat
y✝ : Subarray α
k : Nat
x y : Subarray α
hk : k < Subarray.size y
hi : k < Subarray.size x
hl : 2 * k + 1 < Subarray.size x
hr : 2 * k + 2 < Subarray.size x
hx' : lt x[2 * k + 2] x[2 * k + 1] = false
hx : lt x[k] x[2 * k + 2] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr }) (2 * k + 2) y
IH :
  ∀ {hk : k < Subarray.size y},
    ¬Descendant (2 * k + 2) k → y[k] = (Subarray.swap x { val := k, isLt := hi } { val := 2 * k + 2, isLt := hr })[k]
hdesc : ¬Descendant k k
⊢ False

case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : 2 * i + 2 < Subarray.size y},
    ¬Descendant (2 * i + 2) (2 * i + 2) →
      y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
hk : 2 * i + 2 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 2)
⊢ False
Tactic:
. exact hdesc (.refl _)
Proof state after:
case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : 2 * i + 2 < Subarray.size y},
    ¬Descendant (2 * i + 2) (2 * i + 2) →
      y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
hk : 2 * i + 2 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 2)
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_not_descendant
Proof state before:
case hjk.refl
α : Type u
lt : α → α → Bool
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
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : 2 * i + 2 < Subarray.size y},
    ¬Descendant (2 * i + 2) (2 * i + 2) →
      y[2 * i + 2] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr })[2 * i + 2]
hk : 2 * i + 2 < Subarray.size y
hdesc : ¬Descendant i (2 * i + 2)
⊢ False
Tactic:
. exact hdesc (.child_right _)
Proof state after:
no goals