##
**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_{\alpha}^{rc} and Crs_{\alpha}^{rcd}. 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} = P_{i in I}^{\alpha}W_{i} for some function W = < W_{i}: i in I>. We let Crs_{\alpha}^{rc}: = **{**\Cal A in Crs_{\alpha}: \Cal A is rectangular**}**. A Crs_{\alpha}: \Cal A is said to be disjointly rectangular if 1^{\Cal A} = P_{i in I}W_{i} for some function < W_{i}: i in I> such that (\forall i,j in I)[i\neq j ==> W_{i}\cap W_{j} = 0]. We let Crs_{\alpha}^{rcd}: = **{**\Cal A in Crs_{\alpha}^{rc}: \Cal A is disjointly rectangular**}**. The two new classes introduced in the reported paper are Crs_{\alpha}^{rc} and Crs_{\alpha}^{rcd}.

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_{\alpha}^{rc}-s ``cylindric set algebras with diagonal'' and Crs_{\alpha}^{rcd}-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_{\alpha}^{rc} and ICrs_{\alpha}^{rcd} 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_{\alpha}^{rc}\models\forall x[(\Delta x = 0) ––> (x = 0\lor x = 1)] while this formula is not valid in PCrs_{\alpha}^{rcd}. Let \alpha \geq \omega. Then PCrs_{\alpha}^{rc}\neq ICrs_{\alpha}^{rc} because of the following. Let Th = **{**c_{i} d_{ij} = 1: i,j in \alpha**}**. Then (*) Crs_{\alpha}^{rc}\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_{\alpha}^{rc} while ^{2}\Cal A\not in ICrs_{\alpha}^{rc} for this \Cal A, by (*). By I.7.3 on p. 88 of HMTAN we have Crs_{\alpha}^{rc} = UfUpCrs_{\alpha}^{rc} and the same for Crs_{\alpha}^{rcd} if \alpha > \omega. That is, for finite \alpha the classes ICrs_{\alpha}^{rc} and ICrs_{\alpha}^{rcd} are first order axiomatizable. If \alpha \geq \omega then UpCrs_{\alpha}^{rc}\neq ICrs_{\alpha}^{rc} 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_{\alpha}^{rc} would imply \Cal B in ICs_{\alpha}. A contradiction. We note that Cs_{\alpha}\subseteq Crs_{\alpha}^{rc} but Gs_{\alpha}\nsupseteq ICrs_{\alpha}^{rc}\supseteq ICrs_{\alpha}^{rcd}\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 **{**Cs_{2},Crs_{2}^{rc},Crs_{2}^{rcd}**}**. 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_{\alpha}^{rcd} is 7 if \alpha = 2 and 2^{\omega} if 2 < \alpha < \omega. The number of non-isomorphic 1-generated Crs_{\alpha}^{rs}-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