| finout(g) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n)(a) ↔ a ∈ s0 |
finout(g) ⊦ ∃ s0. ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0
finout(g), ∀ g, s. finout(g) → (∃ s0. ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 +1)(a) ↔ a ∈ s0
Used simplifier rules: nat freely generated by 0, +1;;
| finout(g) ⊦ ∃ s0. ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0 |
finout(g) ⊦ ∃ s0. ∀ a. reach(g)(s, n)(a) ↔ a ∈ s0
finout(g), ∃ s0. ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0
Used terms: g, s, 0
| finout(g) ⊦ ∃ s0. ∀ a. reach(g)(s, n)(a) ↔ a ∈ s0 |
| finout(g), ∃ s0. ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0 |
finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0
| finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0 |
finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0
Used terms: s0
| finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ ∀ a. reach≤(g)(s, 0)(a) ↔ a ∈ s0 |
¬(reach≤(g)(s, 0)(a) ↔ a ∈ s0), finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦
| ¬(reach≤(g)(s, 0)(a) ↔ a ∈ s0), finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ |
⊦ reach≤(g)(s, n)(b) ↔ (∃ m. m ≤ n ∧ reach(g)(s, m)(b))
finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ (∃ m. m ≤ 0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0
Used terms: a, 0, s, g
| ⊦ reach≤(g)(s, n)(b) ↔ (∃ m. m ≤ n ∧ reach(g)(s, m)(b)) |
| finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ (∃ m. m ≤ 0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 |
¬(reach(g)(s, 0)(a) ↔ a ∈ s0), finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦
Used simplifier rules: ⊦ m ≤ 0 ↔ m = 0; (s)
| ¬(reach(g)(s, 0)(a) ↔ a ∈ s0), finout(g), ∀ a. reach(g)(s, 0)(a) ↔ a ∈ s0 ⊦ |
Used terms: a
| finout(g), ∀ g, s. finout(g) → (∃ s0. ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 +1)(a) ↔ a ∈ s0 |
finout(g), ∀ g, s. finout(g) → (∃ s0. ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0
Used simplifier rules: ⊦ m +1 = m + 1; (s)
| finout(g), ∀ g, s. finout(g) → (∃ s0. ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 |
finout(g), finout(g) → (∃ s0. ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0
Used terms: g, s
| finout(g), finout(g) → (∃ s0. ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0) ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 |
finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0
| finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 |
finout(g) ⊦ ∃ s0. ∀ a. reach(g)(s, n)(a) ↔ a ∈ s0
finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0, ∃ s0. ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0
Used terms: g, s, n0 + 1
| finout(g) ⊦ ∃ s0. ∀ a. reach(g)(s, n)(a) ↔ a ∈ s0 |
| finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0, ∃ s0. ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 |
finout(g), ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0
| finout(g), ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0 ⊦ ∃ s0. ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 |
finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0, ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1 ⊦ ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 ∪ s1
Used terms: s0 ∪ s1
| finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0, ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1 ⊦ ∀ a. reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 ∪ s1 |
¬(reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 ∪ s1), finout(g), ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0 ⊦
| ¬(reach≤(g)(s, n0 + 1)(a) ↔ a ∈ s0 ∪ s1), finout(g), ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0 ⊦ |
⊦ reach≤(g)(s, n)(b) ↔ (∃ m. m ≤ n ∧ reach(g)(s, m)(b))
finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0, ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1 ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1
Used terms: a, n0 + 1, s, g
| ⊦ reach≤(g)(s, n)(b) ↔ (∃ m. m ≤ n ∧ reach(g)(s, m)(b)) |
| finout(g), ∀ a. reach≤(g)(s, n0)(a) ↔ a ∈ s0, ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1 ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1 |
reach≤(g)(s, n0)(a) ↔ a ∈ s0, finout(g), ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1 ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1
Used terms: a
| reach≤(g)(s, n0)(a) ↔ a ∈ s0, finout(g), ∀ a. reach(g)(s, n0 + 1)(a) ↔ a ∈ s1 ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1 |
reach≤(g)(s, n0)(a) ↔ a ∈ s0, reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g) ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1
Used terms: a
| reach≤(g)(s, n0)(a) ↔ a ∈ s0, reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g) ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1 |
⊦ reach≤(g)(s, n)(b) ↔ (∃ m. m ≤ n ∧ reach(g)(s, m)(b))
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g), (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1
Used terms: a, n0, s, g
| ⊦ reach≤(g)(s, n)(b) ↔ (∃ m. m ≤ n ∧ reach(g)(s, m)(b)) |
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g), (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ⊦ (∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ∪ s1 |
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g), ¬ a ∈ s0 ∪ s1, (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0, ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a) ⊦
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g), a ∈ s0 ∪ s1, (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g), ¬ a ∈ s0 ∪ s1, (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0, ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a) ⊦ |
finout(g), reach(g)(s, n)(a), n ≤ n0 + 1, ¬ reach(g)(s, n0 + 1)(a), ¬ a ∈ s0, ¬ a ∈ s1 ⊦ ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)
Used simplifier rules: unc: ⊦ s ∪ s0 = s0 ∪ s; from specification set-union una: ⊦ (s ∪ s0) ∪ s1 = s ∪ s0 ∪ s1; from specification set-union ⊦ a ∈ s ∪ s0 ↔ ¬(¬ a ∈ s ∧ ¬ a ∈ s0); (ss)
| finout(g), reach(g)(s, n)(a), n ≤ n0 + 1, ¬ reach(g)(s, n0 + 1)(a), ¬ a ∈ s0, ¬ a ∈ s1 ⊦ ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a) |
Used simplifier rules: ⊦ m ≤ n ↔ ¬ n < m; (ss) ⊦ m < n → (n ≤ m + 1 ↔ n = m + 1); (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: n
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, finout(g), a ∈ s0 ∪ s1, (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a) |
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, s0 ∪ s1 ≠ ∅, finout(g), a ∈ s0 ∪ s1, (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)
Used simplifier rules: size-zero-01: ⊦ s ≠ ∅ → # s ≠ 0; (forward) from specification set-basic ne-01: ⊦ a ∈ s → s ≠ ∅; (forward) from specification set-basic
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, s0 ∪ s1 ≠ ∅, finout(g), a ∈ s0 ∪ s1, (∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)) ↔ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a) |
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, s0 ∪ s1 ≠ ∅, finout(g), a ∈ s0 ∪ s1, ¬ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a), ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, s0 ∪ s1 ≠ ∅, finout(g), a ∈ s0 ∪ s1, a ∈ s0, ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a) ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, s0 ∪ s1 ≠ ∅, finout(g), a ∈ s0 ∪ s1, ¬ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a), ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a) |
#(s0 ∪ s1) ≠ 0, # s1 ≠ 0, s1 ≠ ∅, s0 ∪ s1 ≠ ∅, finout(g), reach(g)(s, n0 + 1)(a), a ∈ s1, ¬ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a), ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a)
Used simplifier rules: size-zero-01: ⊦ s ≠ ∅ → # s ≠ 0; (forward) from specification set-basic ne-01: ⊦ a ∈ s → s ≠ ∅; (forward) from specification set-basic unc: ⊦ s ∪ s0 = s0 ∪ s; from specification set-union una: ⊦ (s ∪ s0) ∪ s1 = s ∪ s0 ∪ s1; from specification set-union ⊦ ¬ a ∈ s → (a ∈ s ∪ s0 ↔ a ∈ s0); (s)
| #(s0 ∪ s1) ≠ 0, # s1 ≠ 0, s1 ≠ ∅, s0 ∪ s1 ≠ ∅, finout(g), reach(g)(s, n0 + 1)(a), a ∈ s1, ¬ a ∈ s0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a), ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a) |
Used simplifier rules: ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: n0 + 1
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, s0 ∪ s1 ≠ ∅, finout(g), a ∈ s0 ∪ s1, a ∈ s0, ∃ m. m ≤ n0 ∧ reach(g)(s, m)(a) ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a) |
reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, # s0 ≠ 0, s0 ≠ ∅, s0 ∪ s1 ≠ ∅, finout(g), reach(g)(s, n)(a), a ∈ s0 ∪ s1, a ∈ s0, n ≤ n0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a)
Used simplifier rules: size-zero-01: ⊦ s ≠ ∅ → # s ≠ 0; (forward) from specification set-basic ne-01: ⊦ a ∈ s → s ≠ ∅; (forward) from specification set-basic
| reach(g)(s, n0 + 1)(a) ↔ a ∈ s1, #(s0 ∪ s1) ≠ 0, # s0 ≠ 0, s0 ≠ ∅, s0 ∪ s1 ≠ ∅, finout(g), reach(g)(s, n)(a), a ∈ s0 ∪ s1, a ∈ s0, n ≤ n0 ⊦ ∃ m. m ≤ n0 + 1 ∧ reach(g)(s, m)(a) |
Used simplifier rules: ⊦ m ≤ n ↔ ¬ n < m; (ss) f: ⊦ m < n → n ≠ 0; (forward) from specification nat-basic fle: ⊦ m < n ∧ n ≤ n0 → m < n0; (forward) from specification nat ⊦ m < n → n ≠ 0; (s) ⊦ ¬ m + n < m; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: n
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.