4. Let F be the formal system whose set of well-formed formulas (wff's) includes precisely those strings of the form xΔyΔz, where each of x, y, and z is a string composed of ∗'s and whose axioms and inference rules are as follows:
| Axiom | R1 | R2 |
|---|---|---|
A wff is, in other words, any string containing zero or more *'s and exactly two Δ's. The wff that includes no *'s is accepted, without proof, as a theorem.
Rule 1 says, informally, that if we take a theorem and insert one * at the beginning and two at the end, what we get is another theorem.
Rule 2 says, informally, that if we take a theorem and remove one * from both the left and right ends, and add one * in the region lying between the two Δ's, what we get is another theorem.
As an example, here is a proof of ∗Δ∗∗Δ∗∗∗∗, which we can also write as ∗Δ∗2Δ∗4, using the convention that, for any natural number r, ∗r stands for a string of ∗'s of length r.
| (1) | ΔΔ | (axiom) |
|---|---|---|
| (2) | ∗ΔΔ∗2 | (R1[u,v,w := λ, λ, λ] applied to (1)) |
| (3) | Δ∗Δ∗ | (R2[u,v,w := λ, λ, ∗] applied to (2)) |
| (4) | ∗Δ∗Δ∗3 | (R1[u,v,w := λ,∗,∗] applied to (3)) |
| (5) | ∗2Δ∗Δ∗5 | (R1[u,v,w := ∗,∗,∗3] applied to (4)) |
| (6) | ∗Δ∗2Δ∗4 | (R2[u,v,w := ∗,∗,∗4] applied to (5)) |
Note that λ refers to the empty string.
(a) Show a proof of ∗Δ∗3Δ∗5
Solution: A solution can be inferred from the solution to part (b).
(b) Argue for the following claim:
For every pair of natural numbers k and m, ∗kΔ∗mΔ∗2k+m is a theorem.
Suggested Approach: Provide informal instructions (i.e., an algorithm) for writing a proof of ∗kΔ∗mΔ∗2k+m that would work for all possible choices of the values of k and m.
Solution: The first line of the proof would be the axiom, ΔΔ. Each of the next k+m lines would be the result of applying Rule 1 to the theorem on the previous line, eventually producing ∗k+mΔ∗0Δ∗2(k+m), as each such application adds one ∗ at the beginning and two at the end. Each of the next m lines would be the result of applying Rule 2 to the theorem on the previous line, in the end producing ∗k+m-mΔ∗0+mΔ∗2(k+m)-m (which is the goal ∗kΔ∗mΔ∗2k+m), as each such application removes one ∗ from both the beginning and end, and adds one in the middle.
More generally, any proof that applies Rule 1 k+m times and Rule 2 m times (where each application is to the most recently generated theorem) would produce the desired result. Note that, at any point during such a proof, Rule 1 would have been applied at least as many times as Rule 2, because to apply Rule 2 to a wff requires that it begin with least one ∗, and the number of ∗'s at the beginning of a theorem is the number of applications of Rule 1 minus the number of applications of Rule 2 (in arriving at that theorem).
(c) Argue for the following claim:
If ∗kΔ∗mΔ∗n is a theorem, then 2k+m = n.
Suggested approach: Explain why it must be that every line of every proof is such that the wff on that line satisfies the stated condition. For one-line proofs, this is easy. For multiple-line proofs, you need only argue that the wff on the last line satisfies the stated condition, under the assumption that the wff's on all previous lines do.
Solution: For purposes of brevity, we refer to a wff that satisfies the specified condition as a conforming wff. What we want to prove, then, is that every theorem is a conforming wff.
The suggested approach is based upon this logic: Every theorem is conforming if
Clearly, if both of these conditions holds, there is no way to produce a theorem that is non-conforming.
Now, the axiom is ∗0Δ∗0Δ∗0. Letting k, m, and n refer to the number of ∗'s in the three positions, we have k = m = n = 0, which certainly satisfies 2k + m = n.
Now suppose that ∗kΔ∗mΔ∗n is a conforming wff, which is to say that 2k+m = n.
Applying Rule 1 to it produces ∗k+1Δ∗mΔ∗n+2, which is a conforming wff iff 2(k+1) + m = n+2. But this equation is equivalent to 2k+m = n (which we have assumed to be true), as the calculation below and left demonstrates:
Applying Rule 2 to it produces ∗k-1Δ∗m+1Δ∗n-1, which is a conforming wff iff 2(k-1) + m+1 = n-1. But this equation is equivalent to 2k+m = n (which we have assumed to be true), as the calculation below and right demonstrates:
2(k+1) + m = n+2 = < algebra > 2k + 2 + m = n+2 = < algebra > 2k + m = n |
2(k-1) + m+1 = n-1 = < algebra > 2k - 2 + m+1 = n-1 = < algebra > 2k + m = n |
| Rule 1 Calculation | Rule 2 Calculation |
|---|
Note: It is important to recognize that the claims proved in parts (b) and (c) are implications and that each one is the converse of the other. (The converse of p ⇒ q is q ⇒ p.)
Specifically, the claim of (b) is:
If E is a conforming wff, then E is a theorem.
Meanwhile, the claim of (c) is
If E is a theorem, then E is a conforming wff.
Thus, together the solutions to (b) and (c) prove that E is a theorem if and only if E is a conforming wff.