| findepth(g) ⊦ nocycle(g) |
findepth(g), ¬ nocycle(g) ⊦
| findepth(g), ¬ nocycle(g) ⊦ |
⊦ nocycle(g) ↔ (∀ a, y. ¬ pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ))
findepth(g), ∃ a, y. ¬ ¬ pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) ⊦
Used terms: g
| ⊦ nocycle(g) ↔ (∀ a, y. ¬ pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )) |
| findepth(g), ∃ a, y. ¬ ¬ pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) ⊦ |
findepth(g), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) ⊦
| findepth(g), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) ⊦ |
⊦ findepth(g) ↔ (∀ σ. pathp(g)(σ) → # σ ≠ ∞)
pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ σ. pathp(g)(σ) → # σ ≠ ∞ ⊦
Used terms: g
| ⊦ findepth(g) ↔ (∀ σ. pathp(g)(σ) → # σ ≠ ∞) |
| pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ σ. pathp(g)(σ) → # σ ≠ ∞ ⊦ |
∀ n. lf(n).last = lf(n + 1).head ∧ lf(n) ≠ [] ⊦ ∃ σ, ii. ii(0) = 0 ∧ (∀ n. ii(n + 1) = ii(n) + # lf(n) - 1 ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to # lf(n) = ⌜lf(n)⌝ ) ∧ (∀ m, n. m ≤ n → ii(m) ≤ ii(n)) ∧ (finp(σ) ⊃ ∃ n. # σ = ⌜ii(n) + 1⌝ ∧ (∀ m. n ≤ m → lf(m).tail = [] ∧ ii(m) = ii(n));∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1))
pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∃ σ, ii. ii(0) = 0 ∧ (∀ n. ii(n + 1) = ii(n) + #(a ' + y + a ') - 1 ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to #(a ' + y + a ') = ⌜a ' + y + a '⌝ ) ∧ (∀ m, n. m ≤ n → ii(m) ≤ ii(n)) ∧ (finp(σ) ⊃ ∃ n. # σ = ⌜ii(n) + 1⌝ ∧ (∀ m. n ≤ m → (a ' + y + a ').tail = [] ∧ ii(m) = ii(n));∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1)) ⊦
Used simplifier rules: ⊦ (a ' + x + b ').last = b; (s) ⊦ (a ' + x).head = a; (s) ⊦ a ' + x ≠ []; (s) a: ⊦ (x + y) + z = x + y + z; from specification list Used terms: λ n. a ' + y + a '
| ∀ n. lf(n).last = lf(n + 1).head ∧ lf(n) ≠ [] ⊦ ∃ σ, ii. ii(0) = 0 ∧ (∀ n. ii(n + 1) = ii(n) + # lf(n) - 1 ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to # lf(n) = ⌜lf(n)⌝ ) ∧ (∀ m, n. m ≤ n → ii(m) ≤ ii(n)) ∧ (finp(σ) ⊃ ∃ n. # σ = ⌜ii(n) + 1⌝ ∧ (∀ m. n ≤ m → lf(m).tail = [] ∧ ii(m) = ii(n));∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1)) |
| pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∃ σ, ii. ii(0) = 0 ∧ (∀ n. ii(n + 1) = ii(n) + #(a ' + y + a ') - 1 ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to #(a ' + y + a ') = ⌜a ' + y + a '⌝ ) ∧ (∀ m, n. m ≤ n → ii(m) ≤ ii(n)) ∧ (finp(σ) ⊃ ∃ n. # σ = ⌜ii(n) + 1⌝ ∧ (∀ m. n ≤ m → (a ' + y + a ').tail = [] ∧ ii(m) = ii(n));∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1)) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), (finp(σ) ⊃ # σ = ⌜ii(n)⌝ + ⌜1⌝ ∧ (∀ m. ¬ n ≤ m);∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to 2 + # y = ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ x + a ' ≠ []; (s) ⊦ (a ' + x).tail = x; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s) ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ m +1 = m + 1; (s) ⊦ # a ' = 0 +1; (s) ⊦ #(x + y) = # x + # y; (s) ⊦ #(a ' + x) = (# x)+1; (s) ⊦ n ≤ m → m + n0 - n = (m - n) + n0; (s)
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), (finp(σ) ⊃ # σ = ⌜ii(n)⌝ + ⌜1⌝ ∧ (∀ m. ¬ n ≤ m);∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to 2 + # y = ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ⊦ |
# σ = ⌜ii(n)⌝ + ⌜1⌝ , ii(0) = 0, finp(σ), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to 2 + # y = ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ , ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ m. ¬ n ≤ m ⊦
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ finp(σ), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to 2 + # y = ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ , ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦
| # σ = ⌜ii(n)⌝ + ⌜1⌝ , ii(0) = 0, finp(σ), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to 2 + # y = ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ , ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ m. ¬ n ≤ m ⊦ |
ii(n) + 1 = # x, ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ m. ¬ n ≤ m, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ n0. ii(n0 + 1) = 1 + ii(n0) + # y ∧ ¬ ii(n) < ii(n0 + 1) ∧ a ' + y + a ' = (x from ii(n0)) to 2 + # y ⊦
Used simplifier rules: append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ ⌜x⌝ + ⌜y⌝ + ⌜z⌝ = ⌜x0⌝ ↔ x + y + z = x0; (s) ⊦ ⌜x⌝ to n = ⌜x to n⌝ ; (s) ⊦ ⌜x⌝ from n = ⌜x from n⌝ ; (s) ⊦ finp(⌜x⌝ ); (s) add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ ⌜n⌝ + ⌜m⌝ = ⌜n0⌝ ↔ n + m = n0; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) stream-fin-forward: ⊦ finp(σ) → (∃ x. ⌜x⌝ = σ); (forward) from specification stream-basic c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m < n + 1 ↔ ¬ n < m; (s) ⊦ n∞ = ⌜m⌝ + ⌜n0⌝ → (⌜n⌝ < n∞ ↔ n < m + n0); (s)
| ii(n) + 1 = # x, ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ m. ¬ n ≤ m, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ n0. ii(n0 + 1) = 1 + ii(n0) + # y ∧ ¬ ii(n) < ii(n0 + 1) ∧ a ' + y + a ' = (x from ii(n0)) to 2 + # y ⊦ |
Used simplifier rules: ⊦ m ≤ n ↔ ¬ n < m; (ss) ⊦ ¬ n < n; (s) Used terms: n
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ finp(σ), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ ⌜ii(n + 1)⌝ < # σ ∧ (σ from ii(n)) to 2 + # y = ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ , ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦
Used simplifier rules: append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ ⌜x⌝ + ⌜y⌝ + ⌜z⌝ = ⌜x0⌝ ↔ x + y + z = x0; (s) ⊦ ⌜nf⌝ to n = ⌜nf to n⌝ ; (s) ⊦ ⌜nf⌝ from n = ⌜nf from n⌝ ; (s) ⊦ ¬ finp(⌜nf⌝ ); (s) stream-inf-forward: ⊦ ¬ finp(σ) → (∃ nf. ⌜nf⌝ = σ); (forward) from specification stream-basic ⊦ ⌜m⌝ < ∞; (s) ⊦ ¬ finp(σ) → # σ = ∞; (s)
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ σ. pathp(g)(σ) → # σ ≠ ∞, ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), pathp(g)(⌜nf⌝ ) → # ⌜nf⌝ ≠ ∞, ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦
Used terms: ⌜nf⌝
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), pathp(g)(⌜nf⌝ ) → # ⌜nf⌝ ≠ ∞, ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ pathp(g)(⌜nf⌝ ), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦
Used simplifier rules: ⊦ # ⌜nf⌝ = ∞; (s)
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ pathp(g)(⌜nf⌝ ), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦ |
⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1]))
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), (∃ n. ¬(⌜n⌝ < # ⌜nf⌝ → dom(g)(⌜nf⌝ [n]))) ∨ (∃ n. ¬(⌜n + 1⌝ < # ⌜nf⌝ → edge(g)(⌜nf⌝ [n], ⌜nf⌝ [n + 1]))) ⊦
Used terms: ⌜nf⌝ , g
| ⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1])) |
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), (∃ n. ¬(⌜n⌝ < # ⌜nf⌝ → dom(g)(⌜nf⌝ [n]))) ∨ (∃ n. ¬(⌜n + 1⌝ < # ⌜nf⌝ → edge(g)(⌜nf⌝ [n], ⌜nf⌝ [n + 1]))) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ¬ dom(g)(nf(n)) ∨ ¬ edge(g)(nf(n0), nf(n0 + 1)) ⊦
Used simplifier rules: ⊦ ⌜nf⌝ [n] = nf(n); (s) add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ ⌜n⌝ ≠ ∞; (s) ⊦ ⌜m⌝ + n∞ = ∞ ↔ n∞ = ∞; (s) ⊦ n∞ < ∞ ↔ n∞ ≠ ∞; (s) ⊦ # ⌜nf⌝ = ∞; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s) ⊦ ⌜m⌝ < ∞; (s)
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ¬ dom(g)(nf(n)) ∨ ¬ edge(g)(nf(n0), nf(n0 + 1)) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ dom(g)(nf(n)), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ dom(g)(nf(n)), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦
Used terms: n
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦ |
ii(0) = 0, ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦
Used simplifier rules: ⊦ m < n → n ≠ 0; (s) fle-01: ⊦ m ≤ n ∧ n < n0 → m < n0; (forward) from specification nat f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic
| ii(0) = 0, ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦ |
a ' + y + a ' = (nf from ii(n0)) to 2 + # y, ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used terms: n0
| a ' + y + a ' = (nf from ii(n0)) to 2 + # y, ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
a ' + y + a ' = (nf from ii(n0)) to 2 + # y, ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n ≤ ii(n0) + # y, ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m ≤ m + n; (s) let: ⊦ n ≤ n0 ∧ n0 ≤ n1 → n ≤ n1; (forward) from specification nat ⊦ m < n ↔ ¬ n ≤ m; (ss) ⊦ ¬ m + n < m; (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) lf-01: ⊦ m < n ∧ n = n0 → m < n0; (forward) from specification nat-basic a: ⊦ (x + y) + z = x + y + z; from specification list in-14: ⊦ a ' + x = y → a ∈ y; (forward) from specification list
| a ' + y + a ' = (nf from ii(n0)) to 2 + # y, ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n ≤ ii(n0) + # y, ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
⊦ x = y ↔ # x = # y ∧ (∀ n. n < # x → x[n] = y[n])
#(a ' + y + a ') = #((nf from ii(n0)) to 2 + # y), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, ii(n0) ≤ n, n ≤ ii(n0) + # y, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. n < #(a ' + y + a ') → (a ' + y + a ')[n] = ((nf from ii(n0)) to 2 + # y)[n] ⊦
Used terms: (nf from ii(n0)) to 2 + # y, a ' + y + a '
| ⊦ x = y ↔ # x = # y ∧ (∀ n. n < # x → x[n] = y[n]) |
| #(a ' + y + a ') = #((nf from ii(n0)) to 2 + # y), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, ii(n0) ≤ n, n ≤ ii(n0) + # y, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. n < #(a ' + y + a ') → (a ' + y + a ')[n] = ((nf from ii(n0)) to 2 + # y)[n] ⊦ |
ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n ≤ ii(n0) + # y, ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n0)) ⊦
Used simplifier rules: ⊦ ((nf from n))(m) = nf(m + n); (s) m < n ⊦ (nf to n)[m] = nf(m); (s) ⊦ m < n → (n ≤ m ↔ false); (s) ⊦ m < n ↔ ¬ n ≤ m; (ss) a: ⊦ (x + y) + z = x + y + z; from specification list c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m +1 = m + 1; (s) ⊦ # a ' = 0 +1; (s) ⊦ #(x + y) = # x + # y; (s) ⊦ #(a ' + x) = (# x)+1; (s) ⊦ m + n = m + n0 ↔ n = n0; (s) ⊦ #(nf to n) = n; (s)
| ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n ≤ ii(n0) + # y, ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n0)) ⊦ |
ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, ii(n0) ≤ n, n ≤ ii(n0) + # y, ¬ dom(g)(nf(n)), n - ii(n0) < 2 + # y → (a ' + y + a ')[n - ii(n0)] = nf((n - ii(n0)) + ii(n0)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used terms: n - ii(n0)
| ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, ii(n0) ≤ n, n ≤ ii(n0) + # y, ¬ dom(g)(nf(n)), n - ii(n0) < 2 + # y → (a ' + y + a ')[n - ii(n0)] = nf((n - ii(n0)) + ii(n0)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n - ii(n0)] = nf((n - ii(n0)) + ii(n0)), ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, n < (2 + # y) + ii(n0), ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n ≤ ii(n0) + # y, ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic n < n0 ⊦ (* n) ≠ m0 + (* n0); (s) ⊦ m < m + n ↔ n ≠ 0; (s) fle-01: ⊦ m ≤ n ∧ n < n0 → m < n0; (forward) from specification nat f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic ⊦ m + m0 ≤ m ↔ m0 = 0; (s) ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s) let: ⊦ n ≤ n0 ∧ n0 ≤ n1 → n ≤ n1; (forward) from specification nat ⊦ m < n ↔ ¬ n ≤ m; (ss) n0 ≤ n ⊦ n - n0 < m ↔ n < m + n0; (s) ⊦ m ≤ n → (n < m ↔ false); (s) ⊦ m ≤ n ↔ ¬ n < m; (ss)
| (a ' + y + a ')[n - ii(n0)] = nf((n - ii(n0)) + ii(n0)), ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, n < (2 + # y) + ii(n0), ii(n0) < ii(n0 + 1), n < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n ≤ ii(n0) + # y, ii(n0) ≤ n, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n = n1 + ii(n0), n < ii(n0 + 1), ii(n0) < ii(n0 + 1), n < (2 + # y) + ii(n0), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, ii(n0) ≤ n, n ≤ ii(n0) + # y, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: n ≤ m ⊦ n0 = m - n ↔ m = n0 + n; (elim) Used terms: n, ii(n0), n1
| (a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n = n1 + ii(n0), n < ii(n0 + 1), ii(n0) < ii(n0 + 1), n < (2 + # y) + ii(n0), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, ii(n0) ≤ n, n ≤ ii(n0) + # y, ¬ dom(g)(nf(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n1 < 2 + # y, n1 + ii(n0) < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n1 ≤ # y, ¬ dom(g)(nf(n1 + ii(n0))), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m ≤ n → (n < m ↔ false); (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) ⊦ m + n < m + n0 ↔ n < n0; (s) n < n0 ⊦ (* n) ≠ m0 + (* n0); (s) lf-01: ⊦ m < n ∧ n = n0 → m < n0; (forward) from specification nat-basic f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic ⊦ m ≤ m + n; (s) ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s)
| (a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n1 < 2 + # y, n1 + ii(n0) < ii(n0 + 1), ii(n0) < ii(n0 + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n0)) to 2 + # y, n1 ≤ # y, ¬ dom(g)(nf(n1 + ii(n0))), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1]))
(a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, ii(n0) < ii(n0 + 1), n1 + ii(n0) < ii(n0 + 1), n1 < 2 + # y, a ∈ (nf from ii(n0)) to 2 + # y, n1 ≤ # y, ¬ dom(g)(nf(n1 + ii(n0))), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ⌜n⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → dom(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → edge(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n], (⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n + 1]) ⊦
Used terms: ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ , g
| ⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1])) |
| (a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(n0 + 1) = 1 + ii(n0) + # y, ii(0) = 0, ii(n0) < ii(n0 + 1), n1 + ii(n0) < ii(n0 + 1), n1 < 2 + # y, a ∈ (nf from ii(n0)) to 2 + # y, n1 ≤ # y, ¬ dom(g)(nf(n1 + ii(n0))), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ⌜n⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → dom(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → edge(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n], (⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n + 1]) ⊦ |
(a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n1 < 2 + # y, n1 + ii(n0) < ii(n0 + 1), ii(n0) < ii(n0 + 1), a ∈ (nf from ii(n0)) to 2 + # y, n1 ≤ # y, ¬ dom(g)(nf(n1 + ii(n0))), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ¬ # y < n → edge(g)((a ' + y + a ')[n], (y + a ')[n]), ∀ n. n < 2 + # y → dom(g)((a ' + y + a ')[n]) ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ (⌜x⌝ + ⌜x0⌝ + ⌜x1⌝ )[m] = (x + x0 + x1)[m]; (s) add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ ⌜n⌝ < ⌜m⌝ + ⌜n0⌝ ↔ n < m + n0; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜(* n)⌝ + ⌜(* m)⌝ = ⌜n + m⌝ ; (s) ⊦ # a ' = 0 +1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ #(σ + σ1) = # σ + # σ1; (s) ⊦ (⌜x⌝ + ⌜x0⌝ )[m] = (x + x0)[m]; (s) ⊦ (⌜a '⌝ + σ)[n + 1] = σ[n]; (s) ⊦ ⌜m⌝ < ⌜n⌝ ↔ m < n; (s) ⊦ ⌜n⌝ < ⌜1⌝ + n∞ ↔ ¬ n∞ < ⌜n⌝ ; (s) ⊦ m ≤ n → (⌜(* m)⌝ + n∞2 < ⌜(* n)⌝ + n∞1 ↔ n∞2 < ⌜n - m⌝ + n∞1); (s) ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s)
| (a ' + y + a ')[n1] = nf(n1 + ii(n0)), ii(0) = 0, ii(n0 + 1) = 1 + ii(n0) + # y, n1 < 2 + # y, n1 + ii(n0) < ii(n0 + 1), ii(n0) < ii(n0 + 1), a ∈ (nf from ii(n0)) to 2 + # y, n1 ≤ # y, ¬ dom(g)(nf(n1 + ii(n0))), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ¬ # y < n → edge(g)((a ' + y + a ')[n], (y + a ')[n]), ∀ n. n < 2 + # y → dom(g)((a ' + y + a ')[n]) ⊦ |
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list Used terms: n1
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ∃ m. ii(m) ≤ n ∧ n < ii(m + 1) ⊦ |
ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∃ m. ii(m) ≤ n0 ∧ n0 < ii(m + 1) ⊦
Used terms: n0
| ii(0) = 0, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y, ∃ m. ii(m) ≤ n0 ∧ n0 < ii(m + 1) ⊦ |
ii(0) = 0, ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦
Used simplifier rules: ⊦ m < n → n ≠ 0; (s) fle-01: ⊦ m ≤ n ∧ n < n0 → m < n0; (forward) from specification nat f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic
| ii(0) = 0, ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ii(n + 1) = 1 + ii(n) + # y ∧ a ' + y + a ' = (nf from ii(n)) to 2 + # y ⊦ |
a ' + y + a ' = (nf from ii(n)) to 2 + # y, ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used terms: n
| a ' + y + a ' = (nf from ii(n)) to 2 + # y, ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
a ' + y + a ' = (nf from ii(n)) to 2 + # y, ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n0 ≤ ii(n) + # y, ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m ≤ m + n; (s) let: ⊦ n ≤ n0 ∧ n0 ≤ n1 → n ≤ n1; (forward) from specification nat ⊦ m < n ↔ ¬ n ≤ m; (ss) ⊦ ¬ m + n < m; (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) lf-01: ⊦ m < n ∧ n = n0 → m < n0; (forward) from specification nat-basic a: ⊦ (x + y) + z = x + y + z; from specification list in-14: ⊦ a ' + x = y → a ∈ y; (forward) from specification list
| a ' + y + a ' = (nf from ii(n)) to 2 + # y, ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n0 ≤ ii(n) + # y, ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
⊦ x = y ↔ # x = # y ∧ (∀ n. n < # x → x[n] = y[n])
#(a ' + y + a ') = #((nf from ii(n)) to 2 + # y), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, ii(n) ≤ n0, n0 ≤ ii(n) + # y, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n0. n0 < #(a ' + y + a ') → (a ' + y + a ')[n0] = ((nf from ii(n)) to 2 + # y)[n0] ⊦
Used terms: (nf from ii(n)) to 2 + # y, a ' + y + a '
| ⊦ x = y ↔ # x = # y ∧ (∀ n. n < # x → x[n] = y[n]) |
| #(a ' + y + a ') = #((nf from ii(n)) to 2 + # y), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, ii(n) ≤ n0, n0 ≤ ii(n) + # y, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n0. n0 < #(a ' + y + a ') → (a ' + y + a ')[n0] = ((nf from ii(n)) to 2 + # y)[n0] ⊦ |
ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n0 ≤ ii(n) + # y, ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)) ⊦
Used simplifier rules: ⊦ ((nf from n))(m) = nf(m + n); (s) m < n ⊦ (nf to n)[m] = nf(m); (s) ⊦ m < n → (n ≤ m ↔ false); (s) ⊦ m < n ↔ ¬ n ≤ m; (ss) a: ⊦ (x + y) + z = x + y + z; from specification list c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m +1 = m + 1; (s) ⊦ # a ' = 0 +1; (s) ⊦ #(x + y) = # x + # y; (s) ⊦ #(a ' + x) = (# x)+1; (s) ⊦ m + n = m + n0 ↔ n = n0; (s) ⊦ #(nf to n) = n; (s)
| ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n0 ≤ ii(n) + # y, ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)) ⊦ |
ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, ii(n) ≤ n0, n0 ≤ ii(n) + # y, ¬ edge(g)(nf(n0), nf(n0 + 1)), n0 - ii(n) < 2 + # y → (a ' + y + a ')[n0 - ii(n)] = nf((n0 - ii(n)) + ii(n)), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used terms: n0 - ii(n)
| ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, ii(n) ≤ n0, n0 ≤ ii(n) + # y, ¬ edge(g)(nf(n0), nf(n0 + 1)), n0 - ii(n) < 2 + # y → (a ' + y + a ')[n0 - ii(n)] = nf((n0 - ii(n)) + ii(n)), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n0 - ii(n)] = nf((n0 - ii(n)) + ii(n)), ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, n0 < (2 + # y) + ii(n), ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n0 ≤ ii(n) + # y, ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)) ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic n < n0 ⊦ (* n) ≠ m0 + (* n0); (s) ⊦ m < m + n ↔ n ≠ 0; (s) fle-01: ⊦ m ≤ n ∧ n < n0 → m < n0; (forward) from specification nat f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic ⊦ m + m0 ≤ m ↔ m0 = 0; (s) ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s) let: ⊦ n ≤ n0 ∧ n0 ≤ n1 → n ≤ n1; (forward) from specification nat ⊦ m < n ↔ ¬ n ≤ m; (ss) n0 ≤ n ⊦ n - n0 < m ↔ n < m + n0; (s) ⊦ m ≤ n → (n < m ↔ false); (s) ⊦ m ≤ n ↔ ¬ n < m; (ss)
| (a ' + y + a ')[n0 - ii(n)] = nf((n0 - ii(n)) + ii(n)), ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, n0 < (2 + # y) + ii(n), ii(n) < ii(n + 1), n0 < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n0 ≤ ii(n) + # y, ii(n) ≤ n0, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)) ⊦ |
(a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 = n2 + ii(n), n0 < ii(n + 1), ii(n) < ii(n + 1), n0 < (2 + # y) + ii(n), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, ii(n) ≤ n0, n0 ≤ ii(n) + # y, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: n ≤ m ⊦ n0 = m - n ↔ m = n0 + n; (elim) Used terms: n0, ii(n), n2
| (a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n0 = n2 + ii(n), n0 < ii(n + 1), ii(n) < ii(n + 1), n0 < (2 + # y) + ii(n), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, ii(n) ≤ n0, n0 ≤ ii(n) + # y, ¬ edge(g)(nf(n0), nf(n0 + 1)), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n2 < 2 + # y, n2 + ii(n) < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), nf((n2 + ii(n)) + 1)), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m ≤ n → (n < m ↔ false); (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) ⊦ m + n < m + n0 ↔ n < n0; (s) n < n0 ⊦ (* n) ≠ m0 + (* n0); (s) lf-01: ⊦ m < n ∧ n = n0 → m < n0; (forward) from specification nat-basic f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic ⊦ m ≤ m + n; (s) ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s)
| (a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n2 < 2 + # y, n2 + ii(n) < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), nf((n2 + ii(n)) + 1)), ∀ n1. n1 < 2 + # y → (a ' + y + a ')[n1] = nf(n1 + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n2 + ii(n) < ii(n + 1), n2 < 2 + # y, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), nf((n2 + ii(n)) + 1)), n2 + 1 < 2 + # y → (a ' + y + a ')[n2 + 1] = nf((n2 + 1) + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used terms: n2 + 1
| (a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n2 + ii(n) < ii(n + 1), n2 < 2 + # y, pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), nf((n2 + ii(n)) + 1)), n2 + 1 < 2 + # y → (a ' + y + a ')[n2 + 1] = nf((n2 + 1) + ii(n)), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
(a ' + y + a ')[n2] = nf(n2 + ii(n)), (y + a ')[n2] = nf((n2 + 1) + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n2 < 2 + # y, n2 + ii(n) < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), (y + a ')[n2]), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ (a ' + x)[n + 1] = x[n]; (s) ⊦ m ≤ n → (n < m ↔ false); (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) n < n0 ⊦ m + (* n) < m0 + (* n0) ↔ m < m0 + (n0 - n); (s)
| (a ' + y + a ')[n2] = nf(n2 + ii(n)), (y + a ')[n2] = nf((n2 + 1) + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n2 < 2 + # y, n2 + ii(n) < ii(n + 1), ii(n) < ii(n + 1), pathp(g)(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), (y + a ')[n2]), ∀ m, n. m ≤ n → ii(m) ≤ ii(n) ⊦ |
⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1]))
(y + a ')[n2] = nf((n2 + 1) + ii(n)), (a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n2 + ii(n) < ii(n + 1), n2 < 2 + # y, a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), (y + a ')[n2]), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ⌜n⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → dom(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → edge(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n], (⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n + 1]) ⊦
Used terms: ⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ , g
| ⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1])) |
| (y + a ')[n2] = nf((n2 + 1) + ii(n)), (a ' + y + a ')[n2] = nf(n2 + ii(n)), ii(n + 1) = 1 + ii(n) + # y, ii(0) = 0, ii(n) < ii(n + 1), n2 + ii(n) < ii(n + 1), n2 < 2 + # y, a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), (y + a ')[n2]), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n. ⌜n⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → dom(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ ) → edge(g)((⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n], (⌜a '⌝ + ⌜y⌝ + ⌜a '⌝ )[n + 1]) ⊦ |
(a ' + y + a ')[n2] = nf(n2 + ii(n)), (y + a ')[n2] = nf((n2 + 1) + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n2 < 2 + # y, n2 + ii(n) < ii(n + 1), ii(n) < ii(n + 1), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), (y + a ')[n2]), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n0. ¬ # y < n0 → edge(g)((a ' + y + a ')[n0], (y + a ')[n0]), ∀ n0. n0 < 2 + # y → dom(g)((a ' + y + a ')[n0]) ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ (⌜x⌝ + ⌜x0⌝ + ⌜x1⌝ )[m] = (x + x0 + x1)[m]; (s) add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ ⌜n⌝ < ⌜m⌝ + ⌜n0⌝ ↔ n < m + n0; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜(* n)⌝ + ⌜(* m)⌝ = ⌜n + m⌝ ; (s) ⊦ # a ' = 0 +1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ #(σ + σ1) = # σ + # σ1; (s) ⊦ (⌜x⌝ + ⌜x0⌝ )[m] = (x + x0)[m]; (s) ⊦ (⌜a '⌝ + σ)[n + 1] = σ[n]; (s) ⊦ ⌜m⌝ < ⌜n⌝ ↔ m < n; (s) ⊦ ⌜n⌝ < ⌜1⌝ + n∞ ↔ ¬ n∞ < ⌜n⌝ ; (s) ⊦ m ≤ n → (⌜(* m)⌝ + n∞2 < ⌜(* n)⌝ + n∞1 ↔ n∞2 < ⌜n - m⌝ + n∞1); (s) ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s)
| (a ' + y + a ')[n2] = nf(n2 + ii(n)), (y + a ')[n2] = nf((n2 + 1) + ii(n)), ii(0) = 0, ii(n + 1) = 1 + ii(n) + # y, n2 < 2 + # y, n2 + ii(n) < ii(n + 1), ii(n) < ii(n + 1), a ∈ (nf from ii(n)) to 2 + # y, n2 ≤ # y, ¬ edge(g)(nf(n2 + ii(n)), (y + a ')[n2]), ∀ m, n. m ≤ n → ii(m) ≤ ii(n), ∀ n0. ¬ # y < n0 → edge(g)((a ' + y + a ')[n0], (y + a ')[n0]), ∀ n0. n0 < 2 + # y → dom(g)((a ' + y + a ')[n0]) ⊦ |
Used simplifier rules: ⊦ m ≤ n → (n < m ↔ false); (s) a: ⊦ (x + y) + z = x + y + z; from specification list Used terms: n2
The following image shows the proof tree of sequent calculus. The proved goal is at the bottom. You can click on the nodes to view additional rules. See here for details on colors in a proof tree.