internlm/Lean-Github huggingface dataset:
Theorem: project.empty_heap_merge_right
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
h : List (BinTree α)
⊢ (match h, [] with
    | [], h => h
    | h, [] => h
    | f@h:(h₁ :: t₁), s@h_1:(h₂ :: t₂) =>
      if h₁.rank < h₂.rank then h₁ :: mergeNodes le t₁ s
      else
        if h₂.rank < h₁.rank then h₂ :: mergeNodes le t₂ f
        else
          let merged := combine le h₁ h₂;
          let r := merged.rank;
          if (r != hRank t₁) = true then
            if (r != hRank t₂) = true then merged :: mergeNodes le t₁ t₂ else mergeNodes le (merged :: t₁) t₂
          else if (r != hRank t₂) = true then mergeNodes le t₁ (merged :: t₂) else merged :: mergeNodes le t₁ t₂) =
    h
Tactic:
split
Proof state after:
case h_1
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
⊢ [] = []

case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝³ x✝² x✝¹ : List (BinTree α)
x✝ : x✝³ = [] → False
heq✝ : [] = []
⊢ x✝³ = x✝³

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₂✝ :: t₂✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₁✝ :: t₁✝
Theorem: project.empty_heap_merge_right
Proof state before:
case h_1
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
⊢ [] = []

case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝³ x✝² x✝¹ : List (BinTree α)
x✝ : x✝³ = [] → False
heq✝ : [] = []
⊢ x✝³ = x✝³

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₂✝ :: t₂✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₁✝ :: t₁✝
Tactic:
. rfl
Proof state after:
case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝³ x✝² x✝¹ : List (BinTree α)
x✝ : x✝³ = [] → False
heq✝ : [] = []
⊢ x✝³ = x✝³

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₂✝ :: t₂✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₁✝ :: t₁✝
Theorem: project.empty_heap_merge_right
Proof state before:
case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝³ x✝² x✝¹ : List (BinTree α)
x✝ : x✝³ = [] → False
heq✝ : [] = []
⊢ x✝³ = x✝³

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₂✝ :: t₂✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₁✝ :: t₁✝
Tactic:
. rfl
Proof state after:
case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₂✝ :: t₂✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₁✝ :: t₁✝
Theorem: project.empty_heap_merge_right
Proof state before:
case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₂✝ :: t₂✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₁✝ :: t₁✝
Tactic:
. rename_i heq
  cases heq
Proof state after:
no goals
Theorem: project.IsHeapForest'_weaken
Proof state before:
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
xs : List (BinTree α✝)
m : ℕ
⊢ IsHeapForest' n xs → m ≤ n → IsHeapForest' m xs
Tactic:
intros hf hle
Proof state after:
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
xs : List (BinTree α✝)
m : ℕ
hf : IsHeapForest' n xs
hle : m ≤ n
⊢ IsHeapForest' m xs
Theorem: project.IsHeapForest'_weaken
Proof state before:
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
xs : List (BinTree α✝)
m : ℕ
hf : IsHeapForest' n xs
hle : m ≤ n
⊢ IsHeapForest' m xs
Tactic:
cases hf with 
| nil => constructor
| cons hlt _ _ => 
  constructor <;> try assumption
  . apply Nat.lt_of_le_of_lt hle hlt
Proof state after:
no goals
Theorem: project.IsHeapForest'_weaken
Proof state before:
case nil
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
m : ℕ
hle : m ≤ n
⊢ IsHeapForest' m []
Tactic:
constructor
Proof state after:
no goals
Theorem: project.IsHeapForest'_weaken
Proof state before:
case cons
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
m : ℕ
hle : m ≤ n
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝¹ : IsBinTree t✝
a✝ : IsHeapForest' t✝.rank ts✝
hlt : n < t✝.rank
⊢ IsHeapForest' m (t✝ :: ts✝)
Tactic:
constructor <;> try assumption
Proof state after:
case cons.a
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
m : ℕ
hle : m ≤ n
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝¹ : IsBinTree t✝
a✝ : IsHeapForest' t✝.rank ts✝
hlt : n < t✝.rank
⊢ m < t✝.rank
Theorem: project.IsHeapForest'_weaken
Proof state before:
case cons.a
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
m : ℕ
hle : m ≤ n
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝¹ : IsBinTree t✝
a✝ : IsHeapForest' t✝.rank ts✝
hlt : n < t✝.rank
⊢ m < t✝.rank
Tactic:
. apply Nat.lt_of_le_of_lt hle hlt
Proof state after:
no goals
Theorem: project.IsHeapForest'_weaken
Proof state before:
case cons.a
α : Sort ?u.12184
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
n : ℕ
α✝ : Type u_1
m : ℕ
hle : m ≤ n
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝¹ : IsBinTree t✝
a✝ : IsHeapForest' t✝.rank ts✝
hlt : n < t✝.rank
⊢ IsHeapForest' t✝.rank ts✝
Tactic:
assumption
Proof state after:
no goals
Theorem: project.rank_combine
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
⊢ t₁.rank = t₂.rank → (combine le t₁ t₂).rank = t₁.rank + 1
Tactic:
intro
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
⊢ (combine le t₁ t₂).rank = t₁.rank + 1
Theorem: project.rank_combine
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
⊢ (combine le t₁ t₂).rank = t₁.rank + 1
Tactic:
unfold combine
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
⊢ (if le t₂.val t₁.val = true then
        { val := t₂.val, rank := t₂.rank + 1, children := Heap.heap (Heap.nodes t₂.children ++ [t₁]) }
      else { val := t₁.val, rank := t₁.rank + 1, children := Heap.heap (Heap.nodes t₁.children ++ [t₂]) }).rank =
    t₁.rank + 1
Theorem: project.rank_combine
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
⊢ (if le t₂.val t₁.val = true then
        { val := t₂.val, rank := t₂.rank + 1, children := Heap.heap (Heap.nodes t₂.children ++ [t₁]) }
      else { val := t₁.val, rank := t₁.rank + 1, children := Heap.heap (Heap.nodes t₁.children ++ [t₂]) }).rank =
    t₁.rank + 1
Tactic:
split
Proof state after:
case inl
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
h✝ : le t₂.val t₁.val = true
⊢ { val := t₂.val, rank := t₂.rank + 1, children := Heap.heap (Heap.nodes t₂.children ++ [t₁]) }.rank = t₁.rank + 1

case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
h✝ : ¬le t₂.val t₁.val = true
⊢ { val := t₁.val, rank := t₁.rank + 1, children := Heap.heap (Heap.nodes t₁.children ++ [t₂]) }.rank = t₁.rank + 1
Theorem: project.rank_combine
Proof state before:
case inl
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
h✝ : le t₂.val t₁.val = true
⊢ { val := t₂.val, rank := t₂.rank + 1, children := Heap.heap (Heap.nodes t₂.children ++ [t₁]) }.rank = t₁.rank + 1

case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
h✝ : ¬le t₂.val t₁.val = true
⊢ { val := t₁.val, rank := t₁.rank + 1, children := Heap.heap (Heap.nodes t₁.children ++ [t₂]) }.rank = t₁.rank + 1
Tactic:
. dsimp
  simp
  simp_all
Proof state after:
case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
h✝ : ¬le t₂.val t₁.val = true
⊢ { val := t₁.val, rank := t₁.rank + 1, children := Heap.heap (Heap.nodes t₁.children ++ [t₂]) }.rank = t₁.rank + 1
Theorem: project.rank_combine
Proof state before:
case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
t₁ t₂ : BinTree α
a✝ : t₁.rank = t₂.rank
h✝ : ¬le t₂.val t₁.val = true
⊢ { val := t₁.val, rank := t₁.rank + 1, children := Heap.heap (Heap.nodes t₁.children ++ [t₂]) }.rank = t₁.rank + 1
Tactic:
. dsimp
Proof state after:
no goals
Theorem: project.IsHeapForest'_strengthen_pred
Proof state before:
α : Sort ?u.14584
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
α✝ : Type u_1
t : BinTree α✝
ts : List (BinTree α✝)
hf : IsHeapForest' r (t :: ts)
hpos : t.rank > 0
⊢ IsHeapForest' (t.rank - 1) (t :: ts)
Tactic:
cases hf
Proof state after:
case cons
α : Sort ?u.14584
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
α✝ : Type u_1
t : BinTree α✝
ts : List (BinTree α✝)
hpos : t.rank > 0
a✝² : IsBinTree t
a✝¹ : r < t.rank
a✝ : IsHeapForest' t.rank ts
⊢ IsHeapForest' (t.rank - 1) (t :: ts)
Theorem: project.IsHeapForest'_strengthen_pred
Proof state before:
case cons
α : Sort ?u.14584
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
α✝ : Type u_1
t : BinTree α✝
ts : List (BinTree α✝)
hpos : t.rank > 0
a✝² : IsBinTree t
a✝¹ : r < t.rank
a✝ : IsHeapForest' t.rank ts
⊢ IsHeapForest' (t.rank - 1) (t :: ts)
Tactic:
constructor <;> try assumption
Proof state after:
case cons.a
α : Sort ?u.14584
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
α✝ : Type u_1
t : BinTree α✝
ts : List (BinTree α✝)
hpos : t.rank > 0
a✝² : IsBinTree t
a✝¹ : r < t.rank
a✝ : IsHeapForest' t.rank ts
⊢ t.rank - 1 < t.rank
Theorem: project.IsHeapForest'_strengthen_pred
Proof state before:
case cons.a
α : Sort ?u.14584
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
α✝ : Type u_1
t : BinTree α✝
ts : List (BinTree α✝)
hpos : t.rank > 0
a✝² : IsBinTree t
a✝¹ : r < t.rank
a✝ : IsHeapForest' t.rank ts
⊢ t.rank - 1 < t.rank
Tactic:
. apply Nat.sub_lt_self
  . decide
  . assumption
Proof state after:
no goals
Theorem: project.IsHeapForest'_strengthen_pred
Proof state before:
case cons.a
α : Sort ?u.14584
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
α✝ : Type u_1
t : BinTree α✝
ts : List (BinTree α✝)
hpos : t.rank > 0
a✝² : IsBinTree t
a✝¹ : r < t.rank
a✝ : IsHeapForest' t.rank ts
⊢ IsHeapForest' t.rank ts
Tactic:
assumption
Proof state after:
no goals
Theorem: project.IsHeapForest'_strengthen
Proof state before:
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ts : List (BinTree α✝)
ry : ℕ
⊢ IsHeapForest' rx ts → ry < hRank ts → IsHeapForest' ry ts
Tactic:
intros hf _
Proof state after:
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ts : List (BinTree α✝)
ry : ℕ
hf : IsHeapForest' rx ts
a✝ : ry < hRank ts
⊢ IsHeapForest' ry ts
Theorem: project.IsHeapForest'_strengthen
Proof state before:
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ts : List (BinTree α✝)
ry : ℕ
hf : IsHeapForest' rx ts
a✝ : ry < hRank ts
⊢ IsHeapForest' ry ts
Tactic:
cases hf
Proof state after:
case nil
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
a✝ : ry < hRank []
⊢ IsHeapForest' ry []

case cons
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝³ : IsBinTree t✝
a✝² : IsHeapForest' t✝.rank ts✝
a✝¹ : rx < t✝.rank
a✝ : ry < hRank (t✝ :: ts✝)
⊢ IsHeapForest' ry (t✝ :: ts✝)
Theorem: project.IsHeapForest'_strengthen
Proof state before:
case nil
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
a✝ : ry < hRank []
⊢ IsHeapForest' ry []

case cons
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝³ : IsBinTree t✝
a✝² : IsHeapForest' t✝.rank ts✝
a✝¹ : rx < t✝.rank
a✝ : ry < hRank (t✝ :: ts✝)
⊢ IsHeapForest' ry (t✝ :: ts✝)
Tactic:
. constructor
Proof state after:
case cons
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝³ : IsBinTree t✝
a✝² : IsHeapForest' t✝.rank ts✝
a✝¹ : rx < t✝.rank
a✝ : ry < hRank (t✝ :: ts✝)
⊢ IsHeapForest' ry (t✝ :: ts✝)
Theorem: project.IsHeapForest'_strengthen
Proof state before:
case cons
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝³ : IsBinTree t✝
a✝² : IsHeapForest' t✝.rank ts✝
a✝¹ : rx < t✝.rank
a✝ : ry < hRank (t✝ :: ts✝)
⊢ IsHeapForest' ry (t✝ :: ts✝)
Tactic:
. constructor
  repeat assumption
Proof state after:
no goals
Theorem: project.IsHeapForest'_strengthen
Proof state before:
case cons.a
α : Sort ?u.15173
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
rx : ℕ
α✝ : Type u_1
ry : ℕ
t✝ : BinTree α✝
ts✝ : List (BinTree α✝)
a✝³ : IsBinTree t✝
a✝² : IsHeapForest' t✝.rank ts✝
a✝¹ : rx < t✝.rank
a✝ : ry < hRank (t✝ :: ts✝)
⊢ IsHeapForest' t✝.rank ts✝
Tactic:
assumption
Proof state after:
no goals
Theorem: project.Bool.not_eq_false'
Proof state before:
α : Sort ?u.15922
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x : Bool
⊢ (!x) = false ↔ x = true
Tactic:
cases x <;> simp
Proof state after:
no goals
Theorem: project.min_hRank_mergeNodes
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
⊢ min (hRank []) (hRank h) ≤ hRank (mergeNodes le [] h)
Tactic:
rw[Nat.min_eq]
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
⊢ (if hRank [] ≤ hRank h then hRank [] else hRank h) ≤ hRank (mergeNodes le [] h)
Theorem: project.min_hRank_mergeNodes
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
⊢ (if hRank [] ≤ hRank h then hRank [] else hRank h) ≤ hRank (mergeNodes le [] h)
Tactic:
split
Proof state after:
case inl
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
h✝ : hRank [] ≤ hRank h
⊢ hRank [] ≤ hRank (mergeNodes le [] h)

case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
h✝ : ¬hRank [] ≤ hRank h
⊢ hRank h ≤ hRank (mergeNodes le [] h)
Theorem: project.min_hRank_mergeNodes
Proof state before:
case inl
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
h✝ : hRank [] ≤ hRank h
⊢ hRank [] ≤ hRank (mergeNodes le [] h)

case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
h✝ : ¬hRank [] ≤ hRank h
⊢ hRank h ≤ hRank (mergeNodes le [] h)
Tactic:
. rw[empty_heap_merge_left]
  assumption
Proof state after:
case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
h✝ : ¬hRank [] ≤ hRank h
⊢ hRank h ≤ hRank (mergeNodes le [] h)
Theorem: project.min_hRank_mergeNodes
Proof state before:
case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r []
ht₂ : IsHeapForest' r h
h✝ : ¬hRank [] ≤ hRank h
⊢ hRank h ≤ hRank (mergeNodes le [] h)
Tactic:
. rw[empty_heap_merge_left]
Proof state after:
no goals
Theorem: project.min_hRank_mergeNodes
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
⊢ min (hRank h) (hRank []) ≤ hRank (mergeNodes le h [])
Tactic:
rw[empty_heap_merge_right, Nat.min_eq]
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
⊢ (if hRank h ≤ hRank [] then hRank h else hRank []) ≤ hRank h
Theorem: project.min_hRank_mergeNodes
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
⊢ (if hRank h ≤ hRank [] then hRank h else hRank []) ≤ hRank h
Tactic:
split
Proof state after:
case inl
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
h✝ : hRank h ≤ hRank []
⊢ hRank h ≤ hRank h

case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
h✝ : ¬hRank h ≤ hRank []
⊢ hRank [] ≤ hRank h
Theorem: project.min_hRank_mergeNodes
Proof state before:
case inl
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
h✝ : hRank h ≤ hRank []
⊢ hRank h ≤ hRank h

case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
h✝ : ¬hRank h ≤ hRank []
⊢ hRank [] ≤ hRank h
Tactic:
. rfl
Proof state after:
case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
h✝ : ¬hRank h ≤ hRank []
⊢ hRank [] ≤ hRank h
Theorem: project.min_hRank_mergeNodes
Proof state before:
case inr
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys h : List (BinTree α)
ht₁ : IsHeapForest' r h
ht₂ : IsHeapForest' r []
h✝ : ¬hRank h ≤ hRank []
⊢ hRank [] ≤ hRank h
Tactic:
. simp at *
  apply Nat.le_of_lt
  assumption
Proof state after:
no goals
Theorem: project.min_hRank_mergeNodes
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
ht₁ : IsHeapForest' r (h₁ :: t₁)
ht₂ : IsHeapForest' r (h₂ :: t₂)
⊢ min (hRank (h₁ :: t₁)) (hRank (h₂ :: t₂)) ≤ hRank (mergeNodes le (h₁ :: t₁) (h₂ :: t₂))
Tactic:
unfold mergeNodes
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
r : ℕ
xs ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
ht₁ : IsHeapForest' r (h₁ :: t₁)
ht₂ : IsHeapForest' r (h₂ :: t₂)
⊢ min (hRank (h₁ :: t₁)) (hRank (h₂ :: t₂)) ≤
    hRank
      (if h₁.rank < h₂.rank then h₁ :: mergeNodes le t₁ (h₂ :: t₂)
      else
        if h₂.rank < h₁.rank then h₂ :: mergeNodes le t₂ (h₁ :: t₁)
        else
          let merged := combine le h₁ h₂;
          let r := merged.rank;
          if (r != hRank t₁) = true then
            if (r != hRank t₂) = true then merged :: mergeNodes le t₁ t₂ else mergeNodes le (merged :: t₁) t₂
          else if (r != hRank t₂) = true then mergeNodes le t₁ (merged :: t₂) else merged :: mergeNodes le t₁ t₂)