Proof step 1 from proof inj-tr-gen (conclusion) (back to tree)

System applied rule normalize

And obtained the following new goals

• Proof step 2:

  t0 ≠ t, h0 ⊆ h, h1 ⊆ h, tr(r, t0)(h1), tr(r, t)(h0) ⊦

Rule argument

Additional information

Proof step 2 from proof inj-tr-gen (previous step) (back to tree)

User applied rule structural induction

And obtained the following new goals

• Proof step 3:

  t0 ≠ branch(t1, a, t2), h0 ⊆ h, h1 ⊆ h, tr(r, branch(t1, a, t2))(h0), tr(r, t0)(h1), ∀ t0, h0, h, h1, r. ¬(t0 ≠ t2 ∧ h0 ⊆ h ∧ h1 ⊆ h ∧ tr(r, t0)(h1) ∧ tr(r, t2)(h0)), ∀ t0, h0, h, h1, r. ¬(t0 ≠ t1 ∧ h0 ⊆ h ∧ h1 ⊆ h ∧ tr(r, t0)(h1) ∧ tr(r, t1)(h0)) ⊦

Rule argument

Additional information

Used simplifier rules: tr-base: ⊦ tr(r, leaf) = (emp ∧ ⌜r = null⌝ ); tr-null: ⊦ tr(null, t) = (emp ∧ ⌜t = leaf⌝ ); Tree[A] freely generated by leaf, branch; ⊦ (hP0 ∧ hP1)(h) ↔ hP0(h) ∧ hP1(h); (s) ⊦ emp(h) ↔ h = ∅; (s) ⊦ ⌜bv⌝ (h) ↔ bv; (s) ⊦ ⌜false⌝ = false; (s) ⊦ (false ∧ hP) = false; (s) and-ass: ⊦ ((hP0 ∧ hP1) ∧ hP2) = (hP0 ∧ hP1 ∧ hP2); from specification heap-sep and-com: ⊦ (hP0 ∧ hP1) = (hP1 ∧ hP0); from specification heap-sep ⊦ ¬ false(h); (s)

Proof step 3 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 4:

  t0 ≠ branch(t1, a, t2), h0 ⊆ h, h1 ⊆ h, tr(r, t0)(h1), tr(r, branch(t1, a, t2))(h0), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Proof step 4 from proof inj-tr-gen (previous step) (back to tree)

User applied rule constructor cut

And obtained the following new goals

• Proof step 5:

  t0 = branch(t3, a0, t4), t0 ≠ branch(t1, a, t2), h0 ⊆ h, h1 ⊆ h, tr(r, branch(t1, a, t2))(h0), tr(r, t0)(h1), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: tr-base: ⊦ tr(r, leaf) = (emp ∧ ⌜r = null⌝ ); tr-null: ⊦ tr(null, t) = (emp ∧ ⌜t = leaf⌝ ); Tree[A] freely generated by leaf, branch; ⊦ (hP0 ∧ hP1)(h) ↔ hP0(h) ∧ hP1(h); (s) ⊦ emp(h) ↔ h = ∅; (s) ⊦ ⌜bv⌝ (h) ↔ bv; (s) ⊦ ∅ ⊆ h; (s) ⊦ leaf ≠ branch(t, val, t0); (s) ⊦ ⌜false⌝ = false; (s) ⊦ (false ∧ hP) = false; (s) and-ass: ⊦ ((hP0 ∧ hP1) ∧ hP2) = (hP0 ∧ hP1 ∧ hP2); from specification heap-sep and-com: ⊦ (hP0 ∧ hP1) = (hP1 ∧ hP0); from specification heap-sep ⊦ ¬ false(h); (s)

Proof step 5 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 6:

  branch(t3, a0, t4) ≠ branch(t1, a, t2), h0 ⊆ h, h1 ⊆ h, tr(r, branch(t3, a0, t4))(h1), tr(r, branch(t1, a, t2))(h0), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Proof step 6 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 7:

  ⊦ branch(t, val, t0) = branch(t1, val0, t2) ↔ t = t1 ∧ val = val0 ∧ t0 = t2

• Proof step 8:

  h0 ⊆ h, h1 ⊆ h, tr(r, branch(t1, a, t2))(h0), tr(r, branch(t3, a0, t4))(h1), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used terms: a0, t4, a, t2, t1, t3

Proof step 7 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 8 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 9:

  ⊦ tr(r, branch(t0, a, t1)) = _∃(λ r0, r1. r => mknode(r0, a, r1) * tr(r0, t0) * tr(r1, t1))

• Proof step 10:

  (_∃(λ r0, r1. r => mknode(r0, a, r1) * tr(r0, t1) * tr(r1, t2)))(h0), h0 ⊆ h, h1 ⊆ h, tr(r, branch(t3, a0, t4))(h1), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used terms: r, t1, a, t2

Proof step 9 from proof inj-tr-gen (previous step) (back to tree)

Lemma tr-rec

Proof step 10 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 11:

  h0 ⊆ h, h1 ⊆ h, (r => mknode(r0, a, r1) * tr(r0, t1) * tr(r1, t2))(h0), tr(r, branch(t3, a0, t4))(h1), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ (_∃ bcP)(h) ↔ (∃ b, c. bcP(b, c)(h)); (s)

Proof step 11 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 12:

  ⊦ tr(r, branch(t0, a, t1)) = _∃(λ r0, r1. r => mknode(r0, a, r1) * tr(r0, t0) * tr(r1, t1))

• Proof step 13:

  (_∃(λ r0, r1. r => mknode(r0, a0, r1) * tr(r0, t3) * tr(r1, t4)))(h1), h0 ⊆ h, h1 ⊆ h, (r => mknode(r0, a, r1) * tr(r0, t1) * tr(r1, t2))(h0), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used terms: r, t3, a0, t4

Proof step 12 from proof inj-tr-gen (previous step) (back to tree)

Lemma tr-rec

Proof step 13 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 14:

  h0 ⊆ h, h1 ⊆ h, (r => mknode(r0, a, r1) * tr(r0, t1) * tr(r1, t2))(h0), (r => mknode(r2, a0, r3) * tr(r2, t3) * tr(r3, t4))(h1), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ (_∃ bcP)(h) ↔ (∃ b, c. bcP(b, c)(h)); (s)

Proof step 14 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 15:

  ⊦ (hP0 * hP1)(h) ↔ (∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ hP0(h0) ∧ hP1(h1))

• Proof step 16:

  h0 ⊆ h, h1 ⊆ h, (r => mknode(r2, a0, r3) * tr(r2, t3) * tr(r3, t4))(h1), ∃ h1, h2. h1 ⊥ h2 ∧ h0 = h1 ∪ h2 ∧ tr(r1, t2)(h1) ∧ (r => mknode(r0, a, r1) * tr(r0, t1))(h2), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: sep-ass: ⊦ (hP0 * hP1) * hP2 = hP0 * hP1 * hP2; from specification heap-sep sep-com: ⊦ hP0 * hP1 = hP1 * hP0; from specification heap-sep Used terms: h0, tr(r1, t2), r => mknode(r0, a, r1) * tr(r0, t1)

Proof step 15 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 16 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 17:

  h1 ⊆ h, h2 ⊥ h3, h2 ⊆ h, h3 ⊆ h, (r => mknode(r0, a, r1) * tr(r0, t1))(h3), (r => mknode(r2, a0, r3) * tr(r2, t3) * tr(r3, t4))(h1), tr(r1, t2)(h2), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ h0 ⊥ h1 → (h0 ∪ h1 ⊆ h ↔ h0 ⊆ h ∧ h1 ⊆ h); (ws)

Proof step 17 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 18:

  ⊦ (hP0 * hP1)(h) ↔ (∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ hP0(h0) ∧ hP1(h1))

• Proof step 19:

  h1 ⊆ h, h2 ⊆ h, h2 ⊥ h3, h3 ⊆ h, (r => mknode(r0, a, r1) * tr(r0, t1))(h3), tr(r1, t2)(h2), ∃ h0, h2. h0 ⊥ h2 ∧ h1 = h0 ∪ h2 ∧ tr(r3, t4)(h0) ∧ (r => mknode(r2, a0, r3) * tr(r2, t3))(h2), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: sep-ass: ⊦ (hP0 * hP1) * hP2 = hP0 * hP1 * hP2; from specification heap-sep sep-com: ⊦ hP0 * hP1 = hP1 * hP0; from specification heap-sep Used terms: h1, tr(r3, t4), r => mknode(r2, a0, r3) * tr(r2, t3)

Proof step 18 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 19 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 20:

  h0 ⊥ h4, h0 ⊆ h, h2 ⊥ h3, h2 ⊆ h, h3 ⊆ h, h4 ⊆ h, (r => mknode(r2, a0, r3) * tr(r2, t3))(h4), (r => mknode(r0, a, r1) * tr(r0, t1))(h3), tr(r3, t4)(h0), tr(r1, t2)(h2), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ h0 ⊥ h1 → (h0 ∪ h1 ⊆ h ↔ h0 ⊆ h ∧ h1 ⊆ h); (ws)

Proof step 20 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 21:

  ⊦ (hP0 * hP1)(h) ↔ (∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ hP0(h0) ∧ hP1(h1))

• Proof step 22:

  h0 ⊆ h, h0 ⊥ h4, h2 ⊆ h, h2 ⊥ h3, h3 ⊆ h, h4 ⊆ h, (r => mknode(r2, a0, r3) * tr(r2, t3))(h4), tr(r1, t2)(h2), tr(r3, t4)(h0), ∃ h0, h1. h0 ⊥ h1 ∧ h3 = h0 ∪ h1 ∧ tr(r0, t1)(h0) ∧ (r => mknode(r0, a, r1))(h1), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used terms: h3, tr(r0, t1), r => mknode(r0, a, r1)

Proof step 21 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 22 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 23:

  h0 ⊥ h4, h0 ⊆ h, h1 ⊥ h5, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h2 ⊥ h5, h4 ⊆ h, h5 ⊆ h, (r => mknode(r0, a, r1))(h5), (r => mknode(r2, a0, r3) * tr(r2, t3))(h4), tr(r0, t1)(h1), tr(r3, t4)(h0), tr(r1, t2)(h2), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: h1 ⊥ h ⊦ h0 ⊥ h1 ∪ h ↔ h0 ⊥ h1 ∧ h0 ⊥ h; (ws) ⊦ h0 ⊥ h1 → (h0 ∪ h1 ⊆ h ↔ h0 ⊆ h ∧ h1 ⊆ h); (ws)

Proof step 23 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 24:

  ⊦ (hP0 * hP1)(h) ↔ (∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ hP0(h0) ∧ hP1(h1))

• Proof step 25:

  h0 ⊆ h, h0 ⊥ h4, h1 ⊆ h, h1 ⊥ h5, h2 ⊥ h5, h2 ⊥ h1, h2 ⊆ h, h4 ⊆ h, h5 ⊆ h, (r => mknode(r0, a, r1))(h5), tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), ∃ h0, h1. h0 ⊥ h1 ∧ h4 = h0 ∪ h1 ∧ tr(r2, t3)(h0) ∧ (r => mknode(r2, a0, r3))(h1), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used terms: h4, tr(r2, t3), r => mknode(r2, a0, r3)

Proof step 24 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 25 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 26:

  h0 ⊆ h, h0 ⊥ h3, h0 ⊥ h6, h1 ⊥ h5, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h2 ⊥ h5, h3 ⊥ h6, h3 ⊆ h, h5 ⊆ h, h6 ⊆ h, (r => mknode(r2, a0, r3))(h6), (r => mknode(r0, a, r1))(h5), tr(r2, t3)(h3), tr(r0, t1)(h1), tr(r3, t4)(h0), tr(r1, t2)(h2), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: h1 ⊥ h ⊦ h0 ⊥ h1 ∪ h ↔ h0 ⊥ h1 ∧ h0 ⊥ h; (ws) ⊦ h0 ⊥ h1 → (h0 ∪ h1 ⊆ h ↔ h0 ⊆ h ∧ h1 ⊆ h); (ws)

Proof step 26 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 27:

  ⊦ (r => o)(h) ↔ h = (∅ ++ r)(r := o) ∧ r ≠ null

• Proof step 28:

  h5 = (∅ ++ r)(r := mknode(r0, a, r1)), r ≠ null, h0 ⊥ h6, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h1 ⊥ h5, h2 ⊥ h5, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, h3 ⊥ h6, h5 ⊆ h, h6 ⊆ h, (r => mknode(r2, a0, r3))(h6), tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), tr(r2, t3)(h3), t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used terms: r, mknode(r0, a, r1), h5

Proof step 27 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 28 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 29:

  r ≠ null, h0 ⊆ h, h0 ⊥ h3, h0 ⊥ h6, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h3 ⊥ h6, h3 ⊆ h, h6 ⊆ h, (r => mknode(r2, a0, r3))(h6), tr(r2, t3)(h3), tr(r0, t1)(h1), tr(r3, t4)(h0), tr(r1, t2)(h2), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ h ⊥ ∅; (s) r ≠ null, ¬ r ∈ h1 ⊦ h0 ⊥ (h1 ++ r)(r := o) ↔ h0 ⊥ h1 ∧ ¬ r ∈ h0; (s) ⊦ ¬ r ∈ ∅; (s)

Proof step 29 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 30:

  ⊦ (r => o)(h) ↔ h = (∅ ++ r)(r := o) ∧ r ≠ null

• Proof step 31:

  h6 = (∅ ++ r)(r := mknode(r2, a0, r3)), r ≠ null, h0 ⊥ h6, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, h3 ⊥ h6, h6 ⊆ h, tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Used terms: r, mknode(r2, a0, r3), h6

Proof step 30 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 31 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 32:

  r ≠ null, h0 ⊆ h, h0 ⊥ h3, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h3 ⊆ h, tr(r2, t3)(h3), tr(r0, t1)(h1), tr(r3, t4)(h0), tr(r1, t2)(h2), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, (∅ ++ r)(r := mknode(r2, a0, r3)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ h ⊥ ∅; (s) r ≠ null, ¬ r ∈ h1 ⊦ h0 ⊥ (h1 ++ r)(r := o) ↔ h0 ⊥ h1 ∧ ¬ r ∈ h0; (s) ⊦ ¬ r ∈ ∅; (s)

Proof step 32 from proof inj-tr-gen (previous step) (back to tree)

User applied rule cut formula

And obtained the following new goals

• Proof step 33:

  a = a0, r0 = r2, r1 = r3, r ≠ null, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r2, a0, r3)) ⊆ h, (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

• Proof step 37:

  r ≠ null, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r2, a0, r3)) ⊆ h, (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦ r0 = r2 ∧ r1 = r3 ∧ a = a0

Rule argument

Additional information

Used formulas: r0 = r2 ∧ r1 = r3 ∧ a = a0

Proof step 33 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 34:

  r ≠ null, h0 ⊆ h, h0 ⊥ h3, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h3 ⊆ h, tr(r2, t3)(h3), tr(r2, t1)(h1), tr(r3, t4)(h0), tr(r3, t2)(h2), (∅ ++ r)(r := mknode(r2, a0, r3)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦

Rule argument

Additional information

Proof step 34 from proof inj-tr-gen (previous step) (back to tree)

User applied rule case distinction

And obtained the following new goals

• Proof step 35:

  r ≠ null, t3 ≠ t1, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, tr(r3, t2)(h2), tr(r3, t4)(h0), tr(r2, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r2, a0, r3)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

• Proof step 36:

  r ≠ null, t4 ≠ t2, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, tr(r3, t2)(h2), tr(r3, t4)(h0), tr(r2, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r2, a0, r3)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦

Rule argument

Additional information

Proof step 35 from proof inj-tr-gen (previous step) (back to tree)

Heuristic quantifier closing applied rule all left

And closed the goal!

Rule argument

Additional information

Used terms: t3, h1, h, h3, r2

Proof step 36 from proof inj-tr-gen (previous step) (back to tree)

Heuristic quantifier closing applied rule all left

And closed the goal!

Rule argument

Additional information

Used terms: t4, h2, h, h0, r3

Proof step 37 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 38:

  ⊦ h0 ⊆ h1 ↔ (∀ r. (r ∈ h0 → r ∈ h1) ∧ (r ∈ h0 → h0(r) = h1(r)))

• Proof step 39:

  r ≠ null, h0 ⊆ h, h0 ⊥ h3, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h3 ⊆ h, tr(r2, t3)(h3), tr(r0, t1)(h1), tr(r3, t4)(h0), tr(r1, t2)(h2), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ r0. (r0 ∈ (∅ ++ r)(r := mknode(r2, a0, r3)) → r0 ∈ h) ∧ (r0 ∈ (∅ ++ r)(r := mknode(r2, a0, r3)) → (∅ ++ r)(r := mknode(r2, a0, r3))(r0) = h(r0)), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦ r0 = r2 ∧ r1 = r3 ∧ a = a0

Rule argument

Additional information

Used terms: (∅ ++ r)(r := mknode(r2, a0, r3)), h

Proof step 38 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma

Proof step 39 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 40:

  r ≠ null, h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ r4. (r4 = r → r ∈ h) ∧ (r4 = r → mknode(r2, a0, r3) = h(r)), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦ r0 = r2 ∧ r1 = r3 ∧ a = a0

Rule argument

Additional information

Used simplifier rules: r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) ⊦ ¬ r ∈ ∅; (s) ⊦ h(r0 := o)(r) = (r = r0 ∧ r0 ∈ h ⊃ o;h(r)); (s) ⊦ r ∈ h(r0 := o) ↔ r ∈ h; (s)

Proof step 40 from proof inj-tr-gen (previous step) (back to tree)

User applied rule all left

And obtained the following new goals

• Proof step 41:

  r ≠ null, h0 ⊆ h, h0 ⊥ h3, h1 ⊆ h, h2 ⊆ h, h2 ⊥ h1, h3 ⊆ h, tr(r2, t3)(h3), tr(r0, t1)(h1), tr(r3, t4)(h0), tr(r1, t2)(h2), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, r = r → r ∈ h, r = r → mknode(r2, a0, r3) = h(r), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2), ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2) ⊦ r0 = r2 ∧ r1 = r3 ∧ a = a0

Rule argument

Additional information

Used terms: r

Proof step 41 from proof inj-tr-gen (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 42:

  mknode(r2, a0, r3) = h(r), h0 ⊥ h3, h0 ⊆ h, h1 ⊆ h, h2 ⊥ h1, h2 ⊆ h, h3 ⊆ h, r ∈ h, tr(r1, t2)(h2), tr(r3, t4)(h0), tr(r0, t1)(h1), tr(r2, t3)(h3), (∅ ++ r)(r := mknode(r0, a, r1)) ⊆ h, ¬ r ∈ h2, ¬ r ∈ h1, ¬ r ∈ h3, ¬ r ∈ h0, t3 ≠ t1 ∨ a0 ≠ a ∨ t4 ≠ t2, ∀ t, h2, h3, h4, r0. t = t1 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t1)(h2), ∀ t, h2, h3, h4, r0. t = t2 ∨ ¬ h2 ⊆ h3 ∨ ¬ h4 ⊆ h3 ∨ ¬ tr(r0, t)(h4) ∨ ¬ tr(r0, t2)(h2) ⊦ r0 = r2 ∧ r1 = r3 ∧ a = a0

Rule argument

Additional information

Used simplifier rules: ⊦ r ∈ h → r ≠ null; (s)

Proof step 42 from proof inj-tr-gen (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 43:

  ⊦ h0 ⊆ h1 ↔ (∀ r. (r ∈ h0 → r ∈ h1) ∧ (r ∈ h0 → h0(r) = h1(r)))

Rule argument

Additional information

Used simplifier rules: ⊦ r ∈ h(r0 := o) ↔ r ∈ h; (s) ⊦ h(r0 := o)(r) = (r = r0 ∧ r0 ∈ h ⊃ o;h(r)); (s) ⊦ r ∈ h → r ≠ null; (s) ⊦ ¬ r ∈ ∅; (s) r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) ⊦ mknode(left, val, left0) = mknode(left1, val0, left2) ↔ left = left1 ∧ val = val0 ∧ left0 = left2; (ws) Used terms: (∅ ++ r)(r := mknode(r0, a, r1)), h

Proof step 43 from proof inj-tr-gen (previous step) (back to tree)

A spec-lemma