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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.