Rippling: Meta-level Guidance for Mathematical Reasoning

The examples of rippling we met in Chapter 1 illustrate only part of the story. In this chapter we will discuss variations on the rippling theme. We will illustrate these variations with examples and in doing so we will gradually build up a more complete picture of what is possible using rippling.
Sometimes wave-fronts are compound, that is, they consist of more than a single function application. It may then be necessary to split the wave-front into parts and move it in several wave-rule applications.
Consider, for instance, the proof of the theorem
by the two-step induction rule (1.17). The step case produces the following rippling problem
Given: even( m) ? even( m) ? even( m+ n)
Goal: ![]()
where the following wave-rules arise from the recursive definitions [1] of even and +
| (2.1) | |
| (2.2) | |
Note that, in the even rule, there are no wave-fronts at all on the right-hand side. This is good, since the removal of wave-fronts always represents a decrease in the wave-measure and, therefore, progress towards fertilization.
The necessity for wave-front splitting arises in the application of wave-rule (2.1) to the redex
. There is a mismatch between the wave-front on the left-hand side of the wave-rule and that in the redex. The solution to this is to split the compound wave-front in the redex into two nested wave-fronts, namely
. Now the wave-front in wave-rule (2.1) matches...