| ⊦ frag(IOAut(startf, stepf))(σ, α) ∧ ⌜n⌝ < # α → frag(IOAut(startf, stepf))(σ from n, α from n) |
⌜n⌝ < # α, frag(IOAut(startf, stepf))(σ, α), ¬ frag(IOAut(startf, stepf))(σ from n, α from n) ⊦
| ⌜n⌝ < # α, frag(IOAut(startf, stepf))(σ, α), ¬ frag(IOAut(startf, stepf))(σ from n, α from n) ⊦ |
⌜n⌝ < # α, frag(IOAut(startf, stepf))(σ, α), ¬ frag(IOAut(startf, stepf))(σ from n, α from n) ⊦
| ⌜n⌝ < # α, frag(IOAut(startf, stepf))(σ, α), ¬ frag(IOAut(startf, stepf))(σ from n, α from n) ⊦ |
⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[n +1]))
# σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ¬ frag(IOAut(startf, stepf))(σ from n, α from n), ∀ n. ⌜n⌝ < # α → stepf(σ[n], α[n], σ[n +1]) ⊦
Used terms: α, σ, stepf, startf
| ⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[n +1])) |
| # σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ¬ frag(IOAut(startf, stepf))(σ from n, α from n), ∀ n. ⌜n⌝ < # α → stepf(σ[n], α[n], σ[n +1]) ⊦ |
# σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ¬ frag(IOAut(startf, stepf))(σ from n, α from n), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦
Used simplifier rules: ⊦ m +1 = m + 1; (s)
| # σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ¬ frag(IOAut(startf, stepf))(σ from n, α from n), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦ |
⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[n +1]))
# σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]), #(σ from n) ≠ #(α from n) + ⌜1⌝ ∨ (∃ n0. ¬(⌜n0⌝ < #(α from n) → stepf((σ from n)[n0], (α from n)[n0], (σ from n)[n0 +1]))) ⊦
Used terms: α from n, σ from n, stepf, startf
| ⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[n +1])) |
| # σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]), #(σ from n) ≠ #(α from n) + ⌜1⌝ ∨ (∃ n0. ¬(⌜n0⌝ < #(α from n) → stepf((σ from n)[n0], (α from n)[n0], (σ from n)[n0 +1]))) ⊦ |
# σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]), #(σ from n) ≠ #(α from n) + ⌜1⌝ ∨ ¬(⌜n0⌝ + ⌜n⌝ < # α → stepf((σ from n)[n0], α[n + n0], (σ from n)[n0 + 1])) ⊦
Used simplifier rules: ⊦ m +1 = m + 1; (s) ⊦ ⌜n⌝ + ⌜m⌝ < # σ → (σ from n)[m] = σ[n + 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 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) ⌜n⌝ < # σ ⊦ ⌜n0⌝ < #(σ from n) ↔ ⌜n0 + n⌝ < # σ; (s)
| # σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]), #(σ from n) ≠ #(α from n) + ⌜1⌝ ∨ ¬(⌜n0⌝ + ⌜n⌝ < # α → stepf((σ from n)[n0], α[n + n0], (σ from n)[n0 + 1])) ⊦ |
# σ = # α + ⌜1⌝ , #(σ from n) ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦
# σ = # α + ⌜1⌝ , ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ¬ stepf((σ from n)[n0], α[n + n0], (σ from n)[n0 + 1]), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦
| # σ = # α + ⌜1⌝ , #(σ from n) ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦ |
⊦ ⌜n⌝ < # σ ∧ finp(σ) → #(σ from n) = ⌜(# σ).n - n⌝
# σ = # α + ⌜1⌝ , ⌜(# σ).n - n⌝ ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, ⌜n⌝ < # σ, finp(σ), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦
Used simplifier rules: ⊦ n∞ = n∞0 + ⌜1⌝ ∧ ⌜n⌝ < n∞0 → (⌜n⌝ < n∞ ↔ true); (ss) ⊦ ¬ finp(σ) → # σ = ∞; (s) ⊦ ⌜m⌝ + n∞ = ∞ ↔ n∞ = ∞; (s) ⊦ # σ = ∞ → #(σ from n) = ∞; (s) ⊦ ⌜m⌝ + ∞ = ∞; (s) add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf stream-inf-forward: ⊦ ¬ finp(σ) → (∃ nf. ⌜nf⌝ = σ); (forward) from specification stream-basic[IOstatestream] ⊦ ⌜m⌝ < ∞; (s) ⊦ ⌜nf⌝ from n = ⌜nf from n⌝ ; (s) ⊦ # ⌜nf⌝ = ∞; (s) Used terms: n, σ
| ⊦ ⌜n⌝ < # σ ∧ finp(σ) → #(σ from n) = ⌜(# σ).n - n⌝ |
| # σ = # α + ⌜1⌝ , ⌜(# σ).n - n⌝ ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, ⌜n⌝ < # σ, finp(σ), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦ |
⌜# sl⌝ = # α + ⌜1⌝ , sl ≠ [], ⌜# sl - n⌝ ≠ #(α from n) + ⌜1⌝ , n < # sl, ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(sl[n0], α[n0], sl[n0 + 1]) ⊦
Used simplifier rules: ⊦ # x = 0 ↔ x = []; (s) f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic ⊦ ⌜x⌝ [n] = x[n]; (s) ⊦ ⌜m⌝ < ⌜n⌝ ↔ m < n; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ finp(⌜x⌝ ); (s) ⊦ ⌜n⌝ .n = n; (s) stream-fin-forward: ⊦ finp(σ) → (∃ x. ⌜x⌝ = σ); (forward) from specification stream-basic[IOstatestream]
| ⌜# sl⌝ = # α + ⌜1⌝ , sl ≠ [], ⌜# sl - n⌝ ≠ #(α from n) + ⌜1⌝ , n < # sl, ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(sl[n0], α[n0], sl[n0 + 1]) ⊦ |
# sl = n1 + n, ⌜# sl⌝ = # α + ⌜1⌝ , sl ≠ [], ⌜n1⌝ ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, n < # sl, n ≤ # sl, ∀ n0. ⌜n0⌝ < # α → stepf(sl[n0], α[n0], sl[n0 + 1]) ⊦
Used simplifier rules: ⊦ m < n → m ≤ n; (s) n ≤ m ⊦ n0 = m - n ↔ m = n0 + n; (elim) Used terms: # sl, n, n1
| # sl = n1 + n, ⌜# sl⌝ = # α + ⌜1⌝ , sl ≠ [], ⌜n1⌝ ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, n < # sl, n ≤ # sl, ∀ n0. ⌜n0⌝ < # α → stepf(sl[n0], α[n0], sl[n0 + 1]) ⊦ |
# sl = n1 + n, ⌜n1⌝ + ⌜n⌝ = # α + ⌜1⌝ , n1 ≠ 0, sl ≠ [], ⌜n1⌝ ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(sl[n0], α[n0], sl[n0 + 1]) ⊦
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 ↔ n ≠ 0; (s) ⊦ m < n → n ≠ 0; (s) ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (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 < n → m ≤ n; (s)
| # sl = n1 + n, ⌜n1⌝ + ⌜n⌝ = # α + ⌜1⌝ , n1 ≠ 0, sl ≠ [], ⌜n1⌝ ≠ #(α from n) + ⌜1⌝ , ⌜n⌝ < # α, ∀ n0. ⌜n0⌝ < # α → stepf(sl[n0], α[n0], sl[n0 + 1]) ⊦ |
Used simplifier rules: actionstream freely generated by ⌜ ⌝, ⌜ ⌝;; ⊦ # ⌜nf⌝ = ∞; (s) ⊦ ⌜m⌝ + ∞ = ∞; (s) ⊦ ⌜m⌝ + n∞ = ∞ ↔ n∞ = ∞; (s) ⊦ ⌜n⌝ ≠ ∞; (s) add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf ⊦ ⌜n⌝ + ⌜m⌝ = ⌜n0⌝ + ⌜n1⌝ ↔ n + m = n0 + n1; (s) ⊦ ⌜x⌝ from n = ⌜x from n⌝ ; (s) ¬ # x < n ⊦ #(x from n) = # x - n; (s) ⊦ ⌜n⌝ + ⌜m⌝ = ⌜n0⌝ ↔ n + m = n0; (s) ⊦ m ≤ n ↔ ¬ n < m; (ss) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ ⌜m⌝ < ⌜n⌝ ↔ m < n; (s) ⊦ m < n → ¬ n < m; (s) n ≤ m ⊦ (m - n) + n0 = n1 ↔ m + n0 = n + n1; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic
| # σ = # α + ⌜1⌝ , ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ¬ stepf((σ from n)[n0], α[n + n0], (σ from n)[n0 + 1]), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦ |
# σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ⌜n0⌝ + ⌜n⌝ < # α, ¬ stepf((σ from n)[n0], α[n + n0], (σ from n)[n0 + 1]), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦
| # σ = # α + ⌜1⌝ , ⌜n⌝ < # α, ⌜n0⌝ + ⌜n⌝ < # α, ¬ stepf((σ from n)[n0], α[n + n0], (σ from n)[n0 + 1]), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦ |
⊦ ⌜n⌝ + ⌜m⌝ < # σ → (σ from n)[m] = σ[n + m]
# σ = # α + ⌜1⌝ , ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ⌜n⌝ + ⌜n0⌝ < # σ, ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦
Used simplifier rules: add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf lels-trans: ⊦ ¬ n∞1 < n∞ ∧ n∞1 < n∞2 → n∞ < n∞2; (forward) from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ n∞0 + ⌜1⌝ = n∞ → (n∞ < n∞0 ↔ false); (s) Used terms: n0, n, σ
| ⊦ ⌜n⌝ + ⌜m⌝ < # σ → (σ from n)[m] = σ[n + m] |
| # σ = # α + ⌜1⌝ , ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ⌜n⌝ + ⌜n0⌝ < # σ, ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]), ∀ n0. ⌜n0⌝ < # α → stepf(σ[n0], α[n0], σ[n0 + 1]) ⊦ |
# σ = # α + ⌜1⌝ , ⌜n⌝ + ⌜n0⌝ < # σ, ⌜n⌝ < # α, ⌜n0⌝ + ⌜n⌝ < # α, ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]), ⌜n + n0⌝ < # α → stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]) ⊦
Used terms: n + n0
| # σ = # α + ⌜1⌝ , ⌜n⌝ + ⌜n0⌝ < # σ, ⌜n⌝ < # α, ⌜n0⌝ + ⌜n⌝ < # α, ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]), ⌜n + n0⌝ < # α → stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]) ⊦ |
# σ = # α + ⌜1⌝ , ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ⌜n⌝ + ⌜n0⌝ < # σ, stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]), ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]) ⊦
Used simplifier rules: add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf 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)
| # σ = # α + ⌜1⌝ , ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ⌜n⌝ + ⌜n0⌝ < # σ, stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]), ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]) ⊦ |
⊦ ⌜n⌝ + ⌜m⌝ < # σ → (σ from n)[m] = σ[n + m]
# σ = # α + ⌜1⌝ , ⌜n⌝ + ⌜n0⌝ < # σ, ⌜n⌝ < # α, ⌜n0⌝ + ⌜n⌝ < # α, stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]), ¬ ⌜n⌝ + ⌜n0 + 1⌝ < # σ, ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]) ⊦
Used simplifier rules: a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: n0 + 1, n, σ
| ⊦ ⌜n⌝ + ⌜m⌝ < # σ → (σ from n)[m] = σ[n + m] |
| # σ = # α + ⌜1⌝ , ⌜n⌝ + ⌜n0⌝ < # σ, ⌜n⌝ < # α, ⌜n0⌝ + ⌜n⌝ < # α, stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]), ¬ ⌜n⌝ + ⌜n0 + 1⌝ < # σ, ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]) ⊦ |
# σ = # α + ⌜1⌝ , (⌜n⌝ + ⌜n0⌝ ) + ⌜1⌝ = # σ, ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ⌜n⌝ + ⌜n0⌝ < # σ, stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]), ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]) ⊦
Used simplifier rules: 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∞0 → (n∞ + ⌜1⌝ < n∞0 ↔ ¬(n∞ + ⌜1⌝ = n∞0 ∧ n∞ ≠ ∞)); (ss) 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)
| # σ = # α + ⌜1⌝ , (⌜n⌝ + ⌜n0⌝ ) + ⌜1⌝ = # σ, ⌜n0⌝ + ⌜n⌝ < # α, ⌜n⌝ < # α, ⌜n⌝ + ⌜n0⌝ < # σ, stepf(σ[n + n0], α[n + n0], σ[(n + n0) + 1]), ¬ stepf(σ[n + n0], α[n + n0], (σ from n)[n0 + 1]) ⊦ |
Used simplifier rules: ⊦ m ≤ n → (⌜(* n)⌝ + n∞1 = ⌜(* m)⌝ + n∞2 ↔ ⌜n - m⌝ + n∞1 = n∞2); (s) ⊦ n∞ + ⌜0⌝ = n∞; (s) ⊦ n∞ = ⌜m⌝ + ⌜n0⌝ → (⌜n⌝ < n∞ ↔ n < m + n0); (s) ⊦ m < m + n ↔ n ≠ 0; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic ls-trans: ⊦ n∞ < n∞1 ∧ n∞1 < n∞2 → n∞ < n∞2; (forward) from specification nat-inf ⊦ n∞1 < n∞ + n∞1 ↔ n∞ ≠ ⌜0⌝ ∧ n∞1 ≠ ∞; (s) ⊦ ⌜n⌝ = ⌜n0⌝ ↔ n = n0; (s) ⊦ n∞ = ⌜m⌝ + ⌜n⌝ → (n∞ = ∞ ↔ false); (s) add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf ⊦ ¬ n∞ < n∞; (s)
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.