3.7. References 79
Problem 3.34.
We want to find predicate formulas about the nonnegative integers,N, in which
is the only predicate that appears, and no constants appear.
For example, there is such a formula defining the equality predicate:
ŒxDyçWWDŒxy AND yxç:Once predicate is shown to be expressible solely in terms of, it may then be used
in subsequent translations. For example,
Œx > 0çWWD 9y:NOT.xDy/ANDyx:(a)ŒxD0ç.(b)ŒxDyC1ç(c)xD 3