7_340_ahmed.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 5, 2010, 853-880 ISSN 1307-5543 – www.ejpam.com On Neat Reducts of Cylindric Algebras Tarek Sayed Ahmed Department of Mathematics, Faculty of Science,Cairo University, Giza, Egypt. Abstract. Let 1 < n < m ≤ω. We investigate the following question: For which reducts of CAm is the class of neat n - reducts (not) elementary. We also characterize the class of neat reducts using games. 2000 Mathematics Subject Classifications: Primary 03G15, Secondary 03C05, 03C40 Key Words and Phrases: Algebraic logic, cylindric algebras, neat reducts 1. The Class of Neat Reducts Neat reducts have been a central notion in algebraic logic since the very beginning, and the notion is still a versatile active field of research, [see e.g 18, 21, 34, 31, 43, 24, 45, 41, 42, 30, 33]. Indeed, the consecutive problems 2.11, 2.12, 2.13 in the monograph [11] are on neat reducts. Problem 2.12 is solved by Hirsch Hodkinson and Maddux [10]. The authors of [10] show that the sequence 〈SNrnCAn+k : k ∈ ω〉 is strictly decreasing for ω > n > 2 with respect to inclusion. (Recall that we generalized this result to quasipolyadic equality algebras). The infinite dimensional case is settled by Pigozzi as reported in [11]. The main result in [10] strengthes Monk’s classical result that for every finite n > 2 and any k ∈ ω, RCAn ⊂ SNrnCAn+k. Taking Ak ∈ SNrnCAn+k ∼ RCAn, and forming the ultraproduct ∏ Ak/F relative to a non-principal ultrafilter on ω, the resulting structure will be representable, showing that RCAn, though, elementary (indeed a variety) is not finitely axiomatizable. Problem 2.13 is solved in [41]. Problem 2.11 which is relevant to our later discussion asks: For which pair of ordinals α < β is the class NrαCAβ closed under forming subalgebras and homomorphic images? Németi proves that for any 1 < α < β the class NrαCAβ though closed under forming homomorphic images and products is not a variety, i.e., it is not closed under forming subalgebras [14]. The next natural question is whether this class is elementary, and in this particular case, since the class of neat reducts is closed under ultraproducts, this amounts to asking whether it is closed under elementary subalgebras? In [18] it is proved that for any 1 < α < β , the class NrαCAβ is not elementary answering problem 4.4 in [12]. In [30], it is shown that this class cannot be characterized by any L∞ω sentence. We know that NrnCAω Email address: rutahmed�gmail. om http://www.ejpam.com 853 c© 2010 EJPAM All rights reserved. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 854 is closed under products and homomorphic images, thus under ultraproducts. However, for n > 1, it is not closed under elementary subalgebras, equivalently, under ultraroots. (For n ≤ 1,NrnCAω = RCAn = CAn; so this is a degenerate case which we ignore). For a class K , E LK denotes the elementary closure of K , that is the least elementary class containing K . UpK denotes the class of all ultraproducts of members of K and UrK denotes the class of all ultraroots of members of K . Recall that, by the celebrated Shelah - Keisler theorem, ElK = UpUrK . Theorem 1. Let n > 1. Then the class NrnCAω is pseudo-elementary, but is not elementary. Furthermore, ElNrnCAω ⊂ RCAn, E LNrnCAω is recursively enumerable, and for n > 2 is not finitely axiomatizable. Proof. The class NrnCAω is not elementary [18]. To show that it is pseudo-elementary, we use a three sorted defining theory, with one sort for a cylindric algebra of dimension n(c), the second sort for the Boolean reduct of a cylindric algebra (b) and the third sort for a set of dimensions (δ). We use superscripts n, b,δ for variables and functions to indicate that the variable, or the returned value of the function, is of the sort of the cylindric algebra of dimension n, the Boolean part of the cylindric algebra or the dimension set, respectively. The signature includes dimension sort constants iδ for each i < ω to represent the dimensions. The defining theory for NrnCAω incudes sentences demanding that the constants iδ for i <ω are distinct and that the last two sorts define a cylindric algebra of dimension ω. For example the sentence ∀xδ, yδ, zδ(d b(xδ, yδ) = cb(zδ, d b(xδ, zδ).d b(zδ, yδ))) represents the cylindric algebra axiom di j = ck(dik.dk j) for all i, j, k < ω. We have have a function I b from sort c to sort b and sentences requiring that I b be injective and to respect the n dimensional cylindric operations as follows: for all x r I b(di j) = d b(iδ, jδ) I b(ci x r) = cb i (I b(x)). Finally we require that I b maps onto the set of n dimensional elements ∀y b((∀zδ(zδ 6= 0δ, . . . (n− 1)δ→ cb(zδ, y b) = y b))↔∃x r(y b = I b(x r))). For A ∈ CAn, Rd3A denotes the CA3 obtained from A by discarding all operations indexed by indices in n ∼ 3. Dfn denotes the class of diagonal free cylindric algebras. Rdd f A denotes the Dfn obtained from A by deleting all diagonal elements. To prove the non-finite axiomati- zability result we use Monk’s algebras. For 3 ≤ n, i < ω, with n− 1 ≤ i,Cn,i denotes the CAn associated with the cylindric atom structure as defined on p. 95 of [11]. Then by [11, 3.2.79] for 3≤ n, and j <ω, Rd3Cn,n+ j can be neatly embedded in a CA3+ j+1. (1) By [11, 3.2.84]) we have for every j ∈ω, there is an 3≤ n such that Rdd f Rd3C n,n+ j is a non-representable Df3. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 855 (2) Now suppose m ∈ ω. By (2), choose j ∈ ω ∼ 3 so that Rdd f Rd3C j, j+m+n−4 is a non-representable Df3. By (1) we have Rdd f Rd3C j, j+m+n−4 ⊆Nr3Bm, for some B ∈ CAn+m. Put Am = NrnBm. Rdd f Am is not representable, a friotri, Am /∈ RCAn, for else its Df reduct would be representable. Therefore Am /∈ E LNrnCAω. Now let Cm be an algebra similar to CAω’s such that Bm = Rdn+mCm. Then Am = NrnCm. Let F be a non-principal ultrafilter on ω. Then ∏ m∈ω Am/F = ∏ m∈ω (NrnCm)/F =Nrn( ∏ m∈ω Cm/F) But ∏ m∈ωCm/F ∈ CAω. Hence CAn ∼ ElNrnCAω is not closed under ultraproducts. It follows that the latter class is not finitely axiomatizable. In [18] it is proved that for 1 < α < β , ElNrαCAβ ⊂ SNrαCAβ . From the above proof it follows that Corollary 1. Let K be any class such that NrnCAω ⊆ K ⊆ RCAn. Then E LK is not finitely axiomatizable For n> 2 the addition of finitely many first order definable operations does not remedy the non-finite axiomatizability result for RCAn, as proved by Biro. First order definable operations are those operations that can be defined using spare dimensions, and hence the notion of neat reducts are appropriate for handing them. A non-trivial question that involves the class NrnCAω in an essential way, is whether we can expand the signature of cylindric algebras by extra natural operations on n-ary relations so that if A ∈ Csn and is closed under these opera- tions then this forces A to be in the class NrnCAω. (For example, the polyadic operations are not enough.) The class NrnCAω contains all first order definable operations, so the question can be reformulated as to whether one can capture all first order definable operations using a finite set of operations. This is strongly related to the Finitizability Problem [48] in algebraic logic. Next we characterize the class NrnCAω using games. Since games go deeper into the analysis, they could shed light on the possible choice of such operations. For that, we need some preparations. We use “cylindric algebra” games that are analogues to certain “relation algebra” games used by Robin Hirsch in [7]. In [7] Robin Hirsch studies quite extensively the class RaCAn of relation algebra reducts of cylindric algebras of dimension n. This class was studied by many authors, to mention a few, Maddux, Simon and Nemeti. References for their work can be found in the most recent reference [7]. Our treatment in this part follows very closely [7]. Definition 1. Let n be an ordinal. An s word is a finite string of substitutions (s j i ), a c word is a finite string of cylindrifications (ck). An sc word is a finite string of substitutions and cylindrifi- cations Any sc word w induces a partial map ŵ : n→ n by • ε̂ = Id • cw i j = ŵ ◦ [i| j] • dwci = ŵ ↾ (n∼ {i} T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 856 If ā ∈ n. Let C ∈ CAm and let A ⊆Nrn(C) be atomic. Let N be a network over A and i, j < n. 1. If i 6∈ nodes(N) then ci bN = bN. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 859 2.ØN Id− j ≥ bN. 3. If i 6∈ nodes(N) and j ∈ nodes(N) then bN 6= 0→ÙN[i/ j] 6= 0. where N[i/ j] = N ◦ [i| j] 4. If θ is any partial, finite map n→ n and if nodes(N) is a proper subset of n, then bN 6= 0→dNθ 6= 0. Proof. The first part is easy. The second part is by definition of b. For the third part suppose bN 6= 0. Since i 6∈ nodes(N), by part 1, we have ci bN = bN . By cylindric algebra axioms it follows that bN . di j 6= 0. By lemma 2 there is a network M where nodes(M) = nodes(N)∪ {i} such that bM .bN . di j 6= 0. By lemma 2 we have M ⊇ N and M(i, j) ≤ 1′. It follows that M = N[i/ j]. HenceÙN[i/ j] 6= 0. For the final part (cf. [9, lemma 13.29]), since there is k ∈ n \ nodes(N), θ can be expressed as a product σ0σ1 . . .σt of maps such that, for s ≤ t, we have either σs = Id−i for some i < n or σs = [i/ j] for some i, j < n and where i 6∈ nodes(Nσ0 . . .σs−1). Now apply the previous parts of the lemma. We now prove two Theorems relating neat embeddings to the games we defined: Theorem 2. Let n < m, and let A be a CAm. If A ∈ ScNrnCAm, then ∃ has a winning strategy in F m(AtA). Proof. If A ⊆ NrnC for some C ∈ CAm then ∃ always plays hypernetworks N with nodes(N) ⊆ n such that bN 6= 0. In more detail, in the initial round , let ∀ play a ∈ AtA . ∃ play a network N with N(0, . . . n− 1) = a. Then bN = a 6= 0. At a later stage suppose ∀ plays the cylindrifier move (N , 〈 f0, . . . fµ−2〉, k, b, l) by picking a previously played hypernet- work N and fi ∈ nodes(N), l < µ, k /∈ { fi : i < n − 2}, and b ≤ clN( f0, . . . fi−1, x , fn−2). Let ā = 〈 f0 . . . fl−1, k . . . fn−2〉. Then ck bN · sā b 6= 0. By 1 there is a network M such that bM .ÔckN · sā b 6= 0. Hence M( f0, k, fn−2) = b. Theorem 3. Let α be a countable CAn atom structure. If ∃ has a winning strategy in Hn(α) then there is a representable cylindric algebra C of dimension ω such that NrnC is atomic and AtNrnC ∼= α. Proof. Suppose ∃ has a winning strategy in H(α). Fix some a ∈ α. We can define a nested sequence N0 ⊆ N1 . . . of hypernetworks where N0 is ∃’s response to the initial ∀-move a, requiring that 1. If Nr is in the sequence and and b ≤ clNr(〈 f0, fn−2〉 . . . , x , fn−2). then there is s ≥ r and d ∈ nodes(Ns) such that Ns( f0, fi−1, d , fn−2) = b. 2. If Nr is in the sequence and θ is any partial isomorphism of Nr then there is s ≥ r and a partial isomorphism θ+ of Ns extending θ such that rng(θ+)⊇ nodes(Nr). Since α is countable there are countably many requirements to extend. Since the sequence of networks is nested , these requirements to extend remain in all subsequent rounds. So that we can schedule these requirements to extend so that eventually, every requirement gets T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 860 dealt with. If we are required to find k and Nr+1 ⊃ Nr such that Nr+1( f0, k, fn−2) = b then let k ∈ω \nodes(Nr) be least possible for definiteness, and let Nr+1 be ∃’s response using her winning strategy, to the ∀move Nr , ( f0, . . . fn−1), k, b, l). For an extension of type 2, let τ be a partial isomorphism of Nr and let θ be any finite surjection onto a partial isomorphism of Nr such that dom(θ) ∩ nodes(Nr) = domτ. ∃’s response to ∀’s move (Nr ,θ) is necessarily Nθ . Let Nr+1 be her response , using her wining strategy, to the subsequent ∀move (Nr , Nrθ). Now let Na be the limit of this sequence. This limit is well-defined since the hypernetworks are nested. Note, for b ∈ α, that (∃i0, . . . Iµ−1 ∈ nodes(Na), Na(i0 . . . , iµ−1) = b) ⇐⇒ b ∼ a (1) Let θ be any finite partial isomorphism of Na and let X be any finite subset of nodes(Na). Since θ , X are finite, there is i < ω such that nodes(Ni) ⊇ X ∪ dom(θ). There is a bijection θ+ ⊇ θ onto nodes(Ni) and j ≥ i such that N j ⊇ Ni, Niθ +. Then θ+ is a partial isomorphism of N j and rng(θ+) = nodes(Ni) ⊇ X . Hence, if θ is any finite partial isomorphism of Na and X is any finite subset of nodes(Na) then ∃ a partial isomorphism θ+ ⊇ θ of Na where rng(θ+)⊇ X (2) and by considering its inverse we can extend a partial isomorphism so as to include an ar- bitrary finite subset of nodes(Na) within its domain. Let L be the signature with one µ -ary predicate symbol (b) for each b ∈ α, and one k-ary predicate symbol (λ) for each k-ary hy- perlabel λ. [Notational point: if λ is k-ary and l-ary for k 6= l then make one k-ary predicate symbol λ and one l-ary predicate symbol λ′, so that every predicate symbol has a unique arity.] The set of variables for L-formulas is {x i : i < ω}. We also have equality. Pick fa ∈ ωnodes(Na). Let Ua = { f ∈ ωnodes(Na) : {i < ω : g(i) 6= fa(i)} is finite}. We can make Ua into the base of an L-structure Na and evaluate L-formulas at f ∈ Ua as follow. For b ∈ α, l0, . . . lµ−1, i0 . . . , ik−1 <ω, k-ary hyperlabels λ, and all L-formulas φ,ψ, let Na, f |= b(x l0 . . . xn−1) ⇐⇒ Na( f (l0), . . . f (ln−1)) = b Na, f |= λ(x i0 , . . . , x ik−1 ) ⇐⇒ Na( f (i0), . . . , f (ik−1)) = λ Na, f |= ¬φ ⇐⇒ Na, f 6|= φ Na, f |= (φ ∨ψ) ⇐⇒ Na, f |= φ or Na, f |=ψ Na, f |= ∃x iφ ⇐⇒ Na, f [i/m] |= φ, some m ∈ nodes(Na) For any L-formula φ, write φNa for { f ∈ ωnodes(Na) : Na, f |= φ}. Let FormNa = {φNa : φ is an L-formula} and define a cylindric algebra Da = (FormNa ,∪,∼,Di j ,Ci , i, j <ω) where Di j = (x i = x j) Na , Ci(φ Na ) = (∃x iφ) Na . Observe that ⊤Na = Ua, (φ ∨ ψ)Na = φNa ∪ψNa , etc. Note also that D is a subalgebra of the ω-dimensional cylindric set algebra on the base nodes(Na), hence D ∈ RCAω. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 861 Let φ(x i0 , x i1 , . . . , x ik ) be an arbitrary L-formula using only variables belonging to {x i0 , . . . , x ik }. Let f , g ∈ Ua (some a ∈ α) and suppose is a partial isomorphism of Na. We can prove by induction over the quantifier depth of φ and using (2), that Na, f |= φ ⇐⇒ Na, g |= φ (3) Let C = ∏ a∈α Da. Then C ∈ RCAω. An element x of C has the form (xa : a ∈ α), where xa ∈ Da. For b ∈ α let πb : C → Db be the projection defined by πb(xa : a ∈ α) = xb. Conversely, let ιa : Da →C be the embedding defined by ιa(y) = (xb : b ∈ α), where xa = y and xb = 0 for b 6= a. Evidently πb(ιb(y)) = y for y ∈ Db and πb(ιa(y)) = 0 if a 6= b. Suppose x ∈NrµC \{0}. Since x 6= 0, it must have a non-zero component πa(x) ∈ Da, for some a ∈ α. Say ; 6= φ(x i0 , . . . , x ik )Da = πa(x) for some L-formula φ(x i0 , . . . , x ik ). We have φ(x i0 , . . . , x ik )Da ∈NrµDa). Pick f ∈ φ(x i0 , . . . , x ik )Da and let b = Na( f (0), f (1), . . . fn−1) ∈ α. We will show that b(x0, x1, . . . xn−1) Da ⊆ φ(x i0 , . . . , x ik )Da . Take any g ∈ b(x0, x1 . . . xn−1) Da , so Na(g(0), g(1) . . . g(n−1)) = b. The map {( f (0), g(0)), ( f (1), g(1)) . . . ( f (n−1), g(n−1))} is a partial isomorphism of Na. By (2) this extends to a finite partial isomorphism θ of Na whose domain includes f (i0), . . . , f (ik). Let g′ ∈ Ua be defined by g′(i) = ¨ θ(i) if i ∈ dom(θ) g(i) otherwise By (3), Na, g′ |= φ(x i0 , . . . , x ik ). Observe that g′(0) = θ(0) = g(0) and similarly g′(n − 1) = g(n − 1), so g is identical to g′ over µ and it differs from g′ on only a finite set of coordinates. Since φ(x i0 , . . . , x ik ) Da ∈ Nrµ(C ) we deduce Na, g |= φ(x i0 , . . . , x ik ), so g ∈ φ(x i0 , . . . , x ik )Da . This proves that b(x0, x1 . . . xµ−1) Da ⊆ φ(x i0 , . . . , x ik )Da = πa(x), and so ιa(b(x0, x1, . . . xn−1) Da)≤ ιa(φ(x i0 , . . . , x ik )Da)≤ x ∈ C \ {0}. Hence every non-zero element x of NrnC is above a non-zero element ιa(b(x0, x1 . . . n1) Da) (some a, b ∈ α) and these latter elements are the atoms of NrnC . So NrnC is atomic and α∼= AtNrnC — the isomorphism is b 7→ (b(x0, x1, . . . xn−1) Da : a ∈ A). In [36], we use such games to show that for n ≥ 3, there is a representable A ∈ CAn with atom structure α such that ∀ can win the game F n+2(α). However ∃ has a winning strategy in Hn(α), for any n < ω. It will follow that there a countable cylindric algebra A ′ such that A ′ ≡ A and ∃ has a winning strategy in H(A ′). So let K be any class such that NrnCAω ⊆ K ⊆ ScNrnCAn+2. A ′ must belong to Nrn(RCAω), henceA ′ ∈ K . ButA 6∈ K and A � A ′. Thus K is not elementary. From this it easily follows that the class of completely representable cylindric algebras is not elementary, and that the class NrnCAn+k for any k ≥ 0 is not elementary either. Furthermore the constructions works for many variants of cylindric algebras like Halmos’ polyadic equality algebras and Pinter’s substitution algebras. Theorem 4. Let 3≤ n<ω. Then the following hold: (i) Any K such that NrnCAω ⊆ K ⊆ ScNrnCAn+2 is not elementary. (ii) The inclusions NrnCAω ⊆ ScNrnCAω ⊆ SNrnCAω are all proper Proof. (i) is already mentioned. While for (ii), for the first inclusion [18], and for the second [8]. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 862 2. Other algebras Now we turn our attention for other algebras for which the notion of neat reducts make sense. SCn,CAn,QAn and QEAn abbreviate the classes of substitution, cylindric, quasipolyadic, and quasipolyadic equality algebras, of dimension n, respectively. Such algebras are studied in e.g. [45, 34, 21, 22, 24, 2, 15, 29, 33]. Dfn stands for the class of diagonal free cylindric algebras. It is known, and indeed easy to show, that for 1 < n < m, the class NrnDfm of neat n-reducts of Dfm is a variety. In fact, it is equal to Dfn [12][5.1.2]. In particular, it is an elementary class. On the other hand, it is known [18] that for 1 < n < m the class NrnCAm is not an elementary class. It is also known [29], [34] that NrnQAm and NrnQEAm are not elementary classes. It is proved in Op.cit that such classes are not closed under ultraroots. So what about reducts, i.e algebras “in between” Df and CA. By “in between” we mean a class Km that is a reduct of CAm and an expansion of Dfm. A typical example is the class SCm [15]. We define another reduct rSCm (class of algebras of dimension m) which is a (proper) reduct of SCm, which in turn is a reduct of CAm, QAm QEAm. Definition 5. Let m be an ordinal. A ∈ rSCm, is defined to be an algebra A = 〈A,+, .,−0,1,ci , s j i 〉i, j∈m obeying the following axioms for x , y ∈ A and i, j, k, l < m: (E0) 〈A,+, .,−, 0,1〉 is a boolean algebra (E1) c j0= 0, x ≤ ci x, ci(xci y) = ci x .ci y, and cic j x = c jci x, and si i x = x In other words the cis are complemented closure operators and ci,c j commute. (E2) s i i x = x (E3) s i j are boolean endomorphisms. (E4) s i j ci x = ci x (E5) cis i j x = si j x whenever i 6= j (E6) s i j ck x = cks i j x, whenever k /∈ {i, j} (E7) cis j i x = c js i j x (E8) s i j sk i ci x = sk j ci x (E9) s j i sl k x = sl k s j i x when |{i, j, k, l}| = 4 Definition 6. (i) Let n < m be ordinals. Let B ∈ rSCm Then the neat n-reduct of B, in symbols NrnB is the rSCn with universe N rnB = {b ∈ B : ci b = b for all n≤ i < m}, and whose operations are those of the similarity type of SCm (evaluated in B and) restricted to N rnB. (ii) For a given class M ⊆ rSCm, we let NrnM denote the class obtained by forming the neat n-reduct of algebras in M, that is NrnM = {NrnB : B ∈M}. The definition of neat reducts for SCm is the same. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 863 We now prove: Theorem 5. Let 1< n and n+ 1< m≤ω. Then NrnrSCm and NrnSCm are not elementary. We do not know whether NrnŁn+1 for Ł ∈ {SC, rSC} is elementary or not. But why is it of interest to settle such questions on neat reducts. There are (at least) three possible answers to this question. First there are aesthetic reasons. Motivated by intellectual curiosity, the inves- tigation of such questions is likely to lead to nice mathematics. The second reason concerns definability or classification. Now that we have the class of neat reducts in front of us, the most pressing need is to try to classify it. Classifying is a kind of defining. Most mathematical classification is by axioms (preferably first order) or, even better, equations (if the class in question is a variety.) It is known (and indeed not difficult to show) that the class NrnCAm is closed under products and homomorphic images for all n< m [45]. However, it is not closed under forming (elementary) subalgebras [18], that is, it is not axiomatizable, a priori not a variety. Studying neat reducts of reducts of CA’s and for that matter expansions [34], [29], clarifies the properties of neat reducts. (This is similar to the situation with representabil- ity [15] where axiomatizations of representable algebras are better understood by passing to reducts or expansions.) Now we come to the third reason, where neat reducts are not treated on its own but rather in its interaction with algebraic properties like representability, amalga- mation and complete representations. This in turn is related to completeness, interpolation and omittting types for variants of first order logic, be it reducts or expansions [24, 22], [33]. Indeed the old but venerable notion of neat reducts has turned to be central notion in the theory of cylindric like algebras of relations, [23, 32, 30, 16]. We shall need the following Lemma on substitutions: Lemma 4. For any k, l,u < n and A ∈ rSCn, set us(k, l)x = su k sk l s l u x . Then (i) If k, l,u and v are distinct, then us(k, l)cucv x = us(l, k)cucv x (ii) With the same condition in (i), we have us(k, l)us(k, l)cucv x = cucv x . The proof is tedious, but fairly straight forward. We use the axiomatization (E1 − E9). Proof. sl us u k sk l sl ucucv x = (by E8) sl us u k sk l sv us l vcvcu x = (by E9 )sl us u ks v us k l s l vcucv x (by E6) = sl us u ks v us k l cus l vcv x (by E6) = sl us u ks v ucus k l s l vcv x = (by E8) sl us v kcus k l s l vcucv x . T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 864 Now sl us v kcus k l s l vcucv x( by E8 ) = sl us v ks k l s l vcucv x = ( by E9) sv ks l us k l s l vcucv x = ( by E5 )sv ks l us k l cls l vcucv x = (by E8) sv ks k ucls l vcucv x = (by E5 )sv ks k us l vcucv x (by E9) = sv ks l vs k ucucv x = ( by E6 ) sv ks l vcvs k ucu x = ( by E8 )sl ks k ucucv x . We have proved that sl us u k sk l s l ucucv x = sl k sk ucucv x . Now we apply su l to both sides, we obtain, the right hand side is equal to su l sl us u k sk l sl ucucv x = ( by E5 )su l sl ucus u k sk l sl ucucv x = (by E8) sl l cus u k sk l sl ucucv x = (by E5) su k sk l sl ucucv x = us(k, l)cucv x And by definition the left hand side is equal to us(l, k)cucv x . We have proved (i). We now prove (ii). From (i) we have us(k, l)us(k, l)cucv x =u s(l, k)us(k, l)cucv x = ( by definition ) su l sl k sk us u k sk l s l ucucv x = ( by E5 ) su l sl k sk us u k cks k l s l ucucv x = (by E8 ) su l s l ks u ucks k l s l ucucv x = ( by E2 ) su l s l kcks k l s l ucucv x = ( by E5 ) su l s l ks k l s l ucucv x = (by E5 ) su l s l ks k l cls l ucucv x = ( by E8 ) su l s k kcls l ucucv x = ( by E8 ) su l s l ucucv x = ( by E8 ) sl lcucv x = ( by E2 ) cucv x . (i) and (ii) are sometimes called the merry-go-round identities [12]. Since our proof is model theoretic, we recall some notions and concepts from Model Theory. A good reference is [6]. (Our treatment will be self contained.) 3. Some Model-theoretic preparations Definition 7. Let L be a signature. By an unnested atomic formula of signature L we mean an atomic formula of one of the following forms: x = y, c = y, F( x̄) = y and R( x̄) where c is a constant, F is a function symbol and R is a relation symbol. Definition 8. Let L and K be signatures, A a K structure B an L structure and n a positive integer. An n dimensional interpretation Γ of B in A is defined to consist of (1) a formula ∂Γ(x0, . . . xn−1) of signature K, T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 865 (2) for each unnested atomic formula φΓ( ȳ0, . . . ȳm−1) a formula φΓ( x̄0, . . . x̄m−1) of signature K in which the x i ’s are disjoint n tuples of distinct variables, (3) a surjective map fΓ : ∂Γ( nA)→ dom(B), such that for all unnested atomic formula φ of L and āi ∈ ∂Γ( nA) B |= φ( fΓ ā0, . . . fΓam−1)←→ A |= φ(ā0, . . . ¯am−1). The formula ∂Γ is the domain formula of Γ; the formula ∂Γ and φT for all unnested atomic formula φ are the defining formulas of Γ. If Γ is an interpretation of an L structure B in a K structure A , then there are certain sequences of signature K which must be true in A just becuase Γ is an interpretation, regardless of what A and B are. These sentences say: (i) Let =Γ be φΓ when φ is y0 = y1. Then =Γ is an equivalence relation. (ii) for each unnested atomic formula φ of L, if A |= φΓ(ā0, . . . ¯an−1) where ā0, . . . ¯an−1 ∈ ∂ n Γ A, then also A |= φΓ( b̄0 . . . ¯bn−1) where each b̄i is an element of ∂Γ( nA) which is = Γ equivalent to āi. (iii) if φ(y0) is a formula of L of the form c = y0, then there is an ā in ∂Γ( nA)such that for all b̄ in ∂Γ( nA), A |= φΓ b̄ if b̄ is =Γ equivalent to ā. (iv) a clause like (iii) for each function symbol. For a signature L, L∞ω denotes the extension of the first order language of L by infinitary conjunctions and disjunctions. The following Lemma is more general than what we need (however the proof is the same): Lemma 5. Let A be a K structure, B an L structure and Γ an n interpretation of B in A. Then for every formula φ( ȳ) of the language L∞ω there is a formula φΓ(x) of the language K∞ω such that B |= φ( fΓ ā)←→ A |= φΓ(ā) Proof. Every formula of L∞ω is equivalent to a formula in which all atomic subformulas are nested. We prove the theorem by induction on complexity of formulas, and Definition 6 takes care for the atomic formulas. For compound formulas, we define: (¬φ)Γ = ¬(φΓ), ( ∧ φi)Γ = ∧ (φi)Γ and likewise with ∨ (∃yφ)Γ = ∃x0 . . . xn−1(∂Γ(x0, . . . , xn−1)∧φΓ). We need to show that elementary equivalence is preserved by taking products. For this purpose we devise a game between ∀ (male) and ∃(female). We imagine that ∀wants to prove that A is different from B while ∃ tries to show that A is the same as B. So their conversation has the form of a game. Player ∀ wins if he manages to find a difference between A and B T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 866 before the play is over; otherwise ∃ wins. The game is played in µ≤ω steps. At the ith step of a play, player ∀ takes one of the structures A, B and chooses an element this structure; then ∃ chooses an atom of the other structure. So between them they choose an element ai of A and an element bi of B. Apart from the fact that player ∃ must choose from the other structure from player ∀ at each step, both players have complete freedom to choose as they please; in particular, either player can choose an element which was chosen at an earlier step. Player ∃ is allowed to see and remember all previous moves in the play. (As the game theorists would say, this is a game of perfect information.) At the end of the play sequences ā = (ai : i < µ) and b̄ = (bi : i < µ) have been chosen. The pair (ā, b̄) is known as the play. We count the play (ā, b̄) as a win for player ∃, and we say that ∃ wins the play, if for every unnested atomic formula φ of L A |= φ(ā)←→B |= φ( b̄) Let us denote this game by EFµ(A,B). (It is an instance of an Ehrenfeuch-Fraisse game.) The more A is like B, the better chance player ∃ has of winning these games. For example if player ∃ knows about an isomorphism i : A→B then she can be sure of winning every time. All she has to do to follow the rule is: Choose i(a) whenever player ∀ has just chosen an element a of A and i−1(b) whenever player ∀ has just chosen b from B. We write A ∼k B if ∃ can win EFk(A,B). Lemma 6. Let L be a first order language with finite signature. Then for any two L structures A and B the following are equivalent (i) A ≡B (ii) A ∼k B for all k <ω. Proof. [Sketch] A and B agree on all unnested sentences of finite quantifier rank, so (i) implies (ii). The other direction follows from the fact that every first order sentence is equivalent to an unnested sentence of finite quantifier rank. A strategy for a player in a game is a set of rules which tell the player exactly how to move, depending on what has happened earlier in the play. We say that the player uses the strategy σ in a play if each of his or her moves obeys the rules of σ. We say that σ is a winning strategy if the player wins every play in which he or she uses σ. We now have Lemma 7. Let B1, B2 and B be boolean algebras. Assume that B1 ≡ B2, then B1 ×B ≡ B2 ×B. Proof. It suffices to show that if k < ω and B1 ∼k B2 then B1 ×B ∼k B2 ×B. Assume henceforth that B1 ∼k B2. Then ∃ has a winning strategy σ for the game EFk(B1,B2). Let the two players play the game EFk(B1 ×B,B2 ×B). ∃ guides her choices by the side game EFk(B1,B2). Whenever ∀ offers an element, say the element a ∈ B1 × B, player ∃ first splits it into a product a = (g,h) with g ∈ B1 and h ∈ B. Then she pretends that ∀ has chosen g in the side game. She uses her strategy σ to choose a reply g′ of g in the side game. Her reply to the element a will be the element b = (g′,h) ∈ B2 × B. At the end of the game T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 867 let the play be ((g0,h0), . . . (gk−1,hk−1); (g ′ 0,h′0), . . . (g ′ k−1 ,h′ k−1 )). Player ∃ has won the side game. Now the unnested atomic formulas of boolean algebras are of the form x = y, 1 = x , 0= x , x0 ∧ x1 = y, x0 ∨ x1 = y and −x = y. So for i, j, l < k we have gi = g j iff g′i = g′j 1= gi iff 1= g′i 0= gi iff 0= g′i gi ∧ g j = gl iff g′i ∧ g′j = g′l gi ∨ gi = gl iff g′i ∧ g′j = g′ l −gi = g j iff − g′i = g′j . By the cartesian product for boolean algebras , this implies that for all i, j, l < k we also have (gi,hi) = (g j,h j) iff (g′i ,hi) = (g ′ j,hi) 1= (gi,hi) iff 1= (g′i ,hi) same for 0 0= (gi,hi) iff 0= (g′i ,hi) (gi ∧ hi , g j ∧ h j) = (gl ,hl) iff (g′i ∧ hi, g′j ∧ h j) = (g ′ l ,hl) (gi ∨ hi , g j ∨ h j) = (gl ,hl) iff (g′i ∨ hi, g′j ∨ h j) = (g ′ l ,hl) −(gi,hi) = (g j,h j) iff − (g′i ,hi) = (g ′ j,h j). So ∃ wins the game, which proves the lemma.. Definition 9. (1) Let L be a signature and D an L structure. The age of D is the class K of all finitely generated structures that can be embedded in D. (2) A class K is the age of D if the structures in K are up to isomorphism, exactly the finitely generated substructures of D. (3) Let K be a class of structures. (4) K has the Hereditary Property, HP for short. if whenever A ∈ K and B is a finitely generated substructure of A then B is isomorphic to some structure in K. (5) K has the Joint Embedding Property, J EP for short if whenever A,B ∈ K then there is a C ∈ K such that both A and B are embeddable in C. (6) K has Amalgamation Property, or AP for short if A,B,C ∈ K and e : A→ B, f : A→ C are embeddings, then there are D in K and embeddings g : B→ D and h : C → D such that g ◦ e = h ◦ f . T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 868 (7) A structure D is weakly homogeneous if it has the the following property if A, B are finitely generated substructures of D, A⊆ B and f : A→D is an embedding, then there is an embedding g : B→D which extends f . (8) We call a structure D homogeneous if every isomorphism between finitely generated sub- structures extends to an automorphism of D. Note that if D is homogeneous, then it is weakly homogeneous. We recall from [6] Thm 7.1.2, a theorem of Fraisse that puts the above pieces together. Theorem 6. Let L be a countable signature and let K be a non-empty finite or countable set of finitely generated L-structures which has HP, J EP and AP. Then there is an L structure D, unique up to isomorphism, such that (1) D has cardinality ≤ω (2) K is the age of D, and (3) D is homogeneous. Following Hodges [6] we also refer to D is as Fraisse limit of the class K. Our next theorem, gives a sufficient condition for when the Fraisse limit D of a class K of finitely generated structures, has quantifier elimination. Recall that an L-structure M has quantifier elimination if every L formula φ( x̄) is equivalent in M to a boolean combination of quantifier free formulas, equivalently atomic formulas. A theory T is ω- categorical if all countable models of T are isomorphic. Lemma 8. Suppose that the signature L is finite and has no function symbols. Suppose that K is a countable set of finite L structures with HP, J EP and AP. Let M be the Fraisse limit of K. Let T be the first order theory Th(M) of M. Then (i) T is ω-categorial. (ii) M has quantifier elimination Proof. The proof is taken from [6]. We include it for the sake of completeness. We note that the following hold: If A is any finite L structure with n generators ā, then there is a quantifier free formula ψA,ā(x0 . . . xn−1) such that for any L structure B and n-tuple b̄ of elements of B, (1) B |= φ[ b̄] if and only if there is an isomorphism from A to 〈b〉B which takes ā to b̄. In fact ψA,ā is a conjunction of literals satisfied by ā in A. Also or each n<ω there are only finitely many isomorphism types of structures in K with n generators. Let U0 be the set of all sentences of the form (∀ x̄)(ψA,ā( x̄) =⇒ ∃yψB,āb( x̄ , y)) (4) T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 869 where B is a structure in K generated by a tuple ā b of distinct elements, and A is the sub- structure generated by ā. let U1 be the set of sentences of the form (∀x) ∨ ψA,ā( x̄) (5) where the disjunction is over all pairs A, ā such that A ∈ K and ā is a tuple of the same length as x̄ which generates A. Then this is a finite disjunction. Let U = U0 ∪U1. Then M is a model of U . Suppose that D is any countable model of U . Then the sentences (1) say that if (4) A, B are finitely generated substructures of D A⊆ B, B comes from A by adding one more generator, and f : A → D is an embedding , then there is an embedding g : B → D which extends f . Using induction on the number of generators, imply that every structure in K is embeddable in D; so together with (3) this implies that the age of D is exactly K. Using (2) an induction on the size of dom(B) \ dom(A), tells us that D is weakly homogeneous, so D is isomorphic to M. Hence U is ω categorical and U is a set of axioms for T . Suppose now that φ( x̄) is a formula of L, and let X be the set of all tuples ā in M such that M |= φ(ā). If ā is in X , and b̄ is a tuple of elements such that there is an isomorphism e : 〈āM 〉 → 〈 b̄M 〉 taking ā→ b̄, then e extends to an automorphism of M, so that b̄ is in X too. It follows that φ is equivalent modulo T to the disjunction of all the formulas ψ〈ā〉,ā( x̄) with ā ∈ X .This is a finite disjunction of quantifier free formulas. Finally if φ is a sentence of L then since T is complete, φ is equivalent to either ⊤ or ⊥. Notation . S3 denotes the set of all permutations of 3. X Y denotes the set of functions from X to Y . For u, v ∈ 33, i < 3 we write ui for u(i) < 3, and we write u≡i v if u and v agree off i, i.e if u j = v j for all j ∈ 3r {i}. For a symbol R of the signature of M we write RM for the interpretation of R in M. Lemma 9. Let L be a signature consisting of the unary relation symbols P0, P1, P2 and uncount- ably many 3-ary predicate symbols. For u ∈ 33, let χu be the formula ∧ i<3 Pui (x i). Then there exists an L-structure M with the following properties: (1) M has quantifier elimination, i.e. every L-formula is equivalent in M to a boolean combi- nation of atomic formulas. (2) The sets PM i for i < 3 partition M, (3) M |= ∀x0 x1 x2(R(x0, x1 x2)−→ ∨ u∈S3 χu), for all R ∈ L, (4) M |= ∃x0 x1 x2(χu ∧ R(x0, x1, x2) ∧ ¬S(x0, x1, x2)) for all distinct ternary R,S ∈ L, and u ∈ S3, (5) For u ∈ S3, i < 3, M |= ∀x0 x1 x2(∃x iχu←→ ∨ v∈33,v≡iu χv), (6) For u ∈ S3 and any L-formula φ(x0, x1, x2), if M |= ∃x0 x1 x2(χu ∧φ) then M |= ∀x0 x1 x2(∃x iχu←→∃x i(χu ∧φ)) for all i < 3. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 870 Proof. Throughout the proof, we use the notation x̄ , ā for finite sequences, or tuples 〈x0, · · · xm−1〉, 〈a0, · · · am−1〉. Given a structure M and a tuple ā, we often write, with a slight abuse of notation, ā ∈ M instead of ā ∈ mM , where m is the arity of the tuple ā. The arity of tuples will be clear from context. Let L be the relational signature containing unary relation symbols P0, . . . , P3 and a 4-ary relation symbol X . Let K be the class of all finite L -structures D satsfying The Pi ’s are disjoint : ∀x ∨ i< j<4 (Pi(x)∧ ∧ j 6=i ¬Pj(x)). (6) ∀x0 · · · x3(X (x0, · · · , x3)−→ P3(x3)∧ ∨ u∈s3 χu). (7) Then K contains countably many isomorphism types, because for each n ∈ω, there are count- ably many isomorphism types of finite L structures (satifying (6) and (7)) having cardinality ≤ n. Also it is easy to check that K is closed under substructures and that K has the AP. From the latter it follows that it has the J EP, since K contains the one element structure that is embeddable in any structure in K. ∗ Then there is a countably infinite homogeneous L - structure N with age K. N has quantifier elimination, and obviously, so does any elementary extension of N. K contains structures with arbitrarily large P3-part, so PN 3 is infinite. Let N∗ be an elementary extension of N such that |PN ∗ 3 | = |L|, and fix a bijection ∗ from the set of ternary relation symbols of L to PN ∗ 3 . Define an L-structure M with domain PN ∗ 0 ∪ PN ∗ 1 ∪ PN ∗ 2 , by: PM i = PN ∗ i for i < 3 and for ternary R ∈ L, M |= R(a0, a1, a2) iff N∗ |= X (a0, a1, a2,R∗). If φ( x̄) is any L-formula, let φ∗( x̄ , R̄) be the L -formula with parameters R̄ from N ∗ ob- tained from φ by replacing each atomic subformula R(x , y, z) by X (x , y, z,R∗) and relativizing quantifiers to ¬P3, that is replacing (∃x)φ(x) and (∀x)φ(x) by (∃x)(¬P3(x) → φ(x)) and (∀x)(¬P3(x) → φ(x)), respectively. A straightforward induction on complexity of formulas gives that for ā ∈M M |= φ(ā) iff N∗ |= φ∗(ā, R̄). We show that M is as required. For quantifier elimination, if φ( x̄) is an L-formula , then φ∗( x̄ , R̄∗) is equivalent in N ∗ to a quantifier free L -formula ψ( x̄ , R̄∗). Then replacing ψ’s atomic subformulas X (x , y, z,R∗) by R(x , y, z), replacing all X (t0, · · · t3) not of this form by ⊥ , replacing subformulas P3(x) by ⊥, and Pi(R ∗) by ⊥ if i < 3 and ⊤ if i = 3, gives a quantifier free L -formula ψ equivalent in M to φ. For (2), let σ = ∀x(¬P3(x)−→ ∨ i<3 (Pi(x)∧ ∧ j 6=i ¬Pj(x))). Then K |= σ, so N |= σ and N ∗ |= σ. It follows from the definition that M satisfies (2); (3) is similar. ∗It is not always true that AP implies J EP; think of fields. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 871 For (4), let u ∈ S3 and let r, s ∈ PM 3 be distinct. Take a finite L -structure D with points ai ∈ PD ui (i < 3) and distinct r ′, s′ ∈ PD 3 with D |= X (a0, a1, a2, r ′)∧¬X (a0, a1, a2, s′). Then D ∈ K, so D embeds into N. By homogeneity, we can assume that the embedding takes r ′ to r and s′ to s. Therefore N |= ∃ x̄(χu ∧ X ( x̄ , r)∧¬X ( x̄ , s)), where x̄ = 〈x0, x1, x2〉. Since r, s were arbitrary and N ∗ is an elementary extension of N, we get that N ∗ |= ∀yz(P3(y)∧ P3(z)∧ y 6= z −→ ∃ x̄(χu ∧ X ( x̄ , y)∧¬(X ( x̄, z))). The result for M now follows. Note that it follows from (3,4) that PM i 6= ; for each i < 3. So it is clear that M |= ∀x0 x1 x2(∃x iχu←→ ∨ v∈33,v≡i u χv); giving (5). Finally consider (6). Clearly, it is enough to show that for any L -formula φ( x̄) with parameters r̄ ∈ PM 3 ,u ∈ S3, i < 3, we have N |= ∃ x̄(χu ∧φ) −→∀ x̄(∃x i(χu −→ ∃x i(χu ∧φ)). For simplicity of notation assume i = 2. Let ā, b̄ ∈N with N |= (χu ∧φ)(ā) and N |= ∃x2(χu( b̄)). We require N |= ∃x2(χu ∧φ)( b̄). It follows from the assumptions that N |= Pu0 (a0)∧ Pu1 (a1)∧ a0 6= a1, and N |= Pu0 (b0)∧ Pu1 (b1)∧ b0 6= b1. These are the only relations on a0ar r̄ and on b0 b1 r̄ (cf. property (3) of Lemma 13), so θ− = {(a0, b0)(a1, b1)(rl , rl) : l < |r̄|} is a partial isomorphism of N. By homogeneity, it is induced by an automorphism θ of N. Let c = θ(ā) = (b0, b1,θ(a2)). Then N |= (χu∧φ)(c̄). Since c̄ ≡2 b̄, we have N |= ∃x2(χu∧φ)( b̄) as required. Now we explain the idea behind the construction of such an M, and in the process give an outline of the proof that the class of neat reducts is not elementary, that paves the way for a smooth (formal) proof of our main Theorem. Throughout fix M as in Lemma 9. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 872 We will go through the conditions one by one. Condition 1 of quantifier elimination says that the set of atomic formulas J = {R(y0, y1, y2) : {y0, y1.y2} = {x0, x1, x2} and R ∈ L is a ternary relation} ⋃ {Pi(x j) : i, j < 3} ∪ {x i = x j : i, j < 3} is an elimination set for M, meaning that every formula φ ∈ L is equivalent in M to a boolean combination of formulas in J . This implies that the cylindric set algebra based on M using only the first three variables is a neat reduct. In more detail, for φ ∈ L, let φM be the set of all assignments satisfying φ in M i.e. φM = {s ∈ ωM : M |= φ[s]}. Csn denotes the class of cylindric set algebras of dimension n. Let Aω be the Csω with domain {φM : φ ∈ L} and operations (well-) defined by (cf.[12])† φM.ψM = φM ∩ψM = (φ ∧ψ)M; −φM = (¬φ)M; and for i, j <ω di j = (x i = x j) M; and ci(φ M) = (∃x iφ) M. Now write L3 for the set of all L-formulas using only the first three variables. Then a moment’s reflection will show that condition 1 says that the Cs3 A with domain {φM : φ ∈ L3} is the same as the (possibly bigger) Cs3 with domain {φM : φ ∈ L and φ contains x0, x1, x2 as free variables}, with the operation defined, for both, as for Aω. But the latter, as easily checked, is isomorphic to Nr3Aω, so condition 1 guarantees that A ∈Nr3CAω. The rest of the conditions are designed to extract an elementary subalgebra of A such that its rSC reduct is not in Nr3(rSC5). But let us first understand the (abstract) structure of A based on M. Condition (2), says that {χM u : u ∈ 33} †In [12], sec 4.3, cf. Definition 4.3.4 Aω would be denoted by C f M 3 , which is the set algebra based on M. In this connection we note that A is a regular locally finite Csω. T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 873 is a partition of 3M , the unit of A. That is ⋃ u∈33 (χu) M = 3M , and for distinct u, v ∈ 33 we have (χu) M ∩ (χv) M = ;. Conditions (3) and (4) single out the χM u ’s that are indexed by permutations u ∈ S3. Note that for any such u, if 〈a0, a1, a2〉 ∈ χ M u , then the ai ’s are distinct because ai ∈ Pui for i < 3 and by (2) these are disjoint. Condition (3) says that for any ternary R( x̄) ∈ L, R( x̄)M ⊆ ⋃ u∈S3 (χu) M with u ∈ S3, so this means that if 〈a0, a1, a2〉 ∈ R( x̄)M, then the ai ’s must be distinct, too. Condition (4) says that below every such (χu) M with u ∈ S3, there are uncountably many pairwise distinct non-empty elements, namely, the R( x̄)M∩(χu) M, for ternary R ∈ L. Condition (5) tells us how the (χu) M’s behave with respect to cylindrifications. It simply says that for u ∈ S3 and i < 3 we have ci(χu) M = ⋃ v∈33,v≡iu (χv) M. A moment’s reflection will reveal that this follows from (3) and (4.) Finally, condition (6) says that elements below χM u are big, as far as cylindrifications are concerned, that is for any φ such that (φ ∩ χu) M 6= ; and any i < 3, we have ci(φ M ∩χM u ) = ci(χ M u ) = ⋃ v∈33,v≡iu (χv) M. Summarizing the above, let 1u denote χM u . Then by condition (2), we have {1u : u ∈ 33} is a partition of the unit of A. If u ∈ S3, then below every 1u, there are uncountably many pairwise distinct non empty elements, namely the R( x̄)M’s intersected with 1u. (conditions (3), (4)). Such elements are big as far as the cylindrifications are concerned, that is for i < 3 we have (by conditions (5), (6)) ci(R( x̄) M ∩ 1u) = ci(1u) = ⋃ v≡iu 1u. Having explained the idea behind the conditions of Lemma 13 we explain how we will go about extracting an elementary subalgebra of A that is not a neat reduct. For u ∈ 33, let Au stand for the relativisation of A to 1u i.e. Au = {x ∈ A : x ≤ 1u}. Au is the domain of a boolean set algebra which we denote by Au. Then for u ∈ S3, Au is uncountable. Because {1u : u ∈ 33} is a partition of the unit of A, it follows that the boolean T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 874 reduct of A is isomorphic to the boolean product, ∏ u∈33 Au. Moreover we can expand the language of boolean algebras by diagonal elements and the constants 1u in such a way that the cylindric algebra A becomes interpretable in this product. Then we are able to extract an elementary subalgebra B of A by an infinite cardinality twist, that first order logic does not see. B is simply obtained from A by keeping only many countably elements below 1I d , where Id is the identity function on 3, and throwing away the rest of the elements below 1I d . In the product, this corresponds to replacing the component AI d by an arbitrary elementary countable boolean subalgebra BI d of AI d and giving the resulting algebra the interpretation given to the the boolean product ∏ u∈33 Au. This will not be witnessed by first order logic, but will enforce that the resulting structure B, which is of course a CA3, is not a neat reduct. In fact, B will not be even in Nr3CA4 and its rSC reduct is not in Nr3rSC5. The idea is that had B been a neat reduct then using a substitution term definable in extra dimensions, will give uncountably many elements in the component BI d , which contradicts that the latter, by construction, is countable. Now we implement the details of the above sketch. Proof. [main result] Fix L and M as in Lemma 9. Let Aω, A be as specified above. That is Aω = {φ M : φ ∈ L} and A= {φM : φ ∈ L3}. Then A∼=Nr3Aω, the isomorphism is given by φM 7→ φM. Quantifier elimination in M guarantees that this map is onto. For u ∈ 33, let Au denote the relativisation of A to χM u i.e Au = {x ∈ A : x ≤ χM u }. Au is a boolean algebra. Also Au is uncountable for every u ∈ S3 because by property (4) of Lemma 9 the sets (χu ∧ R(x0, x1, x2)) M, for R ∈ L are distinct elements of Au. Define a map f : A→ ∏ u∈33(Au), by f (a) = 〈a.χu〉u∈33. We will expand the language of the boolean algebra ∏ u∈33 Au in such a way that the cylindric algebra A becomes interpretable in the expanded structure. For this we need. Definition 10. Let ¶ denote the following structure for the signature of boolean algebras ex- panded by constant symbols 1u for u ∈ 33 and di j for i, j ∈ 3: (1) The boolean part of ¶ is the boolean algebra ∏ u∈33 Au, (2) 1¶ u = f (χM u ) = 〈0, · · ·0,1,0, · · · 〉 (with the 1 in the uth place) for each u ∈ 33, (3) d¶ i j = f (dAi j) for i, j < 3. We now show that A is interpretable in ¶. For this it is enough to show that f is one to one and that Rng( f ) (Range of f ) and the f -images of the graphs of the cylindric algebra functions in A are definable in ¶. Since the χM u partition the unit of A, each a ∈ A has a unique expression in the form ∑ u∈33(a.χM u ), and it follows that f is boolean isomorphism: bool(A)→ ∏ u∈33 Au. So the f -images of the graphs of the boolean functions on A are trivially T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 875 definable. f is bijective so Rng( f ) is definable, by x = x . For the diagonals, f (dAi j) is definable by x = di j. Finally we consider cylindrifications. For S ⊆ 33, i < 3, let tS be the closed term ∑ {1v : v ∈ 33, v ≡i u for some u ∈ S}. Let ηi(x , y) = ∧ S⊆33 ( ∧ u∈S x .1u 6= 0∧ ∧ u∈33rS x .1u = 0−→ y = tS). We claim that for all a ∈ A, b ∈ P, we have ¶ |= ηi( f (a), b) iff b = f (cAi a). To see this, let f (a) = 〈au〉u∈33, say. So in A we have a = ∑ u au. Let u be given; au has the form (χi ∧φ) M for some φ ∈ L3, so cA i (au) = (∃x i(χu ∧φ)) M. By property 6 of Lemma 9, if au 6= 0, this is (∃x iχu) M ; by property 5, this is ( ∨ v∈33,v≡iu χv) M. Let S = {u ∈ 33 : au 6= 0}. By normality and additivity of cylindrifications we have, cA i (a) = ∑ u∈33 cA i au = ∑ u∈S cA i au = ∑ u∈S ( ∑ v∈33,v≡iu χM v ) = ∑ {χM v : v ∈ 33, v ≡i u for some u ∈ S}. So ¶ |= f (cA i a) = tS . Hence ¶ |= ηi( f (a), f (cA i a)). Conversely, if ¶ |= ηi( f (a), b), we require b = f (cia). Now S is the unique subset of 33 such that ¶ |= ∧ u∈S f (a).1u 6= 0∧ ∧ u∈33rS f (a).1u = 0. So we obtain b = tS = f (cA i a). We have proved that ¶ is interpretable in A. Furthermore it is easy to see that the inter- pretation is one dimensional and quantifier free. Next we extract an algebra B elementary equivalent to A that is not a neat reduct i.e. not in Nr3CA4. Also RdrSCB /∈ Nr3rSC5. Let Id ∈ 33 be the identity map on 3. Choose any countable boolean elementary subalgebra of AI d , BI d say. Thus BI d � AI d . By lemma 9 Q = ((BI d × ∏ u∈33rI d Au), 1u, di j)u∈33,i, j<3 ≡ ( ∏ u∈33 Au)), 1u,di j)u∈33,i, j<3 = P. (Note that the Id th coordinate of each constant is 0 or 1, so the constants do lie in Q.) Let B be the result of applying the interpretation given above to Q. Then B ≡ A as cylindric algebras. Now we show that B cannot be a neat reduct, in fact we show that B /∈ Nr3CAβ T. Ahmed / Eur. J. Pure Appl. Math, 3 (2010), 853-880 876 for any β > 3, while RdrSCB /∈ Nr3rSCβ for β > 4. We settle first the cylindric case. Assume for contradiction that B = Nr3D for some D ∈ CAβ ; with β > 3. Note that D may not be representable. It is only here that we deal with possibly non-representable algebras. Now χM u ∈ B for each u ∈ 33. Identifying functions with sequences we let v = 〈1,0,2〉 ∈ 33. Let t(x) be the CA2 term s0 1c1 x .s1 0c0 x , where s j i (x) = ci(di j .x), for i 6= j. Then we claim that tB(χM v ) = χ M I d . For the sake of brevity, denote χM v by 110 and χM I d by 101. Then, by definition, we have tB(101) = c0(d01.c1110).c1(d01.c0110). Computing we get c0(d01.c1110) = c0(d01.( ∑ {1u : u≡1 110}) = c0(d01.1112) = 101 + 1112. Here 1112 denotes χ〈1,1,2〉. Note that we are using that the evaluation of the term c1110 in B is equal to its value in A. This is so, because B inherits the interpretation given to ∏ Au. A similar computation gives c1(d01.c0101) = 1002 + 101, where 1002 denotes χ〈0,0,2〉. Therefore as claimed tB(110) = 101. Now let 3s(0,1) be the unary substitution term as defined in [11] 1.5.12, that is 3s(0,1)x = s3 0s 0 1s 1 3(x). Then for any β > 3 we have CAβ |= 3s(0,1)c3 x ≤ t(c3 x). Indeed by [11] 1.5.12, 1.5.8 and 1.5.10 (ii), we get 3s(0,1)c3x ≤ 3s(0,1)c1c3 x = s3 0s 0 1s 1 3c1c3 x = s3 0s 0 1c1c3 x = s3 0s 0 1c3c1 x = s3 0c3s 0 1c1 x = c3s 0 1c1 x = s1 0c1c3 x . Similarly 3s(0,1)c3x ≤ s0 1c0c3 x Therefore 3s(0,1)c3 x ≤ t(c3 x). It thus follows that D |= 3s(0,1)(χM u ) ≤ s0 1c1(χ M u ).s 1 0c0(χ M u ) = χ M I d . Now 3s(0,1) preserves ≤ and is one to one Nr3D. By [11], 1.5.12 and 1.5.1, we have: 3s(0,1)c3 x = sn 0s 0 1s 1 3c3 x = c3(d30 ∩ c0(d01 ∩ c1(d01 ∩ c1(d13 ∩ c3 x))). REFERENCES 877 By [11], 1.3.8, 0< x , implies 0< di j ∩ c j x , for all i, j ∈ β . We have shown that if x > 0 ∈ N r3D, then 3s(0,1)x > 0, i.e that 3s(0,1), being a boolean endomorphism, is one to one. Since Bv = Av it follows (by condition (4) in Lemma 13) that Bv = {b ∈ B : b ≤ χM v } is uncountable. Since 3s(0,1) is one to one, it follows that 3s(0,1)Bu is also uncountable. But by the above we have 3s(0,1)Bu ⊆ BI d = {b ∈ B : b ≤ χB I d}, and so BI d is also uncountable. But by construction, we have BI d = {b ∈ B : b ≤ χM I d } is countable. This contradiction shows that B /∈Nr3CAβ for any β > 3. The rSC is the same by using the axiomatization (E1 − E9) and noting that 3s(0,1) is a permutation of Nr3D when D ∈ rSC5. Same reasoning for SCm. Finally we should mention that the proof presented herein is substantially different than the proofs in [21], [18], [34], [29], since it uses genuine model theoretic arguments. References [1] H. Andréka, I. Németi, T. Sayed Ahmed, Omitting types for finite variable fragments and complete representations of algebras. Journal of Symbolic Logic 73(1) (2008) p.65-89 [2] H. Andréka, S.Givant, S. Mikulus, I. Németi, A. Simon Notions of density that imply representability in algebraic logic Annals of pure and applied logic 91 (1998) p.93-190 [3] J. Burgess Forcing Chapter in Handbook of Mathemmatical Logic Edited by Barwise. J. [4] M. Ferenczi, On representability of neatly embeddable cylindric algebras Journal of Ap- plied Non-classical Logic, 10 3-4(2000), p. 1-11 [5] D, H, Fremlin, Consequences of MA. Cambridge University press. (1984) [6] W. Hodges Model Theory, volume 42 of Encyclopedia of mathematics and its applica- tions [7] Hirsch R. Relation algebra reducts of cylindric algebras and complete representations Jour- nal of Symbolic Logic, 72(2) (2007) p.673-703. [8] R. Hirsch and I. Hodkinson, Complete representations in algebraic logic. Journal of Sym- bolic Logic, 62(3) (1997), 816–847. [9] R. Hirsch I. Hodkinson Relation algebras by games. (2002) Studies in Logic and the Foundations of Mathematics. Volume 147. (2002) [10] R. Hirsch, I. Hodkinson, R. Maddux, Relation algebra reducts of cylindric algebras and an application to proof theory. Journal of Symbolic Logic 67(1) (2002), 197–213. [11] L. Henkin, J.D. Monk and A. Tarski Cylindric Algebras Part I. North Holland, (1971.) REFERENCES 878 [12] L. Henkin, J.D. Monk, and A. Tarski Cylindric Algebras Part II. North Holland, (1985). [13] L. Henkin, J. D. Monk, A. Tarski, H. Andreka, and I. Németi, Cylindric Set Algebras. Lecture Notes in Mathematics, Vol. 883, Springer-Verlag, Berlin, (1981), p.vi + 323. [14] I. Németi, The Class of Neat Reducts of Cylindric Algebras is Not a Variety But is closed w.r.t. HP. Notre Dame Journal of Formal logic, 24(3) (1983), pp 399-409. [15] I. Németi, Algebraisation of quantifier logics, an introductory overview. Math.Inst.Budapest, Preprint, No 13-1996. A shortened version appeared in Stu- dia Logica 50(4) (1991)p.465-569. [16] J. Madárasz J., and T. Sayed Ahmed, Amalgamation, interpolation and epimorphisms Algebra Universalis 56 (2) (2007) p. 179-210. [17] A. Miller, Some properties of measure and category Transactions of the American Math- ematical Society, 266 (1981),. 93-113 [18] T. Sayed Ahmed The class of neat reducts is not elementary. Logic Journal of IGPL, 9 (2001) p. 31-65 electronically available at http://www.math-inst.hu/pub/algebraic- logic. [19] T. Sayed Ahmed Martin’s axiom, omitting types and complete representations in algebraic logic . Studia Logica 72 (2002), p.1-25 [20] T. Sayed Ahmed Neat embeddings, interpolation, and omitting types, an overview. Notre Dame Journal of formal logic, 44 (3)(2003), p.157-173 [21] T. Sayed Ahmed, The class of 2-dimensional neat reducts of polyadic algebras is not ele- mentary. Fundementa Mathematicea, 172 (2002), p.61-81. [22] T. Sayed Ahmed, Martin’s axiom, omitting types and complete representations in alge- braic logic . Studia Logica 72 (2002), p.1-25 [23] T. Sayed Ahmed, A confirmation of a conjecture of Tarski Bulletin section of logic 32 (3) (2003), p.103-105 [24] T. Sayed Ahmed, Neat embeddings, Interpolation, and omitting types, an overview. Notre Dame Journal of formal logic, 44 (3)(2003), p.157-173 [25] T. Sayed Ahmed, On Amalgamation of Reducts of Polyadic Algebras. Algebra Universalis 51 (2004), p.301-359. [26] T. Sayed Ahmed, On amalgamation of algebras of logic Studia Logica 81 (2005), p.61- 77. [27] T. Sayed Ahmed, Algebraic Logic, where does it stand today? Bulletin of Symbolic Logic. 11 (4) (2005), p.465-516. REFERENCES 879 [28] T. Sayed Ahmed , The class of infinite dimensional neat reducts quasi-polyadic algebras is not axiomatizable Mathematical Logic quaterly 52 (1) (2006), p.106-112 [29] T.Sayed Ahmed A note on neat reducts, Studia Logica 85(2), (2007)p. 139-151. [30] T. Sayed Ahmed On Amalgamation of Reducts of Polyadic Algebras. Algebra Universalis 51 (2004), p.301-359. [31] T. Sayed Ahmed, Amalgamation Theorems in Algebraic Logic, an overview Logic Journal of IGPL, 13 (2005), 277-286. [32] T. Sayed Ahmed, On amalgamation of algebras of logic Studia Logica 81 (2005), p.61- 77. [33] T. Sayed Ahmed, Algebraic Logic, where does it stand today? Bulletin of Symbolic Logic. 11 (4) (2005), p.465-516. [34] T. Sayed Ahmed, The class of infinite dimensional neat reducts of quasi-polyadic algebras is not axiomatizable Mathematical Logic quaterly 52 (1) (2006), p.106-112 [35] T. Sayed Ahmed, Omitting types for algebraizable extensions of first order logic Journal of Applied non-classical logics 15 (4) (2006), p.465-487 [36] T.Sayed Ahmed Non elementary classes in algebraic logic submitted [37] T. Sayed Ahmed. On a Theorem of Vaught for first order logic with finitely many variables Journal of Applied Non-classical Logic 19(1) (2009) p. 97-112. [38] T. Sayed Ahmed. A note on substitutions in cylindric algebras Mathematical Logic Quar- terly 55(3)(2009) p. 280-287 [39] T. Sayed Ahmed On neat embeddings of cylindric algebras Mathematical Logic Quarterly 55(6)(2009)p.666-668 [40] T. Sayed Ahmed. The class of polyadic algebras has the superamalgamation property Mathematical Logic Quarterly 56(1)(2010)p.103-112 [41] T. Sayed Ahmed On neat embedding of algebraisations of first order logic Journal of Algebra, number theory, advances and applications 1(2) 2009 p. 113-125 [42] T. Sayed Ahmed The amalgmation property, and a problem of Henkin Monk and Tarski Journal of Algebra, number theory, advances and applications 1(2) 2009 p. 127-141 [43] T. Sayed Ahmed The class of polyadic algebras has the superamalgamation property Mathematical Logic Quarterly 56(1)(2010)p.103-112 [44] T. Sayed Ahmed Some results on neat reducts Algebra Universalis, in press. REFERENCES 880 [45] T. Sayed Ahmed, I. Németi, On neat reducts of algebras of logic. Studia Logica, 62 (2) (2001), p.229-262. [46] T.Sayed Ahmed and M. Amer Polyadic and cylindric algebras of sentences Mathematical logic quaterly vol 52 no 5 p.44-49 (2006) [47] T. Sayed Ahmed and B.Samir A Neat embedding theorem for expansions of cylindric algebras Logic journal of IGPL 15 (2007) p. 41-51 [48] I. Sain. Searching for a finitizable algebraization of first order logic. Logic Journal of IGPL. Oxford University Press. 8(4) (2000), 495–589. [49] G. Sagi, A completeness theorem for higher order logics Journal of Symbolic Logic 65(3)(2000) p.857-884. [50] S. Shelah. Classification Theory Second Edition North Holland P.C., Amsterdam 1990. [51] A. Tarski and S. Givant A formalization of set theory without variables. AMS Colloquium Publications 41, (1987).