internlm/Lean-Github huggingface dataset:
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq : (h₁.rank + 1 != hRank []) = true
bt : BinTree α
ts✝ : List (BinTree α)
hlt : h₁.rank < bt.rank
a✝¹ : IsBinTree bt
a✝ : IsHeapForest' bt.rank ts✝
hneq₂ : (!h₁.rank + 1 == bt.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (bt :: ts✝)
h : ¬([] = [] ∧ bt :: ts✝ = [])
h✝ min_le : hRank [] ≤ bt.rank
⊢ h₁.rank + 1 < bt.rank
Tactic:
rw[Nat.not_beq_eq_true_eq] at hneq₂
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq : (h₁.rank + 1 != hRank []) = true
bt : BinTree α
ts✝ : List (BinTree α)
hlt : h₁.rank < bt.rank
a✝¹ : IsBinTree bt
a✝ : IsHeapForest' bt.rank ts✝
hneq₂ : ¬h₁.rank + 1 = bt.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (bt :: ts✝)
h : ¬([] = [] ∧ bt :: ts✝ = [])
h✝ min_le : hRank [] ≤ bt.rank
⊢ h₁.rank + 1 < bt.rank
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq : (h₁.rank + 1 != hRank []) = true
bt : BinTree α
ts✝ : List (BinTree α)
hlt : h₁.rank < bt.rank
a✝¹ : IsBinTree bt
a✝ : IsHeapForest' bt.rank ts✝
hneq₂ : ¬h₁.rank + 1 = bt.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (bt :: ts✝)
h : ¬([] = [] ∧ bt :: ts✝ = [])
h✝ min_le : hRank [] ≤ bt.rank
⊢ h₁.rank + 1 < bt.rank
Tactic:
have n : h₁.rank + 1 ≤ bt.rank := by
  apply Nat.succ_le_of_lt hlt
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq : (h₁.rank + 1 != hRank []) = true
bt : BinTree α
ts✝ : List (BinTree α)
hlt : h₁.rank < bt.rank
a✝¹ : IsBinTree bt
a✝ : IsHeapForest' bt.rank ts✝
hneq₂ : ¬h₁.rank + 1 = bt.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (bt :: ts✝)
h : ¬([] = [] ∧ bt :: ts✝ = [])
h✝ min_le : hRank [] ≤ bt.rank
n : h₁.rank + 1 ≤ bt.rank
⊢ h₁.rank + 1 < bt.rank
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq : (h₁.rank + 1 != hRank []) = true
bt : BinTree α
ts✝ : List (BinTree α)
hlt : h₁.rank < bt.rank
a✝¹ : IsBinTree bt
a✝ : IsHeapForest' bt.rank ts✝
hneq₂ : ¬h₁.rank + 1 = bt.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (bt :: ts✝)
h : ¬([] = [] ∧ bt :: ts✝ = [])
h✝ min_le : hRank [] ≤ bt.rank
n : h₁.rank + 1 ≤ bt.rank
⊢ h₁.rank + 1 < bt.rank
Tactic:
apply lt_of_le_of_ne <;> assumption
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq : (h₁.rank + 1 != hRank []) = true
bt : BinTree α
ts✝ : List (BinTree α)
hlt : h₁.rank < bt.rank
a✝¹ : IsBinTree bt
a✝ : IsHeapForest' bt.rank ts✝
hneq₂ : ¬h₁.rank + 1 = bt.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (bt :: ts✝)
h : ¬([] = [] ∧ bt :: ts✝ = [])
h✝ min_le : hRank [] ≤ bt.rank
⊢ h₁.rank + 1 ≤ bt.rank
Tactic:
apply Nat.succ_le_of_lt hlt
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (h₁.rank + 1 != hRank (t :: ts)) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : hRank (t :: ts) ≤ hRank t₂
min_le : hRank (t :: ts) ≤ hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
rw[hrank_of_cons] at *
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (h₁.rank + 1 != t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (h₁.rank + 1 != t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
have : h₁.rank < hRank (mergeNodes le (t :: ts) t₂) := by
  apply lt_of_lt_of_le <;> assumption
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (h₁.rank + 1 != t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (h₁.rank + 1 != t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
unfold bne at hneq
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (!h₁.rank + 1 == t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (!h₁.rank + 1 == t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
rw[Nat.not_beq_eq_true_eq] at hneq
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
have : h₁.rank + 1 ≤ t.rank := by
  apply Nat.succ_le_of_lt hlt
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this✝ : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank + 1 ≤ t.rank
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this✝ : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank + 1 ≤ t.rank
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
have : h₁.rank + 1 < t.rank := by
  apply lt_of_le_of_ne <;> assumption
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this✝¹ : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
this✝ : h₁.rank + 1 ≤ t.rank
this : h₁.rank + 1 < t.rank
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this✝¹ : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
this✝ : h₁.rank + 1 ≤ t.rank
this : h₁.rank + 1 < t.rank
⊢ h₁.rank + 1 < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
apply lt_of_lt_of_le <;> assumption
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : (h₁.rank + 1 != t.rank) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
Tactic:
apply lt_of_lt_of_le <;> assumption
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
⊢ h₁.rank + 1 ≤ t.rank
Tactic:
apply Nat.succ_le_of_lt hlt
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq₂ : (h₁.rank + 1 != hRank t₂) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝⁵ : IsBinTree h₁
a✝⁴ : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝³ : IsBinTree h₂
a✝² : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
t : BinTree α
ts : List (BinTree α)
hlt : h₁.rank < t.rank
a✝¹ : IsBinTree t
a✝ : IsHeapForest' t.rank ts
hneq : ¬h₁.rank + 1 = t.rank
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le (t :: ts) t₂)
h : ¬(t :: ts = [] ∧ t₂ = [])
h✝ : t.rank ≤ hRank t₂
min_le : t.rank ≤ hRank (mergeNodes le (t :: ts) t₂)
this✝ : h₁.rank < hRank (mergeNodes le (t :: ts) t₂)
this : h₁.rank + 1 ≤ t.rank
⊢ h₁.rank + 1 < t.rank
Tactic:
apply lt_of_le_of_ne <;> assumption
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq : (h₁.rank + 1 != hRank t₁) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝³ : IsBinTree h₁
a✝² : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝¹ : IsBinTree h₂
a✝ : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq₂ : (h₁.rank + 1 != hRank []) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) (mergeNodes le t₁ [])
h : ¬(t₁ = [] ∧ [] = [])
h✝ : ¬hRank t₁ ≤ hRank []
min_le : hRank [] ≤ hRank (mergeNodes le t₁ [])
⊢ h₁.rank + 1 < hRank (mergeNodes le t₁ [])
Tactic:
rw[empty_heap_merge_right] at *
Proof state after:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq : (h₁.rank + 1 != hRank t₁) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝³ : IsBinTree h₁
a✝² : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝¹ : IsBinTree h₂
a✝ : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq₂ : (h₁.rank + 1 != hRank []) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) t₁
h : ¬(t₁ = [] ∧ [] = [])
h✝ : ¬hRank t₁ ≤ hRank []
min_le : hRank [] ≤ hRank t₁
⊢ h₁.rank + 1 < hRank t₁
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
hneq : (h₁.rank + 1 != hRank t₁) = true
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝³ : IsBinTree h₁
a✝² : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝¹ : IsBinTree h₂
a✝ : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq₂ : (h₁.rank + 1 != hRank []) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) t₁
h : ¬(t₁ = [] ∧ [] = [])
h✝ : ¬hRank t₁ ≤ hRank []
min_le : hRank [] ≤ hRank t₁
⊢ h₁.rank + 1 < hRank t₁
Tactic:
match ht₁ with
| .nil =>
  simp at h
| .cons (t := t) (ts := ts) lt _ _ => 
  rw[hrank_of_cons] at *
  unfold bne at hneq
  rw[Nat.not_beq_eq_true_eq] at hneq
  have : h₁.rank + 1 ≤ t.rank := by
    apply Nat.succ_le_of_lt lt
  apply lt_of_le_of_ne <;> assumption
Proof state after:
no goals
Theorem: project.IsHeap_merge
Proof state before:
α : Type u_1
le : α → α → Bool
rx : ℕ
xs : List (BinTree α)
ry : ℕ
ys : List (BinTree α)
h₁ : BinTree α
t₁ : List (BinTree α)
h₂ : BinTree α
t₂ : List (BinTree α)
not_le_le : ∀ (x y : α), le x y = false → le y x = true
h✝² : h₂.rank ≤ h₁.rank
h✝¹ : h₁.rank ≤ h₂.rank
heq : h₁.rank = h₂.rank
a✝³ : IsBinTree h₁
a✝² : rx < h₁.rank
ht₁ : IsHeapForest' h₁.rank t₁
a✝¹ : IsBinTree h₂
a✝ : ry < h₂.rank
ht₂ : IsHeapForest' h₂.rank t₂
hneq₂ hneq : (h₁.rank + 1 != hRank []) = true
ih : IsHeapForest' (min h₁.rank h₂.rank) []
h : ¬([] = [] ∧ [] = [])
h✝ : ¬hRank [] ≤ hRank []
min_le : hRank [] ≤ hRank []
⊢ h₁.rank + 1 < hRank []
Tactic:
simp at h
Proof state after:
no goals