Sets of natural numbers of positive density and cylindric set algebras of dimension 2 (Q1158424)

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 \textit{L.Henkin, J.D.Monk, A.Tarski, H.Andréka} and \textit{I. Németi} Cylindric set algebras, Lect. Notes Math. 883 (1981; Zbl 0497.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}\mathcal A\) is said to be rectangular if its unit \(1^{\mathcal A}\) is a Cartesian product, that is if \(1^{\mathcal A}=P_{i\in I}^{\alpha}W_i\) for some function \(W=\langle W_i:i\in I\rangle\). We let \(Crs_{\alpha}^{rc} := \{\mathcal A\in Crs_{\alpha}:\mathcal A\) is rectangular\}. A \(Crs_{\alpha}:\mathcal A\) is said to be disjointly rectangular if \(1^{\mathcal A}=P_{i\in I}W_i\) for some function \(\langle W_i:i\in I\rangle\) such that \((\forall i,j\in I)[i\neq j\Rightarrow W_i\cap W_j=0]\). We let \(Crs_{\alpha}^{rcd} := \{\mathcal A\in Crs_{\alpha}^{rc}:\mathcal 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 \textit{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 0502.68024)], see Thm. 24 on p. 599 there. To see the above, observe that \(Crs_{\alpha}^{rc}\models\forall x[(\Delta x=0)\to(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}\cap\text{Mod}(Th)=Cs_{\alpha}\). By 6.5(ii) of HMTAN o.228, \(ICs\) is not closed under direct squares. I.e. \(\exists\mathcal A\in Cs_{\alpha})^2\mathcal A\not\in ICs_{\alpha}\). Then \(\mathcal A\in Crs_{\alpha}^{rc}\) while \(^2\mathcal A\not\in ICrs_{\alpha}^{rc}\) for this \(\mathcal 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}\mathcal A\) and an ultrapower \(\mathcal B\) of \(\mathcal A\) with \(\mathcal B\not\in ICs_{\alpha}\). But since \(\mathcal B\models Th\), by (*), the assumption \(\mathcal B\in ICrs_{\alpha}^{rc}\) would imply \(\mathcal 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 \(\mathcal L\in_\omega K\) not embeddable into any finitely generated member of \(K\). Further, to each finitely generated \(\mathcal A\subseteq\mathcal L\) there is a 2-generated \(\mathcal B\subseteq\mathcal S1^{\mathcal L}\) such that \(\mathcal A\subseteq\mathcal 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\to\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\to\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\cdot\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 \textit{H. Andréka} and \textit{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 0542.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 \dots algebra [Universal algebra, Colloq. Math. Soc. J. Bolyai Vol. 29, 95-106(1981)].