Theory of Computation

1.1   SETS AND LOGIC; NAÏVELY

The most elementary elements from “set theory” and logic are a good starting point for our review. The quotes are necessary since the term set theory as it is understood today applies to the axiomatic version, which is a vast field of knowledge, methods, tools and research [cf. Shoenfield (1967); Tourlakis (2003b)]—and this is not what we outline here. Rather, we present the standard notation and the elementary operations on sets, on one hand, and take a brief look at infinity and the diagonal method of Cantor’s, on the other. Diagonalization is a tool of significant importance in computability. The tiny fragment of concepts from set theory that you will find in this section (and then see them applied throughout this volume) are framed within Cantor’s original “naïve set theory”, good expositions of which (but far exceeding our needs) can be found in Halmos (1960) and Kamke (1950).

We will be forced to interweave our exposition of concepts from set theory with concepts—and notation—from elementary logic, since all mathematics is based on logical deductions, and the vast majority of the literature, from the most elementary to the most advanced, employs logical notation; e.g., symbols such as “∀” and “∃”.

The term “set” is not defined,¹¹ in either the modern or in the naïve Cantorian version of the theory. Expositions of the latter, however, often ask the reader to think of a set as just a synonym for the words “class”,¹² “collection”, or “aggregate”. ...