Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 473.03057
Autor: Erdös, Paul; Faber, Vance; Larson, Jean
Title: Sets of natural numbers of positive density and cylindric set algebras of dimension 2. (In English)
Source: Algebra Univers. 12, 81-92 (1981).
Review: Among others, the reported paper solves some fundamental problems of Ulam concerning projective algebras. To this, the paper uses and improves the theory of cylindric set algebras and their generalizations. Since the reported paper investigates structures treated systematically and extensively in the textbook by L.Henkin, J.D.Monk, A.Tarski, H.Andréka and I. Németi Cylindric set algebras, Lect. Notes Math. 883 (1981; Zbl 497.03025) on cylindric-relativized set algebras and their generalizations, we shall use the notation and terminology of this book. To this book we shall refer as HMTAN.
The broadest generalization of cylindric set algebras of dimension \alpha(Cs\alpha-s) is the class Crs\alpha of cylindric-relativized set algebras, see Def. I.1.1 in HMTAN p.4. The reported paper introduces two special classes of Crs\alpha-s which we shall denote by Crs\alpharc and Crs\alpharcd. Definition: A Crs\alpha\Cal A is said to be rectangular if its unit 1\Cal A is a Cartesian product, that is if 1\Cal A = Pi in I\alphaWi for some function W = < Wi: i in I>. We let Crs\alpharc: = {\Cal A in Crs\alpha: \Cal A is rectangular}. A Crs\alpha: \Cal A is said to be disjointly rectangular if 1\Cal A = Pi in IWi for some function < Wi: i in I> such that (\forall i,j in I)[i\neq j ==> Wi\cap Wj = 0]. We let Crs\alpharcd: = {\Cal A in Crs\alpharc: \Cal A is disjointly rectangular}. The two new classes introduced in the reported paper are Crs\alpharc and Crs\alpharcd.
The reported paper uses a terminology different from the one introduced here which we use in order to avoid confusion with the standard terminoloy of cylindric set algebra theory. The reported paper calls Crs\alpharc-s ``cylindric set algebras with diagonal'' and Crs\alpharcd-s ``cylindric set algebras''. Since in the standard literatur these two terms are already reserved for other purposes, we propose the above terminology for the two very interesting classes introduced in the reported paper. We note that ICrs\alpharc and ICrs\alpharcd are not closed under direct products if \omega > \alpha > 1 while HSPCRS\alpha = Crs\alpha was proved for all \alpha > 1 by I. Németi's paper: Connections between cylindric algebras and initial algebra semantics of CF languages [Mathematical Logic in Computer Science, Proc. Salgótarján 1978, Colloq. Math. Soc. Janos Bolyai 26, 561-605 (1981; Zbl 502.68024)], see Thm. 24 on p. 599 there. To see the above, observe that Crs\alpharc\models\forall x[(\Delta x = 0) ––> (x = 0\lor x = 1)] while this formula is not valid in PCrs\alpharcd. Let \alpha \geq \omega. Then PCrs\alpharc\neq ICrs\alpharc because of the following. Let Th = {ci dij = 1: i,j in \alpha}. Then (*) Crs\alpharc\capMod(Th) = Cs\alpha. By 6.5(ii) of HMTAN o.228, ICs is not closed under direct squares. I.e. \exists\Cal A in Cs\alpha)2\Cal A\not in ICs\alpha. Then \Cal A in Crs\alpharc while 2\Cal A\not in ICrs\alpharc for this \Cal A, by (*). By I.7.3 on p. 88 of HMTAN we have Crs\alpharc = UfUpCrs\alpharc and the same for Crs\alpharcd if \alpha > \omega. That is, for finite \alpha the classes ICrs\alpharc and ICrs\alpharcd are first order axiomatizable. If \alpha \geq \omega then UpCrs\alpharc\neq ICrs\alpharc as the following argument shows. By I.7.18 of HMTAN there is a Cs\alpha\Cal A and an ultrapower \Cal B of \Cal A with \Cal B\not in ICs\alpha. But since \Cal B\models Th, by (*), the assumption \Cal B in ICrs\alpharc would imply \Cal B in ICs\alpha. A contradiction. We note that Cs\alpha\subseteq Crs\alpharc but Gs\alpha\nsupseteq ICrs\alpharc\supseteq ICrs\alpharcd\nsupseteq Ws\alpha, see Fig. 1 on p. 586 of I. Németi's paper (loc.cit.) together with Fig,s 7.6 and I.1.4 on pages 243 and 7 of HMTAN respectively.
The folowing is proved in \S2 of the reported paper. Let K in {Cs2,Crs2rc,Crs2rcd}. Then there is a countable \Cal L in \omega K not embeddable into any finitely generated member of K. Further, to each finitely generated \Cal A\subseteq\Cal L there is a 2-generated \Cal B\subseteq\Cal S1\Cal L such that \Cal A\subseteq\Cal B. Some of the announced results are the following. The number of non-isomorphic 1-generated Crs\alpharcd is 7 if \alpha = 2 and 2\omega if 2 < \alpha < \omega. The number of non-isomorphic 1-generated Crs\alphars-s is 2\omega if 2 \leq \alpha < \omega. At the end of the paper a result of comer is quoted in a form which is not true. Namely, the results is quoted for Cs\alpha-s without diagonal, but there are Cs\alpha-s without diagonal and with base \alpha which cannot be generated by a single element if \alpha < 2. (For \alpha = 2 the quoted form of the result is true.) An improvement of Comer's quoted result is stated in I.4.8 of HMTAN p.65, in the form of approximating the function q: 2\omega ––> \omega defined there. In particular, any Cs\alpha with base \leq \alpha+1 can be generated by a single element if \alpha < \omega. This upper bound \alpha+1 is stated to be sharp in the formulation of problem 8 of HMTAN p.311 for \alpha < 5. That is, if \alpha < 5 then there is a Cs\alpha with base \alpha+2 which cannot be generated by a singke element. The existence of a Cs\alpha with base \alpha+2 which cannot be generated by a single element is still an open problem for \alpha = 5 as well as for 5 \leq \alpha \leq \omega, see the parts concerning the function q^+: \omega ––> \omega of Problems 8 and 2 of HTMAN on p.311 and p.127 respectively (here the page numbers are important because there is a Problem 8 on p.311 as well as on p.127 in HMTAN). An improvment of the results of Henkin quoted at the enf of the reviewed paper is stated in I.4.8 of HMTAN p.65 in the form of stating properties of the function q. Note that Henkin's quoted result is a lower bound for q stating that q(\alpha,\alpha·\beta). Partial solutions for the problem of monk quoted at the end of the reviewed paper are in I.4.8 of HMTAN and Statement (*) in the formulation of Problem 8 on p.311 of HMTAN. In this connection we note that the function denoted by f in the reviewed is denoted by q in HMTAN.
A related result is in the paper by H. Andréka and I.Németi: Which finite cylindric algebras are generated by a single element [Finite Algebra and multiple-Valued Logic, Proc. Coll. Szeged 1979, Colloq. Math. Soc. Janos Bolyai 28, 23-39(1981; Zbl 542.03038)].
Two final remarks: The reviewer has the impression that in all references on p. 91, [8] should be replaced with [11]. The precise version of reference [2] is G. M. Bergman: The ... algebra [Universal algebra, Colloq. Math. Soc. J. Bolyai Vol. 29, 95-106(1981)].
Reviewer: H.Andréka
Classif.: * 03G15 Cylindric and polyadic algebras, etc.
05A99 Classical combinatorial problems
11B83 Special sequences of integers and polynomials
11U99 Connections of number theory with logic
03B10 First-order logic
03G25 Other algebras related to logic
08A02 General relational systems
Keywords: representable cylindric algebras; number of generators; algebras of relations; number of non-isomorphic algebras; projective algebras
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag