Chapter 2

Background

This chapter covers a collection of topics that are not computability

theory per se, but are needed for it. They are set apart so the rest

of the text reads more smoothly. If you are not familiar with logical

and set notation, read §§2.1 and 2.2 now. The rest should be covered

as needed when they become relevant.

2.1. First-Order Logic

In this section we learn a vocabulary for expressing formulas, logical

sentences. This is useful for brevity (x y is much shorter than

“x is less than y,” and the savings grow as the statement becomes

more complicated) but also for clarity. Expressing a mathematical

statement symbolically can make it more obvious what needs to be

done with it, and however carefully words are used they may admit

some ambiguity.

We use lowercase Greek letters (mostly ϕ, ψ, and θ) to represent

formulas. The simplest formula is a single symbol (or assertion) which

can be either true or false. There are several ways to modify formulas,

which we’ll step through one at a time.

The conjunction of formulas ϕ and ψ is written “ϕ and ψ,”

“ϕ ∧ ψ,” or “ϕ & ψ.” It is true when both ϕ and ψ are true, and

false otherwise. Logically “and” and “but” are equivalent, and so

9

http://dx.doi.org/10.1090/stml/062/02