Zum Begriff der Axiomatisierbarkeit by Hans Hermes Review by: Jonathan Bennett The Journal of Symbolic Logic, Vol. 22, No. 1 (Mar., 1957), p. 83 Published by: Association for Symbolic Logic Stable URL: http://www.jstor.org/stable/2964069 . Accessed: 12/06/2014 22:27 Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at . http://www.jstor.org/page/info/about/policies/terms.jsp . JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact
[email protected]. . Association for Symbolic Logic is collaborating with JSTOR to digitize, preserve and extend access to The Journal of Symbolic Logic. http://www.jstor.org This content downloaded from 195.78.108.147 on Thu, 12 Jun 2014 22:27:17 PM All use subject to JSTOR Terms and Conditions http://www.jstor.org/action/showPublisher?publisherCode=asl http://www.jstor.org/stable/2964069?origin=JSTOR-pdf http://www.jstor.org/page/info/about/policies/terms.jsp http://www.jstor.org/page/info/about/policies/terms.jsp REVIEWS 83 where R(X, n) is a certain formula of P which contains no identity formulas involving large variables. The reviewer sees no possibility of proving 3.2 in Q, unless identity between large variables is introduced by definition; but then at least part (b) of Wang's assertion would be false. RICHARD MONTAGUE HANS HERMES. Zum Begrifl der Axiomatisierbarkeit. Mathematische Nach- richten, vol. 4 (1951), pp. 343-347. Proof is given of a theorem from which follows a series of corollaries regarding syntactical axiomatisability, defined as follows: a set M of expressions is called syntactically axiomatisable if it has a finite sub-set MO such that M is the smallest set containing MO and closed with respect to some finite set of decidable n-adic rela- tions (where n is finite). (A set M is called closed with respect to an (n + 1)-adic relation R when (xl). . . (xn) (y) (xl, . . . , xn E M . Rx1 ... .xny . D . y E M).) The theorem is that for any effectively enumerable set M of natural numbers there is a decidable dyadic relation R such that, for any c belonging to M, X(Rpocx) = M. (Here we use the Principia notation Rpo for the ancestral or transitive closure of R; i.e. Rpo cx holds if and only if R?1cx holds for some positive n.) Proof. For a finite Ml, R can be defined by enumeration. Assume Ml is infinite. There is a calculable function p(n) whose range of values is M; and R is defined as the relation such that, for any a, Rab holds for all and only the cases where b = qp(O), ,p(1), ..., c(a); and, if all these - a, then also where b = qp(a + 1), qp(a + 2),. qp(a + r), where r is the smallest number such that qp(a + r) > a. Thus, using 'ey(V(y))' for 'the smallest y such that Vp(y),' we have: Rab . (3x)(x ? max(a, ey(qp(y) > a)) . b = p(x)). It follows that R is decidable, and, since Rab D b E M, that for any c in Ml x}(Rpocx) C M. For the other half of the proof, take any c and d in Al. There is an s such that d = qp(s); and it follows from the definition of R that (a) (3b) (Rab . a < b), and thus that there is an n and a t such that Rnct and s < t. Thus Rtp(s), which implies Rn+'cq(s). Whence q(s) E x(Rp0cx), and thus Al C x(Rp0cx). Q.e.d. The theorem has as a corollary that any denumerable set of expressions is, in the sense of the definition, syntactically axiornatisable with just one rule of inference and with any one of its elements as single axiom. The result holds, for instance, for any system satisfiable by a finite matrix. Further, since any set is denumerable if it is axiomatisable in the sense of the definition except that its MO includes schemata representing denumerably infinite bundles of axioms, it follows that the result holds for all such sets and thus that the definition is applicable, without change of sense, to them. (Since the definition is not relative to any standard rules of inference, how- ever, this corollary cannot be taken as an answer to die Frage, ob mnan immer Axiom- schemiata zuriick/iihren kann auf Einzelaxiorne in the sense in which this is usually asked.) The author points out that, while the proof that there is an R fulfilling the given conditions is constructive, in most cases the R will be of such complexity that the result is of theoretical rather than practical significance. JONATHAN BENNETT H. HERMES. Stir le concept d'axiomatisabilite. Les mdthodes formelles en axiomatique Paris decembre 1950, Colloques internationaux du Centre National de la Recherche Scientifique no. 36, Paris 1953, pp. 23-25. PAUL BERNAYS, ABRAHAM ROBINSON. Discussion. Ibid., p. 26. A briefer, informal exposition of the above. JONATHAN BENNETT GREGORIO KLIMOVSKY. Problemnas relatives a la de/inicion de "Verdad Ldgica" en los sistemas semdinticos y sintdcticos. Segundo Symposium sobre Algunos Pro- blemas Matemdticos que se estdn estudiando en Latino America, Villavi- cencio-Mendoza 21-25 Julio 1954, Centro de Cooperacion Cientifica de la UNESCO para Am6rica Latina, Montevideo 1954, pp. 299-318. This content downloaded from 195.78.108.147 on Thu, 12 Jun 2014 22:27:17 PM All use subject to JSTOR Terms and Conditions http://www.jstor.org/page/info/about/policies/terms.jsp Article Contents p. 83 Issue Table of Contents The Journal of Symbolic Logic, Vol. 22, No. 1 (Mar., 1957), pp. i-vi+1-112 Volume Information [pp. i - iv] Front Matter Errata [pp. v - vi] A Generalization of the Concept of ω-Completeness [pp. 1 - 14] Eulerian Syllogistic [pp. 15 - 16] Sur La Structuration du Tableau Des Connectifs Interpropositionnels Binaires [pp. 17 - 18] A Theory of Restricted Quantification I [pp. 19 - 35] Two Theories with Axioms Built by Means of Pleonasms [pp. 36 - 38] Decidability and Essential Undecidability [pp. 39 - 54] Languages in Which Self Reference is Possible [pp. 55 - 67] Reviews untitled [pp. 68 - 72] untitled [pp. 72 - 73] untitled [pp. 73 - 76] untitled [pp. 76 - 77] untitled [pp. 77 - 79] untitled [p. 79] untitled [pp. 79 - 80] untitled [pp. 80 - 81] untitled [pp. 81 - 82] untitled [pp. 82 - 83] untitled [p. 83] untitled [p. 83] untitled [pp. 83 - 84] untitled [pp. 84 - 85] untitled [pp. 85 - 86] untitled [p. 86] untitled [pp. 86 - 87] untitled [pp. 87 - 88] untitled [p. 88] untitled [pp. 88 - 89] untitled [pp. 89 - 90] untitled [p. 90] untitled [pp. 90 - 91] untitled [p. 91] untitled [p. 91] untitled [p. 92] untitled [p. 92] untitled [pp. 92 - 93] untitled [pp. 93 - 94] untitled [p. 94] untitled [p. 94] untitled [pp. 94 - 95] untitled [pp. 95 - 96] untitled [p. 96] untitled [p. 96] untitled [pp. 96 - 97] untitled [p. 97] untitled [p. 98] untitled [p. 98] untitled [p. 99] untitled [pp. 99 - 100] untitled [pp. 100 - 101] untitled [p. 101] untitled [p. 101] untitled [p. 101] untitled [p. 102] untitled [p. 102] untitled [pp. 102 - 103] Further Citations [pp. 103 - 104] Twenty-First Annual Meeting of the Association for Symbolic Logic [pp. 105 - 112]