Theory of Computation

1.6   INDUCTIVELY DEFINED SETS

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 , 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 , 01, 0011 and 001. The first was included outright, while the second and third are justified by the rule, via the presence of 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 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 ...