This chapter presents preliminaries on set-theoretical notions, binary relations, linear orderings, fixpoint theory and computational complexity classes. Mainly, we provide notations for standard notions rather than giving a thorough introduction to these notions. More definitions are provided in the book, and we invite the reader to consult textbooks on these subjects for further information. For instance, in Moschovakis (2006) any reader can find material about set-theoretical notions, ordinals or fixpoints far beyond what is sketched in this chapter. Still, we implicitly assume that the reader has basic set-theoretic background. As stated already in Chapter 1, we do not intend to teach this material here but rather to recall the most basic notions, terminology and notation. The current chapter is included for the convenience of the reader as a quick reference.

Structure of the chapter. The chapter is divided into two sections. The first section contains standard material on sets and relations. Section 2.1.1 presents standard set-theoretical notions that are used throughout the book. Binary relations are ubiquitous structures in this volume, and Section 2.1.2 is dedicated to standard definitions about them. In Section 2.1.3, we provide basic definitions about partial and linear orders.

The second section contains material that is more specialised and needed for the development of a theory of and algorithms for temporal logics. Section 2.2.1 presents the basics of fixpoint theory; Chapter 8, which deals with the modal μ-calculus with fixpoint operators, uses some of the results stated herein. In Section 2.2.2, we recall standard complexity classes defined via deterministic and nondeterministic time- and space-bounded Turing machines. Other classes, in particular involving alternating Turing machines, are discussed in Chapter 11. Section 2.2.3 provides an introduction to 2-player zero-sum games of perfect information that are useful, for instance, in defining the game-theoretic approach to temporal logics.

Sets and Relations

Operations on Sets

Throughout this book we use the standard notations for set-theoretical notions:membership (∈), inclusion (⊆), strict (or proper) inclusion (⊂), union of sets (∪), intersection of sets (∩), difference of sets (\) and product of sets (×). The empty set is denoted by ∅.