Chapter 1. Preliminaries

In this chapter, we review some basic concepts required for understanding the contents of this book.

Sets, Relations, and Functions

Sets

A set is a collection of well-defined objects. Usually the elements of a set have common properties. For example, all the students who enroll for a course ‘Computability’ make up a set. Formally,

Note that the definition of a set is intuitive in nature and was stated by the German mathematician Cantor in 1895. The objects in a set are called the elements or members of the set.

Example 1.1. 

The set E of even positive integers less than 20 can be expressed by:

E = {2, 4, 6, 8, 10, 12, 14, 16, 18}

or

E = {x|x is even and 0 < x < 20}

A set ...

Get Introduction to Formal Languages, Automata Theory and 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.