internlm/Lean-Github huggingface dataset:
Theorem: project.deleteMin_non_empty_minimum
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
heq : deleteMin le (Heap.heap xs) = some (y, ys)
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
⊢ le y t.val = true
Tactic:
unfold deleteMin at heq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
heq :
  (match Heap.heap xs with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
⊢ le y t.val = true
Theorem: project.deleteMin_non_empty_minimum
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
heq :
  (match Heap.heap xs with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
⊢ le y t.val = true
Tactic:
split at heq
Proof state after:
case h_1
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝ : Heap α
heq✝ : Heap.heap xs = Heap.heap []
heq : none = some (y, ys)
⊢ le y t.val = true

case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝ : Heap α
h✝ : HeapNodeAux α (Heap α)
heq✝ : Heap.heap xs = Heap.heap [h✝]
heq : some (h✝.val, h✝.children) = some (y, ys)
⊢ le y t.val = true

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝¹ : Heap α
h✝ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
x✝ : hs✝ = [] → False
heq✝ : Heap.heap xs = Heap.heap (h✝ :: hs✝)
heq :
  (match findMin le hs✝ 1 (h✝, 0) with
    | (min, minIdx) =>
      let rest := List.eraseIdx (h✝ :: hs✝) minIdx;
      let tail := merge le (Heap.heap rest) min.children;
      some (min.val, tail)) =
    some (y, ys)
⊢ le y t.val = true
Theorem: project.deleteMin_non_empty_minimum
Proof state before:
case h_1
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝ : Heap α
heq✝ : Heap.heap xs = Heap.heap []
heq : none = some (y, ys)
⊢ le y t.val = true

case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝ : Heap α
h✝ : HeapNodeAux α (Heap α)
heq✝ : Heap.heap xs = Heap.heap [h✝]
heq : some (h✝.val, h✝.children) = some (y, ys)
⊢ le y t.val = true

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝¹ : Heap α
h✝ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
x✝ : hs✝ = [] → False
heq✝ : Heap.heap xs = Heap.heap (h✝ :: hs✝)
heq :
  (match findMin le hs✝ 1 (h✝, 0) with
    | (min, minIdx) =>
      let rest := List.eraseIdx (h✝ :: hs✝) minIdx;
      let tail := merge le (Heap.heap rest) min.children;
      some (min.val, tail)) =
    some (y, ys)
⊢ le y t.val = true
Tactic:
. contradiction
Proof state after:
case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝ : Heap α
h✝ : HeapNodeAux α (Heap α)
heq✝ : Heap.heap xs = Heap.heap [h✝]
heq : some (h✝.val, h✝.children) = some (y, ys)
⊢ le y t.val = true

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝¹ : Heap α
h✝ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
x✝ : hs✝ = [] → False
heq✝ : Heap.heap xs = Heap.heap (h✝ :: hs✝)
heq :
  (match findMin le hs✝ 1 (h✝, 0) with
    | (min, minIdx) =>
      let rest := List.eraseIdx (h✝ :: hs✝) minIdx;
      let tail := merge le (Heap.heap rest) min.children;
      some (min.val, tail)) =
    some (y, ys)
⊢ le y t.val = true
Theorem: project.deleteMin_non_empty_minimum
Proof state before:
case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝ : Heap α
h✝ : HeapNodeAux α (Heap α)
heq✝ : Heap.heap xs = Heap.heap [h✝]
heq : some (h✝.val, h✝.children) = some (y, ys)
⊢ le y t.val = true

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝¹ : Heap α
h✝ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
x✝ : hs✝ = [] → False
heq✝ : Heap.heap xs = Heap.heap (h✝ :: hs✝)
heq :
  (match findMin le hs✝ 1 (h✝, 0) with
    | (min, minIdx) =>
      let rest := List.eraseIdx (h✝ :: hs✝) minIdx;
      let tail := merge le (Heap.heap rest) min.children;
      some (min.val, tail)) =
    some (y, ys)
⊢ le y t.val = true
Tactic:
. simp_all
Proof state after:
case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝¹ : Heap α
h✝ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
x✝ : hs✝ = [] → False
heq✝ : Heap.heap xs = Heap.heap (h✝ :: hs✝)
heq :
  (match findMin le hs✝ 1 (h✝, 0) with
    | (min, minIdx) =>
      let rest := List.eraseIdx (h✝ :: hs✝) minIdx;
      let tail := merge le (Heap.heap rest) min.children;
      some (min.val, tail)) =
    some (y, ys)
⊢ le y t.val = true
Theorem: project.deleteMin_non_empty_minimum
Proof state before:
case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
x✝¹ : Heap α
h✝ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
x✝ : hs✝ = [] → False
heq✝ : Heap.heap xs = Heap.heap (h✝ :: hs✝)
heq :
  (match findMin le hs✝ 1 (h✝, 0) with
    | (min, minIdx) =>
      let rest := List.eraseIdx (h✝ :: hs✝) minIdx;
      let tail := merge le (Heap.heap rest) min.children;
      some (min.val, tail)) =
    some (y, ys)
⊢ le y t.val = true
Tactic:
. simp_all
  dsimp at heq
  rw[← heq.left]
  cases hel
  . rename_i heq₂
    rw[← heq₂]
    apply findMin_is_minimum_head <;> simp_all; assumption
  . apply findMin_is_minimum_tail
    . simp_all
    repeat assumption
    . apply findMin_is_minimum_head
      . simp_all
      repeat assumption
    . assumption
Proof state after:
no goals
Theorem: project.deleteMin_non_empty_minimum
Proof state before:
case h_3.inr.a.le_rfl
α : Type u_1
le : α → α → Bool
xs : List (HeapNodeAux α (Heap α))
y : α
ys : Heap α
t : HeapNodeAux α (Heap α)
x✝¹ : Heap α
h✝¹ : HeapNodeAux α (Heap α)
hs✝ : List (HeapNodeAux α (Heap α))
not_le_le : ∀ (x y : α), le x y = false → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
x✝ : hs✝ = [] → False
heq✝ : xs = h✝¹ :: hs✝
heq :
  (findMin le hs✝ 1 (h✝¹, 0)).fst.val = y ∧
    merge le (Heap.heap (List.eraseIdx (h✝¹ :: hs✝) (findMin le hs✝ 1 (h✝¹, 0)).snd))
        (findMin le hs✝ 1 (h✝¹, 0)).fst.children =
      ys
h✝ : t ∈ hs✝
⊢ ∀ (z : α), le z z = true
Tactic:
assumption
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
⊢ deleteMin le (Heap.heap []) = some (y, ys) → IsHeap ys ∧ IsMinHeap le ys
Tactic:
intro eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
eq : deleteMin le (Heap.heap []) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
eq : deleteMin le (Heap.heap []) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
unfold deleteMin at eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
eq :
  (match Heap.heap [] with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
eq :
  (match Heap.heap [] with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
dsimp at eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
eq : none = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h₁ : IsHeap (Heap.heap [])
h₂ : IsMinHeap le (Heap.heap [])
eq : none = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
contradiction
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
⊢ deleteMin le (Heap.heap [h]) = some (y, ys) → IsHeap ys ∧ IsMinHeap le ys
Tactic:
intro eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : deleteMin le (Heap.heap [h]) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : deleteMin le (Heap.heap [h]) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
unfold deleteMin at eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq :
  (match Heap.heap [h] with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq :
  (match Heap.heap [h] with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
dsimp at eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : some (h.val, h.children) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : some (h.val, h.children) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
rw[Option.some_inj, Prod.eq_iff_fst_eq_snd_eq] at eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : (h.val, h.children).fst = (y, ys).fst ∧ (h.val, h.children).snd = (y, ys).snd
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : (h.val, h.children).fst = (y, ys).fst ∧ (h.val, h.children).snd = (y, ys).snd
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
simp at eq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
apply And.intro
Proof state after:
case left
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsHeap ys

case right
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
case left
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsHeap ys

case right
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsMinHeap le ys
Tactic:
. rw[← eq.right]
  apply children_IsHeap
  assumption
Proof state after:
case right
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
case right
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
h₁ : IsHeap (Heap.heap [h])
h₂ : IsMinHeap le (Heap.heap [h])
eq : h.val = y ∧ h.children = ys
⊢ IsMinHeap le ys
Tactic:
. rw[← eq.right]
  apply children_IsMinHeap
  assumption
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
⊢ deleteMin le (Heap.heap (h :: hs)) = some (y, ys) → IsHeap ys ∧ IsMinHeap le ys
Tactic:
intro dmeq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
dmeq : deleteMin le (Heap.heap (h :: hs)) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
dmeq : deleteMin le (Heap.heap (h :: hs)) = some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys
Tactic:
unfold deleteMin at dmeq
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
dmeq :
  (match Heap.heap (h :: hs) with
    | Heap.heap [] => none
    | Heap.heap [h] => some (h.val, h.children)
    | Heap.heap hhs@h_1:(h :: hs) =>
      match findMin le hs 1 (h, 0) with
      | (min, minIdx) =>
        let rest := List.eraseIdx hhs minIdx;
        let tail := merge le (Heap.heap rest) min.children;
        some (min.val, tail)) =
    some (y, ys)
⊢ IsHeap ys ∧ IsMinHeap le ys