Good Math

Branching Proofs

The two truth-tree proofs we’ve seen so far have both been single-branch proofs. In practice a lot of interesting proofs, particularly in number theory and geometry, turn out to be single-branch. Some proofs, though, do need branching. To see how that works, we’re going to look at another tautology: the transitivity of implication. If we know that statement A implies statement B, and we also know that statement B implies a third statement, C, then it must be true that A implies C. In logical form, (A ⇒ B ∧ B ⇒ C) ⇒ (A ⇒ C).

The following figure shows the truth-tree proof of this. We’ll walk through the steps together. The strategy in this proof is similar to what we did in our proof of the law of the excluded middle. We want ...