Acta Mathematica Academiae Scientiarum Hungaricae 3. (1952)
1952 / 1-2. szám - Kalmár László: Another proof of the Markov-Post theorem
L. KALMAR Markov’s proofs especially for readers who are not acquainted with Church’s theory of A-convertability5 6 * nor with Post’s reduction theory of logical systems.“ 1. An associative system is a set in which an associative binary operation, called multiplication, has been defined. We denote the result of this operation, applied to the elements a and b, by ab; we call it the product of a and b. On account of the associative law (ab)c = a(bc), a product a,a2... a, of several factors has an obvious sense (at for /=1). We confine ourselves to associative systems containing a unit, i. e. an element e for which we have ae = ea^- a for every element a of the system. For / 0, we define the “empty product” axa2... a, to denote e. An equation of the form (1) ahau...air = ajxah...ajt is called a relation; moreover, a relation in aua2,.. ., ai if each of h, h, ■ ■ •, irjiji, ■ .-,js is one of 1,2,...,/. If a,,, a,,,..., a,r, a}l, ah,. ..,ajs denote some elements of an associative system 91, we say, the relation (1) holds in 21, or 21 is satisfying (1), if ai,ai,... a,r is the same element of 21 as a „a,.... ajs. As an instance of an associative system, form the finite sequences or “words”, each element or “letter” of which is a member of a given finite set or “alphabet”. Two words are identical, by definition, if and only if they contain the same letters with the same multiplicity and in the same order. The product of two words is defined as the word formed of them by juxtaposition. In this associative system, called the free associative system on the given alphabet, the relation (1) holds if and only if it is “trivial”, i. e. if űtla,-2... ö,r and üjßj,... aJt are identical words. However, there are associative systems in which some non-trivial relations hold; e. g. the associative systems 21s defined below. Given a finite system S of relations in ű1; a2,..., a,, a further relation in au a2,..., a, is called a consequence of S if and only if it holds in every associative system containing alya2,..a> and satisfying each of the relations 5 See, A. Church, Ioc. cit. 3; A set of postulates for the foundation of logic, Annals of Math., (2) 33 (1932), pp. 346—366 and 34 (1933), pp. 839—864; A proof of freedom of contradiction, Proceedings of the National Academy of Sciences (Washington), 21 (1935), pp. 275—281; Mathematical logic (Princeton, N. J., 1936); The calculi of lambda-conversion (Princeton, N. J., 1941); A. Church and J. B. Rosser, Some properties of conversion, Transactions of the American Math. Society, 39 (1936), pp. 472—482; S. C. Kleene, Proof by cases in formal logic, Annals of Math., (2) 35 (1934), pp. 529— 544; A theory of positive integers in formal logic, American Journal of Math., 57 (1935), pp. 153—173 and 219— 244; 2-definiability and recursiveness, Duke Math. Journal, 2 (1936), pp. 340—353; J. B. Rosser, Ioc. cit.3. 6 See E. L. Post, Ioc. cit.8; A variant of a recursively unsolvable problem, Bulletin of the American Math. Society, 52 (1946), pp. 264—268; and loc. cit.l.