One frequently encounters inductive—or, as they are increasingly frequently called, recursive—definitions of sets. This starts like this: Suppose that we start with the alphabet {0, 1} and want to build strings as follows: We want to include Images, the empty string. We also want the rule or operation that asks us to include 0A1 if we know that the string A is included. So, some strings we might include are Images, 01, 0011 and 001. The first was included outright, while the second and third are justified by the rule, via the presence of Images and 01, respectively. The last one would be legitimate if we knew that 0 was included. But is it? That is not a fair question. It becomes fair if we consider the smallest—with respect to inclusion ⊆—set of strings that we can build, by including Images and repeatedly applying the rule. Then it can be proved that neither 0 nor 001 can be included in this smallest set.

There are several examples in mathematics and theoretical computer science of “smallest” sets defined from some start-up objects via a set of operations or rules whose application ...

Get Theory of Computation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.