The Class of Neat Reducts is Not Elementary

Tarek Sayed Ahmed Department of Mathematics, Faculty of Science, Cairo University, Giza, Egypt.

July 30, 1999

Abstract . We solve a problem of Tarski, and his co-authors Andreka, Henkin, Monk, and Nemeti. We show that for any pair of ordinals 1 < α < β, the class of α-dimensional neat reducts of β-dimensional cylindric algebras is not elementary. The construction we use when α is infinite also settles a conjecture of Tarski in the affirmative.

§0. INTRODUCTION AND MAIN RESULTS

Subject

Neat reducts and related notions, like neat embeddings, play a central role in algebraic logic. One of the main representation methods used in the theory of cylindric algebras , and variants thereof, like polyadic algebras, is based on the Neat Embedding Theorem to be recalled below. (See also [HMT1] p.400 and [HMT2] Thm 3.2.10).

It is known (cf, for eg [S97] or [AGN77]) that the Neat Embedding Theorem, or the NET for short, proved by Henkin in the late fifties, is an algebraization of Henkin’s celebrated proof of the completeness of first order logic.

The NET is also one of the earliest examples of what Hirsch and Hodkinson call “Step-by-step building representations in algebraic logic” (cf [HH97a]).

Ever since, variants of the NET have been applied successfully to prove (algebraically) completeness of other versions of quantifier logics (eg. Kieslers logics, cf [DM63]).

Other works addressing the notion of neat reducts, one way or another, include [A93],[S97] and [Sa98]. In [A93] and [S97], neat reducts are studied in connection with algebras of sentences of first order logic. In [Sa98] a NET is introduced (and proved) to demonstrate completeness of certain “finitary” fragments of Kieslers logics, that are also expansions of first order logic without equality. This provides a positive solution to one version of the so called finitization problem in algebraic logic. We refer the reader to [N96] for a survey on the finitization problem.

The connection of neat reducts to other metalogical properties like the Beth-definabilty property and omitting types will be discussed in section 6 below. This (and other) connection(s) are investigated more thoroughly in ([Pi71],[Ma77],[Ma78],[N83] [F92],[F98]), [ANS98] and [AS98].

History (Previous results)

Let 0 ≤ α < β be ordinals. Solving problem 2.11 in [HMT1], Nemeti proved in [N83], that the class Nr_{α}(CA_{β}), of α-dimensional neat reducts of β-dimensional cylindric algebras, though closed under homomorphic images, products and ultraproducts, is not a variety (i.e, not closed under forming subalgebras), iff α > 1.

In II.8.6 of [HMTAN] (cf, p.266, therein), Andreka and Nemeti proved that the class Nr_{α}(CA_{β}) is not elementary for α = 2 (i.e, not even closed under forming elementary subalgebras). ^{1}

Problem 18 on p.312 in [HMTAN] asks whether this result extends to higher dimensions and in [N83], Nemeti conjectures that it does. (cf, conjecture 8, p.408, therein).

Unsettled, this problem appears once again as problem 4.4 in [HMT2]. This paper is devoted to investigating this problem for various subclasses of cylindric algebras. More precisely the question we investigate is : For which ordinals 1 < α < β, and L ⊆ CA_{β}, is the class Nr_{α}L not elementary? Theorem 1 below formulates the answer for every pair 1 < α < β of ordinals and various classes of cylindric algebras.

Basic notions and formulation of the main results

To formulate the main results, we review some basic notions. We try to use conventional notation. We introduce less usual notations at their first occurrence in the text.

ω denotes the least infinite ordinal, which is also the set of all finite ordinals. More generally an ordinal is the set of smaller ordinals. Cardinals, as usual, are identified with initial ordinals. If X, Y are sets then ^{X}Y denotes the set of all functions from X into Y. Composition of two functions f and g, f ∘ g is defined so that f ∘ g(x) = f(g(x)). Id_{X}, or simply Id when X is clear from context, denotes the identity function on X. |X| denotes the cardinality of X, and Sb(X) denotes the set of all subsets of X. The following notation will be used extensively: For a function f, and X ⊆ domf (the domain of f), f ↾ X and f(X) denote the restriction of f to X and the image of X under f, respectively.

1Independently Roger Maddux [Ma78] showed that the class Nr_{α}(CA_{β}) is not closed under forming subalgebras for α = 3 and β > 4. In [N83], the following is actually proved:

For any pair of ordinals 1 < α < β and any class L such that W s_{β} ⊆ L ⊆ CA_{β}, the class Nr_{α}L is not closed under forming subalgebras, i.e is not a variety. When α = 2, this result is strengthened in [HMTAN] to: The class Nr_{2}L is not closed under forming elementary subalgebras, hence not elementary. It is rather this (stronger) result that we generalize to higher dimensions (cf, Theorem 1). Here W s_{β} stands for the class of weak set algebras of dimension β, to be recalled below.

Let K be a class of algebras. Then IK, HK, SK, and P K denote the classes of all isomorphic images, homomorphic images, subalgebras, and algebras isomorphic to direct products of members of K respectively. EqK, denotes the smallest variety containing K. That is EqK = HSP K. Given an algebra A and X ⊆ A, then Sg^{A}X or simply SgX, when A is clear from context, denotes the subalgebra of A generated by X. Let B be an algebra having the same similarity type as A. Then we write f ∈ Ism(A, B) to abbreviate that f is an isomorphism from A into B. In boolean algebras (BA’s), ∪, ∩, −, 0 and 1, stand for join, meet, complementation, least element and greatest element, respectively.

Let A be a cylindric algebra of dimension β, briefly a CA_{β}. Recall that A is of the form

⟨A, ∪, ∩, −, 0, 1, c_{i}, d_{ij}⟩_{i,j∈β}

where ⟨A, ∪, ∩, −, 0, 1⟩ is a boolean algebra, henceafter BlA, and for i, j ∈ β, c_{i} is a unary operation on A, and d_{ij} is a distinguished element of A. The class CA_{β} of all β dimensional cylindric algebras is a variety defined by a finite schema of equations (cf., [HMT1] Def.1.1.1) . We do not have to remember the specific form of these here. We recall from [HMT1], Def.2.6.28, a notion that prevails throughout this paper, that of of neat reducts:^{2}

Let α and β be any ordinals with α ≤ β. Let A ∈ CA_{β}. Then the neat α − reduct of A, in symbols Nr_{α}A , is the following CA_{α}:

Nr_{α}A = ⟨Nr_{α}A, ∪, ∩, −, c_{i}^{A}, d_{ij}^{A}⟩_{i,j∈α}, where Nr_{α}A = {x ∈ A : c_{i}^{A}x = x, for all α ≤ i < β}.

A subalgebra B of Nr_{α}A is called a subneat reduct of A. When further B generates A, then B is called a generating subneat reduct of A, or simply a generating subreduct of A. For any class K of CA_{β}’s, and α ≤ β, Nr_{α}K denotes {Nr_{α}A : A ∈ K}.

Let α be an ordinal. Then Cs_{α} and W s_{α} stand for the classes of cylindric set algebras and weak cylindric set algebras, of dimension α, respectively. (cf. [HMT2], Def.3.1.1). That is A ∈ Cs_{α}, (W s_{α}) if A is a boolean field of sets with unit a (weak) cartesian space of dimension α. A cartesian space of dimension α is of the form ^{α}U, for some set U, while a weak one of dimension α is of the form ^{α}U^{(p)} = {s ∈ ^{α}U : |{i ∈ α : s_{i} ≠ p_{i}}| < ω}, for some p ∈ ^{α}U. In addition to this, A of course, has to be closed under the usual concrete interpretation of the cylindric operations c_{i} and diagonals d_{ij}, for all i, j ∈ α. Note that when α is finite we have Cs_{α} = W s_{α}. In any case, it is known (see e.g [N96]), that SP Cs_{α} = SP W s_{α}, and that SP Cs_{α} is a variety, i.e SP Cs_{α} = EqCs_{α}. EqCs_{α} (which is the same as EqW s_{α}), referred to as the class of representable CA_{α}’s, is sometimes denoted by RCA_{α}. Every A ∈ RCA_{α}, α ≥ 2, is isomorphic to a generalized cylindric set algebra (a Gs_{α}): A Gs_{α} is a boolean field of sets with unit a disjoint union of cartesian spaces each of dimension α. A fundamental theorem of CA theory, the so called Neat Embedding Theorem (NET), states that RCA_{α} = SNr_{α}CA_{α+ω}. ^{3} The NET is known to hold for the most well known variants of CA’s. These include: Pinter’s substitution algebras and Halmos’ quasi-polyadic algebras. For a survey on the NET and algebras other than CA’s to which variations of the NET apply the reader can consult [Sa98].

2The notion of neat reducts was introduced by Henkin (cf [HMT1], footnote on p. 401).

For a detailed and comprehensive treatment of the notion of neat reducts and related notions like neat embeddings we refer the reader to [HMT1] p.401-428.

In contrast to BA’s, it is known that not every CA_{α} α > 1 is representable (as algebras of true α ary relations).^{4} We hasten to remark that all algebras considered herein though are weak set algebras, hence representable .

We are now ready to formulate the main results. Recall that a class K is elementary (or first order axiomatizable), if and only if it is closed under ultraproducts and elementary equivalence.

Theorem 1 (Main Theorem) . For K ∈ {W s, Cs, Gs, CA} and 1 < α < β, the class Nr_{α}(K_{β}) is not elementary.

Theorem 1 solves problem 18 on page 312 in [HMTAN] and 4.4 in [HMT2]. Theorem 1 also confirms a conjecture of Nemeti. As further conjectured by Nemeti in [N83] p.408 , Theorem 1 can be, and is indeed proved herein by methods similar to those used in the proof of II.8.6 in [HMTAN] and statement 1 in [N83]. Further refined by Andreka, such methods are more commonly referred to in the literature as Andreka’s method of splitting elements, or simply “Andreka’s splitting”[An98]. ^{5}

Using Andreka’s splitting, we shall prove slightly more than what is stated in Theorem 1, namely, for any pair of ordinals 1 < α < β and any L such that W s_{β} ⊆ L ⊆ CA_{β}, the class Nr_{α}L is not closed under forming elementary subalgebras, hence not elementary.

3Algebras in the class SNr_{α}CA_{α+ω}, are referred to in [HMT1] as algebras having the neat embedding property. These, according to the NET, are isomorphic to Gs_{α}’s. Ferenczi ( [F92]- [F98]) investigates the question : For which proper superclasses K of CA_{α+ω} is it still true that IGs_{α} = SNr_{α}K. This has implications in proof theory.

4Henkin showed that RCA_{2} can be defined by adjoining two equations to the equations axiomatizing CA_{2}, cf. [HMT2] 3.2.65. In sharp contrast, when α > 2 RCA_{α} is not even axiomatizable by any set of universal formulas using only finitely many variables. The latter, a result of Andreka [An98], considerably sharpens Monk’s celebrated result [M69] of non finite schema axiomatizability of RCA_{α}’s when α > 2.

5The roots of this method, though, can be traced back to Henkin’s method of splitting elements introduced on page 390 in [HMT1].

Theorem 2 . Let β > α ≥ ω. Then there exist B ∈ W s_{α}, and C ∈ W s_{β} such that B is a generating subreduct of C, and B ≠ Nr_{α}C.

Theorem 2, is actually an immediate consequence of Theorem 1 (when α is infinite). Theorem 2 contrasts Theorem 2.6.67 in [HMT1]. The latter states that if B is a dimension complemented CA_{α}, briefly a Dc_{α}^{6}, and B happens to be a generating subreduct of C ∈ CA_{β}, β > α, then B = Nr_{α}C. In [HMT1], at the top of p.426, it was also stated that the class Dc_{α} in the hypothesis of Theorem 2.6.67 cannot be replaced by arbitrary CA_{α}’s even if they are restricted to representable ones. The proof was postponed to appear in part 2. This statement appears again as item (v) in the introduction of [HMT2], this time among results of Tarski the proofs of which could not be reconstructed. Theorem 2, thus confirms what seems to have been a conjecture of Tarski. ^{7}

Organization of the paper

First we will give the proof of Theorem 1 for α finite, because in this case we use a fairly simpler construction (than that used in the infinite case) and so we believe that the idea of the proof will be easier to grasp. Sections 1-4 are devoted to this purpose. In Section 5 we give a separate proof to Theorem 1 with the necessary modifications to adapt the infinite case . Apparently more involved, the idea, in essence is the same as that of the finite dimensional case. We also obtain, as a byproduct, Theorem 2. In Section 6, a corollary dealing with certain reducts of CA’s (namely Pinters substitution algebras), together with a conjecture dealing wih other variants of CA’s (like Halmos qausipolyadic algebras) are stated. A few related results concerning neat reducts are also discussed in some detail.

§1. THE FINITE CASE

Throughout sections 1 − 4, R denotes a fixed uncountable set, and n = {0, ⋯, n − 1} denotes a fixed finite ordinal with 1 < n.

6B ∈ Dc_{α} if for all x ∈ B, there is an i ∈ α such that c_{i}x = x. Dc_{α} (α ≥ ω), contains properly the class of locally finite cylindric algebras of dimension α (Lf_{α}). The class Lf_{α}, introduced by Tarski, is the algebraic counterpart of first order logic with its provability and semantical notions. For more on these connections we refer the reader to the introduction of [HMT1] and [HMT2] sec 4.3.

7In the context of proving amalgamation results, Pigozzi conjectures in [Pi71], at the top of p. 331, that Theorem 2.6.67 does not even generalize to the classes of semisimple cylindric algebras (Sc_{α}) and the so called diagonal cylindric algebras (Di_{α}), respectively.

(cf, footnote on p.416 in [HMT1]). Since W s_{α} ⊆ Sc_{α} ⊆ Di_{α} for α ≥ ω (cf. [HMT2] Thm 2.6.50), Theorem 2 settles Pigozzi’s conjecture as well.

Notation . Let k < ω. Then S(n, k) denotes the set of sequences ⟨i_{0}, ⋯, i_{n−1}⟩ such that i_{0} ≤ i_{1} ⋯ ≤ i_{n−1} = k. Cof^{+}(R) denotes the set of all nonempty finite or cofinite subsets of R, i.e.

Cof^{+}(R) = {X ⊆ R : X is non empty and finite, or R − X is finite}.

Let C_{r} be an n-ary relation symbol for all r ∈ R. For any X ⊆ R, X finite we define the formulas:

η(X) = ∨{C_{r}(x_{0}, ⋯, x_{n−1}) : r ∈ X}, and
η(R − X) = ∧{¬C_{r}(x_{0}, ⋯, x_{n−1}) : r ∈ X}.

Lemma 1 . There are a set W and n-ary relations C_{r} ⊆ ^{n}W on W for all r ∈ R such that conditions (i)-(iv) below hold:

(i) C_{r}(w_{0}, ⋯, w_{n−1}) implies C_{r}(w_{π(0)}, ⋯, w_{π(n−1)}) for all r ∈ R, w_{0}, ⋯, w_{n−1} ∈ W and permutation π of n.

(ii) For all w_{0}, ⋯, w_{n−2} ∈ W and r ∈ R there is a w_{n−1} ∈ W −{w_{0}, ⋯, w_{n−2}} such that C_{r}(w_{0}, ⋯, w_{n−1}).

(iii) For all k ∈ ω, for all w_{0}, ⋯, w_{k−1} ∈ W and for any function

f : S(n, k) → Cof^{+}(R), there is a w_{k} ∈ W − {w_{0}, ⋯, w_{k−1}} such that:

∧{η(f(i))[w_{i_{0}}, ⋯, w_{i_{n−1}}] : i ∈ S(n, k)}.

(iv) The C_{r}’s are pairwise disjoint.

Proof. We shall construct the structure ⟨W, C_{r}⟩_{r∈R} by a routine step by step fashion. We note that condition (ii) follows from (iii). Often, however, we will only need (and refer to) the weaker condition (ii), hence the redundancy in the formulation of Lemma 1. Let

Q = ∪{^{k}(|R|) ×^{S(n,k)} Cof^{+}(R) : k < ω}

.

Then |Q| = |R| = μ, say. We will construct a set W with cardinality μ. Q is intended to represent all the instances of condition (iii), as follows: An element of Q is of the form ⟨α_{0}, ⋯, α_{k−1}, f⟩, where α_{0}, ⋯, α_{k−1} < μ and f : S(n, k) → Cof^{+}(R). This represents the instance of (iii) where we take k, w_{α_{0}}, ⋯, w_{α_{k−1}}, f as the concrete values of the quantified items in (iii). Let ρ be an enumeration of Q such that :

For all l < μ, for all q ∈ Q, there exists j, with l < j < μ, such that ρ(j) = q. Such a ρ clearly exists. Fix a well ordering ≺ of R. Let l < μ, and suppose that for all i < l we have already defined the element w_{i}, and the n-ary relation C_{r}^{i} ⊆ ^{n}W_{i}, where W_{i} = {w_{k} : k < i}. In the l’th step we will make the ρ(l)’th instance of (iii) true. Assume that ρ(l) = ⟨α_{0}, ⋯, α_{k−1}, f⟩. Then α_{0}, ⋯, α_{k−1} < μ and f : S(n, k) → Cof^{+}R, for some k. (k = 0 is allowed, too). Let w_{l} be an element not in ∪{W_{i} : i < l}. If there exists i < k such that l ≤ α_{i}, then for all r ∈ R, we define C_{r}^{l} = ∪{C_{r}^{i} : i < l}. Else, l > α_{i} for all i < k. In this case, let v_{0} = w_{α_{0}}, ⋯, v_{k−1} = w_{α_{k−1}} and v_{k} = w_{l}. For all r ∈ R we define:

X_{r}^{l} = {⟨v_{i_{0}}, ⋯, v_{i_{n−1}}⟩ : i_{0} ≤ ⋯ ≤ i_{n−1} = k
and r is the ≺-least element of f(⟨i_{0}, ⋯, i_{n−1}⟩)}

and

C_{r}^{l} = ∪{C_{r}^{i} ∪ {⟨s_{π(0)}, ⋯, s_{π(n−1)}⟩ : s ∈ X_{r}^{l}, π is a permutation of n} : i < l}.

Finally set

W = ∪{W_{l} : l < μ} and C_{r} = ∪{C_{r}^{l} : l < μ}

Now we are going to check that the structure ⟨W, C_{r}⟩_{r∈R} , so defined, satisfies conditions (i)-(iv). To this end, for any l < μ and r ∈ R let

Y_{r}^{l} = {⟨s_{π(0)}, ⋯, s_{π(n−1}⟩ : s ∈ X_{r}^{l} and π is a permutation on n}

and

D_{r}^{l} = ∪{C_{r}^{j} : j < l}.

Then for all r ∈ R we have C_{r}^{l} = Y_{r}^{l} ∪ D_{r}^{l}. Also, the following are not difficult to check:

(1) w_{l} ∈ Rgs (the range of s) if s ∈ Y_{r}^{l}, and w_{l} ∉ Rgs if s ∈ D_{r}^{l}.

(2) C_{r}^{j} ⊆ C_{r}^{m} if j ≤ m < μ.

It is easy to show by induction on l < μ that for all r ∈ R, C_{r}^{l} is symmetric, thus C_{r} is symmetric, and so (i) holds.

Let r, p ∈ R be distinct. We want to show by induction on l < μ that C_{r}^{l} and C_{p}^{l} are disjoint. Now D_{r}^{l} and D_{p}^{l} are disjoint by the induction hypothesis and by (2). By (1), it is therefore, enough to show that Y_{r}^{l} and Y_{p}^{l} are disjoint. Assume s ∈ Y_{r}^{l}, and let ρ(l) = ⟨α_{0}, ⋯, α_{k−1}, f⟩ and v = ⟨v_{0}, ⋯, v_{k}⟩ = ⟨w_{α_{0}}, ⋯, w_{α_{k−1}}, w_{l}⟩. Then v is one to one and there are a unique i ∈ S(n, k) and permutation π of n such that s = ⟨z_{π(0)}, ⋯, z_{π(n−1)}⟩, where z = ⟨v_{i_{0}}, ⋯, v_{i_{n−1}}⟩ ∈ X_{r}^{l}. Thus r is the ≺- least element of f(i), by z ∈ X_{r}^{l}. Since p ≠ r, we get that z ∉ X_{p}^{l}, and so z ∉ Y_{p}^{l}. We have shown that C_{r}^{l} and C_{p}^{l} are disjoint. By (2) condition (iv) holds. Finally we check condition(s) (iii) (and (ii)): Let k < ω, w_{α_{0}}, ⋯, w_{α_{k−1}} ∈ W and f : S(n, k) → Cof^{+}R. Let l < μ be such that ρ(l) = ⟨α_{0}, ⋯, α_{k−1}, f⟩ and l > α_{0}, ⋯, l > α_{k−1}. Such an l exists by the properties of ρ. Then it is not difficult to check that we constructed the w_{l} so that it satisfies ϕ = ∧{η(f(i))(w_{α_{i_{0}}}, w_{α_{i_{1}}}, ⋯, w_{α_{i_{n−2}}}, x_{i_{n−1}}) : i ∈ S(n, k)} in ⟨W_{l}, C_{r}^{l}⟩_{r∈R}. By (1) and (2) we have C_{r}^{l} = ^{n}W_{l} ∩ C_{r} and so ϕ is satisfied in ⟨W, C_{r}⟩_{r∈R}, as well. By this the proof of Lemma 1 is complete.

Remarks .

(a) Notice that by the construction of W, |W | = |R|. In particular, W is also an uncountable set.

(b) We have excluded the empty set from Cof^{+}R in order that (iii) can be satisfied, because η(∅) is false for any relations C_{r}. Notice that condition (iii) in Lemma 1, is a “saturation condition” on W. It will be used in the proof of fact 2.1 below, to show that the structure ⟨W, C_{r}⟩_{r∈R} admits elimination of quantifiers in a rather strong sense.

(c) We note that condition (iii) in Lemma 1, can be proved using a game theoretic approach, along the lines adopted in [HH97a].

Notation . Let W = ⟨W, C_{r}⟩_{r∈R} with C_{r} ⊆ ^{n}W, be the relational structure described in Lemma 1. Let U = W × {0} ∪ W × {1} ⋯ ∪ W × {n − 1}. U is simply n disjoint copies of W. Let β be an ordinal, then C(β) = ⟨Sb(^{β}U), ∪, ∩, −, c_{i}, d_{ij}⟩_{i,j∈β}, denotes the full Cs_{β}, with unit ^{β}U. S_{n} denotes the set of permutations on n . Let f be a function, then f = ⟨f_{x} : x ∈ domf⟩ and ker(f) = {(x, y) ∈ ^{2}domf : f_{x} = f_{y}}.

Defining our algebras

Let u = ⟨u_{0}, ⋯, u_{n−1}⟩ ∈ S_{n}. Let r ∈ R. Then p(u, r) is the following n-ary relation on U:

{⟨(a_{0}, u_{0}), ⋯, (a_{n−1}, u_{n−1})⟩ ∈ ^{n}U : ⟨a_{0}, ⋯, a_{n−1}⟩ ∈ C_{r}}.

Intuitively, p(u, r) is the relation C_{r} “diagonally embedded” in U, and then permuted along u.

P (u) = {p(u, r) : r ∈ R}.

Let N be a fixed countably infinite subset of R. ^{8} That is N ⊆ R and |N| = ω. Then P_{ω}(u) = {p(u, r) : r ∈ N}.

8We point out that countability of N is not essential. In fact any infinite subset N of R with |N| < |R| will do the job, just as well.

Now we define A(n) ∈ Cs_{n}, and B(n) ⊆ A(n) as follows:

A(n) = Sg^{C(n)}(∪{P (u) : u ∈ S_{n}}).

B(n) = Sg^{A(n)}(∪{P (u) : u ∈ S_{n} − {⟨0, ⋯, n − 1⟩} ∪ P_{ω}(⟨0, ⋯, n − 1⟩)).

Plan of the proof

We will show that:

1. A(n) ∈ INr_{n}W s_{β}, for all β > n.

See fact 2.4 below.

2. A(n) is elementary equivalent to B(n).

See fact 3.3 below.

3. B(n) ∉ Nr_{n}CA_{β}, for all β > n.

See fact 4.3 below.

From (1),(2) and (3), Theorem 1 for α = n and β > α will immediately follow, since W s_{β} ⊆ Cs_{β} ⊆ Gs_{β} ⊆ CA_{β}. Actually (1),(2) and (3) will show, as previously noted, that for any β > n and any L such that W s_{β} ⊆ L ⊆ CA_{β} , the class Nr_{n}L is not closed under forming elementary subalgebras, hence not elementary.

§2. A(n) IS A NEAT REDUCT

In this section, we will show that A(n) ∈ INr_{n}(W s_{β}), for all β > n. This will be done in two steps. First we will show that A(n) ∈ ∩_{n≤k<ω}INr_{n}Cs_{k}. Then we will show that A(n) ∈ INr_{n}W s_{β}, for infinite β.

Convention . As is standard practice, we do not distinguish between an algebra A, and its universe A.

Notation . L_{ω} denotes the (usual) first order language of W, the subscript ω indicating that all ω variables are available. F m^{L_{ω}} stands for the set of all L_{ω} formulas. For ϕ ∈ F m^{L_{ω}}, var(ϕ) denotes the set of all variables occurring in ϕ.

To show that A(n) ∈ ∩_{n≤k<ω}INr_{n}Cs_{k}, we need:

Some more Definitions.

Let n ≤ k < ω, u = ⟨u_{0}, u_{1}, ⋯, u_{k−1}⟩ ∈ ^{k}n and ϕ ∈ F m^{L_{ω}} with var(ϕ) ⊆ {x_{0}, ⋯, x_{k−1}}. Then E(u, ϕ) is the following k-ary relation on U:

{⟨(a_{0}, u_{0}), ⋯, (a_{k−1}, u_{k−1})⟩ ∈ ^{k}U : W ⊧ ϕ[a_{0}, ⋯, a_{k−1}]}.

Notice that when k = n and ϕ is C_{r}(x_{0}, ⋯, x_{n−1}), then E(u, C_{r}(x_{0}, ⋯, x_{n−1})) is the same as p(u, r). Eq(u) stands for the set {x_{i} = x_{j}, x_{i} ≠ x_{j} : (i, j) ∈ ker(u)}. We identify the formulas x_{i} = x_{i}, and x_{i} ≠ x_{i} with the propositional constants T and F, standing for “True” and “False”, respectively. In particular, {T, F } ⊆ Eq(u), for any u ∈ ^{k}n. Let u ∈ ^{k}n. Then

F_{k}(u) = {C_{r}(x_{i_{0}}, ⋯, x_{i_{n−1}}), ¬ C_{r}(x_{i_{0}}, ⋯, x_{i_{n−1}}) : r ∈ R, i ∈ ^{n}k,
and |{u_{i_{0}}, ⋯, u_{i_{n−1}}}| = n} ∪ Eq(u).

Forming finite conjunctions of formulas in F_{k}(u), set

F_{k}(u)^{∗} = {∧J : J ⊆_{ω} F_{k}(u)}.

Here, and elsewhere, ⊆_{ω} abbreviates “finite subset”.

Forming finite disjunctions of formulas in F_{k}(u)^{∗}, set

F_{k}(u)^{∗∗} = {∨J : J ⊆_{ω} F_{k}(u)^{∗}}.

Now let

G(k) = {E(u, ϕ) : u ∈ ^{k}n, ϕ ∈ F_{k}(u)^{∗∗}} and
G(k)^{∗} = {∪J : J ⊆_{ω} G(k)}.

We will show that G(k)^{∗} is (the universe of) a Cs_{k} and that A(n) ≅ Nr_{n}G(k)^{∗} for all n ≤ k < ω. Then we form a W s_{β} for infinite β as a “limit” of the G(k)^{∗}’s (n ≤ k < ω); A(n) will be the neat n − reduct of this limit.

Fact 2.1. G(k)^{∗} ∈ Cs_{k}, for all n ≤ k < ω.

To prove fact 2.1 and fact 2.3 below, we shall need (and prove) the following rather easy consequence of Lemma 1 :

(*) Let u ∈ ^{k}n and ϕ ∈ F_{k}(u)^{∗}. Then for all i < k and all v ∈ ^{k}n that differs from u in at most the ith place, there exists ψ ∈ F_{k}(v)^{∗}, such that x_{i} ∉ var(ψ) and W ⊧ ∃x_{i}ϕ ≡ ψ. Here, and elsewhere ≡ abbreviates “(semantically) equivalent to”.

Notation . Let ϕ ∈ F m^{L_{ω}}, and i, j ∈ ω. Then ϕ[i|j] stands for the formula obtained from ϕ, by replacing all (free and bound) ocurrances of x_{i} in ϕ by x_{j}.

Let v, u ∈ ^{k}n. Then v ≡_{i} u, abbreviates “v differs from u in at most the ith place”.

Proof of (*). Fix u ∈ ^{k}n, ϕ ∈ F_{k}(u)^{∗}, i < k, and v ≡_{i} u. Then ϕ = ∧J, for some J ⊆_{ω} F_{k}(u). Let J^{+} = {ψ ∈ J : x_{i} ∈ var(ψ)} and J^{−} = J − J^{+}. Then ∧J^{−} ∈ F_{k}(v)^{∗}, x_{i} ∉ var(∧J^{−}), and W ⊧ ∃x_{i}ϕ ≡ ∃x_{i}(∧J^{+}) ∧ (∧J^{−}).

It suffices, therefore, to show that W ⊧ ∃x_{i}(∧J^{+}) ≡ ψ for some ψ ∈ F_{k}(v)^{∗}. Case (a): x_{i} = x_{j} ∉ J^{+} and x_{j} = x_{i} ∉ J^{+} for all j < k. For j ∈ S(n, k) put

π(j) = {r ∈ R : C_{r}(x_{y_{0}}, ⋯, x_{y_{n−1}}) ∈ J^{+} and {y_{0}, ⋯, y_{n−1}}−{i} = {j_{0}, ⋯, j_{n−2}}}

and

τ(j) = {r ∈ R : ¬C_{r}(x_{y_{0}}, ⋯, x_{y_{n−1}}) ∈ J^{+} and {y_{0}, ⋯, y_{n−1}}−{i} = {j_{0}, ⋯, j_{n−2}}}.

If x_{l} ≠ x_{l} ∈ J^{+} for some l < k, or π(j) ∩ τ(j) ≠ ∅ for some j ∈ S(n, k), or |π(j)| ≥ 2 for some j ∈ S(n, k), then W ⊧ ∧J^{+} ≡ F and W ⊧ ∃x_{i}(∧J^{+}) ≡ F. Assume therefore that for all l < k, x_{l} ≠ x_{l} ∉ J^{+}, that |π(j)| < 2 and that π(j) ∩ τ(j) = ∅, for all j ∈ S(n, k). Let us define

f : S(n, k) → Cof^{+}R as follows: f(j) = \{ \begin{matrix}π(j) & if π(j) is nonempty, \\ R − τ(j) & otherwise \end{matrix}

Then applying Lemma 1 (iii) to f so defined, amounts to getting for any w_{0}, ⋯, w_{k−1} ∈ W a new element, i.e w_{k} ∈ W − {w_{0}, ⋯, w_{k−1}}, such that

W ⊧ ((∧J^{+})[i|k])[w_{0}, ⋯, w_{k}], i.e.W ⊧ ∃x_{k}((∧J^{+})[i|k]) ≡ T.

But since x_{k} does not occur in ∧J^{+}, we have W ⊧ ∃x_{k}((∧J^{+})[i|k])) ≡ ∃x_{i}(∧J^{+}) ≡ T. Since {T, F } ⊆ F_{k}(v)^{∗}, and x_{i} does not occur in either of them, we are done. Case (b): there is an m < k such that x_{i} = x_{m} ∈ J^{+} or x_{m} = x_{i} ∈ J^{+}. We can and will assume that x_{i} = x_{m} ∈ J^{+} and that i ≠ m. Thus ∧J^{+} is of the form (∧I) ∧ x_{i} = x_{m}. Claim. (∧I)[i|m] ∈ F_{k}(v)^{∗}, from which our conclusion readily follows, since W ⊧ ∃x_{i}(∧J^{+}) ≡ (∧I)[i|m].

Proof of Claim: Let ϕ ∈ I Subcase (a): ϕ is of the form x_{j} = x_{i}, where j, i and m are pairwise distinct. Then v(j) = v(m) because u(i) = u(j) = u(m), by (i, j), (j, m) ∈ ker(u) and since u ≡_{i} v. By definition, we then have x_{j} = x_{m} ∈ F_{k}(v). Subcase (b): ϕ is of the form D_{r}(x_{y_{0}}, ⋯, x_{y_{n−1}}), where D_{r} ∈ {C_{r}, ¬C_{r}}. By definition of F_{k}(u), we have |{u_{y_{0}}, ⋯, u_{y_{n−1}}}| = n. Assume that y_{l} = i, with 0 ≤ l < n. Then |{u_{y_{0}}, .u_{y_{l}}, ⋯, u_{y_{n−1}}}| = |{u_{y_{0}}, .u_{i}, ⋯, u_{y_{n−1}}}| = n. By u(i) = u(m) (since (i, m) ∈ ker(u)), and v ≡_{i} u, we have |{u_{y_{0}}, .u_{m}, ⋯, u_{y_{n−1}}}| = |{v_{y_{0}}, .v_{m}, ⋯, v_{y_{m−1}}}| = n. But this implies that D_{r}(x_{y_{0}}, ⋯, x_{y_{n−1}})[i|m] ∈ F_{k}(v). From the subcases (a) and (b) we get (∧I)[i|m] ∈ F_{k}(v)^{∗}.

Let everything be as in (*) and suppose further, that l ≤ k. For brevity let v ∈ ^{l}n denote u ↾ l. Then an easy consequence of (*) is:

(**) There exists ψ ∈ F_{l}(v)^{∗}, such that

W ⊧ ∃x_{l} ⋯ ∃x_{k−1}ϕ ≡ ψ.

Proof of (**). Applying (*) successively we obtain ψ in F_{k}(u)^{∗}, such that {x_{l}, ⋯, x_{k−l}} ∩ var(ψ) = ∅ and W ⊧ ∃x_{l} ⋯ ∃x_{k−l}ϕ ≡ ψ. By noting that F_{l}(v)^{∗} = {ϕ ∈ F_{k}(u)^{∗} : var(ϕ) ⊆ {x_{0}, ⋯, x_{l−1}}} we get the desired. Proof of fact 2.1.

(1) G(k)^{∗} is closed under the boolean set operations.

It is enough to show that for all g_{1}, g_{2} ∈ G(k), g_{1} ∩ g_{2} and ^{k}U − g_{1} are in G(k)^{∗}. To this end, let u, v ∈ ^{k}n, ϕ ∈ F_{k}(v)^{∗∗} and ψ ∈ F_{k}(u)^{∗∗}. Then as easily checked E(u, ϕ) ∩ E(v, ψ) = E(u, ϕ ∧ ψ) if u = v and is zero otherwise, while ^{k}U − E(u, ϕ) = ∪{E(v, T) : v ∈ ^{k}n − {u}} ∪ E(u, ¬ϕ). From the definition of G(k)^{∗}, and by noting that for u ∈ ^{k}n, ϕ and ψ ∈ F_{k}(u)^{∗∗}, there exist η and θ ∈ F_{k}(u)^{∗∗}, such that W ⊧ ϕ ∧ ψ ≡ η and W ⊧ ¬ϕ ≡ θ, we get the desired.

(2) G(k)^{∗} contains the diagonals.

Let i < j < k. Then d_{ij} = ∪{E(u, x_{i} = x_{j}) : u ∈ ^{k}n, u_{i} = u_{j}} and so, by definition of F_{k}(u), d_{ij} ∈ G(k)^{∗}.

(3) G(k)^{∗} is closed under cylindrifications.

Let g ∈ G(k)^{∗}, and i < k. We will show that c_{i}g ∈ G(k)^{∗}. Since the c′_{i}s(∃) distribute(s) over joins (∨), we can assume that g = E(u, ϕ), with u ∈ ^{k}n and ϕ ∈ F_{k}(u)^{∗}. Now c_{i}g = c_{i}E(u, ϕ) = ∪{E(v, ∃x_{i}ϕ) : v ≡_{i} u}. By (*), we get that c_{i}g ∈ G(k)^{∗}.

Fact 2.2. A(n) = G(n)^{∗}.

Proof. Since P = ∪{P (u) : u ∈ S_{n}} ⊆ G(n)^{∗}, P generates A(n) and G(n)^{∗} ∈ Cs_{n}, we have A(n) ⊆ G(n)^{∗}. For the other inclusion, it is obviously enough to show that for any u ∈ ^{n}n and ϕ ∈ F_{n}(u), we have E(u, ϕ) ∈ A(n). We shall start by showing that E(u, T) ∈ A(n), for all u ∈ ^{n}n. Case (a): u ∈ S_{n}, i.e u is one to one. Let r ∈ R. Then by Lemma 1(ii) we have

∩_{i<n}{c_{i}(E(u, C_{r}(x_{0}, ⋯, x_{n−1}))} = ∪{E(v, T) : v ≡_{i} u, for all i < n} = E(u, T).

Case (b): u is not one to one. Suppose then that |Rgu| = l, say with l < n. Let y ∈ ^{l}n, be such that y_{0} < ⋯ < y_{l−1} and {u_{y(0)}, ⋯, u_{y(l−1)}} = Rgu. For i < l, put m_{y(i)} = min u^{−1}(u_{y(i)}), where min is short for minimum. Choose v ∈ S_{n} such that v(m_{y(i)}) = u_{y(i)}. Such a v, clearly, exists. Let J = n − {m_{y(0)}, ⋯, m_{y(l−1)}}; suppose that J = {j_{0}, ⋯, j_{n−(l+1)}} with j_{0} < ⋯ < j_{n−(l+1)}. For i, l ∈ n, set t_{i}^{l}x = c_{l}x ∩ d_{il}. A straightforward computation yields

t_{u_{j(n−(l+1))}}^{j(n−(l+1))} ∘ ⋯ ∘ t_{u_{j(0)}}^{j(0)}E(v, T) = E(u, T).

From case (a), it follows that E(u, T) ∈ A(n). Now let u ∈ ^{n}n, and suppose that (i, j) ∈ ker(u) with i < j. Then

E(u, x_{i} = x_{j}) = E(u, T) ∩ d_{ij} ∈ A(n).

Also, for all u, v ∈ S_{n}, we have by Lemma 1 (i) that

E(u, C_{r}(x_{0}, ⋯, x_{n−1})) = E(u, C_{r}(x_{v(0)}, ⋯, x_{v(n−1)})) = p(u, r).

Finally by noting that E(u, ¬ϕ) = E(u, T) − E(u, ϕ) for all u ∈ ^{n}n, and ϕ ∈ F_{n}(u); we get the desired.

Fact 2.3. For n ≤ l ≤ k < ω, we have G(l)^{∗} ≅ Nr_{l}G(k)^{∗}. In particular A(n) ∈ ∩_{n≤k<ω}INr_{n}(Cs_{k}).

Proof. Let n ≤ l < k. Recall that C(k) denote the full Cs_{k} with unit ^{k}U. Let i(l, k) be the function with domain G(l)^{∗} such that

i(l, k)a = {t ∈ ^{k}U : (t ↾ l) ∈ a}.

Then i(l, k) : G(l)^{∗} → C(k). Also, by [HMT2] 3.1.122, we have i(l, k) ∈ Ism(G(l)^{∗}, Nr_{l}C(k)). Now fix n ≤ l < k < ω. We will show that i(l, k)G(l)^{∗} ⊆ G(k)^{∗}. To this end let v ∈ ^{l}n, and ϕ ∈ F_{l}(v). Then i(l, k)E(v, ϕ) = ∪{E(u, ϕ) : u ∈ ^{k}n, and u ↾ l = v}. The latter is in G(k)^{∗}, because F_{l}(v)^{∗∗} ⊆ F_{k}(u)^{∗∗}, whenever v = u ↾ l. But G(k)^{∗} ∈ Cs_{k}, and so i(l, k)E(v, ϕ) ∈ G(k)^{∗} for any v ∈ ^{l}n and ϕ ∈ F_{l}(v)^{∗∗}, whence the desired. By Nr_{l}G(k)^{∗} = G(k)^{∗} ∩ Nr_{l}C(k), we get i(l, k) ∈ Ism(G(l)^{∗}, Nr_{l}G(k)^{∗}). We will now show that i(l, k) is actually onto Nr_{l}G(k)^{∗}, i.e that i(l, k)G(l)^{∗} = Nr_{l}G(k)^{∗}. Since the c′_{i}s are additive, it suffices to show that for all g ∈ G(k), there exists a ∈ G(l)^{∗} such that i(l, k)a = c_{l}c_{l+1} ⋯ c_{k−1}g. So let g ∈ G(k) be as indicated above. Suppose that g = E(u, ϕ) say, with u ∈ ^{k}n and ϕ ∈ F_{k}(u)^{∗∗}. Suppose further, that ϕ = ϕ_{0} ∨ ⋯ ϕ_{m}, where ϕ_{j} ∈ F_{k}(u)^{∗}, for 0 ≤ j ≤ m. For brevity, let v (∈ ^{l}n) denote u ↾ l. By (**), for each j, with 0 ≤ j ≤ m, there exists ψ_{j} ∈ F_{l}(v)^{∗} such that i(l, k)E(v, ψ_{j}) = c_{l}c_{l+1} ⋯ c_{k−1}E(u, ϕ_{j}).

Now

c_{l}c_{l+1} ⋯ c_{k−1}E(u, ϕ) = c_{l}c_{l+1} ⋯ c_{k−1}E(u, ϕ_{0} ∨ ⋯ ϕ_{m})
= c_{l}c_{l+1} ⋯ c_{k−1}E(u, ϕ_{0}) ∪ ⋯ ∪ c_{l}c_{l+1} ⋯ c_{k−1}E(u, ϕ_{m})
= i(l, k)(E(v, ψ_{0}) ∪ ⋯ ∪ i(l, k)E(v, ψ_{m})
= i(l, k)(E(v, ψ_{0} ∨ ⋯ ψ_{m}).

Since by definition ψ_{0} ∨ ⋯ ∨ ψ_{l} ∈ F_{k}(v)^{∗∗}, we are done. Taking l = n, we get, from fact 2.2, that i(n, k)A(n) = Nr_{n}G(k)^{∗}, for all n ≤ k. Since i(n, k)A(n) ≅ A(n), we get that A(n) ∈ INr_{n}Cs_{k} = INr_{n}W s_{k}, for all n ≤ k < ω.

Fact 2.4. A(n) ∈ INr_{n}Cs_{β}, for all β > n.

Proof. By fact 2.3, it suffices to show that A(n) ∈ INr_{n}Cs_{β} for all β ≥ ω. To this end, fix β ≥ ω. Let G(β) = Sg^{C(β)}{i(k, β)G(k)^{∗} : n ≤ k < ω}. Like in fact 2.3, here C(β) denotes the full Cs_{β} with unit ^{β}U and for a ∈ G(k)^{∗}, i(k, β)a = {s ∈ ^{β}U : s ↾ k ∈ a}. Let a ∈ G(β). We will show that a ∈ Nr_{n}G(β) iff a ∈ i(n, β)A(n), i.e that i(n, β)A(n) = Nr_{n}G(β). First note that ∪{i(k, β)G(k)^{∗} : n ≤ k < ω} is a subuniverse of G(β). This is straightforward. Thus G(β) = ∪{i(k, β)G(k)^{∗} : n ≤ k < ω}. It then follows that a = i(l, β)g, for some n ≤ l < ω and g ∈ G(l)^{∗}. Now suppose that a ∈ Nr_{n}G(β). Then g = c_{j}g for all n ≤ j < l, and so g ∈ Nr_{n}G(l)^{∗}. By fact 2.3 we have Nr_{n}G(l)^{∗} = i(n, l)A(n), thus g = i(n, l)g′, say, for some g′ ∈ A(n). But a = i(l, β)g = i(l, β)∘i(n, l)g′ = i(n, β)g′. This shows that a ∈ i(n, β)A(n). Conversely, if a ∈ i(n, β)A(n) then again by fact 2.3 we have a ∈ Nr_{n}G(β). We have shown that i(n, β)A(n) = Nr_{n}G(β). Since A(n) ≅ i(n, β)A(n), we get A(n) ∈ INr_{n}Cs_{β}.

Notation . Let β be an ordinal. Then Cs_{β}^{reg} and Lf_{β} stand for the classes of regular cylindric set algebras and locally finite cylindric algebras of dimension β, respectively.

It is known (see eg [HMT2] sec 4.3) that for β ≥ ω, the class ICs_{β}^{reg} ∩ Lf_{β} relates CA theory to models of first order logic. ^{9}

Fact 2.5. A(n) ∈ INr_{n}W s_{β}, for all β > n Proof. It remains to show that A(n) ∈ INr_{n}W s_{β} for all β ≥ ω. Fix β ≥ ω and let F (β) = Sg^{G(β)}A(n). Then as easily checked F (β) ∈ Cs_{β}^{reg} ∩ Lf_{β}, and A(n) ≅ Nr_{n}F (β). From ICs_{β}^{reg} ∩ Lf_{β} ⊆ IW s_{β}, (cf [HMT2] 3.1.70) and INr_{n}W s_{β} = Nr_{n}IW s_{β}, we get the desired.

9The class of the so called locally finite regular cylindric set algebras is introduced in [AN75], and [AGN77] to investigate connections between (models of) first order logic and CA’s. More information about these connection can be found in [N83] and the references therein. In the above quoted papers this class was denoted by Lr. The notation we use here, is the more “official one” , namely that adopted in [HMT2] sec 4.3

§3. A(n) AND B(n) ARE ELEMENTARY EQUIVALENT

In this section we will show that A(n) admits a particularly rich set of automorphisms, a property we use to show that B(n) is elementary equivalent to A(n).

Notation . For u = ⟨u_{0}, ..u_{n−1}⟩ ∈ ^{n}n, we let 1_{u_{0}...u_{n−1}} and sometimes simply 1_{u} denote E(u, T). For a ∈ A(n) and X ⊆ A(n), Rl_{a}X = {x ∈ X : x ≤ a}.

Fact 3.1. Let u ∈ S_{n}. Then the following hold:

(i) Rl_{1_{u}}A(n) = {E(u, ϕ) : ϕ ∈ F (u)^{∗∗}}. Furthermore Rl_{1_{u}}A(n) is atomic 10 and its set of atoms is equal to P (u).

(ii) For all nonzero a ∈ Rl_{1_{u}}A(n), for all i < n, c_{i}a = c_{i}1_{u}.

(iii) For all a ∈ A(n), for all i < n, c_{i}a ∩ 1_{u} ∈ {0, 1_{u}}.

Proof. (i) follows from fact 2.2, and Lemma 1 (iv). Now let a ∈ Rl_{1_{u}}A(n). Then a ≤ 1_{u}. By fact 3.1 (i) a = E(u, ϕ), for some ϕ ∈ F_{n}(u)^{∗∗}. Suppose 0 ≠ a, and i < n. Then by fact 3.1 (ii) there exists an atom in Rl_{1_{u}}A(n) below a, i.e an r ∈ R, such that E(u, C_{r}(x_{0}, ..x_{n−1})) = p(u, r) ≤ a. By Lemma 1(ii), c_{i}1_{u} = c_{i}p(u, r) ≤ c_{i}a ≤ c_{i}1_{u}. This proves (ii). (iii) easily follows from (ii).

Remark . {1_{u} : u ∈ ^{n}n} is a (finite) partition of the unit 1 of A(n). That is ∪{1_{u} : u ∈ ^{n}n} = 1, and 1_{u} ∩ 1_{v} = 0, for distinct u and v. When u ∈ S_{n}, then P (u) constitutes further an (uncountable) partition of 1_{u}, that is also a splitting of 1_{u}, in the sense of [An98]. This means that every element in P (u) is cylindrically equivalent to 1_{u}, i.e c_{i}x = c_{i}(1_{u}) for every i < n and every x ∈ P (u). So in a sense (at least in the above one ) , the elements in P (u) are “big”. Bieng atoms in Rl_{1_{u}}A(n) (and even more, as easily checked, in A(n)), they are also “small”. Andreka [An98] refers to such elements as big atoms. It is precisely the “duality” in the nature of such elements (the big atoms) that will enable us, in fact 3.2 below, to extend given permutations on the set P = ∪{P (u) : u ∈ S_{n}} , generating A(n), to automorphisms on A(n). A(n) in this respect, resembles the free structure on P.

10A boolean algebra is atomic if every non zero element contains an atom. An atom is a minimal non zero element.

Fact 3.2. Let P = ∪{P (u) : u ∈ S_{n}}. Let L = 1_{01..n−1}. Let p be a permutation of P (⟨0, .., n−1⟩). Then there exists an automorphism f of A_{n} such that p ⊆ f and f ↾ (P − P (⟨0, ..n − 1⟩)) = Id.

Proof. Let p be a given permutation of P (⟨0, .., n − 1⟩). By fact 3.1 (i) , Rl_{L}A(n) is generated as a BA, by the set P (⟨0, .., n − 1⟩) of atoms. It follows from BA theory, that there exists an automorphism p′, say of BlRl_{L}A(n), such that p ⊆ p′.

For x ∈ A, define f(x) = p′(x ∩ L) ∪ (x ∩ −L). We will show that f is the desired automorphism. Clearly f is a BA automorphism of BlA(n), such that p′ ⊆ f and f ↾ (P − P (⟨0, .., n − 1⟩) = Id. So all we have to do is check that f preserves the extra CA operations.

(1) Diagonals:

Let i < j ∈ n. Then

f(d_{ij}) = p(d_{ij} ∩ L) ∪ (d_{ij} ∩ −L) = d_{ij} ∩ −L = d_{ij}.

(2) Cylindrifications:

Let x ∈ A(n) and i ∈ n. On the one hand,

c_{i}f(x) = c_{i}((p′(x ∩ L) ∪ (x ∩ −L)) = c_{i}p(x ∩ L) ∪ c_{i}(x ∩ −L)
= by fact 3.1 (ii) c_{i}(x ∩ L) ∪ c_{i}(x ∩ −L) = c_{i}x.

On the other hand,

f(c_{i}x) = p′(c_{i}x∩L)∪(c_{i}x∩−L) = by fact 3.1 (iii) (c_{i}x∩L)∪(c_{i}x∩−L) = c_{i}x.

We have shown , that for all x ∈ A(n) and i ∈ n, we have c_{i}f(x) = f(c_{i}x) = c_{i}x. 11 By this the proof is complete.

Fact 3.3. A(n) is elementary equivalent to B(n).

Proof. We shall use the Tarski-Vaught criterion to show that B(n) is an elementary submodel of A(n). So let ∃x_{n}ϕ(x_{0}, ...x_{n}) be any first order formula in the language of CA_{n}. Suppose that b_{0}, ...b_{n−1} ∈ B(n), and that A(n) ⊧ ϕ(b_{0}, ..., b_{n−1}, a), for some a ∈ A(n). We want to find b_{n} ∈ B(n), such that A(n) ⊧ ϕ(b_{0}, .., b_{n}).

Since A(n) is generated by P = ∪{P (u) : u ∈ S_{n}}, there exists a finite subset H_{0} of P, such that a ∈ Sg^{A(n)}H_{0}. Let X = ∪{P (u) : u ∈ S_{n}−{⟨0, 1..n− 1⟩} ∪ P_{ω}(⟨0, 1..n − 1⟩). Since b_{0}, ...b_{n−1} ∈ B(n) and B(n) is generated by X, then there exists a finite subset H_{1} of X, such that (H_{0} ∩ B) ∪ {b_{0}, ...b_{n−1}} ⊆ Sg^{B(n)}H_{1}.

11We used the “bigness” condition to show that f preserves cylindrifications. Loosely speaking, when a cylindric algebra is generated by a set of big atoms, then we can “forget about” cylindrifications when constructing automorphisms on A

Let p be a permutation of P (⟨0, ..n−1⟩) such that p ↾ P (⟨0, ..n−1⟩)∩H_{1} ⊆ Id and p(H_{0} − H_{1}) ⊆ P (⟨0, 1, ..n − 1⟩) ∩ B(n). Such a permutation, clearly, exists. By fact 3.2 p extends to an automorphism f of A(n) such that p ⊆ f and f ↾ (P − P (⟨0, .., n − 1⟩)) = Id. But A(n) ⊧ ϕ(b_{0}, .., b_{n−1}, a) and so A(n) ⊧ ϕ(f(b_{0}), .., f(b_{n−1}), f(a)). By f ↾ H_{1} ⊆ Id and {b_{0}, ..b_{n−1}} ⊆ Sg^{B(n)}H_{1}, it follows that f(b_{i}) = b_{i}, for all i < n. Since f(H_{0}) ⊆ B and a ∈ Sg^{A(n)}H_{0}, we get f(a) ∈ B. This completes the proof.

§4. B(n) IS NOT A NEAT REDUCT In this section we will show that B(n) ∉ Nr_{n}CA_{n+1}. Since for n < α < β, Nr_{n}CA_{β} ⊆ Nr_{n}CA_{α} (cf. [HMT1], 2.6.31) and CA_{β}

is the largest of the classes mentioned in Theorem 1, this completes the proof of Theorem 1, when α = n and β > n.

Fact 4.1. (i) For all u ∈ ^{n}n, 1_{u} = E(u, T) ∈ B(n).

(ii) |Rl_{L}B(n)| = ω

Proof.

(i) Let u ∈ S_{n}, and r ∈ N. Then by Lemma 1(ii),

∩_{i<n}{c_{i}E(u, C_{r}(x_{0}, ..., x_{n−1})} = E(u, T).

If u is not one to one, proceed as in the proof of case (b) in fact 2.2 above.

(ii) Let X = ∪{P (u) : u ∈ S_{n} − {⟨0, ...n − 1⟩} ∪ P_{ω}(⟨0, ...n − 1⟩).

Recall that P_{ω}(⟨0, .., n − 1⟩) = {p(⟨0, ..., n − 1⟩, r) : r ∈ N} and that B(n) = Sg^{A(n)}(X).

Let Y = {c_{i}^{A(n)}a : a ∈ A(n) and i < n} ∪ {d_{ij} : i, j ∈ n} and let D(n) = Sg^{BlA(n)}(X ∪ Y). Then by lemma 1(ii) (see also the proof of fact 3.1 (iii) ), |Y | ≤ ω, and D(n) is a clearly a subuniverse of A(n), containing X. Therefore B(n) ⊆ D(n), (In fact, by fact 3.1 (i), B(n) = D(n), but we do not need that much), and so Rl_{L}B(n) ⊆ Rl_{L}D(n). It clearly suffices to show that |Rl_{L}D(n)| ≤ ω. Towards this, let rl_{L} denote the following endomorphism of ⟨A(n), ∪, ∩, −⟩:

rl_{L}(a) = a ∩ L for a ∈ A(n).

Then Rl_{L}D(n) = Sg^{BlA(n)}rl_{L}(X ∪ Y). But rl_{L}(X ∪ Y) is countable because rl_{L}(X) = P_{ω}(⟨0, ...n − 1⟩), and |Y | ≤ ω. Therefore Rl_{L}D(n), generated as a BA by a countable set, is also countable.

Notation . Let t(x) denote the CA_{2} term s_{1}^{0}c_{1}x ∩ s_{0}^{1}c_{0}x. Let α > 1. Then αs(0, 1) denotes the CA_{α+1} substitution term as defined in 1.5.12 of [HMT1].

Fact 4.2. (i) t^{B(n)}(1_{10...n−1}) = 1_{01..n−1}.

(ii) For all β > n, CA_{β} ⊧ _{n}s(0, 1)c_{n}x ≤ t(c_{n}x).

(iii) For all β > n and A ∈ CA_{β}, _{n}s(0, 1) ∈ Ism(BlNr_{n}A, BlNr_{n}A).

Proof.

(i) For brevity set 1_{10} = 1_{10..n−1}, and 1_{01} = 1_{01...n−1}. By [HMT1], 1.5.1, we

have

t^{B(n)}(1_{10}) = c_{0}(d_{01} ∩ c_{1}1_{10}) ∩ c_{1}(d_{01} ∩ c_{0}1_{10}).

Computing we get:

c_{0}(d_{01} ∩ c_{1}1_{10}) = c_{0}(d_{01} ∩ (∪{1_{u} : u ≡_{1} 1_{10}})
= c_{0}(d_{01} ∩ 1_{11,..,n−1}) = 1_{01} ∪ 1_{11,..n−1}.

A similar computation gives:

c_{1}(d_{01} ∩ c_{0}1_{01}) = 1_{00..n−1} ∪ 1_{01}.

Therefore t^{B(n)}(1_{10}) = 1_{01}.

(ii) By [HMT1], 1.5.12,1.5.8 and 1.5.10(ii), we have:

ns(0, 1)c_{n}x ≤ _{n}s(0, 1)c_{1}c_{n}x = s_{0}^{n}s_{1}^{0}s_{n}^{1}c_{1}c_{n}x = s_{0}^{n}s_{1}^{0}c_{1}c_{n}x
= s_{0}^{n}s_{1}^{0}c_{n}c_{1}x = s_{0}^{n}c_{n}s_{1}^{0}c_{1}x = c_{n}s_{1}^{0}c_{1}x = s_{0}^{1}c_{1}c_{n}x

Similarly, _{n}s(0, 1)c_{n}x ≤ s_{1}^{0}c_{0}c_{n}x.

Therefore _{n}s(0, 1)c_{n}x ≤ t(c_{n}x).

(iii) Let C ∈ CA_{β}, with β > n, and 0 < x ∈ Nr_{n}C. By [HMT1], 1.5.12 and 1.5.1, we have:

ns(0, 1)c_{n}x = s_{0}^{n}s_{1}^{0}s_{n}^{1}c_{n}x = c_{n}(d_{n0} ∩ c_{0}(d_{01} ∩ c_{1}(d_{01} ∩ c_{1}(d_{1n} ∩ c_{n}x))).

By [HMT1], 1.3.8, 0 < x, implies 0 < d_{ij} ∩ c_{j}x, for all i, j ∈ β.

We have shown that if x > 0 ∈ Nr_{n}C, then_{n}s(0, 1)x > 0, i.e that_{n}s(0, 1) is one to one.

Since the s_{i}^{j}’s are BA endomorphisms, it follows from [HMT1], 1.5.12, that _{n}s(0, 1) ∈ Ism(BlNr_{n}C, BlC).

It remains to show that _{n}s(0, 1)x ∈ Nr_{n}C, for all x ∈ Nr_{n}C. But this follows easily from [HMT1], 1.6.13.

Fact 4.3. B(n) ∉ Nr_{n}CA_{n+1}.

Proof. Suppose, seeking a contradiction, that B(n) = Nr_{n}C, say with C ∈ CA_{n+1}. ^{12} Then P (⟨10, .., n − 1⟩) ⊆ Rl_{1_{10...n−1}}Nr_{n}C, and so

|Rl_{1_{10..n−1}}Nr_{n}C| > ω.

By fact 4.2 (iii), |_{n}s(0, 1)^{C}(Rl_{1_{10..n−1}}Nr_{n}C)| > ω. On the other hand,

ns(0, 1)^{C}(1_{10..n−1}) = _{n}s(0, 1)^{C}c_{n}(1_{10..n−1}) (by fact 4.2(ii))
≤ t^{C}c_{n}(1_{10..n−1}) = t^{B}(1_{10..n−1}) (by fact 4.1(i)) = 1_{01..n−1}.

This implies that _{n}s(0, 1)^{C}(Rl_{1_{10..n−1}}Nr_{n}C) ⊆ Rl_{1_{01..n−1}}Nr_{n}C = Rl_{1_{01..n−1}}B. By fact 4.1 (ii) we conclude that |_{n}s(0, 1)^{C}(Rl_{10..n−1}Nr_{n}C| ≤ ω. Contradiction, implying that B(n) ∉ Nr_{n}CA_{n+1}. By establishing fact 4.3, the proof of Theorem 1 for α = n (and β > n) is complete.

§5. THE INFINITE CASE In this section we prove Theorem 1, for α ≥ ω. We also prove Theorem 2. Throughout this section α is a fixed arbitrary ordinal with α ≥ ω and R is

an uncountable set with |R| > |α|.

Notation . Let s be an α-ary sequence, and i < α. Then s_{w}^{i} denotes the α-ary sequence for which: s_{w}^{i}(i) = w and s_{w}^{i}(x) = s(x) for x ≠ i. For a set W, w ∈ W and β an ordinal, we let w denote the β-ary sequence for which w_{i} = w, for all i ∈ β. The arity of w, we hope, will be clear from context.

We start by formulating infinite versions of conditions (ii) and (iv) of Lemma 1.

Lemma 1* . There are a set W, w ∈ W, and α-ary relations C_{r} ⊆ ^{α}W^{(w)} for all r ∈ R, such that conditions (i) and (ii) below hold:

(i) For all r ∈ R, for all i < α, for all s ∈ ^{α}W^{(w)}, there exists y ∈ W − Rgs such that s_{y}^{i} ∈ C_{r}.

(ii) The C_{r}’s (r ∈ R) are pairwise disjoint.

12Apart from being a CA_{n+1}, we impose no further restrictions on C. In particular, C may not be representable. It is only here and in fact 5.3 below that we deal with (possibly)

non representable algebras

The proof can be recovered from that of Lemma 1^{∗∗} below.

Notation . Let W = ⟨W, C_{r}⟩_{r∈R}, with C_{r} ⊆ ^{α}W^{(w)}, be the structure described in Lemma 1*. Let U = ∪_{i∈α}W × {i}. U is simply |α| disjoint copies of W. Let s = ⟨(w, 0), ⋯, (w, j) ⋯ ⟩_{j<α}. Then s ∈ ^{α}U. (Recall that w = ⟨w : i < α⟩). Let V be the weak space^{α}U^{(s)} and let C(α) = ⟨Sb(V), ∪, ∩,- c_{i}, d_{ij}⟩ be the full W s_{α} with unit V. S_{α} denotes the set of one to one functions (equivalently permutations) which are almost everywhere identity, i.e, which are in ^{α}α^{(Id)}.

Defining our algebras

Let u = ⟨u_{0}, u_{1}, ⋯ u_{j} ⋯ ⟩_{j∈α} ∈ S_{α}, and r ∈ R. Then p(u, r) denotes the following α-ary relation on U:

{⟨(a_{0}, u_{0}), ⋯, (a_{j}, u_{j}) ⋯ ⟩_{j<α} ∈ V : ⟨a_{0}, ⋯ a_{j}, ⋯ ⟩_{j<α} ∈ C_{r}}.
P (u) = {p(u, r) : r ∈ R}.

Let N be a fixed countably infinite subset of R. Then P_{ω}(u) = {p(u, r) : r ∈ N}. Now we define A(α) ∈ W s_{α} and B(α) ⊆ A(α) as follows:

A(α) = Sg^{C(α)}(∪{P (u) : u ∈ S_{α}})
B(α) = Sg^{A(α)}((∪{P (u) : u ∈ S_{α} − {Id}) ∪ P_{ω}(Id)).

We shall start by showing that A(α) and B(α) are elementary equivalent, and that B(α) is not a neat reduct. At this point we will be ready to prove Theorem 2 (where we shall only be using the fact that B(α) is not a neat reduct). Then in Lemma 1** below, we shall impose further restrictions on the structure ⟨W, C_{r}⟩_{r∈R}, that will force A(α) to be a neat reduct ( and not just a subneat reduct). These restrictions, are loosely speaking, the infinite versions of conditions (i) and (iii) in Lemma 1, way above.

Working with weak set algebras of infinite dimension, is a little more tedious but, as previously noted, the idea at heart is the same as that of the finite dimensional case. We start by the infinite analogue of facts 3.1, 3.2 and 3.3. The proofs we give are rather sketchy since they are almost identical to the finite case.

Notation . Let u = ⟨u_{0}, u_{1}, ⋯ u_{j} ⋯ ⟩_{j∈α} ∈ ^{α}α^{(Id)}. Then 1_{u} denote the α-ary relation on U:

{⟨(a_{0}, u_{0}), (a_{1}, u_{1}), ⋯ (a_{j}, u_{j}) ⋯ ⟩_{j<α} ∈ V : ⟨a_{0}, ⋯ a_{j} ⋯ ⟩_{j∈α} ∈ ^{α}W^{(w)}}.

L stands for 1_{Id}.

Fact 5.1. (i) For all u ∈ S_{α}, 1_{u} ∈ A(α).

(ii) Let Rl_{L}A(α) = {x ∈ A(α) : x ≤ L}. Then Rl_{L}A(α) is atomic and its set of atoms is equal to P (Id). Furthermore, Rl_{L}A(α) is generated as a BA by P (Id).

(iii) For all non zero a ∈ Rl_{L}A(α), for all i < α, c_{i}a = c_{i}L.

(iv) For all a ∈ A(α), for all i < α, c_{i}a ∩ L ∈ {0, L}.

(v) Let P = ∪{P (u) : u ∈ S_{α}}. Let p be a permutation of P (Id). Then there exists an automorphism f of A(α), such that p ⊆ f and f(x) = x, for each x ∈ P − P (Id).

Proof.

(i) Let u ∈ S_{α}. Let r_{1}, r_{2} ∈ R. Then as easily checked c_{0}(p(u, r_{1})) ∩ c_{1}(p(u, r_{2})) = 1_{u}.

(ii) Since the C_{r}’s are pairwise disjoint, we have p(Id, r_{1}) ∩ p(Id, r_{2}) = 0 for distinct r_{1} and r_{2}. Thus the set of atoms of Rl_{L}A(α) is precisely P (Id). By c_{i}(p(Id, r)) ∩ 1_{Id} = 1_{Id} and p(Id, r) ∩ d_{ij} = 0, for distinct i, j < α, it follows that Rl_{L}A(α) is indeed generated as a BA by the set P (Id).

(iii) Let a ∈ Rl_{L}A(α) be non zero. By (ii) there exists an atom p(Id, r) below a. Let i < α. Then c_{i}(p(Id, r)) =(by Lemma 1 (i)) ∪{1_{u} : u ∈ ^{α}α^{(Id)} and u(j) = j for all j ≠ i} = c_{i}L. From p(Id, r) ≤ a, (iii) readily follows.

(iv) follows from (iii).

(v) We first, like we did in the finite case, extend p to a BA automorphism p′, say, of Rl_{L}A(α). This is possible by (i). Then we define f(x) = p′(x ∩ L) ∪ (x ∩ −L). The rest is completely analogous to the proof of fact 3.1.

Fact 5.2. A(α) is elementary equivalent to B(α).

The proof, literally identical to the proof of fact 3.3, is left to the reader.

Now we show that B(α) is not a neat reduct. We proceed basically as we did in the finite case, the trick being “a(n) (infinite) cardinality twist” that first order logic cannot witness.

Fact 5.3. Let Rl_{L}B(α) = {x ∈ B(α) : x ≤ L}. Then |Rl_{L}B(α)| ≤ α.

Proof. First of all note that by 5.1 (i) we have L ∈ B. Now let X = ∪{P (u) : u ∈ S_{α} − {Id}} ∪ P_{ω}(Id), Y = {c_{i}a : a ∈ A} ∪ {d_{ij} : i, j ∈ α} and D(α) = Sg^{BlA(α)}(X ∪ Y). Then |Y | = α. This can be seen by noting that for every x ∈ Y, if x is non zero, and x is not a diagonal element, then by Lemma 1*(ii) there is an S with S ⊆ ^{α}α^{(Id)} such that x = ∪{1_{u} : u ∈ S}. Also D(α) is a subuniverse of A(α) because of the following: D(α) is closed under the boolean set operations , contains the diagonals, and for a ∈ D(α), and i < α, we have a ∈ A(α) and so c_{i}a ∈ D(α), that is D(α) is closed under cylindrifications. Since X ⊆ D(α), X generates B(α) and D(α) ∈ CA_{α}, we have B(α) ⊆ D(α). Let rl_{L}(a) = a ∩ L. Then we have

Rl_{L}D(α) = {x ∈ D(α) : x ≤ L} = Sg^{BlA(α)}rl_{L}(X ∪ Y).

But |rl_{L}(X ∪ Y)| = α, because P_{ω}(Id) is countable and |Y | = α. Therefore |rl_{L}(X ∪ Y)| = α, and so |Rl_{L}D(α)| ≤ α. By Rl_{L}B(α) ⊆ Rl_{L}D(α) we are done.

Fact 5.4. Let p[0, 1] be the transposition on α interchanging 0 and 1. Let v = p[0, 1] ∘ Id = ⟨1023 ⋯ ⟩. Then v ∈ S_{α} and the following hold:

(i) t^{B(α)}(1_{v}) = 1_{Id}

(ii) For all β > α, CA_{β} ⊧ _{α}s(0, 1)c_{α}x ≤ t(c_{α}x).

(iii) For all β > α and A ∈ CA_{β}, _{α}s(0, 1) ∈ Ism(BlNr_{α}A, BlNr_{α}A).

The proof is identical to the proof of fact 4.2. Therefore we omit it.

Fact 5.5. B(α) ∉ Nr_{α}CA_{α+1}.

Proof. Like the proof of fact 4.3, the idea bieng; if B(α) were a neat reduct then we would have |Rl_{L}(B(α)| = |R|. But this contradicts fact 5.3, since by assumption we have |R| > |α|.

Now we are ready to prove Theorem 2. ^{13}

Theorem 2 . Let α ≥ β. Then there exist B ∈ W s_{α} and C ∈ W s_{β} such that B is a generating subreduct of C, but B ≠ Nr_{α}C.

Proof. Let β > α. Then by [HMT2] 3.1.12 we have B = B(α) ∈ SNr_{α}W s_{β}. Let D ∈ W s_{β} be such that B ⊆ Nr_{α}D and let C = Sg^{D}B. Then B and C are clearly as desired.

A(α) constructed so far may or may not be a neat reduct. We now impose further restrictions on the C_{r}’s (or rather on the structure W = ⟨W, C_{r}⟩), described in Lemma 1*, that force A(α) to be in ∩_{k∈ω}Nr_{α}W s_{α+k}. These restrictions are described in Lemma 1** below. Forming a “limit” out of the W s_{α+k}’s (k ∈ ω) , the neat − α reduct of which is A(α), we will show that A(α) ∈ Nr_{α}W s_{α+β} for infinite β as well. This should be done , of course, in such a way that does not interfere with what we have already established, namely: B(α) is not a neat reduct. A(α) and B(α) are elementary equivalent. To formulate Lemma 1** we fix some notation:

13Though not explicitly stated, it is rather easy to derive Theorem 2, from statement 1 in [N83]. In more detail let B be the W s_{α} constructed in statement 1 therein. Then B ∉ Nr_{α}CA_{α+1}. Then proceed as in the proof of Theorem 2 above. Conversely Theorem 2 herein provides another solution to problem 2.11 in [HMT1].

Notation . Let 1 ≤ k < ω. Then S(α, α + k) or simply

S(α, k) = {i ∈ ^{α}(α + k) : α + k − 1 ∈ Rgi and {m ∈ α : |{i(m) ≠ m}| < ω}.

That is S(α, k) = {i ∈ ^{α}(α + k)^{(Id)} : α + k − 1 ∈ Rgi}. Cof^{+}R denotes the set of all non empty finite or cofinite subsets of R. Let C_{r} be an α-ary relation symbol for all r ∈ R. For any X ⊆ R, X finite we define the infinitary formulas:

η(X) = ∨{C_{r}(x_{0}, ⋯ x_{j} ⋯)_{j<α} r ∈ X}, and
η(R − X) = ∧{¬C_{r}(x_{0}, .x_{j} ⋯)_{j<α} : r ∈ X}^{14}.

LEMMA 1** . There are a set W, w ∈ W and α-ary relations C_{r} ⊆ ^{α}W^{(w)} for all r ∈ R such that, in addition to conditions (i) and (ii) of Lemma 1*, the following conditions hold:

(i) For all s ∈ ^{α}W^{(w)} for all r ∈ R, for all permutation π ∈ S_{α}, if s ∈ C_{r}, then soπ ∈ C_{r}.

(ii) For all 1 ≤ k < ω, for all v ∈ ^{α+k−1}W^{(w)}, for any function f : S(α, k) → Cof^{+}R for which {i ∈ S(α, k) : |{f(i) ≠ R}| < ω}, there is a v_{α+k−1} ∈ W − Rgv such that

∧{η(f(i))[⟨v_{i_{j}}⟩_{j<α}] : i ∈ S(α, k)}.

Being very similar to the proof of Lemma 1, we only give a sketch:

14η(X) and η(R−X) are restricted formulas, in the sense of [HMT2] sec 4.3. Satisfiability for such formulas (by α-ary sequences) are defined the usual way. Below we shall have occasion to deal with (infinitary) formulas that are not restricted. These however can be obtained from restricted ones using the (logical interpretation of the) CA operations, i.e quantification on finitely many variables and equality.

Let k ≥ 1. For brevity set

Y (α, R, k) = {f ∈ ^{S(α,k)}Cof^{+}R : {i ∈ S(α, k) : |{f(i) ≠ R}| < ω}.

Let

Q = ∪{^{α+k−1}|R| × Y (α, R, k) : 1 ≤ k < ω},

then |Q| = |R| = μ, say. Let ρ be an enumeration of Q such that: for all l < μ, for all q ∈ Q, there exists j with l < j < μ such that ρ(j) = q. Fix a well ordering ≺ of R. let l < μ and suppose that for all i < l we have already defined the element v_{i}, and the α-ary relation C_{r}^{i} ⊆ ^{α}W_{i}^{(w)}, where W_{i} = {v_{k} : k < i} and w ∈ W_{i}. Assume that ρ(l) = ⟨⟨β_{j}⟩_{j<α+k−1}, f⟩. Then β_{j} ∈ |R| for all j < α + k − 1, and f ∈ Y (α, R, k). Let v_{l} be an element not in ∪{W_{i} : i < l}. If there exists i < α + k − 1 such that l ≤ β_{i}, then for all r ∈ R we define C_{r}^{l} = ∪{C_{r}^{i} : i < l}. Else, l > β_{i} for all i < α + k − 1. Let u_{i} = v_{β_{i}} for i < α + k − 1 and let u_{α+k−1} = v_{l}. For all r ∈ R and i ∈ S(α, k) we let

⟨u_{i_{j}}⟩_{j<α} ∈ X_{r}^{l} iff r is the ≺ − least element of f(i)

and

C_{r}^{l} = ∪{C_{r}^{i} : i < l} ∪ {⟨s_{π(0)}, s_{π(1)}, ⋯ ⟩ : s ∈ X_{r}^{l} and π ∈ S_{α}}.

Finally set

W = ∪{W_{l} : l < μ} and C_{r} = ∪{C_{r}^{l} : l < μ}.

It is not hard to check just like we did in the finite dimensional case, that W = ⟨W, C_{r}⟩_{r∈R} is as desired.

With a slight abuse of notation we let A(α) and B(α) be the (new) algebras consructed out of the (new) structure W = ⟨W, C_{r}⟩_{r∈R}, described in Lemma 1^{∗∗}. It is easy to check that A(α) and B(α) are (still) elementary equivalent (cf., facts 5.1-2) and B(α) is (still) not a neat reduct (cf., facts 5.3-5.5). We will use the new condition of “saturation” or “elimination of quantifiers” expressed in Lemma 1^{∗∗} (ii) to show that A(α) ∈ ∩_{k∈ω}Nr_{α}W s_{α+k}. To “lift” A(α) to arbitrary finite extra dimensions, we shall further need:

Some more definitions.

Let 0 ≤ k < ω. Then U_{k} = U = ∪_{i∈α}W × {i}. Let s_{k} = s ∪ ⟨(w, 0) : α ≤ i < (α + k)⟩. Then s_{k} ∈ ^{α+k}U. (When k = 0, then s_{k} is just s). Let V_{k} be the weak space ^{α+k}U^{(s_{k})} and let C(α + k) be the full W s_{α+k} with unit V_{k}. Let u ∈ ^{α+k}α^{(Id)}. Then

F_{k}(u) = {C_{r}(x_{i_{0}}, ⋯ x_{i_{j}} ⋯)_{j<α}, ¬C_{r}(x_{i_{0}}, ⋯ x_{i_{j}} ⋯)_{j<α} : r ∈ R, i ∈ ^{α}α + k^{(Id)}

and ⟨u_{i_{0}}, ⋯ u_{i_{j}} ⋯ ⟩_{j<α} is one to one } ∪ Eq(u).

Recall that Eq(u) stands for {x_{i} = x_{j} : x_{i} ≠ x_{j} : (i, j) ∈ ker(u)}. Like the finite case we assume that {T, F } ∈ F_{k}(u).

F_{k}(u)^{∗} = {∧J : J ⊆_{ω} F_{k}(u)},
F_{k}(u)^{∗∗} = {∨J : J ⊆_{ω} F_{k}(u)^{∗}}.

Let u ∈ ^{α+k}α^{(Id)} and ϕ ∈ F_{k}(u)^{∗∗}. Then E(u, ϕ) denote the following (α + k)-ary relation on U

{⟨(a_{0}, u_{0}), ⋯ (a_{j}, u_{j}) ⋯ ⟩_{j<α+k} ∈ V_{k} : W ⊧ ϕ[⟨a_{j}⟩_{j<α+k}]}.

As noted before, satisfiability is defined the usual way. In particular, when k = 0, u ∈ S_{α} and r ∈ R, then E(u, C_{r}(x_{0}, x_{1}, ⋯) is the same as p(u, r). ind(ϕ) denotes the set {i ∈ α + k : x_{i} ∈ var(ϕ)}. Let G(k) = {c_{(Δ)}E(u, ϕ), −c_{(Δ)}E(u, ϕ) : Δ ⊆_{ω} α + k, u ∈ ^{α+k}α^{(Id)}, ϕ ∈ F_{k}(u)^{∗∗}, Δ ∩ ind(ϕ) = 0} ∪{d_{ij}^{V_{k}}, −d_{ij}^{V_{k}} : i, j ∈ α + k}. Here c_{(Δ)}, the unary operation referred to as generalized cylindrification in [HMT1]. That is c_{∅}x = x and if Δ = {k_{0}, ⋯ k_{m−1}} is a non-empty finite subset of α + k, then c_{(Δ)}x = c_{k_{0}} ⋯ c_{k_{m−1}}x. For i, j ∈ α + k, d_{ij}^{V_{k}}, or simply d_{ij} is the diagonal element {s ∈ V_{k} : s_{i} = s_{j}}. Finally set

G(k)^{∗} = {∩J : J ⊆_{ω} G(k)}

and

G(k)^{∗∗} = {∪J : J ⊆_{ω} G(k)^{∗}}.

We will show that G(k)^{∗∗} is a W s_{α+k} (with unit V_{k}), that G(0)^{∗∗} = Nr_{α}G(k)^{∗∗} for all k ∈ ω, and finally that G(0)^{∗∗} = A(α). This will show that A(α) ∈ ∩_{k∈ω}INr_{α}W s_{α+k}. To prove that G(k)^{∗∗} is a W s_{α+k} we shall need:

Fact 5.6. (i) Let u ∈ ^{α+k}α^{(Id)} , Δ ⊆_{ω} α + k and ϕ ∈ F_{k}(u)^{∗∗}. Then c_{(Δ)}E(u, ϕ) ∈ G(k)^{∗∗}.

(ii) Let g ∈ G(k)^{∗∗} and i, j ∈ α + k be distinct. Then s_{i}^{j}(g) = c_{j}(g ∩ d_{ij}) ∈ G(k)^{∗∗}.

(iii) Let H(k) = {g ∈ G(k) : g = c_{(Δ)}E(u, ϕ) : Δ ⊆_{ω} α + k, u ∈ ^{α+k}α^{(Id)} and ϕ ∈ F_{k}(u)^{∗∗}}. Then H(k) is closed under finite intersections.

Proof.

(i) We first prove (i) when Δ consists of one element j, say. That is we will show that for u and ϕ as indicated above and j < α + k we have c_{j}E(u, ϕ) ∈ G(k)^{∗∗}. We can and will assume that ϕ ∈ F_{k}(u)^{∗} since

c_{j}E(u, ϕ_{1} ∨ ⋯ ϕ_{n}) = c_{j}E(u, ϕ_{1}) ∪ ⋯ c_{j}E(u, ϕ_{n})

and G(k)^{∗∗} is closed under finite unions. Then ϕ = ∧J, where J ⊆_{ω} F_{k}(u). Next, we break up ϕ into two parts just like we did in the finite dimensional case; that is let J^{+} = {ψ ∈ J : x_{j} ∈ var(ψ)} and J^{−} = {ψ ∈ J : x_{j} ∉ var(ψ)}. For brevity set ϕ^{+} = ∧J^{+} and ϕ^{−} = ∧J^{−}, where by the empty conjunction we understand the formula T. Now ϕ = ϕ^{+} ∧ ϕ^{−}, ϕ^{−} ∈ F_{k}(u)^{∗} and x_{j} occurs only in ϕ^{−}.

Notation . For i, l ∈ α+k and ϕ ∈ F_{k}(u)^{∗∗} ϕ[i|l] stands for the formula obtained from ϕ by replacing all (free and bound) occurances of x_{i} in ϕ by x_{l}.

Case (a): x_{j} = x_{m} ∉ J^{+} and x_{j} = x_{m} ∉ J^{+} for all m ∈ α + k − {j}.

Then either W ⊧ ϕ^{+} ≡ F, in which case W ⊧ ∃x_{j}ϕ^{+} ≡ F , and so c_{j}E(u, ϕ) = c_{j}E(u, F) = 0 ∈ G(k)^{∗∗}. Else ϕ^{+} is satisfiable, in which case , by applying Lemma 1** (ii), we get

W ⊧ (∃x_{α+k−1}ϕ^{+}[j|α + k − 1]) ≡ T,

which is the same as W ⊧ (∃x_{j}ϕ^{+}) ≡ T, and so

c_{j}E(u, ϕ) = c_{j}E(u, (∃x_{j}ϕ^{+}) ∧ ϕ^{−}) = c_{j}E(u, ϕ^{−}).

The latter is in G(k)^{∗∗}, since now x_{j} does not occur in ϕ^{−}, and ϕ^{−} ∈ F_{k}(u)^{∗}. Note that ϕ^{−} ∈ F_{k}(v)^{∗} for any v that differs from u in at most the j-th place; and for any such v we have c_{j}E(u, ϕ) = c_{j}E(v, ϕ^{−}).

Case (b): x_{j} = x_{m} ∈ J^{+} or x_{m} = x_{j} ∈ J^{+} for some m ∈ α + k and m ≠ j.

Assume that x_{j} = x_{m} ∈ J^{+}. Then , by definition of F_{k}(u), we have u_{j} = u_{m} . Also ϕ = (∧I) ∧ x_{j} = x_{m}, for some I ⊆_{ω} F_{k}(u). For brevity let ψ = ∧I. Then of course ψ ∈ F_{k}(u)^{∗}. Computing we get

c_{j}E(u, ϕ) = c_{j}E(u, ψ ∧ x_{j} = x_{m}) = c_{j}E(u, ψ[j|m]).

The latter is in G(k)^{∗∗} since x_{j} does not occur in ψ[j|m], and ψ[j|m] ∈ F_{k}(u)^{∗} because ψ ∈ F_{k}(u)^{∗} and u_{j} = u_{m}. In fact, it is not hard to see that ψ[j|m] ∈ F_{k}(v)^{∗}, for any v that differs from u in at most the j th place. The case when Δ is an arbitrary finite subset of α + k, follows by using the above reasoning eliminating the variables occuring in ϕ, with indices in Δ, one by one. Alternatively one can use a straightforward induction on |Δ|. Note that we have actually proved the following infinite analogue of (**) in fact 2.1 way above:

Let u ∈ ^{α}α + k^{(Id)} and ϕ ∈ F_{k}(u)^{∗∗}. Let Δ = {i_{0}, ⋯ i_{n−1}} be a finite subset of α+k. Let v ∈ ^{α}α+k^{(Id)} be such that v(j) = u(j) for all j ∉ Δ.

Then there exists ψ ∈ F_{k}(v)^{∗∗} such that var(ψ) ∩ {x_{i_{0}}, ⋯, x_{i_{n−1}}} = ∅. i.e., ind(ψ) ∩ Δ = ∅, and W ⊧ ψ ≡ ∃x_{i_{0}} ⋯ ∃x_{i_{n−1}}ϕ. In particular, c_{(Δ)}E(u, ϕ) = c_{(Δ)}E(v, ψ).

(ii) Let g ∈ G(k)^{∗}∗ and i, j ∈ α + k be distinct.

Case (a): g = c_{(Δ)}E(u, ϕ) with u ∈ ^{α+k}α^{(Id)}, ϕ ∈ F_{k}(u)^{∗∗}.

Subcase (a) : j ∈ Δ.

Then by [HMT1] 1.5.8 (i) and 1.7.3 we have

s_{i}^{j}(g) = s_{i}^{j}c_{j}(c_{(Δ−{j}}))E(u, ϕ) = c_{j}(c_{(Δ−{j})})E(u, ϕ) = g

Subcase (b) : j ∉ Δ and i ∉ Δ.

Then by [HMT1], 1.5.8 (ii) we have

s_{i}^{j}g = s_{i}^{j}c_{(Δ)}E(u, ϕ) = c_{(Δ)}s_{i}^{j}E(u, ϕ).

Let g^{∗} = E(u, ϕ)∩d_{ij}. Then g^{∗} and hence s_{j}^{i}g = c_{(Δ)}c_{j}g^{∗}, is equal to zero if u_{i} ≠ u_{j}. Else, as easily checked, g^{∗} = E(u, ϕ ∧ x_{i} = x_{j}). By u_{i} = u_{j} and ϕ ∈ F_{k}(u)^{∗∗}, we have ϕ ∧ x_{i} = x_{j} ∈ F_{k}(u)^{∗∗}. By fact 5.6 (i) we get that s_{j}^{i}g = c_{(Δ)}c_{j}g^{∗} = c_{(Δ)}c_{j}E(u, ϕ ∧ x_{i} = x_{j}) ∈ G(k)^{∗∗}.

Subcase (c) : j ∉ Δ and i ∈ Δ.

By [HMT1] 1.7.3 and 1.5.8 (ii) we have

s_{i}^{j}c_{(Δ)}E(u, ϕ) = s_{i}^{j}c_{(Δ−{i})}c_{i}E(u, ϕ) = c_{(Δ−{i})}s_{i}^{j}c_{i}E(u, ϕ).

Let g^{∗} = s_{i}^{j}c_{i}E(u, ϕ). Then by [HMT1] 1.5.1 we have g^{∗} = c_{j}(c_{i}(E(u, ϕ)∩ d_{ij}). Let v = u_{u(j)}^{i} = uo[i|j]. Here and elsewhere [i|j] denotes the replacement that maps i to j and otherwise coincides with the identity. Then v(j) = u(j) = v(i). Also, it is easy to see that

c_{i}(E(u, ϕ) ∩ d_{ij}) = E(v, ϕ ∧ x_{i} = x_{j}).

Since i ∈ Δ, we can assume by fact 5.6 (i) that x_{i} does not occur in ϕ. Since v differs from u in at most the ith place, we have ϕ ∈ F_{k}(v)^{∗∗}. But v(i) = v(j), and so x_{i} = x_{j} ∈ F_{k}(v)^{∗∗}, thus ϕ ∧ x_{i} = x_{j} ∈ F_{k}(v)^{∗∗}. By fact 5.6 (i) we get that g^{∗} hence g is in G(k)^{∗∗}.

Case (b) : g = d_{kl}, where k, l ∈ α + k

By [HMT1], 1.5.4 we have s_{i}^{k}(d_{kl}) = d_{il} if k ≠ l and s_{i}^{j}d_{kl} = d_{kl} if j ∉ {k, l}. In either case we have s_{i}^{j}g ∈ G(k)^{∗∗}.

Case (c) : g is an element in G(k)^{∗∗}.

Follows from the two previous cases, since the s_{i}^{j}’s (i, j ∈ α + k) are BA endomorphisms of the boolean algebra G(k)^{∗∗} (cf., [HMT1] 1.5.3 (i)).

(iii) Let g = c_{(Δ_{1})}E(u_{1}, ϕ_{1}) ∩ c_{(Δ_{2})}E(u_{2}, ϕ_{2}) where Δ_{i} ∩ ind(ϕ_{i}) = 0 for i ∈ {1, 2}. Then g = 0 if there exists j ∈ (α+k)−(Δ_{1}∪Δ_{2}) such that u_{1}(j) ≠ u_{2}(j). Else, it is not difficult to check that g = c_{(Δ_{1}∩Δ_{2})}E(w, ϕ_{1} ∧ ϕ_{2}), where w is defined as follows:

w(j) = u_{1}(j) = u_{2}(j) for j ∈ α + k − (Δ_{1} ∪ Δ_{2})
w(j) = u_{1}(j) if j ∈ Δ_{2} − Δ_{1}

w(j) = u_{2}(j) if j ∈ Δ_{1} − Δ_{2}, and w is defined arbitrarily on Δ_{1} ∩ Δ_{2}.

Also by ind(ϕ_{i}) ∩ Δ_{i} = 0, for i ∈ {1, 2} and w(j) = u_{1}(j) = u_{2}(j) for all j ∈ α + k − (Δ_{1} ∪ Δ_{2}) we can assume by 5.6 (i) that ϕ_{i} ∈ F_{k}(w)^{∗∗}, hence ϕ_{1} ∧ ϕ_{2} ∈ F_{k}(w)^{∗∗}.

To economise on notation we recall a few notions from [HMT1]. A generalized diagonal element is a finite intersection of diagonal elements. A codiagonal element is the complement of a diagonal element. A generalized co-diagonal element is a finite intersection of co-diagonal elements. In particular the unit of an algebra can be viewed as both a generalized diagonal and a generalized co-diagonal.

Fact 5.7. For all 0 ≤ k < ω, G(k)^{∗∗} ∈ W s_{α+k}.

Proof. Clearly G(k)^{∗∗} is a BA field of sets with greatest element V_{k}. Also G(k)^{∗∗}, by definition, contains all diagonal elements. We are thus left to check cylindrifications, by the additivity of which, it suffices to show that for every g ∈ G(k)^{∗} and j < α + k we have c_{j}g ∈ G(k)^{∗∗}. By 5.6 (iii) a typical element g of G(k)^{∗} is of the form a_{0} ∩ b ∩ c ∩ −a_{1} ∩ −a_{2} ⋯ ∩ −a_{n}, where n ∈ ω, a_{0}, a_{1}, ⋯ a_{n} ∈ H(k), b is a generalized diagonal element, and c is a generalized co-diagonal element. Now fix j < α + k and let g be as indicated above. Case (a) : b = d_{jl} ∩ b′ where b′ is a generalized diagonal element and j ≠ l. Let g^{∗} = a_{0} ∩b′ ∩c∩−a_{1} ⋯∩−a_{n}. Then, of course g^{∗} ∈ G(k)^{∗} and c_{j}g = s_{l}^{j}g^{∗}. By fact 5.6 (i) the latter is in G(k)^{∗∗}. Case (b) : a_{0} = b = V_{k}. In this case we have g = −c_{(Δ_{1})}E(u_{1}, ϕ_{1}) ⋯ ∩ −c_{(Δ_{n})}E(u_{n}, ϕ_{n}) ∩ −d_{jl_{1}} ⋯ ∩ −d_{jl_{m}}, where n, m ∈ ω, Δ_{k} ⊆_{ω} α + k for 1 ≤ k ≤ n and since c_{j}(x ∩ c_{j}y) = c_{j}x ∩ c_{j}y, we can assume that j ∉ Δ_{1} ∪ ⋯ Δ_{n}. Assume that g ≠ 0, for else there is nothing more to prove. In particular, j, l_{1}, ⋯ l_{m} are pairwise distinct. We claim that in this case we have c_{j}g = V_{k}. Indeed, let s = ⟨(a_{l}, i_{l})⟩_{l∈α+k} be an arbitrary element in V_{k}. We will show that s ∈ c_{j}g, by which we will be done. Choose k_{j} ∉ {u_{1}(j), ⋯, u_{n}(j)} ∪ {i_{l_{1}}, ⋯ i_{l_{m}}}, and let u = (a_{j}, k_{j}). Let z = s_{u}^{j}. Assume that 1 ≤ i ≤ n. Then s_{u}^{j} ∉ c_{(Δ_{i})}E(u_{i}, ϕ_{i}) because s_{u}^{j}(j) = (a_{j}, k_{j}) ≠ (a_{j}, u_{i}(j)). Assume now that 1 ≤ i ≤ m. Then z(j) = (a_{j}, k_{j}) ≠ (a_{l_{i}}, i_{l_{i}}) = z(l_{i}), that is z ∉ d_{jl_{i}}. We have shown that z ∈ g. Since s differs fom z in at most the jth place we get that s ∈ c_{j}g. We have proved that c_{j}g = V_{k}. Case (c) :

g = c_{(Δ_{0})}E(u_{0}, ϕ_{0}) ∩ −c_{(Δ_{1})}E(u_{1}, ϕ) ∩ ⋯ c_{(Δ_{n})}E(u_{n}, ϕ_{n}) ∩ −d_{jl_{1}} ⋯ ∩ −d_{jl_{m}},

where n, m ∈ ω, Δ_{k} ⊆_{ω} α + k for 0 ≤ k ≤ n and as in the previous case, we can assume that j ∉ Δ_{0} ∪ ⋯ Δ_{n} and that j, l_{1}, ⋯ l_{m} are pairwise distinct. We can further assume that {l_{1}, ⋯ l_{m}} ⊆ Δ_{0}, for if l_{k} ∉ Δ_{0} for some 1 ≤ k ≤ n, then we can simply “ignore” the co-diagonal element with indices j and l_{k}, i.e the element −d_{jl_{k}}, because of the following:

c_{(Δ_{0})}E(u_{0}, ϕ_{0}) ∩ −d_{jl_{k}} = c_{(Δ_{0})}E(u_{0}, ϕ_{0} ∧ x_{j} ≠ x_{l_{k}})

if u_{0}(j) = u_{0}(l_{k}), and is equal to c_{(Δ_{0})}E(u_{0}, ϕ_{0}) otherwise. Note too, that ϕ_{0} ∧ x_{j} ≠ x_{l_{k}} ∈ F_{k}(u_{0})^{∗∗}, whenever ϕ_{0} ∈ F_{k}(u_{0})^{∗∗} and u_{0}(j) = u_{0}(l_{k}). In either case, g can be written in the form:

c_{(Δ_{0})}E(u_{0}, ψ) ∩ ⋯ − c_{(Δ_{n})}E(u_{n}, ϕ_{n}) ∩ ∩{−d_{jl} : l ∈ {l_{1}, ⋯ l_{m}} − l_{k}},

where c_{(Δ_{0})}E(u_{0}, ψ) ∈ H(k). Now let

Γ = Δ_{0} − {l_{1}, ⋯ l_{m}} and Γ_{1} = {l_{1}, ⋯ l_{m}}.

Then Δ_{0} = Γ ∪ Γ_{1}. Let S = {j} × Γ_{1} = {(j, l) : l ∈ Γ_{1}} and let d_{S} be the co-diagonal element: ∩{−d_{jl} : (j, l) ∈ S}. Let g∗ = −c_{(Δ_{1})}E(u_{i}, ϕ_{1}) ∩ ⋯ − c_{(Δ_{n})}E(u_{n}, ϕ_{n}), g_{1} = c_{(Γ)}E(u_{0}, ϕ_{0}) ∩ g∗ and g_{2} = c_{(Γ_{1})}E(u_{0}, ϕ_{0}) ∩ d_{S} ∩ g∗. Then by [HMT1] 1.7.3, and the additivity of c_{j} we have c_{j}g = c_{j}g_{1} ∪ c_{j}g_{2}. We shall show that c_{j}g_{1} ∈ G(k)^{∗∗} and c_{j}g_{2} ∈ G(k)^{∗∗}, by which we will be done. Proof of c_{j}g_{1} ∈ G(k)^{∗∗}.

Write g_{1} = c_{(Γ)}E(u_{0}, ϕ_{0}) ∩ ⋯ − c_{(Δ_{n})}E(u_{n}, ϕ_{n}). We can assume that for 1 ≤ k ≤ n and i ∉ Γ ∪ Δ_{k}, we have u_{0}(i) = u_{k}(i), for if u_{0}(i) ≠ u_{k}(i) for some 1 ≤ k ≤ n, and some i ∉ Γ ∪ Δ_{k}, then c_{(Γ)}E(u_{0}, ϕ_{0}) ∩ −c_{(Δ_{k})}E(u_{k}, ϕ_{k}) = c_{(Γ)}E(u_{0}, ϕ_{0}). For the time being assume that ϕ_{1} = ϕ_{2} = ⋯ ϕ_{n} = T. Claim c_{j}g_{1} = c_{j}c_{(Γ)}E(u_{0}, ϕ_{0}) ∩ −c_{j}c_{(Δ_{1})}E(u_{1}, T) ∩ ⋯ − c_{j}c_{(Δ_{n})}E(u, T). Proof of claim

It is straightforward to show that r.h.s is contained in c_{j}g. Now for the opposite inclusion: Let s ∈ c_{j}g_{1}. Then there exists b = (b_{j}, l_{j}) ∈ ∪V_{k} such that s_{b}^{j} ∈ c_{(Γ)}E(u_{0}, ϕ_{0}) and s_{b}^{j} ∉ c_{(Δ_{k})}E(u_{k}, T) for all 1 ≤ k ≤ n. Thus s ∈ c_{j}c_{(Γ)}E(u_{0}, ϕ_{0}). We will show that s ∉ c_{j}c_{(Δ_{k})}E(u_{k}, T) for all 1 ≤ k ≤ n, by which case we will be done. Fix 1 ≤ k ≤ n and assume to the contrary that s ∈ c_{j}c_{(Δ_{k})}E(u_{k}, T). Then there exists c = (c_{j}, k_{j}) ∈ ∪V_{k} such that s_{c}^{j} ∈ c_{(Δ_{k})}E(u_{k}, T). For x = (x_{0}, x_{1}) we write (x)_{0} = x_{0} and (x)_{1} = x_{1}. By s_{c}^{j} ∈ c_{(Δ_{k})}E(u_{k}, T) and j ∉ Δ_{k} we get (c)_{1} = u_{k}(j). Similarly, by s_{b}^{j} ∈ c_{(Γ)}E(u_{0}, ϕ_{0}) and j ∉ Γ we get (b)_{1} = u_{0}(j). Recall that we assumed that u_{0}(j) = u_{k}(j) since j ∉ Γ ∪ Δ_{k}, thus (b)_{1} = (c)_{1}. Since s_{b}^{j} and s_{c}^{j} differ in at most the jth place , (b)_{1} = (c)_{1} and s_{c}^{j} ∈ c_{(Δ_{k})}E(u_{k}, T) we get s_{b}^{j} ∈ c_{(Δ_{k})}E(u_{k}, T). Contradiction. Now the general case follows from this by noting that

−c_{(Δ)}E(u, ϕ) = c_{(Δ)}E(u, ¬ϕ) ∪ −c_{(Δ)}E(u, T),

and that H(k) is closed under finite intersections. We now turn to showing that c_{j}g_{2} ∈ G(k)^{∗∗}. This will be done by showing that a = c_{(Γ_{1})}E(u_{0}, ϕ_{0}) ∩ d_{S}, hence g_{2} = a ∩ g∗, can be written as a finite union of elements of the form a_{0} ∩ −a_{1} ⋯ ∩ −a_{n} where a_{i} ∈ H(k). Then by the additivity of c_{j}, and the previous case we get the desired. We start off when Γ_{1} consists of a single element m say. We compute a = c_{m}E(u_{0}, ϕ_{0}) ∩ −d_{jm}. For brevity set u = u_{0}. Let v = u_{u(j)}^{m} = u ∘ [m|j]. Then v(m) = v(j) = u(j). Moreover it is not hard to check that

a = (c_{m}E(u, ϕ_{0}) ∩ −E(v, T)) ∪ E(v, ϕ_{0} ∧ x_{j} ≠ x_{m}).

Since x_{m} does not occur in ϕ_{0}, and v differs from u in at most the m-th place, we infer from fact 5.6 (i) that ϕ_{0} ∈ F_{k}(v)^{∗∗}. By v(m) = v(j) we get that x_{j} ≠ x_{m} is also in F_{k}(v) hence in F_{k}(v)^{∗∗}. It follows that ϕ_{0} ∧ x_{j} ≠ x_{m} ∈ F_{k}(v)^{∗∗}. We have shown that E(v, ϕ_{0} ∧ x_{j} ≠ x_{m}) ∈ H(k). Thus a is as desired, since c_{m}E(u, ϕ_{0}) and E(v, T) are in H(k), too. Now for the general case. Assume that Γ_{1} = {l_{1}, ⋯ l_{m}} . Having treated the case when m = 1 we now assume that m > 1. Then

a = c_{(Γ_{1})}E(u, ϕ) ∩ −d_{S} = ∩{a_{k} : 1 ≤ k ≤ m}

where a_{k} = c_{(Γ_{1}−{l_{k}})}c_{l_{k}}E(u, ϕ) ∩ −d_{jl_{k}}. Therefore a, hence g_{2} = a ∩ g^{∗}, is indeed the finite union of elements of the a_{0} ∩ −a_{1} ⋯ ∩ −a_{n} where a_{i} ∈ H(k). Thus c_{j}g_{2} is in G(k)^{∗∗}. By this the proof of fact 5.7 is complete.

Fact 5.8. G(0)^{∗∗} ≅ Nr_{α}G(k)^{∗∗}, for all 0 ≤ k < ω^{15}

Proof. Let k ≥ 0. Define i(k) as in fact 2.3. That is for a ∈ G(0)^{∗∗}, let i(k)(a) = {t ∈ V_{k} : t ↾ α ∈ a}. Then i(k) ∈ Ism(A(α), Nr_{α}C(α + k)), where C(α + k) is the full W s_{α+k} with unit V_{k}. We will show that i(k)G(0)^{∗∗} ⊆ G(k)^{∗∗}. For that it clearly suffices to show that for all u ∈ ^{α}α^{(Id)}, and ϕ ∈ F_{0}(u), we have i(k)E(u, ϕ) ∈ G(k)^{∗∗}. Let u and ϕ be as indicated: Then i(k)E(u, ϕ) = ∪{E(v, ϕ) : v ∈ ^{α+k}α^{(Id)} : v ↾ α = u} = c_{α} ⋯ c_{α+k−1}E(u∗, ϕ) where u∗ = u∪⟨0 : α ≤ i < α+k⟩. Since F_{0}(u) ⊆ F_{k}(v) whenever v ∈ ^{α+k}α^{(Id)} is such that v ↾ α = u, we get ϕ ∈ F_{k}(u∗)^{∗∗}, hence i(k)E(u, ϕ) ∈ G(k)^{∗∗}. We have shown that i(k) ∈ Ism(G(0)^{∗∗}, Nr_{α}G(k)^{∗∗}). We will now show that i(k) is actually onto Nr_{α}G(k)^{∗∗}. Since the c_{i}’s are additive, it suffices to show that for all g ∈ G(k)^{∗}, there exists a ∈ G(0)^{∗∗}, such that i(k)a = c_{α} ⋯ c_{α+k−1}g. Case (a): g = E(v, ϕ), v ∈ ^{α+k}α^{(Id)}, and ϕ ∈ F_{k}(v)^{∗∗}. Then by fact 5.6 (i) there exists ψ ∈ F_{k}(v)^{∗} such that var(ψ)∩{x_{α}, ⋯ x_{α+k−1}} = ∅ and W ⊧ ∃x_{α} ⋯ ∃x_{α+k−1}ϕ ≡ ψ. Let u = v ↾ α ∈ ^{α}α^{(Id)}. By noting that F_{0}(u)^{∗} = {ϕ ∈ F_{k}(v)^{∗} : var(ϕ) ⊆ α}, we get that ψ ∈ F_{0}(u)^{∗}. Moreover we have i(k)E(u, ψ) = c_{α} ⋯ c_{α+k−1}E(u, ϕ). Case (b): g = a ∩ c, where a = −a_{0} ∩ ⋯ − a_{n}, a_{i} ∈ H(k) and c is a generalized codiagonal. If c_{α} ⋯ c_{α+k−1}g = g, then g ∈ G(0)^{∗∗}. Else c_{α} ⋯ c_{α+k−1}g is either 0 or V_{k}, pending on whether g = 0 or not. The choice of a ∈ G(0)^{∗∗} in this case is also obvious. Case (c): g = d_{0} ∩ −d_{1} ∩ ⋯ − d_{n} ∩ b ∩ c, where d_{i} ∈ H(k), b is a generalized diagonal, and c a generalized codiagonal. Assume that 1 ≤ k < ω; else there is nothing to prove. Let Γ = {α, ⋯ α + k − 1}. By the proof of fact 5.7 , we have c_{(Γ)}g is the finite union of elements of the form a_{0} ∩−a_{1} ⋯∩−a_{n} ∩b∩c where a_{0}, ⋯ a_{n} ∈ H(k), b is a generalized diagonal and c a generalized codiagonal. Further we can assume that if b = ∩{d_{ij}^{V_{k}} : i, j ∈ Δ_{1}} and c = ∩{−d_{ij}^{V_{k}} : i, j ∈ Δ_{2}, i ≠ j} then Δ_{i} ⊆_{ω} α, for i ∈ {1, 2}. By the additivity of generalized cylindrifications (namely of c_{(Γ)}), we can and will assume that

15We should point out that the complete analogue of fact 2.3 is true: That is for 0 ≤ l < k < ω we have G(l)^{∗∗} ≅ Nr_{α+l}G(k)^{∗∗}. Fact 5.8 is the special case when l = 0, which is all what we need to show that A(α) ∈ Nr_{α}W s_{α+k}, for all k < ω.

c_{(Γ)}g = c_{(Γ_{0})}E(v_{0}, ϕ_{0}) ∩ c_{(Γ_{1})}E(v_{1}, ϕ_{1}) ⋯ ∩ −c_{(Γ_{n})}E(v_{n}, ϕ_{n}) ∩ b ∩ c,

where for each i ≤ n we have Γ ⊆ Γ_{i} ⊆_{ω} α + k, ϕ_{i} ∈ F_{k}(v_{i})^{∗∗}, b is a generalized diagonal and c is a generalized codiagonal as indicated above. By fact 5.6 (i) we can assume that var(ϕ_{i}) ∩ {x_{α}, ⋯ x_{α+k−1}} = ∅. For i ≤ n let u_{i} = v_{i} ↾ α. Then u_{i} ∈ ^{α}α^{(Id)}, and by fact 5.6 (i) ϕ_{i} ∈ F_{0}(u_{i})^{∗∗}. Let b′ = ∩{d_{ij}^{V_{0}} : i, j ∈ Δ_{1}} and c′ = ∩{d_{ij}^{V_{0}} : i, j ∈ Δ_{2}, i ≠ j}. Let a = c_{(Γ_{0}−Γ)}E(u_{0}, ϕ_{0}) ∩ ⋯ c_{(Γ_{n}−Γ)}E(u_{n}, ϕ_{n}) ∩ b′ ∩ c′. Then a ∈ G(0)^{∗∗} and an easy checked i(k)a = c_{(Γ)}g.

Fact 5.9. G(0)^{∗} = A(α).

Proof. Let u ∈ ^{α}α^{(Id)} be one to one and r ∈ R. Then by definition we have

p(u, r) = E(u, C_{r}(x_{0}, x_{1}, ⋯)).

Hence p(u, r) ∈ F_{0}(u). Since G(0)^{∗∗} is a W s_{α} containing the generators of A(α) it follows that that A(α) ⊆ G(0)^{∗∗}. For the other inclusion it is enough to show that for u ∈ ^{α}α^{(Id)} and ϕ ∈ F_{0}(u), we have E(u, ϕ) ∈ A(α). We start by showing that E(u, T) ∈ A(α) for all such u. Case (a): u is one to one. Let r ∈ R . Then c_{0}(p(u, r)) ∩ c_{1}(p(u, r)) = E(u, T) ∈ A(α). Case (b): u is not one to one. Let J be a finite subset of α, such that u(J) ⊆ J and u(i) = i whenever i ∉ J. Such a J exists, but of course is not unique. Fix one such J. Let u′ = u|J. Then u′ : J → J. Let n = |Rgu′|. Then n < |J|, because u hence u′ is not one to one. We next procced as in the finite dimensional case; correlating a permuation v to u′ as follows: Let y ∈ ^{n}J such that y(0) < ⋯ < y(n − 1) and {u′_{y(0)}, ⋯ u′_{y(n−1)}} = Rgu′. For i < l put m_{y(i)} = min(u′^{−1}(u′_{y(i)})). Choose v ∈ S_{J} ( a permutation on J) such that v(m_{y(i)}) = u′_{y(i)}. Such a v exists. Let I = J − {m_{y(0)}, ⋯, m_{y(l−1)}}; suppose that I = {j_{0}, ⋯ j_{k}}, k ∈ ω and j_{0} < j_{1} ⋯ < j_{k}. Let t_{i}^{l}(x) = c_{l}x ∩ d_{il}. Let v∗ = v ∪ Id_{α−J}. Then v∗ is a permutation on α, and like the finite case, we have

t_{j(k)}^{u_{j(k)}} ∘ ⋯ ∘ t_{j(0)}^{u_{j(0)}}E(v∗, T) = E(u, T).

From case (a) we get that E(u, T) ∈ A(α). Now let u ∈ ^{α}α^{(Id)} and i, j ∈ ker(u). Then E(u, x_{i} = x_{j}) = E(u, T) ∩ d_{ij} ∈ A(α). Also for all u, v ∈ S_{α}, we have by Lemma 1**(i), E(u, C_{r}(x_{0}, x_{1}, ⋯)) = E(u, C_{r}(x_{v(0)}, ⋯) = p(u, r). Finally by noting that E(u, ¬ϕ) = E(u, T) − E(u, ϕ) we get the desired.

Fact 5.10. A(α) ∈ INr_{α}W s_{β}, for all β > α.

Proof. By fact 5.9, it suffices to show that A(α) ∈ Nr_{α}W s_{α+β} for infinite β. So let β ≥ ω. Let V_{0} = ^{α}U^{(s)} be the unit of A(α). Let s_{β} = s ∪ {(w, 0) : α ≤ i < β}. Then s_{β} ∈ ^{β}U. Let V_{β} be the weak space α+βU^{(s_{β})} and let C(α + β), or simply C(β), be the full W s_{α+β} with unit V_{β}. For k < ω let i(k, β) be the function with domain G(k)^{∗∗}, such that i(k, β)a = {s ∈ V_{β} : s ↾ α + k ∈ a}, a ∈ G(k)^{∗∗}. Then i(k, β) : G(k)^{∗∗} → C(β). Let G(β) = Sg^{C(β)}{i(k, β)G(k)^{∗∗} : 0 ≤ k < ω}. Then G(β) ∈ W s_{α+β}. Moreover, it is easy to show that G(β) = ∪{i(k, β)G(k)^{∗∗} : 0 ≤ k < ω}. From this together with facts 5.8 and 5.9, we get (using the same ideas of the proof of fact 2.4) that A(α) ≅ Nr_{α}G(β), thus A(α) ∈ INr_{α}W s_{α+β}.

By establishing fact 5.10, the proof of Theorem 1 is complete.

Remarks .

(a) Let K be a class of algebras. Then UpK and UfK denote the classes of ultraproducts and ultraroots of members of K, respectively. ElK denotes the smallest elementary class containing K. That is (see eg [HMT1] ), ElK = UfUpK. Let β > α > 1. Since B(α) is elementary equivalent to A(α), then by the Keisler-Shelah ultrapower Theorem (cf [CK], Thm 6.1.15) we have B(α) ∈ UfUp{A(α)}. It then follows from

INr_{α}Gs_{β} = Nr_{α}IGs_{β} = Nr_{α}UpGs_{β} = UpNr_{α}Gs_{β}

(cf [N83], Cor.2), and from fact 4.3 and fact 5.3 that B(α) ∈ UfNr_{α}W s_{β}− Nr_{α}CA_{β}. In particular, some ultrapower of B(α) is in Nr_{α}CA_{α+ω}.

(b) From now on, for undefined categorial terms, we refer the reader to [AHS]. Let K be a class of algebras. Then we identify K with the (concrete) catogory whose objects are the members of K, and whose morphisms are the homomorphisms between members of K. Let β > α > 1. Assume that W s_{β} ⊆ L ⊆ CA_{β}. Then K = Nr_{α}L is not a complete category , i.e not closed under all limits. We will show that in fact K is not closed w.r.t taking equalizers (which are special limits). To see this, let A(α) and B(α) be the algebras dealt with so far. Let P = ∪{P (u) : u ∈ S_{α}}. Let g : P (Id) → P (Id) be any function such that g(p(Id, r)) = p(Id, r) iff r ∈ N. Let f ∈ Aut(A(α)) be such that g ⊆ f and f(x) = x for all x ∈ P − P (Id). Such an f exists by fact 3.2 (the finite dimensional case) and fact 5.1 (v) (the infinite dimensional case). It is now easy to see that B(α) is the equalizer of f and the identity map on A(α). That is K is not closed under forming equalisers, since A(α) is in K while B(α) is not.

In particular, Nr_{α}RCA_{β} and Nr_{α}CA_{β}, though closed under products, are not complete categories (It is known that a category is complete iff it is closed under products and equalizers).

§6. DISCUSSION AND RELATED RESULTS

(1) SC_{α}, QA_{α} and QEA_{α} stand for the classes of Pinters substitution, Halmos’quasipolyadic and quasipolyadic equality algebras of dimension α, respectively. We refer the reader to the appendix of [N96] for an explicit (finite schema) axiomatisation of such varieties.

Let K ∈ {SC, QA, QEA}.

Generalizing the [N83] result cited in the introduction, it is shown in [ANS98] that for 1 < α < β, the class of α-dimensional neat reducts of algebras in K_{β}, or Nr_{α}K_{β} for short, is not closed under forming subalgebras. This result is announced in [ANS96]. In [S98a], it is shown that Nr_{2}K_{β}, (β > 2) is not closed under forming elementary subalgebras (equivalently, not closed under ultraroots). It is absolutely straightforward to check that the construction adopted herein generalizes the [S98a] result to higher dimensions for SC’s. More precisely:

Corollary 1 . Let 1 < α < β. Then Nr_{α}SC_{β} is not elementary.

Sketch of proof. Passing to reducts; that is let Rd_{sc}A(α) ^{16} be the SC reduct of A(α) and let Rd_{sc}B(α) be the SC reduct of B(α). Then Rd_{sc}A(α) ∈ Nr_{α}SC_{α+ω} and Rd_{sc}B(α) ∉ Nr_{α}SC_{α+1}

It is also straightforward to show that the complete analogue of Theorem 1 continue to hold for SC’s. (Since reducts of weak set algebras are weak set algebras).

However the construction adopted herein does not settle the QA and QEA cases. This follows from the fact that in these algebras the term αs(0, 1) (that played the key role in showing that B(α) is not a neat reduct, cf. facts 4.3 and 5.3) is actually a basic operation in these algebras, whereas the the proof adopted herein very much depended on the fact that this term is not (even) term definable in CA’s, a result of Andreka and Nemeti (cf., [AN83]). We should mention , though that, A(α) is actually the reduct of a QEA_{α}, ^{17} and even more this expansion of A(α) is in Nr_{α}QEA_{β}.

Therefore it seems very plausible though, that the [S98a] result, can be generalized to higher dimensions for QA’s and QEA’s using a combination of the ideas presented herein, and those in [S98a]. ^{18}

More precisely:

Conjecture 1 . Let β > α > 1, and K ∈ {QA, QEA}. Then UfNr_{α}K_{β} ≠ Nr_{α}K_{β}.

(2) Let 1 < α < β. Let K ∈ {SC, CA, QA, QEA}.

It is proved in [N83] and [ANS98] that SNr_{α}K_{β} ⊈ ElNr_{α}K_{β}. In particular, in view of Theorem 1 and Corollary 1, the following inclusions are proper for L ∈ {SC, CA}:

16Let A ∈ CA_{α}. Then Rd_{sc}A = ⟨A, ∪, ∩, −, c_{i}, s_{i}^{j}⟩_{i,j∈α}, where s_{i}^{j} is the unary term as defined in 1.5.1 [HMT1]. Pinters algebars, are thus (generalized) reducts of CA’s

17A QEA_{α} is an algebra of the form ⟨A, p_{ij}⟩_{i,j∈α} where A ∈ CA_{α} and the p_{ij}’s are unary operations on A, abstracting the familiar metalogical operation of interchanging the (free)

occurances of the variables x_{i} and x_{j} in a formula ϕ. The p_{ij}’s are BA automorphisms of A. A(α) can be expanded to a representable QEA_{α} by defining p_{ij}X = {s ∈ V :

so[i, j] ∈ X}(X ∈ (A(α)). Here [i, j] is the transposition on α interchanging i, j. and leaving everything else fixed. We note that p_{01} = _{α}s(0, 1).

18In [S98a], instead of _{2}(s(0, 1)) a “composition like” term (that is not term definable in QEA’s) was used.

Nr_{α}L_{β} ⊂ ElNr_{α}L_{β} ⊂ SNr_{α}L_{β}.

In passing we note that SNr_{α}K_{β} is a variety (cf, [HMT1], 2.6.33). ^{19}

In [ANS98], the QA and QEA analogue of Theorem 2 are also proved.

(3) Let K = ⟨K_{α} : α ≥ ω⟩ be a system of varieties, not necessarily definable by schemes in the sense of [HMT2] Def.,5.6.12, but for which the notion of neat reducts make sense, so that in particular , we can talk about the class SNr_{α}K_{α+ω}. For a “concrete” K, and in the presence of a NET, this class is just the class of representable algebras. (See for eg [S97]). In addition to cylindric algebras (CA’s), typical examples include the most well known varients of CA’s namely K ∈ {SC, QA, QEA, P A}. Here P A denotes Halmos’ infinite dimensional polyadic algebras in the sense of [HMT2], Def., 5.4.1.

We say that K has the S neat reduct property if no new α- dimensional elements are generated from α dimensional elements even in the presence of ω extra operations. Formally; for all α ≥ ω, for all C ∈ K_{α+ω}, and for all X ⊆ Nr_{α}C, we have

Sg^{Nr_{α}C}X = Nr_{α}(Sg^{C}X).

The following is investigated in [ANS98]: Under what conditions on (rather abstract) K are (any two of) the following three conditions equivalent:

(a) For all α, the class SNr_{α}K_{α+ω} has the strong amalgamation property .

(b) In SNr_{α}K_{α+ω} epis (in the categorial sense) are surjective.

(c) K has the S neat reduct property.

It is known (see for eg [N96]) that (a) and (b), are the algebraic counterparts of the familiar metalogical properties of Craig and Beth, respectively. By Theorem 2 CA’s do not have the S neat reduct property. In more detail, taking X = B(α), and C = C(α + ω) we get:

19In fact K_{α} is the first member of a descending sequence of varieties: SNr_{α}K_{α+k}, k ∈ ω, approximating RK_{α}. It is easy to check that SNr_{α}K_{α+ω} ⊆ .....SNr_{α}K_{α+k+1} ⊆ SNr_{α}K_{α+k} ⊆ SNr_{α}K_{α} = K_{α}. It is known, see for eg [N96] that RK_{α} (the first member of the sequence) ≠ SNr_{α}K_{α+k} for α > 2 and finite k. Pigozzi showed (unpublished) that the above inclusions are proper when K = CA and α is infinite. Recently, Hirsch, Hodkinson and Maddux proved that, in the CA case, the above inclusions are also proper when α = n is finite (n > 2). That is SNr_{n}CA_{n+k+1} ≠ SNr_{n}CA_{n+k}, for all finite k. Besides generalizing Monks result quoted above (that RCA_{n} ≠ SNr_{n}CA_{n+k} for all finite k), this solves problem 2.12 in [HMT1].

B(α) = Sg^{Nr_{α}C}B(α) ≠ Nr_{α}(Sg^{C}B(α)) = A(α). As previously noted, the above (counterexample) also settles item (v) in the introduction of [HMT2]. (See also [M91], p.724, and [ANS98] for further elaboration). We should also mention, that the connection of (a) and (c) was studied, in the context of CA’s in [Pi71]. (See 2.2.11-2.2.20, therein). ^{20} The logical implications of (c) not holding for CA’s are hinted upon in [N83].p 406. Logics corresponding to SNr_{α}K_{α+ω}, K ∈ {SC, CA} were also investigated in [AGN77]. That P A has the S neat reduct property, was used by Johnson in [J70], to show that (a) and (b) hold for (representable) P A_{α}’s, (α ≥ ω), equivalently that the properties of Beth and Craig hold for Kieslers logics.

In (4) and (5) below, n stands for a finite ordinal.

(4) In [S97], the class Nr_{n}CA_{ω} is extensively studied in connection to first order logic. For example it is shown in [S97], that countable algebras in Nr_{n}CA_{ω} satisfy the algebraic version of Henkin-Orey’s omitting types theorem, (cf, [CK], Theorem 2.2.9), or OT T, for short. This provides a partial answer to the following question: When does the OT T, hold for L_{n} theories, i.e first order theories restricted to the first n variables?.

(5) In [AS98], the OT T for L_{n} theories is further investigated in its own right, and in connection to the notion of complete representations in algebraic logic. (Cf., [HH97a],and [HH97b]). It is shown therein, that atomic countable algebras in Nr_{n}CA_{ω} are completely representable, or CR for short. This is generally not true, for atomic countable algebras in SNr_{n}CA_{ω}, if n > 2. Recall that by the NET, SNr_{n}CA_{ω} = RCA_{n}. We refer the reader to [HH97b] and [An97] for examples of countable atomic RCA′_{n}s, n > 2 that are not CR. These counterexamples are used in [AS98] to show that a weak version of the OT T fails for L_{n}, if n > 2 . The condition n > 2 is important here, since it is known that every atomic (not necessarily countable) RCA_{n}, n ≤ 2 is CR. The latter can be easily recovered from the proof of Thm 3.2.65 in [HMT2].

The class of countable completely representable CA_{n}’s, or CR_{n} for short, is further characterised via special neat embeddings in [AS98]. In more detail, let A and B be boolean algebras, such that A ⊆ B. B is said to be a faithful extension of A, if for all X ⊆ A, whenever supX = 1 in A, then supX = 1 in B.

20In [Pi71], the following was proved: Let L ∈ RCA_{α}. If L has the amalgamation property , briefly AP and whenever A ∈ L is a generating subreduct of B ∈ CA_{α+ω}, (here the NET is actually used) then A = Nr_{α}B; then L has strong AP, briefly SAP. In [ANS98], it is shown that conversely when generating subreducts in L are not neat reducts, then SAP fails for L, even if it already has AP. The following stronger result is also proved: If W s_{α} ⊆ L ⊆ RCA_{α}, then L does not have SAP even w.r.t RCA_{α}. The reader is refered to [Pi71] for definitions.

A ∈ CA_{n} is said to be strongly representable, or SR for short, if there exists B ∈ CA_{ω} such that A ⊆ Nr_{n}B, and B is a faithful extension of A. The following is proved in [AS98]: Let SR_{n} denote the class of strongly representable CA_{n}’s. Let A ∈ CA_{n} be atomic and countable. Then A ∈ CR_{n} iff A ∈ SR_{n}. The proof is a Baire category argument at heart. We do not know, how much “countability” is needed in the above result when n > 2, though. That is:

QUESTION 1 . Let n > 2. Let A ∈ SR_{n}, with |A| > ω be atomic. Is A completely representable? In particular are atomic (not necessarily countable) algebras in Nr_{n}CA_{ω}, n > 2 completely representable?

We point out that the converse of the above is true, regardless of the cardinality of the algebra involved. That is if A ∈ CA_{n} is completely representable, then A ∈ SR_{n}. In this connection, we note that A(n) and B(n) are both in SR_{n}, since, as easily checked, they are completely representable. Also Nr_{n}CA_{ω} is a proper subclass of SR_{n}; since B(n) ∉ Nr_{n}CA_{ω}. We do not know whether there are countable algebras in SR_{n}, that are not in Nr_{n}CA_{ω}. A candidate would be a countable elementary subalgebra of B(n). We should mention that countable algebras in SR_{n} ^{21}, still admit an OT T, in the following sense: Let T be a countable L_{n} theory. If the RCA_{n} of formulas corresponding to T (in the sense of [HMT2] sec 4.3), is in SR_{n}, then any countable family of non principal types in T are omissable. Here types, non principal types and omissable are defined as one might expect; i.e the usual way. ^{22} Also it is shown therein that the omission of < ^{ω}2 (not necessarily countably) many L_{n} types, of a countable L_{n} theory, lead to propositions that are independent of ZF C. In fact, the statement that countable algebras in SR_{n} admit omission of < ^{ω}2 non principal types, can be regarded as an instance of the famous (independent) Martins axiom in set theory, restricted to countable BA’s. A different characterisation of CR_{n}, using game-theoretic techniques is given in [HH97b], to show that CR_{n} is not elementary, iff n > 2. It seems that one can make the translation from the “Baire category” approach adopted in [AS98] to Hirsch-Hodkinsons games, both being instances of Robinsons finite forcing, by way of the Banach-Mazur Theorem (cf [H] p. 358).

21It is shown in [AS98], using the characterisation of countable CR_{n}’s, how SR_{n} can be regarded as the best possible class of RCA_{n}’s admitting an OT T

22Let T be an L_{n} theory. A type is simply a consistent set of L_{n} formulas. A type Γ is non principal if no L_{n} formula consistent with T isolates it: i,e there is no ϕ with var(ϕ) ⊆ {x_{0}, ....x_{n−1}} such that ϕ is consistent over T and T ⊧ ϕ → ψ, for every ψ ∈ Γ. Γ is omissable if there exists a countable model M ⊧ T such such that no assighnment in M satisfies all formulas in Γ.

(6) In contrast to K ∈ {SC, CA, QA, QEA}, it is shown in [S98b] that if K_{α}, with ω ≤ α ≤ ω + ω, is the variety (of algebras of α-ary relations) introduced and investigated in [Sa98], then K_{ω} = Nr_{ω}K_{ω+ω} . In particular, neat reducts are closed under forming subalgebras. Using the ideas presented in [AS98] and [ANS98] an OT T and a Beth-definability Theorem is also proved for the corresponding logics. These, as noted in the introduction, are expansions of first order logic without equality.

Aknowledgement . I wish to express my deepest gratitude to Professor Hajnal Andréka for her help, support and extremely useful suggestions during the writing of this paper.

REFERENCES

1. [AHS] Adamek,J.,Herrlich,H. and Strecker,G.,Abstract and concrete categories, or the joy of cats. John Wiley and sons (1990)

2. [A93] Amer,M., Cylindric algebras of sentences. Abstract. Journal of Symbolic logic 58, 2 p.743. 1993.

3. [An97a] Andreka,H., Complexity of equations valid in algebras of relations. Annals of Pure and Applied logic, 89, pp 149-209. 1997

4. [An97b] Andreka,H., Atomic representable relation and cylindric algebras with nonrepresentable completions. Manuscript. 1998.

5. [AGN77] Andreka,H., Gregely,T., and Nemeti,I., On universal algebraic constructions of logics Studia Logica , vol 36, p.9-47. 1977.

6.[AN75] Andreka,H., Nemeti,I., A simple purely algebraic proof of the completeness of some first order logics Algebra Universalis. vol 5,p. 8-15b 1975

7.[AN83] Andreka,H., Nemeti,I., Definability of substitutions in Gs’s. Preprint. Mathematical Institute. Hungarian Academy of Sciences.

8. [ANS96] Andreka,H., Nemeti,I., and Sayed Ahmed,T., On neat reducts of algebras of logic. Presented in Logic Colloquium 1996. Abstract appeared in the Bulletin of Journal of Symbolic Logic.

9.[ANS98] Andreka.,H, Nemeti.,I, and Sayed Ahmed,T.,Amalgamation in algebras of logic. Presented in the ”Universal Algebra” conference held in Szeged , Hungary 1998. In preparation.

10. [AS98] Andreka,H., and Sayed Ahmed,T., Omitting types in logics with finitely many variables. In preparation. Presented in the Logic Colloquium 1998. Abstract appeared in the Bulletin of the Journal of Symbolic Logic.

11. [CK] Chang, Keisler Model Theory. North Holland, 1994.

12. [DM63] Diagneault,A., and Monk,J.D., Representation Theory for Polyadic algebras. Fund.Math. Vol 52 p.151-176, 1963

13. [F92] Ferenczi M., On representability of cylindric algebras. Abstracts of papers presented to the Amer. Math. Society vol 13 No 3, p.336, 1992.

14. [F98] Ferenczi M., On representability of neatly embeddable cylindric algebras. Journal of applied non-classical logics. To appear.

15. [HMT1] Henkin,L., Monk,J.D., and Tarski, A., Cylindric Algebras Part I. North Holland, 1971.

16. [HMT2] Henkin,L., Monk,J.D., and Tarski,A., Cylindric Algebras Part II. North Holland, 1985.

17. [HMTAN] Henkin,L., Monk,J.D., Tarski,A., Andreka,H., and Nemeti,I., Cylindric Set Algebras, lecture notes in Mathematics 883, Springer Verlag, 1981.

18. [HH97a] Hirsch,R., and Hodkinson,I., Step by step-building representations in algebraic logic. Journal of Symbolic Logic, 62(1)p.225-279, 1997.

19. [HH97b] Hirsch,R., and Hodkinson,I., Complete representations in algebraic logic. Journal of Symbolic Logic 62(3)p.816-847, 1997

20. [H] Hodges W. Model Theory Cambridge. University press. 1995 21.[J70] Johnson, J.S. Amalgamation of Polyadic Algebras. Trans.

Amer.Math.Soc., vol 17, p.834. 1970

22. [Ma77] Maddux ,R., Relation algebras and neat embeddability of cylindric algebras. Notices American Math. Society. vol 24. p.298 1977.

23. [Ma78] Maddux,R., Topics in relation algebras P.h.D dissertation. University of California, Berkley. 1978.

24 .[M69] Monk., J.D., Non finitisability of classes of representable cylindric algebras. Journal of Symbolic Logic. vol 34 p.331-343. 1969.

25. [M91] Monk.,J.D., Remarks on the problems in the books Cylindric Algebras, Part I and Part II and Cylindric set algebras. In Algebraic Logic p.723-746, edited by Andreka, H., Nemeti.I., and Monk.J.D., North Holland, Amsterdam. 1991.

26. [N83] Nemeti,I., 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, Volume 24, Number 3, July 1983, pp 399-409.

27. [N96] Nemeti,I., Algebraisation of quantifier logics, an introductory overview. Math.Inst.Budapest, Preprint, No 13-1996. A shortened version appeared in Studia Logica vol 50.4 p.465-569. 1991.

28. [Pi71] Pigozzi,D., Amalgamation, congruence extension, and interpolation properties in algebras. Algebra Universalis. Vol 1. p.269-349. 1971.

29.[Sa98] Sain,I. Searching for a finitizable algebraization of first order logic. Submitted

30. [S97] Sayed Ahmed, T. Algebras of sentences of Logic. Masters Thesis, Cairo University. 1997.

31. [S98a] Sayed Ahmed, T. The class of 2-dimensional neat reducts of polyadic algebras is not elementary. Manuscript. 1998

32.[S98b]. Sayed Ahmed, T. On Sain’s algebras. Manuscript.1998