O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required