Acta Mathematica Academiae Scientiarum Hungaricae 3. (1952)

1952 / 1-2. szám - Kalmár László: Another proof of the Markov-Post theorem

ANOTHER PROOF OF THE MARKOV—POST THEOREM 3 of S. The word problem for associative systems, relative to a given system S of relations, consists in asking for an algorithm by means of which, given any relation in au a.,,..., at, we could decide if it is a consequence of S. Obviously, a relation in au a2,..a, is certainly a consequence of a system S of relations in au a2,..at if it can be obtained from the relation e = e and from the relations of S by means of a finite number of multipli­cations by one of alt a2,ai on the left or on the right as well as appli­cations of the transitivity law; i. e. if it is a theorem of the following formal system ®s. Symbols of c5s are au a2,..ah — . Terms of <PS are the words formed of the letters ax, a2,..., a,. Formulae of Ф$ are the relations between such words, i. e. t u, where t and u are terms of Ф$. Axioms of Ф5 are e = e (e denoting the empty word) as well as the relations of S. Theorems of 0s are (i) the axioms of Ф$; (ii) a1t = a1u, o2t = ű2u, ..., a;t = ű,u, ta, = uö1, ta2= ua2,..., tűí==uűí if t = u is a theorem of <l>s; (iii) u v if t ^ u and t = v are theorems of ; (iv) nothing else.7 Conversely, each consequence of the system S ;s a theorem of the formal system Ф5. Indeed, the predicate8 “t = u is a theorem of ®s” between the terms (of Фэ) is obviously an equivalence predicate, and, as easily seen, the equivalence clas­ses of the free associative system on the alphabet {aua2,..at) form an associative system9 9ls such that a relation in ax,a2,... .,a\ holds in 2ls if and only if it is a theorem of Фб- Hence, the relations of the system S hold in Üls and a relation which is not a theorem of ®s, not holding in 9is, is no consequence of S. Thus, the word problem relative to a system S of rela­tions can be formulated alternatively as asking for an algorithm by means of which, given two terms t and u of ®s, we could decide if t = u is a theorem of Ф$. This formulation of the word problem is more appropriate for researches of a logical character.10 7 I. e. the set of theorems of Ф% is the smallest set (the intersection of all sets) having the axioms of Ф5, further, together with t=u, the formulae a1t=a1u, a.2t—a2u,ap- =a;u, to3 = Ufl2........tű( = ua(, finally, together with t = u and t = v, the formula u = v as elements. Hence, we can prove a property of the theorems of by proving it for the axioms of <%; then, supposing that t =u has the property in question, proving that the same holds for axt = axu, a,t = a2u,..., mt = щи, taq = ua1; ta3 = ua2,..., tüi= uű; too, and, supposing that t=u and t = v have the property in question, proving that the same holds for u == v too. A similar remark applies for the set of the theorems of other formal systems (viz. Tt, Фх, Ф2,..., Ф5) as well as for the set of the terms of some of them (viz. iPt, Фх, Ф2 and Ф3) too. 8 We use the expression “predicate” instead of “relation” for the latter is used in this paper in a particular sense. 9 21$ is called the associative system generated by the system S of relations. It can be characterized (irrespective of isomorphisms) by the following properties, (i) % is an associative system each element of which can be written as a product each factor of which is one of some elements aita2,..., at of 2is; (ii) a relation in alt a2,..., at holds in % if and only if it is a consequence of the system S. 10 A third formulation of the word problem relative to a system S of relations in aua2,...,ai, perhaps the most interesting one for the algebraist, is to ask for an algo­ l*

Next