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
Previous Page Next Page