|
3 From Proposition VI we now obtain further consequences and for this purpose give the following definition: A relation (class) is called arithmetical, if it can be defined solely by means of the concepts +, . [addition and multiplication, applied to natural numbers]49 and the logical constants Ú, ~, (x), =, where (x) and = are to relate only to natural numbers.50 The concept of "arithmetical proposition" is defined in a corresponding way. In particular the relations "greater [than]" and "congruent to a modulus" are arithmetical, since
x > y
º
~($z)[y
= x+z] We now have: Proposition VII: Every recursive relation is arithmetical. We prove this proposition in the form: Every relation of the form x0 = f(x1 … xn), where f is recursive, is arithmetical, and apply mathematical induction on the degree of f. Let f be of degree s (s > 1). Then either [192] 1. f(x1 … xn) = r[c1(x1 … xn), c2(x1 … xn) … cm(x1 … xn)]51 (where p and all the x's have degrees smaller than s) or 2. f(0,x2 … xn) = y(x2 … xn) f(k+1,x2 … xn) = m[k,f(k,x2 … xn),x2 … xn] (where y, m are of lower degree than s). In the first case we have: x0 = f(x1 … xn) º ($y1 … ym)[R(x0,y1 … ym) & S1(y1,x1 … xn) & … & Sm(ym,x1 … xn)], where R and Si are respectively the arithmetical relations which by the inductive assumption exist, equivalent to x0 = r(y1 … ym) and y = ci(x1 … xn). In this case, therefore, x0 = f(x1 … xn) is arithmetical. In the second case we apply the following procedure: The relation x0 = f(x1 … xn) can be expressed with the help of the concept "series of numbers" (f)52 as follows: x0 = f(x1 … xn) º ($f){f0 = y(x2 … xn) & (k)[k < x1 ® fk+1 = m(k,fk,x2 … xn)] & x0 = fx1} If S(y,x2 … xn) and T(z,x1 … xn+1) are respectively the arithmetical relations–which by the inductive assumption exist–equivalent to y = y(x2 … xn) and z = m(x1 … xn+1), the following then holds: x0 = f(x1 … xn) º ($f){S(f0,x2 … xn) & (k)[k < x1 ® T(fk+1,k,fk,x2 … xn)] & x0 = fx1} (17) We now replace the concept "series of numbers" by "pair of numbers", by assigning to the number pair n, d the number series f(n,d)(fk(n,d) = [n]1+(k+1)d), where [n]p denotes the smallest non-negative residue of n modulo p. We then have the following: Lemma 1: If f is any series of natural numbers and k any natural number, then there exists a pair of natural numbers n, d, such that f(n,d) and f agree in the first k terms. Proof: Let l be the largest of the numbers k,f0,f1 … fk-1. Let n be so determined that n = fi(mod(1+(i+1)l!)] for i = 0,1 … k-1 [193] which is possible, since every two of the numbers 1+(i+1)l! (i = 0,1 … k-1) are relatively prime. For a prime number contained in two of these numbers would also be contained in the difference (i1-i2)l! and therefore, because |i1-i2| < 1, in l!, which is impossible. The number pair n, l! thus accomplishes what is required. Since the relation x = [n]p is defined by x = n(mod p) & x < p and is therefore arithmetical, so also is the relation P(x0,x1 … xn) defined as follows: P(x0 … xn) º ($n,d){S([n]d+1,x2 … xn) & (k) [k < x1 ® T([n]1+d(k+2),k,[n]1+d(k+1),x2 … xn)] & x0 = [n]1+d(x1+1)} which, according to (17) and Lemma 1, is equivalent to x0 = f(x1 … xn) (we are concerned with the series f in (17) only in its course up to the x1+1-th term). Thereby Proposition VII is proved. According to Proposition VII there corresponds to every problem of the form (x) F(x) (F recursive) an equivalent arithmetical problem, and since the whole proof of Proposition VII can be formalized (for every specific F) within the system P, this equivalence is provable in P. Hence: Proposition VIII: In every one of the formal systems53 referred to in Proposition VI there are undecidable arithmetical propositions. The same holds (in virtue of the remarks at the end of Section 3) for the axiom system of set theory and its extensions by w-consistent recursive classes of axioms. We shall finally demonstrate the following result also: Proposition IX: In all the formal systems referred to in Proposition VI53 there are undecidable problems of the restricted predicate calculus54 (i.e. formulae of the restricted predicate calculus for which neither universal validity nor the existence of a counter-example is provable).55 [194] This is based on Proposition X: Every problem of the form (x) F(x) (F recursive) can be reduced to the question of the satisfiability of a formula of the restricted predicate calculus (i.e. for every recursive F one can give a formula of the restricted predicate calculus, the satisfiability of which is equivalent to the validity of (x) F(x)). We regard the restricted predicate calculus (r.p.c.) as consisting of those formulae which are constructed out of the basic signs: ~, Ú, (x), =; x, y … (individual variables) and F(x), G(x,y), H(x,y,z) … (property and relation variables)56 where (x) and = may relate only to individuals. To these signs we add yet a third kind of variables f(x), y(x,y), c(x,y,z) etc. which represent object functions; i.e. f(x), y(x,y), etc. denote one-valued functions whose arguments and values are individuals.57 A formula which, besides the first mentioned signs of the r.p.c., also contains variables of the third kind, will be called a formula in the wider sense (i.w.s.).58 The concepts of "satisfiable" and "universally valid" transfer immediately to formulae i.w.s. and we have the proposition that for every formula i.w.s. A we can give an ordinary formula of the r.p.c. B such that the satisfiability of A is equivalent to that of B. We obtain B from A, by replacing the variables of the third kind f(x), y(x,y) … appearing in A by expressions of the form (,z)F(z,x), (,z)G(z,x y), …, by eliminating the "descriptive" functions on the lines of PM I *14, and by logically multiplying59 the resultant formula by an expression, which states that all the F, G … substituted for the f, y … are strictly one-valued with respect to the first empty place. We now show, that for every problem of the form (x) F(x) (F recursive) there is an equivalent concerning the satisfiability of a formula i.w.s., from which Proposition X follows in accordance with what has just been said. Since F is recursive, there is a recursive function F(x) such that F(x) º [F(x) = 0], and for F there is a series of functions F1,F2 … Fn, such that Fn = F, F1(x) = x+1 and for every Fk(1 < k £ n) either
1. (x2
… xm) [Fk(0,x2
… xm) = (Fp(x2
… xm)] p,q < k [195] or
2. (x1
… xm) [Fk(x1
… xm) =
Fr(Fi1(c1)
… fis(cs))]60
(19) or 3. (x1 … xm) [Fk(x1 … xm) = F1(F1 … F1(0))] (20) In addition, we form the propositions: (x) ~[F1(x) = 0] & (x y) [F1(x) = F1(y) ® x = y] (21) (x) [Fn(x) = 0] (22) In all the formulae (18), (19), (20) (for k = 2,3, … n) and in (21), (22), we now replace the functions Fi by the function variable fi, the number 0 by an otherwise absent individual variable x0 and form the conjunction C of all the formulae so obtained. The formula ($x0)C then has the required property, i.e 1. If (x) [F(x) = 0] is the case, then ($x0)C is satisfiable, since when the functions F1, F2 … Fn are substituted for f1, f2 … fn in ($x0)C they obviously yield a correct proposition. 2. If ($x0)C is satisfiable, then (x) [F(x) = 0] is the case. Proof: Let Y1, Y2 … Yn be the functions presumed to exist, which yield a correct proposition when substituted for f1, f2 … fn in ($x0)C. Let its domain of individuals be I. In view of the correctness of ($x0)C for all functions Yi, there is an individual a (in I) such that all the formulae (18) to (22) transform into correct propositions (18') to (22') on replacement of the Fi by Yi and of 0 by a. We now form the smallest sub-class of I, which contains a and is closed with respect to the operation Y1(x). This subclass (I') has the property that every one of the functions Yi, when applied to elements of I', again yields elements of I'. For this holds of Y1 in virtue of the definition of I'; and by reason of (18'), (19'), (20') this property carries over from Yi of lower index to those of higher. The functions derived from Yi by restriction to the domain of individuals I', we shall call Yi'. For these functions also the formulae (18) to (22) all hold (on replacement of 0 by a and Fi by Yi'). Owing to the correctness of (21) for Y1' and a, we can map the individuals of I' in one-to-one correspondence on the natural numbers, and this in such a manner that a transforms into 0 and the function Y1' into the successor function F1. But, by this mapping, all the functions Yi' transform into the functions Fi, and owing to the correct- [196] ness of (22) for Yn' and a, we get (x) [Fn(x) = 0] or (x) [F(x) = 0], which was to be proved.61 Since the considerations leading to Proposition X (for every specific F) can also be restated within the system P, the equivalence between a proposition of the form (x) F(x) (F recursive) and the satisfiability of the corresponding formula of the r.p.c. is therefore provable in P, and hence the undecidability of the one follows from that of the other, whereby Proposition IX is proved.62 49 Here, and in what follows, zero is always included among the natural numbers. 50 The definiens of such a concept must therefore be constructed solely by means of the signs stated, variables for natural numbers x,y… and the signs 0 and 1 (function and set variables must not occur). (Any other number-variable may naturally occur in to prefixes in place of x.) 51 It is not of course necessary that all x1 … xn should actually occur in ci [cf. the example in footnote 27]. 52 f signifies here a variable, whose domain of values consists of series of natural numbers. fk denotes the k+1-th term of a series f (f0 being the first). 53 These are the w-consistent systems derived from P by addition of a recursively definable class of axioms. 54 Cf. Hilbert-Ackermann, Grundzüge der theoretischen Logik. In the system P, formulae of the restricted predicate calculus are to be understood as those derived from the formulae of the restricted predicate calculus of PM on replacement of relations by classes of higher type, as indicated on [176]. 55 In my article 'Die Vollständigkeit der Axiome des logischen Funktionenkalküls', Monatsh. f. Math. u. Phys. XXXVII, 2, I have shown of every formula of the restricted predicate calculus that it is either demonstrable as universally valid or else that a counter-example exists; but in virtue of Proposition IX the existence of this counter-example is not always demonstrable (in the formal systems in question). 56 D. Hilbert and W. Ackermann, in the work already cited, do not include the sign = in the restricted predicate calculus. But for every formula in which the sign = occurs, there exists a formula without this sign, which is satisfiable simultaneously with the original one (cf. the article cited in footnote 55). 57 And of course the domain of the definition must always be the whole domain of individuals. 58 Variables of the third kind may therefore occur at all empty places instead of individual variables, e.g. y = f(x), F(x,f(y)), G[y(x,f(y)),x] etc. 59 I.e. forming the conjunction. 60 ci(i = 1 … s) represents any complex of the variables x1, x2 … xm, e.g. x1 x3 x2. 61 From Proposition X it follows, for example, that the Fermat and Goldbach problems would be soluble, if one had solved the decision problem for the r.p.c. 62 Proposition IX naturally holds also for the axiom system of set theory and its extensions by recursively definable w-consistent classes of axioms, since in these systems also there certainly exist undecidable theorems of the form (x) F(x) (F recursive).
Revista Matemáticas,
Educación e Internetâ |