Theorem: project.deleteMin_non_empty_minimum (Project/DeleteMin.lean)

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 α
⊢ deleteMin le (Heap.heap xs) = some (y, ys) → ∀ (x : HeapNodeAux α (Heap α)), x ∈ xs → le y x.val = true
Tactic:
intros heq t hel
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 : deleteMin le (Heap.heap xs) = some (y, ys)
t : HeapNodeAux α (Heap α)
hel : t ∈ xs
⊢ le y t.val = true

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
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

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
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

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
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

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
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

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
State after:
no goals

State before:
case h_3.inr.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

case h_3.inr.a
α : 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✝
⊢ le (findMin le hs✝ 1 (h✝¹, 0)).fst.val h✝¹.val = true

case h_3.inr.a
α : 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✝
⊢ t ∈ hs✝
Tactic:
assumption
State after:
case h_3.inr.a
α : 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✝
⊢ le (findMin le hs✝ 1 (h✝¹, 0)).fst.val h✝¹.val = true

case h_3.inr.a
α : 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✝
⊢ t ∈ hs✝

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
State after:
no goals