BOUNDS ON TRANSFER PRINCIPLES 3 II. PREREQUISITES IN LOGIC We require the notions of a first-order language, a statement in the language, a structure for the language, and of the statement holding in the structure. These are developed at the beginning of any logic text, for example [Kreisel & Krivine, p. 15], but we only need the most familiar cases. A language contains function symbols for example +, -, and * relation symbols, for example = and , and constant symbols for example 0, 1, 11, 100, and so on. We also have a countable supply of variables which are usually (subscripted) x, y, and z. A term is either a constant symbol, a variable, or a function symbol applied to the appropriate number of terms. In the example the terms are polynomials with binary coefficients. An atomic formula is a predicate symbol applied to the appropriate number of terms, for example x + y = 0 or y y *z + 11 *x*x. A formula is built from atomic formulae using the logical connectives & (and), j (or), and'*"l(not) and the quantifiers for all and there exists. A variable which is in the scope of a quantifier is called bound otherwise it is called free. A formula with no free variables is called a statement, for example S = (for all x) (there exists y) (x = 0 | x*y = 1). The truth or falsity (truth value) of a statement may be judged in a set K which has a function for every function symbol, a relation for every relation symbol, and an element associated with every constant symbol. Such a set is called a structure for the language. If K is the integers and +, -, *, =, and are the usual addition, subtraction, multiplication and order, then S is false in K but it is true in the structure where K is the rational numbers and +, -, *, =, and are as usual. If S is true in K say that S holds in K, K satisfies S, or that S holds in the theory of K. In each case, the quantifiers are allowed to range over K. If A C K we may explicitly limit x to range over A with the limited quantifier (for all x A) or (there exists xe A). Thus, (for all xeQ-0) (there exists yeQ-0) (x*y=l) holds in the rational numbers. It is easy to show, [Kreisel & Krivine, p. 20], that any formula is equivalent (in any structure) to one of the form (Qj x^_) . . . (Qn xn) B where Q^ to Qn are quantifiers and B is a quantifier-free formula. This is called a prenex form and B is called its matrix. The only theorem we need is: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * THEOREM: If a statement in the language {+, -, *, =, 0, 1, 10, 11, . . . } holds in some algebraically closed field of characteristic p, then it holds in every algebraically closed field of characteristic p. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * which we refer to as the completeness of the theory of algebraically closed fields of fixed characteristic. For a proof see [Kreisel & Krivine, p. 59].
Previous Page Next Page