1. From Truth Tables to Recursion Tables
Truth tables make a small logical structure visible.
Wittgenstein gave them a prominent role in the Tractatus, while related tabular representations were also developed by others around the same period. What matters here is not their exact history, but the representational move they make possible.
Consider a logical connective such as conjunction.
Its behavior depends on the truth values of the propositions it connects. Since there are only finitely many combinations of those truth values, they can all be written down.
The resulting table makes the relevant cases surveyable.
Instead of keeping several rules in mind, we can look at one object and inspect them together.
This essay proposes a similar device for a different setting.
Suppose values are constructed from a finite number of constructors, and functions on those values are defined recursively.
Instead of listing combinations of truth values, we can list combinations of constructors.
Instead of putting only final values into the cells, some cells may contain recursive expressions referring to structurally smaller inputs.
We will call such representations recursion tables.
The analogy with truth tables is limited but useful.
Truth tables make finite semantic cases easy to inspect.
Recursion tables aim to make two features of simple recursive definitions surveyable:
- whether all constructor cases have been handled;
- whether recursive calls move toward structurally simpler cases.