In the preceding chapter we introduced the distinction between enumerable and nonenumerable sets, and gave many examples of enumerable sets. In this short chapter we give examples of nonenumerable sets. We first prove the existence of such sets, and then look a little more closely at the method, called diagonalization, used in this proof.

Modal logic extends ‘classical’ logic by adding new logical operators ▪ and ♦ for ‘necessity’ and ‘possibility’. Section 27.1 is an exposition of the rudiments of (sentential) modal logic. Section 27.2 indicates how a particular system of modal logic GL is related to the kinds of questions about provability in P we considered in Chapters 17 and 18. This connection motivates the closer examination of GL then undertaken in section 27.3.

By a model of (true) arithmetic is meant any model of the set of all sentences of the language L of arithmetic that are true in the standard interpretation N. By a nonstandard model is meant one that is not isomorphic to N. The proof of the existence of an (enumerable) nonstandard model of arithmetic is as an easy application of the compactness theorem (and the Löwenheim–Skolem theorem). Every enumerable nonstandard model is isomorphic to a nonstandard model M whose domain is the same as that of N, namely, the set of natural numbers; though of course such an M cannot assign the same denotations as N to the nonlogical symbols of L. In section 25.1 we analyze the structure of the order relation in such a nonstandard model. A consequence of this analysis is that, though the order relation cannot be the standard one, it at least can be a recursive relation. By contrast, Tennenbaum's theorem tells us that it cannot happen that the addition and multiplication relations are recursive. This theorem and related results will be taken up in section 25.2. Section 25.3 is a sort of appendix (independent of the other sections, but alluding to results from several earlier chapters) concerning nonstandard models of an expansion of arithmetic called analysis.

In the preceding chapter we introduced the notion of Turing computability. In the present short chapter we give examples of Turing-uncomputable functions: the halting function in section 4.1, and the productivity function in the optional section 4.2. If Turing's thesis is correct, these are actually examples of effectively uncomputable functions.

A normal form theorem of the most basic type tells us that for every formula A there is a formula A* of some special syntactic form such that A and A* are logically equivalent. A normal form theorem for satisfiability tells us that for every set г of sentences there is a set г* of sentences of some special syntactic form such that г and г* are equivalent for satisfiability, meaning that one will be satisfiable if and only if the other is. In section 19.1 we establish the prenex normal form theorem, according to which every formula is logically equivalent to one with all quantifiers at the beginning, along with some related results. In section 19.2 we establish the Skolem normal form theorem, according to which every set of sentences is equivalent for satisfiability to a set of sentences with all quantifiers at the beginning and all quantifiers universal. We then use this result to give an alternative proof of the Löwenheim–Skolem theorem, which we follow with some remarks on implications of the theorem that have sometimes been thought ‘paradoxical’. In the optional section 19.3 we go on to sketch alternative proofs of the compactness and Gödel completeness theorems, using the Skolem normal form theorem and an auxiliary result known as Herbrand's theorem. In section 19.4 we establish that every set of sentences is equivalent for satisfiability to a set of sentences not containing identity, constants, or function symbols. […]

This chapter is entirely devoted to the proof of the compactness theorem. Section 13.1 outlines the proof, which reduces to establishing two main lemmas. These are then taken up in sections 13.2 through 13.4 to complete the proof, from which the Löwenheim–Skolem theorem also emerges as a corollary. The optional section 13.5 discusses what happens if nonenumerable languages are admitted: compactness still holds, but the Löwenheim–Skolem theorem in its usual ‘downward’ form fails, while an alternative ‘upward’ theorem holds.

A function is effectively computable if there are definite, explicit rules by following which one could in principle compute its value for any given arguments. This notion will be further explained below, but even after further explanation it remains an intuitive notion. In this chapter we pursue the analysis of computability by introducing a rigorously defined notion of a Turing-computable function. It will be obvious from the definition that Turing-computable functions are effectively computable. The hypothesis that, conversely, every effectively computable function is Turing computable is known as Turing's thesis. This thesis is not obvious, nor can it be rigorously proved (since the notion of effective computability is an intuitive and not a rigorously defined one), but an enormous amount of evidence has been accumulated for it. A small part of that evidence will be presented in this chapter, with more in chapters to come. We first introduce the notion of Turing machine, give examples, and then present the official definition of what it is for a function to be computable by a Turing machine, or Turing computable.

In the preceding chapter we connected our work on recursion with our work on formulas and proofs in one way, by showing that various functions associated with formulas and proofs are recursive. In this chapter we connect the two topics in the opposite way, by showing how we can ‘talk about’ recursive functions using formulas, and prove things about them in theories formulated in the language of arithmetic. In section 16.1 we show that for any recursive function f, we can find a formula φf such that for any natural numbers a and b, if f(a) = b then ∀y(φf (a, y) ↔ y = b) will be true in the standard interpretation of the language of arithmetic. In section 16.2 we strengthen this result, by introducing a theory Q of minimal arithmetic, and showing that for any recursive function f, we can find a formula ψf such that for any natural numbers a and b, if f(a) = b then ∀y(ψf (a, y) ↔ y =b) will be not merely true, but provable in Q. In section 16.3 we briefly introduce a stronger theory P of Peano arithmetic, which includes axioms of mathematical induction, and explain how these axioms enable us to prove results not obtainable in Q. The brief, optional section 16.4 is an appendix for readers interested in comparing our treatment of these matters here with other treatments in the literature.

The aim has been to present the principal fundamental theoretical results about logic, and to cover certain other meta-logical results whose proofs are not easily obtainable elsewhere. We have tried to make the exposition as readable as was compatible with the presentation of complete proofs, to use the most elegant proofs we knew of, to employ standard notation, and to reduce hair (as it is technically known).

Showing that a function is Turing computable directly, by giving a table or flow chart for a Turing machine computing the function, is rather laborious, and in the preceding chapters we did not get beyond showing that addition and multiplication and a few other functions are Turing computable. In this chapter we provide a less direct way of showing functions to be Turing computable. In section 5.1 we introduce an ostensibly more flexible kind of idealized machine, an abacus machine, or simply an abacus. In section 5.2 we show that despite the ostensible greater flexibility of these machines, in fact anything that can be computed on an abacus can be computed on a Turing machine. In section 5.3 we use the flexibility of these machines to show that a large class of functions, including not only addition and multiplication, but exponentiation and many other functions, are computable on a abacus. In the next chapter functions of this class will be called recursive, so what will have been proved by the end of this chapter is that all recursive functions are Turing computable.

Introductory textbooks in logic devote much space to developing one or another kind of proof procedure, enabling one to recognize that a sentence D is implied by a set of sentences г, with different textbooks favoring different procedures. In this chapter we introduce the kind of proof procedure, called a Gentzen system or sequent calculus, that is used in more advanced work, where in contrast to introductory textbooks the emphasis is on general theoretical results about the existence of proofs, rather than practice in constructing specific proofs. The details of any particular procedure, ours included, are less important than some features shared by all procedures, notably the features that whenever there is a proof of D from г, D is a consequence of г, and conversely, whenever D is a consequence of г, there is a proof of D from г. These features are called soundness and completeness, respectively. (Another feature is that definite, explicit rules can be given for determining in any given case whether a purported proof or deduction really is one or not; but we defer detailed consideration of this feature to the next chapter.) Section 14.1 introduces our version or variant of sequent calculus. Section 14.2 presents proofs of soundness and completeness. The former is easy; the latter is not so easy, but all the hard work for it has been done in the previous chapter. […]

Suppose that, in addition to allowing quantifications over the elements of a domain, as in ordinary first-order logic, we allow also quantification over relations and functions on the domain. The result is called second-order logic. Almost all the major theorems we have established for first-order logic fail spectacularly for second-order logic, as is shown in the present short chapter. This chapter and those to follow generally presuppose the material in section 17.1. (They are also generally independent of each other, and the results of the present chapter will not be presupposed by later ones.)

In this chapter we begin to bring together our work on logic from the past few chapters with our work on computability from earlier chapters (specifically, our work on recursive functions from Chapters 6 and 7). In section 15.1 we show how we can ‘talk about’ such syntactic notions as those of sentence and deduction in terms of recursive functions, and draw among others the conclusion that, once code numbers are assigned to sentences in a reasonable way, the set of valid sentences is semirecursive. Some proofs are deferred to sections 15.2 and 15.3. The proofs consist entirely of showing that certain effectively computable functions are recursive. Thus what is being done in the two sections mentioned is to present still more evidence, beyond that accumulated in earlier chapters, in favor of Church's thesis that all effectively computable functions are recursive. Readers who feel they have seen enough evidence for Church's thesis for the moment may regard these sections as optional.

Our ultimate goal will be to present some celebrated theorems about inherent limits on what can be computed and on what can be proved. Before such results can be established, we need to undertake an analysis of computability and an analysis of provability. Computations involve positive integers 1, 2, 3, … in the first instance, while proofs consist of sequences of symbols from the usual alphabet A, B, C, … or some other. It will turn out to be important for the analysis both of computability and of provability to understand the relationship between positive integers and sequences of symbols, and background on that relationship is provided in the present chapter. The main topic is a distinction between two different kinds of infinite sets, the enumerable and the nonenumerable. This material is just a part of a larger theory of the infinite developed in works on set theory: the part most relevant to computation and proof. In section 1.1 we introduce the concept of enumerability. In section 1.2 we illustrate it by examples of enumerable sets. In the next chapter we give examples of nonenumerable sets.

We are now in a position to give a unified treatment of some of the central negative results of logic: Tarski's theorem on the indefinability of truth, Church's theorem on the undecidability of logic, and Gödel's first incompleteness theorem, according to which, roughly speaking, any sufficiently strong formal system of arithmetic must be incomplete (if it is consistent). These theorems can all be seen as more or less direct consequences of a single exceedingly ingenious lemma, the Gödel diagonal lemma. This lemma, and the various negative results on the limits of logic that follow from it, will be presented in section 17.1. This presentation will be followed by a discussion in section 17.2 of some classic particular examples of sentences that can be neither proved nor disproved in theories of arithmetic like Q or P. Further such examples will be presented in the optional section 17.3. According to Gödel's second incompleteness theorem, the topic of the next chapter, such examples also include the sentence stating that P is consistent.

‘Welcome to the wonderful world of finite state machines.’