Computability An Introduction to Recursive Function Theory

The only prerequisite to be able to read this book is familiarity with the basic notations of sets and functions, and the basic ideas of mathematical reasoning. Here we shall review these matters, and explain the notation and terminology that we shall use. This is mostly standard; so for the reader who prefers to move straight to chapter 1 and refer back to this prologue only as necessary, we point out that we shall use the word function to mean a partial function in general. We discuss this more fully below.

Sets

Generally we shall use capital letters A, B, C,… to denote sets. We write x ∈ A to mean that x is a member of A, and we write x ∉ A to mean that x is not a member of A. The notation {x: … x…} where … x … is some statement involving x means the set of all objects x for which … x … is true. Thus {x : x is an even natural number} is the set {0,2,4,6,…}.

If A, B are sets, we write A ⊆ B to mean that A is contained in B (or A is a subset of B); we use the notation A ⊂ B to mean that A ⊆ B but A ≠ B (i.e. A is a proper subset of B). The union of the sets A, B is the set {x : x ∈ A or x ∈ B (or both)}, and is denoted by A ∪ B; the intersection of A, B is the set {x: x ∈ A and x ∈ B} and is denoted by A ∩ B. The difference (or relative complement) of the sets A, B is the set {x : x ∈ A and x ∉ B} and is denoted by A \B.