Logic and Structure

Without adopting one of the various views advocated in the foundations of mathematics, we may agree that mathematicians need and use a language, if only for the communication of their results and their problems. While mathematicians have been claiming the greatest possible exactness for their methods, they have been less sensitive as to their means of communication. It is well known that Leibniz proposed to put the practice of mathematical communication and mathematical reasoning on a firm base; it was, however, not before the nineteenth century that those enterprises were (more) successfully undertaken by G. Frege and G. Peano. No matter how ingeniously and rigorously Frege, Russell, Hilbert, Bernays and others developed mathematical logic, it was only in the second half of this century that logic and its language showed any features of interest to the general mathematician. The sophisticated results of Gödel were of course immediately appreciated, but they remained for a long time technical highlights without practical use. Even Tarski's result on the decidability of elementary algebra and geometry had to bide its time before any applications turned up.

Traditionally, logic is said to be the art (or study) of reasoning; so in order to describe logic in this tradition, we have to know what ‘reasoning’ is. According to some traditional views reasoning consists of the building of chains of linguistic entities by means of a certain relation ‘… follows from …’, a view which is good enough for our present purpose. The linguistic entities occurring in this kind of reasoning are taken to be sentences, i.e. entities that express a complete thought, or state of affairs. We call those sentences declarative. This means that, from the point of view of natural language our class of acceptable linguistic objects is rather restricted.

Fortunately this class is wide enough when viewed from the mathematician’s point of view. So far logic has been able to get along pretty well under this restriction. True, one cannot deal with questions, or imperative statements, but the role of these entities is negligible in pure mathematics. I must make an exception for performative statements, which play an important role in programming; think of instructions as ‘goto, if … then, else …’, etc. For reasons given below, we will, however, leave them out of consideration.

The sentences we have in mind are of the kind ‘27 is a square number’, ‘every positive integer is the sum of four squares’, ‘there is only one empty set’. A common feature of all those declarative sentences is the possibility of assigning them a truth value, trueor false. We do not require the actual determination of the truth value in concrete cases, such as for instance Goldbach's conjecture or Riemann's hypothesis. It suffices that we can ‘in principle’ assign a truth value.

Just as in the case of propositional logic we shall show that ‘derivability’ and ‘semantical consequence’ coincide. We will do quite a bit of work before we get to the theorem. Although the proof of the completeness theorem is not harder than, say, some proofs in analysis, we would advise the reader to read the statement of the theorem and to skip the proof at the first reading and to return to it later. It is more instructive to go to the applications and it will probably give the reader a better feeling for the subject.

In first-order predicate logic the variables range over elements of a structure, in particular the quantifiers are interpreted in the familiar way as “for all elements a of ∣♃∣ … ” and “there exists an element a of ∣♃∣ …”. We will now allow a second kind of variable ranging over subsets of the universe and its cartesian products, i.e. relations over the universe.

The introduction of these second-order variables is not the result of an unbridled pursuit of generality; one is often forced to take all subsets of a structure into consideration. Examples are “each bounded non-empty set of reals has a suppremum”, “each non-empty set of natural numbers has a smallest element”, “each ideal is contained in a maximal ideal”. Already the introduction of the reals on the basis of the rationals requires quantification over sets of rationals, as we know from the theory of Dedekind cuts.

Instead of allowing variables for (and quantification over) sets, one can also allow variables for functions. However, since we can reduce functions to sets (or relations), we will restrict ourselves here to second-order logic with set variables.

When dealing with second-order arithmetic we can restrict our attention to variables ranging over subsets of N, since there is a coding of finite sequences of numbers to numbers, e.g. via Gödel's β-function, or via prime factorisation. In general we will, however, allow for variables for relations.

The introduction of the syntax of second-order logic is so similar to that of first-order logic that we will leave most of the details to the reader.

We will introduce a class of numerical functions which evidently are effectively computable. The procedure may seem rather ad hoc, but it gives us a surprisingly rich class of algorithms. We use the inductive method, that is, we fix a number of initial functions which are as effective as one can wish; after that we specify certain ways to manufacture new algorithms out of old ones.

The initial algorithms are extremely simple indeed: the successor function, the constant functions and the projection functions. It is obvious that composition (or substitution) of algorithms yields algorithms The use of recursion was as a device to obtain new functions already known to Dedekind'; that recursion produces algorithms from given algorithms is also easily seen. In logic the study of primitive recursive functions was initiated by Skolem, Herbrand, Gödel and others.