Proof step 1 from proof diff-size (conclusion) (back to tree)

System applied rule normalize

And obtained the following new goals

• Proof step 2:

  ¬(#(h \ rs) ≤ #((h -- r) \ rs) ↔ false), r ∈ h \ rs ⊦

Rule argument

Additional information

Proof step 2 from proof diff-size (previous step) (back to tree)

User applied rule structural induction

And obtained the following new goals

• Proof step 3:

  ¬(#(h \ ∅) ≤ #((h -- r) \ ∅) ↔ false), r ∈ h \ ∅ ⊦

• Proof step 6:

  ¬(#(h \ (rs0 ++ r0)) ≤ #((h -- r) \ (rs0 ++ r0)) ↔ false), r ∈ h \ (rs0 ++ r0), ∀ h, r. ¬(¬(#(h \ rs0) ≤ #((h -- r) \ rs0) ↔ false) ∧ r ∈ h \ rs0) ⊦

Rule argument

Additional information

Used simplifier rules: refset generated by ∅, ++;;

Proof step 3 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 4:

  r ∈ h, # h ≤ #(h -- r) ⊦

Rule argument

Additional information

Used simplifier rules: diffs-emp: ⊦ h0 \ ∅ = h0;

Proof step 4 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 5:

  ⊦ r ≠ null → (r ∈ h ↔ (∃ h0, o. h = (h0 ++ r)[r, o] ∧ ¬ r ∈ h0))

Rule argument

Additional information

Used simplifier rules: sanity: ⊦ ¬ null ∈ h; size-write: r ∈ h ⊦ # h[r, o] = # h; size-alloc: ¬ r ∈ h, r ≠ null ⊦ #(h ++ r) = # h + 1; in-alloc: r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; write-del: r ∈ h ⊦ h[r, o] -- r = h -- r; del-new: ¬ r ∈ h, r ≠ null ⊦ (h ++ r) -- r = h; ⊦ m + 1 ≤ n ↔ m < n; (s) ⊦ ¬ n < n; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: r, h

Proof step 5 from proof diff-size (previous step) (back to tree)

Lemma exin

Proof step 6 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 7:

  r ∈ (h -- r0) \ rs0, #((h -- r0) \ rs0) ≤ #((h -- r -- r0) \ rs0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used simplifier rules: diffs-ins: ⊦ h0 \ (rs ++ r) = (h0 -- r) \ rs;

Proof step 7 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 8:

  ⊦ (h -- r) \ rs = (h \ rs) -- r

• Proof step 9:

  r ∈ (h \ rs0) -- r0, #((h \ rs0) -- r0) ≤ #((h -- r -- r0) \ rs0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used terms: h, r0, rs0

Proof step 8 from proof diff-size (previous step) (back to tree)

Lemma diffs-sw

Proof step 9 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 10:

  r ≠ r0, r ∈ h \ rs0, #((h \ rs0) -- r0) ≤ #((h -- r -- r0) \ rs0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used simplifier rules: in-del: ⊦ r ∈ h -- r0 ↔ r ≠ r0 ∧ r ∈ h;

Proof step 10 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 11:

  ⊦ (h -- r) \ rs = (h \ rs) -- r

• Proof step 12:

  r ≠ r0, r ∈ h \ rs0, #((h \ rs0) -- r0) ≤ #(((h -- r) \ rs0) -- r0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used terms: h -- r, r0, rs0

Proof step 11 from proof diff-size (previous step) (back to tree)

Lemma diffs-sw

Proof step 12 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 13:

  ⊦ r ∈ h → #(h -- r) = # h - 1

• Proof step 14:

  r ≠ r0, r ∈ h \ rs0, #((h \ rs0) -- r0) ≤ #(((h -- r) \ rs0) -- r0), ¬ r0 ∈ h \ rs0, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

• Proof step 22:

  r ≠ r0, r ∈ h \ rs0, r0 ∈ h \ rs0, #(h \ rs0) - 1 ≤ #(((h -- r) \ rs0) -- r0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used terms: h \ rs0, r0

Proof step 13 from proof diff-size (previous step) (back to tree)

Lemma rm-size

Proof step 14 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 15:

  r ≠ r0, r ∈ h \ rs0, #(h \ rs0) ≤ #(((h -- r) \ rs0) -- r0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

Rule argument

Additional information

Used simplifier rules: del-notin: ⊦ ¬ r ∈ h → h -- r = h; in-diffs: ⊦ r ∈ h \ rs ↔ r ∈ h ∧ ¬ r ∈ rs;

Proof step 15 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 16:

  ⊦ ¬ r ∈ h → h -- r = h

• Proof step 17:

  r ≠ r0, r0 ∈ (h -- r) \ rs0, r ∈ h \ rs0, #(h \ rs0) ≤ #(((h -- r) \ rs0) -- r0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

• Proof step 20:

  r ≠ r0, r ∈ h \ rs0, #(h \ rs0) ≤ #((h -- r) \ rs0), ¬ r0 ∈ (h -- r) \ rs0, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

Rule argument

Additional information

Used terms: (h -- r) \ rs0, r0

Proof step 16 from proof diff-size (previous step) (back to tree)

Lemma del-notin

Proof step 17 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 18:

  r ≠ r0, r ∈ h \ rs0, r0 ∈ (h -- r) \ rs0, #(h \ rs0) ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

Rule argument

Additional information

Used simplifier rules: rm-size: ⊦ r ∈ h → #(h -- r) = # h - 1;

Proof step 18 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 19:

  ⊦ r ∈ h \ rs ↔ r ∈ h ∧ ¬ r ∈ rs

Rule argument

Additional information

Used simplifier rules: in-del: ⊦ r ∈ h -- r0 ↔ r ≠ r0 ∧ r ∈ h; Used terms: r0, h -- r, rs0

Proof step 19 from proof diff-size (previous step) (back to tree)

Lemma in-diffs

Proof step 20 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 21:

  r ≠ r0, r ∈ h \ rs0, #(h \ rs0) ≤ #((h -- r) \ rs0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

Rule argument

Additional information

Used simplifier rules: in-diffs: ⊦ r ∈ h \ rs ↔ r ∈ h ∧ ¬ r ∈ rs; in-del: ⊦ r ∈ h -- r0 ↔ r ≠ r0 ∧ r ∈ h;

Proof step 21 from proof diff-size (previous step) (back to tree)

Heuristic quantifier closing applied rule all left

And closed the goal!

Rule argument

Additional information

Used terms: h, r

Proof step 22 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 23:

  ⊦ r ∈ h → #(h -- r) = # h - 1

• Proof step 24:

  r ≠ r0, r0 ∈ h \ rs0, r ∈ h \ rs0, #(h \ rs0) - 1 ≤ #(((h -- r) \ rs0) -- r0), ¬ r0 ∈ (h -- r) \ rs0, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

• Proof step 29:

  r ≠ r0, r0 ∈ h \ rs0, r ∈ h \ rs0, r0 ∈ (h -- r) \ rs0, #(h \ rs0) - 1 ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used terms: (h -- r) \ rs0, r0

Proof step 23 from proof diff-size (previous step) (back to tree)

Lemma rm-size

Proof step 24 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 25:

  r ≠ r0, r ∈ h \ rs0, r0 ∈ h \ rs0, #(h \ rs0) - 1 ≤ #((h -- r) \ rs0), ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

Rule argument

Additional information

Used simplifier rules: del-notin: ⊦ ¬ r ∈ h → h -- r = h; in-diffs: ⊦ r ∈ h \ rs ↔ r ∈ h ∧ ¬ r ∈ rs; in-del: ⊦ r ∈ h -- r0 ↔ r ≠ r0 ∧ r ∈ h;

Proof step 25 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 26:

  ⊦ r ∈ h \ rs ↔ r ∈ h ∧ ¬ r ∈ rs

• Proof step 27:

  r ≠ r0, r0 ∈ h \ rs0, r ∈ h, #(h \ rs0) - 1 ≤ #((h -- r) \ rs0), ¬ r ∈ rs0, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦ r0 ∈ h ∧ ¬ r0 ∈ rs0

Rule argument

Additional information

Used terms: r, h, rs0

Proof step 26 from proof diff-size (previous step) (back to tree)

Lemma in-diffs

Proof step 27 from proof diff-size (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 28:

  ⊦ r ∈ h \ rs ↔ r ∈ h ∧ ¬ r ∈ rs

Rule argument

Additional information

Used terms: r0, h, rs0

Proof step 28 from proof diff-size (previous step) (back to tree)

Lemma in-diffs

Proof step 29 from proof diff-size (previous step) (back to tree)

User applied rule apply elim lemma

And obtained the following new goals

• Proof step 30:

  #(h \ rs0) = 0, r ≠ r0, r0 ∈ (h -- r) \ rs0, r ∈ h \ rs0, r0 ∈ h \ rs0, #(h \ rs0) - 1 ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

• Proof step 32:

  #(h \ rs0) = n0 + 1, #(h \ rs0) ≠ 0, r ≠ r0, r0 ∈ (h -- r) \ rs0, r ∈ h \ rs0, r0 ∈ h \ rs0, n0 ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used simplifier rules: n ≠ 0 ⊦ m = n - 1 ↔ n = m + 1; (elim) Used terms: #(h \ rs0), m

Proof step 30 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 31:

  #(h \ rs0) = 0, r ≠ r0, r0 ∈ h \ rs0, r ∈ h \ rs0, r0 ∈ (h -- r) \ rs0, 0 - 1 ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Proof step 31 from proof diff-size (previous step) (back to tree)

Heuristic quantifier closing applied rule all left

And closed the goal!

Rule argument

Additional information

Used simplifier rules: ⊦ m ≤ n ↔ ¬ n < m; (ss) ⊦ m < n → n ≠ 0; (s) Used terms: h, r

Proof step 32 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 33:

  #(h \ rs0) = n0 + 1, r ≠ r0, r0 ∈ (h -- r) \ rs0, r ∈ h \ rs0, r0 ∈ h \ rs0, n0 ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m + 1 ≠ 0; (s)

Proof step 33 from proof diff-size (previous step) (back to tree)

User applied rule apply elim lemma

And obtained the following new goals

• Proof step 34:

  #((h -- r) \ rs0) = 0, #(h \ rs0) = n0 + 1, r ≠ r0, r0 ∈ h \ rs0, r ∈ h \ rs0, r0 ∈ (h -- r) \ rs0, n0 ≤ #((h -- r) \ rs0) - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

• Proof step 36:

  #(h \ rs0) = n0 + 1, #((h -- r) \ rs0) = n1 + 1, #((h -- r) \ rs0) ≠ 0, r ≠ r0, r0 ∈ h \ rs0, r ∈ h \ rs0, r0 ∈ (h -- r) \ rs0, n0 ≤ n1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used simplifier rules: n ≠ 0 ⊦ m = n - 1 ↔ n = m + 1; (elim) Used terms: #((h -- r) \ rs0), m

Proof step 34 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 35:

  #(h \ rs0) = n0 + 1, #((h -- r) \ rs0) = 0, r ≠ r0, r0 ∈ (h -- r) \ rs0, r ∈ h \ rs0, r0 ∈ h \ rs0, n0 ≤ 0 - 1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Proof step 35 from proof diff-size (previous step) (back to tree)

Heuristic quantifier closing applied rule all left

And closed the goal!

Rule argument

Additional information

Used simplifier rules: ⊦ m ≤ n ↔ ¬ n < m; (ss) ⊦ m < n → n ≠ 0; (s) Used terms: h -- r, r0

Proof step 36 from proof diff-size (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 37:

  #(h \ rs0) = n0 + 1, #((h -- r) \ rs0) = n1 + 1, r ≠ r0, r0 ∈ h \ rs0, r ∈ h \ rs0, r0 ∈ (h -- r) \ rs0, n0 ≤ n1, ∀ h0, r1. ¬ #(h0 \ rs0) ≤ #((h0 -- r1) \ rs0) ∨ ¬ r1 ∈ h0 \ rs0 ⊦

Rule argument

Additional information

Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m + 1 ≠ 0; (s)

Proof step 37 from proof diff-size (previous step) (back to tree)

User applied rule all left

And closed the goal!

Rule argument

Additional information

Used simplifier rules: ⊦ m ≤ n ↔ ¬ n < m; (ss) f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic lf-02: ⊦ m < n ∧ m = n0 → n0 < n; (forward) from specification nat-basic lf-01: ⊦ m < n ∧ n = n0 → m < n0; (forward) from specification nat-basic ⊦ m + 1 ≠ 0; (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) ⊦ m ≤ m0 ∧ n ≤ n0 → ¬ m0 + n0 < m + n; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: h, r