Boolean Algebras, Tarski Invariants, and Index Sets

Barbara F. Csima Antonio Montalbán^{∗} Richard A. Shore^{∗}

Department of Mathematics Cornell University Ithaca NY 14853

August 27, 2004

Abstract

Tarski defined a way of assigning to each boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we analyze the complexity of the question “Does B have invariant x?”. For each x ∈ In we define a complexity class Γ_{x}, that could be either Σ_{n}, Π_{n}, Σ_{n} ∧Π_{n}, or Π_{ω+1} depending on x, and prove that the set of indices for computable boolean algebras with invariant x is complete for the class Γ_{x}. Analogs of many of these results for computably enumerable Boolean algebras were proven in [Sel90] and [Sel91]. According to [Sel03] similar methods can be used to obtain the results for computable ones. Our methods are quite different and give new results as well. As the algebras we construct to witness hardness are all dense, we establish new similar results for the complexity of various isomorphism problems for dense Boolean algebras.

1 Introduction

A common theme in mathematical investigations is the classification of structures (within a specified class) and the characterization of the (sub)classes delineated. Indeed, Hodges [Hod93] offers the classification process (along with constructions of specified types of structures) as the essence of model theory. Of course, the general endeavor pervades many branches of mathematics. Our topic in this paper has its origin in such a study of the class of Boolean algebras. It begins with Tarski’s classification [Tar49] of Boolean algebras into countably many classes each consisting of the models of a complete extension of the basic theory. (Of course, this classifies Boolean algebras up to elementary equivalence.) His motivation was to prove that the theory of Boolean algebras was decidable and he did this by producing a uniformly computable list of axioms for (each of) the complete extensions corresponding to his classification.

∗Partially supported by NSF Grant DMS-0100035.

Given such a classification (or the prospect of one), one may well want to characterize membership in each subclass in some way and analyze the complexity of the classes (i.e. of membership in each). The algebraist asks for invariants corresponding to structural properties that determine membership in each class. The model theorist might ask for the (simplest) axioms that insure such membership. The descriptive set theorist or recursion theorist wants to determine the location of the classes in some standard hierarchy. The former, expresses the results as completeness properties for the classes of countable structures at levels of the Borel hierarchy. The latter, takes the lightface approach of proving completeness of the subclasses of the computable structures in the arithmetic, hyperarithmetic or analytic hierarchy. (Typically, relativization of such lightface characterizations produces the boldface Borel ones.)

For the classification of Boolean algebras up to elementary equivalence, Tarski [Tar49] (see also [Ers64], [Gon97, Ch. 2] and [Mon89, Ch. 7]) provides the structural information by describing algebraic invariants as well as axiomatizations for each class. The determination of the simplest form of such axiom systems (in the sense syntactic complexity) is given by Wasziewicz [Was74]. In this paper, we provide the recursion (and so descriptive set) theoretic characterizations of these classes as complete at specified levels of the arithmetic hierarchy and a bit more. The classes provide not only index sets complete at the Σ_{n} or Π_{n} level for each n < ω but also for level Π_{ω+1} (the sets co-c.e. in 0^{(ω)}) and even more unusually for the classes Σ_{n} ∧ Π_{n} (the sets which are intersections of one in Σ_{n} and one in Π_{n}) for n ≡ 1, 2 (mod 4). As a by-product of our analysis we reprove the results of [Was74] as well.

A standard question related to classifying the complexity of membership in such subclasses is how to characterize the complexity of the isomorphism problem (when two structures are isomorphic) for structures in the class or specified subclasses. Again, there are natural descriptive set theoretic as well as recursion theoretic versions of this problem. For the class of all Boolean algebras the isomorphism problem is as complicated as possible, i.e. Σ_{1}^{1} complete, and so one typically says that there is no way to classify all Boolean algebras up to isomorphism or provide isomorphism invariants. There is, however, an algebraically defined class of Boolean algebras, the dense Boolean algebras (see Definition 4.2), for which elementary equivalence is the same as isomorphism. (So model theoretically these are the saturated Boolean algebras.) We construct dense Boolean algebras as witnesses for all the hardness results for membership in each of the elementary classes. Thus we can deduce analogous results for isomorphism problems on these classes of Boolean algebras. (Some care needs to be taken as being dense is itself a complicated property.) We present the results in terms of typical strong index set notation, e.g. (Σ_{n}, Π_{n}) ≤_{m} (DB_{r}, DB_{s}) (where DB_{r} and DB_{s} are classes of dense Boolean algebras) as in Soare [Soa87, IV.3.1] and explained in Definition 2.9. This easily translates into the terminology proposed by Knight of the isomorphism relation being, e.g. Π_{n}, within some class of dense Boolean algebras. (See Definition 2.11 and also [Cal] for further discussion of this notion.) Thus our results also supply examples of classes complete (in a strong way) at the same syntactic levels for a collection of isomorphism problems. (Isomorphism problems at certain higher levels of the hyperartihmetical hierarchy are provided by classes of reduced Abelian p-groups as shown in Calvert [Cal].)

While all of these issues are natural in their own right, we should note that we came to the particular questions addressed here from the problem of classifying the complexity of related issues in terms of Reverse Mathematics. The question raised in [Sho04] is the proof theoretic complexity of the existence of invariants for (countable) Boolean Algebras classifying them up to elementary equivalence. Answers to such questions are often provided by index set type results. Indeed, as explained in [Sho04] it seemed plausible, because of the nature of the results and the proof theoretic issues, that one might need such results in this case. As it turned out, weaker hardness theorems for membership in some of the classes sufficed to reach the desired proof theoretic system of ACA_{0}^{+} (corresponding to the existence of X^{(ω)} for every set X). Nonetheless, the recursion theoretic questions remained interesting. In particular, the class at level Π_{ω+1} plays no role in the proof theoretic analysis and we thank Jim Schmerl for raising the corresponding question.

As we were about to submit this paper for publication, we came across [Sel03], a survey of positive (i.e. computably enumerable) structures. Selivanov describes there (Theorems 4.5.5-4.5.7) a number of results on index sets for computably enumerable Boolean algebras which, along with many others, appear in [Sel90] and [Sel91]. He also states (Remark 1 following Theorem 4.5.7) that analogs of the results mentioned may be proven for the computable Boolean algebras (with the index sets one step lower in every case) by straightforwardly generalizing his proofs for the computably enumerable ones. The analogs of the results mentioned in [Sel03] and appearing in [Sel91] cover our completeness results for the finitely axiomatizable classes of Boolean algebras. Others in [Sel90, Lemma 12], if also generalized to the computable case, would cover the other cases except for the nonarithmetic class at level Π_{ω+1}. (The explicit results of [Sel90, Lemma 12] give the strong index set form of the results corresponding to the first four lines of our table in Theorem 2.10. The general ones for finitely axiomatizable classes as in [Sel91, p. 168] provide completeness results but do not explicitly give the strong form of the index set results as in the fifth and sixth lines of our table.) The question corresponding to the nonarithmetic class of computably enumerable Boolean algebras is explicitly left open in [Sel90]. All of our proofs, including the nonarithmetic case, immediately supply the corresponding results for computably enumerable algebras. (The index sets are one level higher in the arithmetic hierarchy than those for computable Boolean algebras in the arithmetic cases and at the same level (Π_{ω+1}) in the nonarithmetic one. To see this, note that one can go from computable to computably enumerable at the cost of one level in the hierarchy by simply relativizing to algebras computable in 0′ as every Δ_{2}^{0} (i.e. computable in 0′) Boolean algebra is isomorphic to a uniformly constructed Σ_{1}^{0}, i.e. computably enumerable, one (essentially by [Fei67] according to [Dow97, Cor. 3.10] or explicitly by [OS89, Th. 2]). Of course, Π_{ω+1} relativized to 0′ is still Π_{ω+1} and so the result is the same for the computably enumerable algebras as for the computable ones in this case.) Thus we also reprove some of the results of [Sel90] and [Sel91].

Our methods are quite different from Selivanov’s. We use no representations as tree algebras but extensively exploit the back and forth relations and notions of k-friendliness of [AK00] to unify and simplify our analysis in the arithmetic cases. The nonarithmetic case also needs some specific constructions using interval algebras. All our results are proven for dense Boolean algebras and so also provide new results on index sets for the isomorphism problem for these algebras as mentioned above.

We provide the basic definitions for Boolean algebras needed to define our classes and state the main index set type theorems in Section 2. We prove the easy, quantifier counting aspect of our complexity results in Section 3. We define dense Boolean algebras in Section 4 and present some useful lemmas about them. Section 5 introduces the back and forth relations of Ash and Knight [AK00] and their notion of k-friendly structures. The remaining sections prove the hardness results for the various classes of Boolean algebras: Σ_{n} or Π_{n} for every n < ω; Σ_{n} ∧ Π_{n} for n ≡ 1, 2(mod 4); and, finally, Π_{ω+1}.

We refer the reader to Monk [Mon89] (especially Ch. 7) and Goncharov [Gon97] (especially Ch. 2) for general background about Boolean algebras. For recursion theory, we suggest Soare [Soa87].

2 Definitions and Theorems

We begin with some basic definitions.

Definition 2.1. Let B be a Boolean algebra. We use the usual notation of constants 0 and 1 and operations ∧, ∨, and ¬. We define the following abbreviations. We let x ≤ y abbreviate x ∧ y = x; x − y abbreviate x ∧ ¬y; and x△y abbreviate (x − y) ∨ (y − x). We say that x ∈ B is an atom if x ≠ 0 & ∀z < x(z = 0); x is atomic if for every non-zero element z < x, there is an atom y ≤ z; x is atomless if it has no atoms below it.

Let I(B) denote the ideal of all elements x of B such that x = y ∨ z, where y is atomic and z is atomless. Let B^{[0]} = B, and B^{[n+1]} = B^{[n]}/I(B^{[n]}). We now define the invariant of B to be inv(B) = ⟨p, q, r⟩, where p ≤ ω, q ≤ ω, r ≤ 1, and

p = \begin{cases}min\{n : B^{[n+1]} = 0\} & if it exists, \\ ω & otherwise, \end{cases}

q = \begin{cases}sup\{n : B^{[p]} has at least n atoms\} & if p < ω, \\ 0 & if p = ω, \end{cases}

r = \begin{cases}1 & if p < ω and B^{[p]} contains an atomless element, \\ 0 & otherwise. \end{cases}

If inv(B) = ⟨p, q, r⟩, we write inv_{1}(B) = p, inv_{2}(B) = q, and inv_{3}(B) = r. We let In be the set of possible invariants. That is, In is the set of triplets ⟨p, q, r⟩ ∈ (ω+1)×(ω+1)×2 such that if p = ω then q = r = 0 and if p < ω then q and r are not both 0.

The original theorem showing that these are invariants for elementary equivalence is Tarski’s:

Theorem 2.2 (Tarski). [Tar49] If A and B are Boolean algebras, then inv(A) = inv(B) if and only if A and B are elementarily equivalent.

To simplify our notation we assign names to the classes (of computable algebras) corresponding to each invariant and an additional level value that will roughly correspond to the level of the associated index sets.

Definition 2.3. Given ⟨p, q, r⟩ ∈ In, we let B_{⟨p,q,r⟩} be the set of indices of computable Boolean algebras with invariant ⟨p, q, r⟩. To each x ∈ In we assign a level, l(x) ∈ ω + 1, as follows

l(x) = \begin{cases}4p + 1 & if x ∈ \{⟨p, q, 0⟩ : q < ω\}, \\ 4p + 2 & if x ∈ \{⟨p, q, 1⟩ : q < ω\}, \\ 4p + 3 & if x = ⟨p, ω, 0⟩, \\ 4p + 4 & if x = ⟨p, ω, 1⟩, \\ ω & if x = ⟨ω, 0, 0⟩. \end{cases}

For a Boolean algebra B, we let l(B) = l(inv(B)). Given n ∈ ω, we let B_{n} be B_{⟨p,1,0⟩} if n = 4p + 1, B_{⟨p,0,1⟩} if n = 4p + 2, B_{⟨p,ω,0⟩} if n = 4p + 3, and B_{⟨p,ω,1⟩} if n = 4p + 4. We let B_{⟨p,q̄,r⟩} = ∪{B_{⟨p,q′,r⟩}|q′ ≠ q, ω} and B_{⟨p̄,q,r⟩} = ∪{B_{⟨p′,q,r⟩}|p′ ≠ p}.

We can now formulate our main results in terms of characterizing the complexity of these index sets. First, we deal with the standard levels of the arithmetic hierarchy.

Theorem 2.4. For every n, B_{n} is Σ_{n}-complete if 4 divides n and Π_{n}-complete if 4 does not divide n.

Next, we turn to completeness results that fall between some of the Σ_{n} and Σ_{n+1} levels.

Definition 2.5. A set S is in Σ_{n} ∧ Π_{n} if there are ϕ ∈ Σ_{n} and ψ ∈ Π_{n} such that x ∈ S ↔ ϕ(x) & ψ(x).

Theorem 2.6. For every p < ω, and 1 < q < ω, B_{⟨p,q,0⟩} is Π_{n} ∧ Σ_{n}-complete, where n = 4p + 1 = l(⟨p, q, 0⟩). For every p < ω, and 0 < q < ω, B_{⟨p,q,1⟩} is Π_{n} ∧ Σ_{n}-complete, where n = 4p + 2 = l(⟨p, q, 1⟩).

Finally, we reach the level beyond the arithmetic ones.

Definition 2.7. A set S is Σ_{ω+1}^{0} if it is c.e. in 0^{(ω)}, and it is Π_{ω+1}^{0} if its complement is Σ_{ω+1}.

(Note that we here follow the notation used in Soare [Soa87, XII.4]. In Ash-Knight [AK00], these classes are called Σ_{ω}^{0} and Π_{ω}^{0}, respectively.)

It is well known, and not hard to prove, that a set S is Π_{ω+1} if there is a computable f such that n ∈ S ⟺ ∀j(f(n, j) ∉ 0^{(j)}). A set S is Σ_{ω+1} iff \overline{S} is Π_{ω+1}, that is, if there is a computable f such that n ∈ S ⟺ ∃j(f(n, j) ∈ 0^{(j)}).

Theorem 2.8. B_{⟨ω,0,0⟩} is Π_{ω+1}-complete.

In fact, in every case our proofs will show more.

Definition 2.9. For any class Γ (of subsets of ω) and its complementary class Γ̆ = {S̄|S ∈ Γ} and for any A, B ⊆ ω, (Γ, Γ̆) ≤_{m} (A, B) means that for every S ∈ Γ there is a computable function f such that ∀x(x ∈ S → f(x) ∈ A) and ∀x(x ∉ S → f(x) ∈ B).

Our constructions will control the outcomes required in the proofs of hardness so as to improve the hardness conclusion. We can summarize our results as follows:

Theorem 2.10. For each x ∈ In, B_{x} is in Γ_{x} where Γ_{x} is specified in the second column of the table below. Moreover, B_{x} is complete for Γ_{x} and, indeed, complete in the sense of a reduction for (Γ_{x}, Γ̆_{x}) as given by the third column:

x  Γ_{x}  (Γ_{x}, Γ̆_{x}) ≤_{m}
⟨p, 1, 0⟩  Π_{4p+1}  (B_{⟨p,1,0⟩}, B_{⟨p,0,1⟩})
⟨p, 0, 1⟩  Π_{4p+2}  (B_{⟨p,0,1⟩}, B_{⟨p,ω,0⟩})
⟨p, ω, 0⟩  Π_{4p+3}  (B_{⟨p,ω,0⟩}, B_{⟨p,ω,1⟩})
⟨p, ω, 1⟩  Σ_{4p+4}  (B_{⟨p,ω,1⟩}, B_{⟨p+1,1,0⟩})
⟨p, q, 0⟩, 1 < q < ω Σ_{4p+1} ∧ Π_{4p+1} (B_{⟨p,q,0⟩}, B_{⟨p,q̄,0⟩})
⟨p, q, 1⟩, 0 < q < ω Σ_{4p+2} ∧ Π_{4p+2} (B_{⟨p,ω,1⟩}, B_{⟨p,ω̄,1⟩})
⟨ω, 0, 0⟩  Π_{ω+1}  (B_{⟨ω,0,0⟩}, B_{⟨ω̄,ω,0⟩})

In addition, in every case we will also be able to restrict the sets of (indices for) Boolean algebras in the third column to the (indices for) dense ones (Definition 4.2) in the same classes. (When we say that B_{x} is in Γ_{x} for ⟨0, 1, 0⟩ and ⟨0, 1, 1⟩ we mean that there formulas of the form specified by Γ_{x} such that any Boolean algebra satisfying them is in B_{x}. The issue here is that to say that a number is an index of a Boolean algebra (or even a structure at all) is already Π_{2}.)

As Goncharov [Gon97, 2.3.2] proves that any two countable dense Boolean algebras with the same invariant are isomorphic, we can restate some of these results in terms of the terminology introduced by Knight (see [GK02] and [Cal, 3.1, 3.2] and the accompanying discussion) for classifying the complexity of the problem of determining if two structures are isomorphic.

Definition 2.11. Let Γ be a class of subsets of ω (e.g. a complexity class such as Π_{n}), A ⊆ B ⊆ ω (e.g. the sets of indices of some subclass and class, respectively, of structures). We say that A is Γ complete within B if, for any S ∈ Γ, there is a computable function f : ω → B such that ∀n(n ∈ S ⇔ f(n) ∈ A).

Corollary 2.12. The isomorphism problem for dense Boolean algebras, i.e. the set A = {⟨i, j⟩| i and j are indices of isomorphic dense computable Boolean algebras}, is Π_{ω+1} complete within DB, the set of indices of dense computable Boolean algebras. Indeed, for x ∈ In, the finer problem of being isomorphic to the dense Boolean algebra D_{x} of level l(x), {i|i is an index of a dense Boolean algebra isomorphic to D_{x}}, is Γ_{x} complete within DB for Γ_{x} as specified in the table in Theorem 2.10.

The results of Wasziewicz [Was74] are also derived along the way and slightly improved. (See Section 3 and the final remarks of Section 6 for the proofs.)

Theorem 2.13. [Was74] If x ∈ In and l(x) = n < ω, then the class of Boolean algebras B with inv(B) = x is axiomatized as follows:

x  Axioms
⟨p, 1, 0⟩  one ∀_{4p+1}
⟨p, 0, 1⟩  one ∀_{4p+2}
⟨p, ω, 0⟩  one ∀_{4p+3} and a computable set of ∃_{4p+2}
⟨p, ω, 1⟩  one ∃_{4p+4} and a computable set of ∃_{4p+2}
⟨p, q, 0⟩, 1 < q < ω  one ∃_{4p+1}and one ∀_{4p+1}
⟨p, q, 1⟩, 0 < q < ω  one ∃_{4p+2}and one ∀_{4p+2}
⟨ω, 0, 0⟩  one ∀_{n} for each n

By [Tar49], each class corresponds to a complete theory and so, for any m < ω, if l(B), l(B′) ≤ m and B ≡_{m} B′ (i.e. they satisfy the same ∃_{m} sentences) then B ≡ B′. On the other hand, if l(B), l(B′) > m then B ≡_{m} B′.

Corollary 2.14. [Was74] The class of Boolean algebras B with inv(B) = x are not axiomatizable by sentences in ∃_{n−1} and ∀_{n−1} where n = l(x) < ω. The classes with invariants ⟨p, ω, 0⟩ and ⟨p, ω, 1⟩ are not finitely axiomatizable. The class of Boolean algebras with invariant ⟨ω, 0, 0⟩ is not axiomatizable by sentences at any bounded level of the ∃_{n} hierarchy.

3 Counting Quantifiers

In this section, we prove that, for each x ∈ In, B_{x} is in Γ_{x}. In fact, we will also analyze the complexity of the axioms needed to guarantee that a Boolean algebra is in B_{x}. We will prove that B_{x} is Γ_{x}-hard in the following sections.

Definition 3.1. We define unary predicates I_{n}, Atom_{n}, Atomless_{n} and Atomic_{n} and the associated formulas in the language of Boolean algebras by induction:

I_{0}(x) ⟺ x = 0;
Atom_{n}(x) ⟺ ¬I_{n}(x) & ∀y ≤ x(I_{n}(y) ∨ I_{n}(x − y));
Atomless_{n}(x) ⟺ ¬∃y ≤ x(Atom_{n}(y));
Atomic_{n}(x) ⟺ ¬∃y ≤ x(¬I_{n}(y) & Atomless_{n}(y));
I_{n+1}(x) ⟺ ∃y, z(Atomless_{n}(y) & Atomic_{n}(z) & x = y ∨ z).

Let B be a Boolean algebra. Note that I_{n}(B) = {x ∈ B : B ⊧ I_{n}(x)} is the ideal of B such that B^{[n]} = B/I_{n}(B). Let [x]_{n} denote the equivalence class of x in B/I_{n}(B), that is [x]_{n} = {y ∈ B : x△y ∈ I_{n}(B)}. Then Atom_{n}(x) holds iff [x]_{n} is an atom of B^{[n]}, Atomless_{n}(x) holds iff [x]_{n} is atomless in B^{[n]}, and Atomic_{n}(x) holds iff [x]_{n} is atomic in B^{[n]}. Observe that the formulas I_{n}, Atom_{n}, Atomless_{n} and Atomic_{n} are ∃_{4n}, ∀_{4n+1}, ∀_{4n+2} and ∀_{4n+3} respectively in the language of Boolean algebras. (Of course, that a computable Boolean algebra B satisfies a ∃_{n} or ∀_{n} formula is a Σ_{n} or Π_{n} relation, respectively.)

Definition 3.2. For p, q < ω, we let B_{⟨p,≤q,r⟩} = ⋃_{i≤q} B_{⟨p,i,r⟩}. Also let l(⟨p, ≤ q, r⟩) = l(⟨p, q, r⟩).

Lemma 3.3. For p, q < ω, x equal to either ⟨p, ≤ q, 0⟩, ⟨p, ≤ q, 1⟩ or ⟨p, ω, 0⟩ and n = l(x), B_{x} is in Π_{n}. Moreover, the corresponding classes of Boolean algebras are axiomatized by a ∀_{n} sentence, a ∀_{n} sentence, a ∀_{n} sentence and a computable set of ∃_{n−1} sentences (but not by any finite set of axioms), respectively. If x = ⟨p, ω, 1⟩, then B_{x} is in Σ_{n}. Moreover, the corresponding class of Boolean algebras is axiomatized by a ∃_{n} sentence and a computable set of ∃_{n−2} sentences but is not finitely axiomatizable. (Of course, B_{⟨p,1,0⟩} = B_{⟨p,≤1,0⟩} and B_{⟨p,0,1⟩} = B_{⟨p,≤0,1⟩}.)

Proof. Consider x = ⟨p, ≤ q, 0⟩, and let B be a computable Boolean algebra. B is in B_{x} if and only if B has first invariant at least p, but no more than q atoms in B^{[p]}, and no atomless members in B^{[p]}. Now, q atoms can generate at most 2^{q} non-equivalent members, so to say that there are at most q atoms it suffices to say

¬∃x_{0}, ..., x_{2^{q}}(∀i, j ≤ 2^{q}¬I_{p}(x_{i}△x_{j})),

which is a Π_{4p+1} predicate of B and indeed clearly equivalent to the truth of a ∀_{4p+1} sentence. (Replace the bounded quantification by the corresponding conjunction.) This sentence also implies there are no atomless elements in B^{[p]}. For B to be in B_{x} we still need to say that B has first invariant at least p, i.e. ¬I_{p}(1) which is a ∀_{4p} sentence.

Now consider x = ⟨p, ≤ q, 1⟩. B is in B_{x} if and only if B has first invariant at least p, no more than q atoms in B^{[p]}, but more than 2^{q} elements in B^{[p]}. This is expressed by ¬I_{p}(1),

¬∃x_{0}, ..., x_{q}(∀i ≤ q(Atom_{p}(x_{i})) & ∀i < j ≤ q(¬I_{p}(x_{j}△x_{i}))),

and

∃x_{0}, ..., x_{2^{q}}(∀i, j ≤ 2^{q}¬I_{p}(x_{i}△x_{j})).

Note that this is clearly equivalent to the truth in B a ∀_{4p+2} sentence.

Consider now x = ⟨p, ω, 0⟩. B is in B_{x} if and only if [1]_{p} is atomic in B^{[p]} and there are infinitely many atoms:

Atomic_{p}(1) &

∀m∃x_{1}, ..., x_{m}(∀i ≤ m(Atom_{p}(x_{i})) & ∀i < j ≤ m(¬I_{p}(x_{j}△x_{i}))).

Observe that this is a Π_{4p+3} predicate on B which is equivalent to the truth of a ∀_{4p+3} sentence and a computable set of Σ_{4p+2} sentences (one for each m). If this class were finitely axiomatizable then, by the completeness of the associated theory, some finite subset of this list of axioms would suffice to axiomatize the class. This, however, is obviously impossible since any finite subset has a an algebra with invariant ⟨p, q, 0⟩ for some q.

Finally let x = ⟨p, ω, 1⟩. Then B ∈ B_{x} if and only if, in B^{[p]}, 1 is the sum of an atomless element and an atomic element, and there are infinitely many atoms. This is expressed by

∃yz(1 = y ∨ z & Atomic_{p}(y) & Atomless_{p}(z) & ¬I_{p}(z)) & ∀m∃x_{1}, ..., x_{m}(∀i ≤ m(Atom_{p}(x_{i})) & ∀i < j ≤ m(¬I_{p}(x_{j}△x_{i}))))

which is a Σ_{4p+4} predicate on B which is equivalent to the truth of a ∃_{4p+4} sentence and a computable set of Σ_{4p+2} sentences. The argument that this class is not finitely axiomatizable is the same as for ⟨p, ω, 0⟩.

It follows that, for all n ∈ ω, B_{n} is in Σ_{n}^{0} if 4 divides n and it is in Π_{n}^{0} otherwise.

Lemma 3.4. For x = ⟨p, q, r⟩ with p < ω and either r = 0 & 1 < q < ω, or r = 1 & 0 < q < ω, B_{x} is in Σ_{n} ∧ Π_{n}, where n = l(x). Moreover, the corresponding classes of Boolean algebras are axiomatized by a sentence in ∃_{n} and one in ∀_{n}.

Proof. For r = 0, observe that B_{⟨p,q,0⟩} consists of the Boolean algebras B in B_{⟨p,≤q,0⟩} which are not in B_{⟨p,≤q−1,0⟩}. By Lemma 3.3, B in B_{⟨p,≤q,0⟩} is guaranteed by a ∀_{4p+1} sentence and B not in B_{⟨p,≤q−1,0⟩} is expressible by a ∃_{4p+1} sentence. Similarly, for r = 1, observe that B_{⟨p,q,1⟩} consists of the Boolean algebras B in B_{⟨p,≤q,1⟩} (guaranteed by a ∀_{4p+2} sentence) which are not in B_{⟨p,≤q−1,1⟩} (expressible by a ∃_{4p+2} sentence).

Lemma 3.5. B_{⟨ω,0,0⟩} is in Π_{ω+1}. The corresponding class of Boolean algebras is axiomatized by a computable set of ∀_{n} sentences with one for each n.

Proof. A computable Boolean algebra B is in B_{⟨ω,0,0⟩} if for all p, B^{[p]} is non-empty. In other words if

∀p < ω(¬I_{p}(1)).

Since 0^{(ω)} knows whether I_{p}(1) for each p uniformly in p, B_{⟨ω,0,0⟩} is co-c.e. in 0^{(ω)}, or equivalently Π_{ω+1}^{0}.

Note that these Lemmas establish the axiomatizabilty of the classes of Boolean algebras by sentences of the complexity required in Theorem 2.13. The second part of this theorem follows from Theorem 6.1(2).

Now that we have that, for each x, B_{x} is in Γ_{x}, we turn to proving that B_{x} is Γ_{x}-hard. We first need to introduce the concepts of dense Boolean algebras and back-and-forth relations.

4 Dense Boolean Algebras

We start by defining the Tarski invariants on elements of a Boolean Algebra.

Definition 4.1. Let B be a Boolean algebra and a ∈ B. We let B ↾ a be the Boolean algebra whose domain is {b ∈ B : b ≤ a}, 1_{B ↾ a} = a, 0_{B ↾ a} = 0, ∨_{B ↾ a} and ∧_{B ↾ a} are the restrictions of the corresponding operations in B, and the complement of b in B ↾ a is a − b. We let inv^{B}(a) = inv(B ↾ a). When no confusion should arise, we may might write inv(a) instead of inv^{B}(a).

Definition 4.2. A Boolean algebra B is dense if for every b ∈ B,

1. ∀k < inv_{1}(b)(∃a ≤ b(inv(a) = ⟨k, ω, 0⟩)) and

2. if inv_{1}(b) = ω or inv_{2}(b) = ω, then there is an a ≤ b such that inv_{1}(a) = inv_{1}(b) = inv_{1}(b − a) and inv_{2}(a) = inv_{2}(b) = inv_{2}(b − a).

Goncharov [Gon97, 2.3.2] proves that any two countable dense Boolean algebras with the same invariant are isomorphic. Moreover, he proves that every countable Boolean algebra B has an elementary extension B^{∗} which is dense. This then shows that any two countable Boolean algebras with the same invariant are elementarily equivalent and so establishes Tarski’s theorem.

We let D_{x} denote the dense Boolean algebra with invariant x. All of them are computably (even decidably) presentable by Morozov [Mor82].

Definition 4.3. We define an addition operation on the set In of invariants as follows:

∑_{i≤m}⟨p_{i}, q_{i}, r_{i}⟩ = ⟨p_{0}, q_{0}, r_{0}⟩ + ... + ⟨p_{m}, q_{m}, r_{m}⟩ = ⟨p, q, r⟩,

where

p = max{p_{i} : i ≤ m},
q = ∑{q_{i} : i ≤ m & p_{i} = p},
r = max{r_{i} : i ≤ m & p_{i} = p}.

We then say that ⟨p_{0}, q_{0}, r_{0}⟩, ..., ⟨p_{m}, q_{m}, r_{m}⟩ is a partition of ⟨p, q, r⟩. (Here, we are using the convention that ω + q = q + ω = ω.)

Definition 4.4. We say that a_{0}, ..., a_{m} ∈ B form a partition of a ∈ B if ⋁_{i≤m} a_{i} = a and for all i ≤ m,

a_{i} ∧ ⋁_{j≤m,j≠i} a_{j} = 0.

Observe that if a_{0}, ..., a_{m} form a partition of 1, then B ≅ B ↾ a_{0} × ... × B ↾ a_{m}. We then say that B ↾ a_{0}, ..., B ↾ a_{m} form a partition of B.

Now consider an arbitrary tuple b̄ = (b_{0}, …, b_{n}) of members of B. This generates a partition of B as follows. Let A_{0} = {b_{0}, 1 − b_{0}}. Let A_{i} = {a − b_{i}, b_{i} ∩ a : a ∈ A_{i}} for 0 ≤ i ≤ n. Then {B ↾ a : a ∈ A_{n}, a ≠ 0} is the partition of B generated by b̄.

Lemma 4.5. If a_{0}, ..., a_{m−1} form a partition of a, then inv(a_{0}), ..., inv(a_{m−1}) form a partition of inv(a).

Proof. See [Gon97, Lemma 2.2.4] for a proof of the lemma when m = 2. The general case follows easily by induction.

When we are dealing with dense Boolean algebras, the converse of the previous lemma also holds.

Lemma 4.6. A Boolean algebra B is dense if and only if, for every b ∈ B and every partition x_{0}, ..., x_{m} of inv(b), there exists a partition a_{0}, ..., a_{m} of b such that, for each i ≤ m, inv(a_{i}) = x_{i}.

Proof. The denseness conditions are just special cases of the partition property.

To see that, if B is dense, then B has the partition property, make use of the denseness conditions along with Lemma 4.7 below.

Lemma 4.7. [Gon97, Lemma 2.2.6] Let B be a Boolean algebra, b ∈ B, and x = ⟨p, q, r⟩ ∈ In.

1. If p < inv_{1}(b), q < ω, and r ≤ 1, then there is an a ≤ b such that inv(b−a) = inv(b).

2. If p = inv_{1}(b), q ≤ inv_{2}(b), and r ≤ inv_{3}(b), then there is an a ≤ b such that inv(a) = x. Moreover, if q < inv_{2}(b) or r = 1, then we can also require that inv_{1}(b − a) = inv_{1}(b), inv_{2}(b − a) = q, and inv_{3}(b − a) = inv_{3}(b), where we take ω − ω to be 0.

Corollary 4.8. The product of dense Boolean algebras is dense.

Proof. Consider x, y ∈ In. We want to prove that D_{x} × D_{y} ≅ D_{x+y}. The element 1 of D_{x+y} has invariant x + y. So, by the lemma above, there exists a partition a, b of 1 such that inv(a) = x and inv(b) = y. Since a, b is a partition of 1, D_{x+y} ≅ D_{x+y} ↾ a × D_{x+y} ↾ b. Since D_{x+y} is dense, so are D_{x+y} ↾ a and D_{x+y} ↾ b. Therefore

D_{x} × D_{y} ≅ D_{x+y} ↾ a × D_{x+y} ↾ b ≅ D_{x+y}.

5 Back-and-Forth relations

In this section we define back-and-forth relations between structures and state the properties about them that we need. We refer the reader to [AK00] for more information on these relations.

Definition 5.1. Let K be a class of structures for a fixed language. For each n < ω, we define the standard back-and-forth relation ≤_{n} on pairs (A, ā), where A ∈ K and ā is a tuple in A. First suppose that ā in A and b̄ in B are tuples of the same length. Then,

1. (A, ā) ≤_{1} (B, b̄) if and only if all Σ_{1} formulas true of b̄ in B are true of ā in A.

2. For n > 1, (A, ā) ≤_{n} (B, b̄) if and only if for each d̄ in B, and each 1 ≤ k < n, there exists a c̄ in A with |c̄| = |d̄| such that (B, b̄, d̄) ≤_{k} (A, ā, c̄).

Now, we extend the definition of ≤_{n} to tuples of different lengths. For ā in A and b̄ in B, let (A, ā) ≤_{n} (B, b̄) if and only if |ā| ≤ |b̄| and for the initial segment b̄′ of b̄ of length |b̄|, we have (A, ā) ≤_{n} (B, b̄′). We may write A ≤_{n} B instead of (A, ∅) ≤_{n} (B, ∅).

One observation that might give the reader some intuition about the back-and-forth relation is that (A, ā) ≤_{n} (B, b̄) if and only if all the Π_{n} infinitary formulas true of ā in A are true of b̄ in B. (See [AK00, Proposition 15.1]; see [AK00, Chapter 6] for information on infinitary formulas.) Also observe that if k < n and (A, ā) ≤_{n} (B, b̄) then (A, ā) ≡_{k} (B, b̄), where (A, ā) ≡_{k} (B, b̄) if and only if (A, ā) ≤_{k} (B, b̄) and (A, ā) ≥_{k} (B, b̄).

The only structures we will be dealing with are Boolean algebras. The following lemma gives us a way of computing the back-and-forth relations on Boolean algebras without having to refer to the definition given above.

Lemma 5.2. [AK00, 15.13] Suppose that A and B are Boolean algebras. Then A ≤_{1} B if and only if A is infinite or can be split into at least as many disjoint parts as B (i.e., if A is generated by p atoms, then B is generated by k atoms, for some k ≤ p). For n > 1, A ≤_{n} B if and only if, for any l with 1 ≤ l < n and any finite partition of B into B_{1}, ..., B_{k}, there is a corresponding partition of A, A_{1}, ..., A_{k}, such that B_{i} ≤_{l} A_{i}.

We will be interested in analyzing the back-and-forth relation among the dense Boolean algebras. Since each isomorphism type of a dense Boolean algebra is determined by its invariant, we translate the back-and-forth relation to one on the set of invariants:

Definition 5.3. Given x, x′ ∈ In and n < ω we let x ≤_{n} x′ if D_{x} ≤_{n} D_{x′}.

The back-and-forth relations on the set of invariants can be computed using the following lemma.

Lemma 5.4. Consider x, x′ ∈ In. Then x ≤_{1} x′ if and only if either l(x) > 1, or x = ⟨0, q, 0⟩, x′ = ⟨0, q′, 0⟩ and q ≥ q′. For n > 1, x ≤_{n} x′ if and only if, for any partition y′_{1}, ..., y′_{k} of x′, there is a corresponding partition y_{1}, ..., y_{k} of x such that y′_{i} ≤_{n−1} y_{i}.

Proof. Immediate from Lemma 5.2, noting that D_{x} is infinite if and only if l(x) > 1, and that if l(x) = 0 then x = ⟨0, q, 0⟩ for some 1 ≤ q < ω, so for D_{x} to be such that it can be split into at least as many disjoint parts as D′_{x} we must have x′ = ⟨0, q′, 0⟩ for some q′ ≤ q.

The above considerations reduce computing the back-and-forth relations on In to a combinatorial task, which we will do in Theorem 6.1. To complete the proofs of our hardness results we also make use of the concept of k-friendliness., which we now introduce. Again, we refer the reader to [AK00, Chapter 15] for more information.

Definition 5.5. A pair of structures {A_{0}, A_{1}} is k-friendly if the structures A_{i} are computable, and for n < k, the standard back-and-forth relations ≤_{n} on (A_{i}, \overline{a}), for \overline{a} ∈ A_{i}, are c.e., uniformly in n.

Theorem 5.6. [AK00, 18.6] Let A_{0} and A_{1} be structures such that A_{1} ≤_{k} A_{0} and {A_{0}, A_{1}} is k-friendly. Then for any Π_{k}^{0} set S, there is a uniformly computable sequence of structures {C_{n}}_{n∈ω} such that

C_{n} ≅ \begin{cases}A_{0} & if n ∈ S \\ A_{1} & otherwise \end{cases}

This theorem can be restated as follows.

Corollary 5.7. Let A_{0} and A_{1} be n-friendly structures and B_{A_{0}} and B_{A_{1}} be subsets of ω such that every index of a computable copy of A_{0} is in B_{A_{0}} and every index of a computable copy of A_{1} is in B_{A_{1}}. Then

A_{1} ≤_{n} A_{0} ⟹ (Σ_{n}, Π_{n}) ≤_{m} (B_{A_{1}}, B_{A_{0}}).

6 The Σ_{n} and the Π_{n} cases (Theorem 2.4)

We start by giving a complete analysis of the back-and-forth relations on the set of invariants, or equivalently, on the dense Boolean algebras. The proof of the following theorem is purely combinatorial and all it uses about the back-and-forth relations on In is Lemma 5.4.

Theorem 6.1. Let x = ⟨p, q, r⟩ and x′ = ⟨p′, q′, r′⟩ be invariants with l(x) = l and l(x′) = l′, and let n ≥ 1. The following conditions determine whether x ≤_{n} x′.

Case 1: If l < n ∨ l′ < n, then x ≤_{n} x′ iff x = x′.

Case 2: If l > n & l′ > n, then x ≤_{n} x′ always.

Case 3: If l = n & l′ = n, then x ≤_{n} x′ iff q ≥ q′.

Case 4: If l > n & l′ = n, then x ≤_{n} x′ iff n ≠ 4p′ + 4.

Case 5: If l = n & l′ > n, then x ≤_{n} x′ iff n = 4p + 4.

Proof. The proof is by induction on n. The case n = 1 follows trivially from Lemma 5.4 (recall l, l′ ≥ 1 by definition of level). Consider n > 1 and assume the theorem holds for all m < n.

Case 1: Suppose that either l < n or l′ < n. Clearly if x = x′ then x ≤_{n} x′. Now suppose x ≤_{n} x′. Then x ≡_{n−1} x′. By induction hypothesis this can only happen either if x = x′ or if l > n − 1 and l′ > n − 1. Therefore, since either l < n or l′ < n, we must have x = x′.

Case 2: Suppose l > n and l′ > n. We have to show that given any finite partition y′_{1}, ..., y′_{k} of x′, there is a corresponding partition y_{1}, ..., y_{k} of x, such that y′_{i} ≤_{n−1} y_{i}.

Assume y′_{1}, ..., y′_{k} are ordered such that for some j ≤ k, y′_{1}, ..., y′_{j} have level ≥ n and y′_{j+1}, ..., y′_{k} have level < n. It is not hard to observe that, whatever n is, since l(x) > n, it is always the case that there exists y_{1}, ..., y_{j} of level ≥ n such that ∑_{i≤j} y_{i} = x. Note that by induction hypothesis, since l(y_{i}) > n − 1 and l(y′_{i}) > n − 1, y′_{i} ≤_{n−1} y_{i} for all i ≤ j. For i > j let y_{i} = y′_{i}. Another easy general observation is that for every y, z ∈ In with l(y) ≤ l(z) − 2, z + y = z. Then ∑_{i≤k} y_{i} = x + ∑_{i=j+1}^{k} y′_{i} = x. So y_{1}, ..., y_{k} is the desired partition of x.

Case 3: Assume l = l′ = n. Note that p = p′ and r = r′. Also if n = 4p + 3 or n = 4p + 4, then q = q′ = ω and therefore x = x′. So suppose n is either 4p + 1 or 4p + 2.

First suppose q ≥ q′; we want to show that x ≤_{n} x′. Consider a partition y′_{1}, ..., y′_{k} of x′ with y′_{i} = ⟨p_{i}, q_{i}, r_{i}⟩. Note that, necessarily, for some i ≤ k, p_{i} = p and r_{i} = r; without loss of generality suppose that p_{1} = p and r_{1} = r. Let y_{1} = ⟨p, q_{1}+(q−q′), r⟩ = ⟨p, q−q′, r⟩+y′_{1}, and for i > 1 let y_{i} = y′_{i}. Observe that

∑_{i≤k} y_{i} = ⟨p, q − q′, r⟩ + ∑_{i≤k} y′_{i} = ⟨p, q − q′, r⟩ + x′ = x.

Also, since l(y_{1}) = l(y′_{1}) = n > n − 1, by Case 2 of the inductive hypothesis y′_{1} ≤_{n−1} y_{1}. So y_{1}, ..., y_{k} is the desired partition.

Now suppose q < q′; we want to show that x ≰_{n} x′.

If n = 4p + 1 or equivalently r = 0, consider the partition y′_{i} = ⟨p, 1, 0⟩ for i ≤ q′ of x′ = ⟨p, q′, 0⟩. It is not hard to see that any partition, y_{1}, ..., y_{q′}, of x cannot have more than q elements at level n. So, for some i ≤ q′, l(y_{i}) < n = l(y′_{i}). Then, by either case 1 or case 4 of the induction hypothesis, y′_{i} ≰_{n−1} y_{i}.

If n = 4p + 2, consider the partition y′_{i} = ⟨p, 1, 0⟩ for i ≤ q′ and y_{q′+1} = ⟨p, 0, 1⟩ of x′ = ⟨p, q′, 1⟩. Suppose toward a contradiction that there is a partition y_{1}, ..., y_{q′+1} of x such that for all i ≤ q′ + 1, y′_{i} ≤_{n−1} y_{i}. By induction hypothesis, ⟨p, 1, 0⟩ ≤_{n−1} y_{i} implies that y_{i} = ⟨p, 1, 0⟩. So, for all i ≤ q′, y_{i} = ⟨p, 1, 0⟩. But then, since q < q′, it cannot be the case that ∑_{i<q′+1} y_{i} = ⟨p, q, 1⟩ = x.

Case 4: Suppose now that l > n and l′ = n.

First suppose that n ≠ 4p′ + 4. Then, any partition y′_{1}, ..., y′_{k} of x′ must have some member at level n. Assume l(y′_{1}) = n. Note that there is a y_{1} of level l > n such that y_{1} + ∑_{1<i≤k} y′_{i} = x. Also observe that since l(y_{1}) > n − 1 and l(y′_{1}) > n − 1, y′_{1} ≤_{n−1} y_{i}. Then, if for 1 < i ≤ k we let y_{i} = y′_{i}, we obtain the desired partition of x.

Now suppose that n = 4p′ +4 and hence x′ = ⟨p′, ω, 1⟩; we want to show that x ≰_{n} x′. Consider the following partition of x′: let y′_{1} = ⟨p′, ω, 0⟩ and y′_{2} = ⟨p′, 0, 1⟩. Suppose toward a contradiction that y_{1}, y_{2} is a partition of x such that y′_{i} ≤_{n−1} y_{i} for i ≤ 2. Then by induction hypothesis we must have y_{1} = ⟨p′, ω, 0⟩ and y_{2} = ⟨p′, 0, 1⟩. But then l(y_{1} + y_{2}) = n < l(x), contradicting y_{1} + y_{2} = x.

Case 5: The last case is l = n and l′ > n.

Suppose first that n = 4p + 4, so x = ⟨p, ω, 1⟩. Let y′_{1}, ..., y′_{k} be a partition of x′. Let y_{i} = y′_{i} if l(y′_{i}) < n and y_{i} = ⟨p, ω, 1⟩ otherwise. Note that ∑_{i≤k} y_{k} = x, and that for i with l(y′_{i}) > n, since l(y_{i}) > n − 1, y′_{i} ≤_{n−1} y_{i}. So, y_{1}, ..., y_{k} is the desired partition.

Note that if l(x^{∗}) ≥ n + 1 and l(x′) ≥ n + 1, then x′ ≤_{n} x^{∗} by Case 2. So to show x ≰_{n} x′ it suffices to show x ≰_{n} x^{∗} for any x^{∗} of level n + 1.

Suppose n = 4p + 1 or n = 4p + 2, so x = ⟨p, q, r⟩ with q < ω and x′ has level n + 1; we want to show that x ≰_{n} x′. By case 3, ⟨p, q, r⟩ ≰_{n} ⟨p, q + 1, r⟩. By case 4, x′ ≤_{n} ⟨p, q + 1, r⟩. So we must have ⟨p, q, r⟩ ≰_{n} x′.

Last, suppose n = 4p + 3. Then x = ⟨p, ω, 0⟩ and let x′ = ⟨p, ω, 1⟩; we want to show that x ≰_{n} x′. Consider the partition y′_{1} = ⟨p, ω, 0⟩ and y′_{2} = ⟨p, 0, 1⟩ of x′. Suppose toward a contradiction that there is a partition y_{1}, y_{2} of x such that y′_{i} ≤_{n−1} y_{i}. Now, ⟨p, 0, 1⟩ ≤_{n−1} y_{2} implies, by induction hypothesis, that y_{2} = ⟨p, 0, 1⟩. But then y_{2} cannot be part of a partition of ⟨p, ω, 0⟩. Contradiction.

Corollary 6.2. Let A and B be computable presented Boolean algebras such that the functions inv^{A} and inv^{B} are computable. Then {A, B} is n-friendly for every n < ω.

Proof. Let A_{0} and A_{1} be in {A, B}, ā_{0} be a tuple in A_{0}, ā_{1} be a tuple in A_{1}, and n < ω. We will show how to decide whether (A_{0}, ā_{0}) ≤_{n} (A_{1}, ā_{1}) computably. If |a_{0}| > |a_{1}|, then (A_{0}, ā_{0}) ≰_{n} (A_{1}, ā_{1}). So suppose |a_{0}| ≤ |a_{1}|. By truncating ā_{1} if necessary, we can assume without loss of generality that they have the same length. Each tuple ā_{i} generates a partition of A_{i}. We can then effectively compute the invariants of the partition, y_{i,0}, …, y_{i,k}. By [AK00, Lemma 15.12], (A_{0}, ā_{0}) ≤_{n} (A_{1}, ā_{1}) iff y_{0,j} ≤_{n} y_{1,j} for 0 ≤ j ≤ k. Then we can use Theorem 6.1 to decide this.

In [Mor82], Morozov uniformly constructs dense Boolean algebras of each invariant which are decidable. While decidability does not quite give the computability of the inv functions on these algebras, it is not hard to see that they are in fact computable. (The argument is a tedious one by induction with several cases. Enough of it to give the ideas is carried out in Shore [Sho04, Proposition 6.5] when that proof is specialized to these algebras.) Therefore, by Corollary 6.2, these Boolean algebras are n-friendly for each n. Then, from Corollary 5.7 we obtain the following:

Corollary 6.3. For every p < ω,

(Σ_{4p+1}, Π_{4p+1}) ≤_{m} (DB_{⟨p,0,1⟩}, DB_{⟨p,1,0⟩})
(Σ_{4p+2}, Π_{4p+2}) ≤_{m} (DB_{⟨p,ω,0⟩}, DB_{⟨p,0,1⟩})
(Σ_{4p+3}, Π_{4p+3}) ≤_{m} (DB_{⟨p,ω,1⟩}, DB_{⟨p,ω,0⟩})
(Σ_{4p+4}, Π_{4p+4}) ≤_{m} (DB_{⟨p,ω,1⟩}, DB_{⟨p+1,1,0⟩})

Theorem 2.4 and the corresponding lines of Theorem 2.10 now follow from this corollary and Lemma 3.3.

We can also now derive the second part of Theorem 2.13 and Corollary 2.14. As remarked above, D_{x} ≡_{n} D_{x′} implies that the same ∀_{n} formulas are true in D_{x} and D_{x′} ([AK00, Proposition 15.1]). Case (2) of Theorem 6.1 then implies that, for every m < ω, if l(B), l(B′) > m then B ≡_{m} B′ as required for the second part of Theorem 2.13. As for Corollary 2.14, if D_{x} were axiomatized by sentences in ∃_{m} and ∀_{m} for m < l(x) then, by the second part of Theorem 2.13, D_{x′} ≡_{m} D_{x} for any x′ with l(x′) > n and so we would have D_{x′} ≡ D_{x} for a contradiction.

7 The Σ_{n} ∧ Π_{n} cases (Theorem 2.6)

Now we prove that, for x = ⟨p, q, r⟩ with 0 < q + r < ω, DB_{x} is Σ_{l(x)}^{0} ∧ Π_{l(x)}^{0}-hard. We first prove it for x ≠ ⟨p, 2, 0⟩. Later, using a more complicated proof, we prove it for x = ⟨p, 2, 0⟩.

Lemma 7.1. For 2 < q < ω, DB_{⟨p,q,0⟩} is (Σ_{4p+1} ∧ Π_{4p+1})-hard. For 0 < q < ω, DB_{⟨p,q,1⟩} is (Σ_{4p+2} ∧ Π_{4p+2})-hard. Moreover, the reductions proving hardness produce, in the case that n is not in the Σ_{4p+1} ∧ Π_{4p+1} or Σ_{4p+2} ∧ Π_{4p+2} set, an index in DB_{⟨p,q̄,0⟩} or DB_{⟨p,q̄,1⟩}, respectively, as required in Theorem 2.10.

Proof. Let 2 < q < ω. Consider two Σ_{4p+1} formulas ϕ(n) and ψ(n). We want to construct a computable function f such that ∀n(ϕ(n) & ¬ψ(n)) ⟺ f(n) ∈ DB_{⟨p,q,0⟩}). Since q > 2, by Theorem 6.1, ⟨p, q, 0⟩ ≤_{4p+1} ⟨p, 1, 0⟩ and ⟨p, q − 1, 0⟩ ≤_{4p+1} ⟨p, 1, 0⟩. So by Corollary 5.7 there are computable g and h such that ϕ(n) ⇒ g(n) ∈ DB_{⟨p,q−1,0⟩}, ¬ϕ(n) ⇒ g(n) ∈ DB_{⟨p,1,0⟩}, ψ(n) ⇒ h(n) ∈ DB_{⟨p,q,0⟩}, and ¬ψ(n) ⇒ h(n) ∈ DB_{⟨p,1,0⟩}. Associating Boolean algebras with their indices, let f(n) = g(n) × h(n) and note that, by Corollary 4.8, f(n) is an index for a dense Boolean algebra. Then if ϕ(n) & ¬ψ(n), we have inv(f(n)) = inv(g(n)) + inv(h(n)) = ⟨p, q − 1, 0⟩ + ⟨p, 1, 0⟩ = ⟨p, q, 0⟩. If ϕ(n) & ψ(n) then inv(f(n)) = ⟨p, q − 1, 0⟩ + ⟨p, q, 0⟩ = ⟨p, 2q − 1, 0⟩, if ¬ϕ(n) & ψ(n) then inv(f(n)) = ⟨p, 1, 0⟩ + ⟨p, q, 0⟩ = ⟨p, q + 1, 0⟩, and if ¬ϕ(n) & ¬ψ(n) then inv(f(n)) = ⟨p, 1, 0⟩ + ⟨p, 1, 0⟩ = ⟨p, 2, 0⟩. Thus f has the required properties.

Now suppose 0 < q < ω and that ϕ(n) and ψ(n) are Σ_{4p+2}. We now wish to construct a computable function f such that ∀n(ϕ(n) & ¬ψ(n) ⟺ f(n) ∈ DB_{⟨p,q,1⟩}). Again by Theorem 6.1 and Corollary 5.7 there are computable g and h such that ϕ(n) ⇒ g(n) ∈ DB_{⟨p,q,1⟩}, ¬ϕ(n) ⇒ g(n) ∈ DB_{⟨p,0,1⟩}, ψ(n) ⇒ h(n) ∈ DB_{⟨p,q+1,1⟩}, and ¬ψ(n) ⇒ h(n) ∈ DB_{⟨p,0,1⟩}. Now let f(n) = g(n)×h(n) and note that f has the required properties. Indeed, if ϕ(n) & ¬ψ(n), we have inv(f(n)) = inv(g(n)) + inv(h(n)) = ⟨p, q, 1⟩ + ⟨p, 0, 1⟩ = ⟨p, q, 1⟩. If ϕ(n) & ψ(n) then inv(f(n)) = ⟨p, q, 1⟩ + ⟨p, q + 1, 1⟩ = ⟨p, 2q + 1, 1⟩, if ¬ϕ(n) & ψ(n) then inv(f(n)) = ⟨p, 0, 1⟩+⟨p, q+1, 1⟩ = ⟨p, q+1, 1⟩, and if ¬ϕ(n) & ¬ψ(n) then inv(f(n)) = ⟨p, 0, 1⟩ + ⟨p, 0, 1⟩ = ⟨p, 0, 1⟩.

To finish the proof of Theorem 2.6 and the corresponding parts of Theorem 2.10, we still need to prove that, for every p, DB_{⟨p,2,0⟩} is (Σ_{4p+1} ∧ Π_{4p+1})-hard via reductions with an appropriate outcome in the case that n is not in the given Σ_{4p+1} ∧ Π_{4p+1} set. We need the following definition.

Definition 7.2. Let {B_{i}}_{i∈ω} be a sequence of Boolean algebras. We define ∏_{i∈ω}^{ω} B_{i}, the weak product of {B_{i}}_{i∈ω}, to be the Boolean algebra with domain the set of infinite strings b̄ = (b_{0}, b_{1}, ...) such that ∀i(b_{i} ∈ B_{i}) and for some i_{0}, either ∀j ≥ i_{0}(b_{j} = 0) or ∀j ≥ i_{0}(b_{j} = 1). The operations and constants of ∏_{i∈ω}^{ω} B_{i} are defined coordinatewise in the obvious way, with \overline{0} = (0_{B_{0}}, 0_{B_{1}}, …), \overline{1} = (1_{B_{0}}, 1_{B_{1}}, …), and so forth.

Observation 7.3. We make two observations. One is that

∏_{i∈ω}^{ω} B_{i} ≅ B_{0} × ∏_{i∈ω,i>0}^{ω}B_{i} ≅ B_{0} × B_{1} × ... × B_{n} × ∏_{i∈ω,i>n}^{ω}B_{i}

The second one is that

∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩} ≅ D_{⟨p+1,1,0⟩}.

Proof. The first observation is clear. To see the second, we will show that inv(∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}) = ⟨p + 1, 1, 0⟩, and that ∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩} is dense. Note that if \overline{1} = \overline{x} ∨ \overline{y}, then we may assume without loss of generality that there exists i_{0} such that ∀j ≥ i_{0}(x_{j} = 1), as either \overline{x} or \overline{y} must have this form. Now since [1]_{p} is neither atomic nor atomless in D_{⟨p,ω1⟩}^{[p]}, [1]_{p} is neither atomic nor atomless in (∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩})^{[p]}. Hence inv_{1}(\overline{1}) > p. Now if \overline{b} ∈ ∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩} is such that ∃i_{0}∀j > i_{0}(b_{j} = 0), then \overline{b} ∈ I_{p+1}(∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}). If \overline{b} is such that ∃i_{0}∀j > i_{0}(b_{j} = 1), then \overline{1}△\overline{b} ∈ I_{p}(∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}). Thus [\overline{1}]_{p} is an atom in (∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩})^{[p]}, and hence inv(∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}) = ⟨p + 1, 1, 0⟩. For denseness, let \overline{b} ∈ ∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}. If \overline{b} = (b_{0}, …, b_{i_{0}}, 0, 0, …) then

(∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}) ↾ \overline{b} ≅ D_{⟨p,ω,1⟩} ↾ b_{0} × ⋯ × D_{⟨p,ω,1⟩} ↾ b_{i_{0}},

which is dense by Corollary 4.8. The denseness condition for b follows. If \overline{b} = (b_{0}, …, b_{i_{0}}, 1, 1, …) then, by the first observation,

inv(\overline{b}) = inv^{D_{⟨p,ω,1⟩}}(b_{0}) + ⋯ + inv^{D_{⟨p,ω,1⟩}}(b_{i_{0}}) + inv^{∏_{i∈ω}^{ω} D_{⟨p,ω,1⟩}}(\overline{1}) = ⟨p + 1, 1, 0⟩.

Note that (0, …, 0, 1, 0, …) < b̄ and has invariant ⟨p, ω, 1⟩. So the denseness condition for b̄ follows from denseness below (0, ..., 0, 1, 0, ...) and the fact that below (0, …, 0, 1, 0, …) there is an element of invariant ⟨p, ω, 0⟩.

Lemma 7.4. For every p < ω, DB_{⟨p,2,0⟩} is (Σ_{4p+1}∧Π_{4p+1})-hard. Moreover, the reductions proving hardness produce, in the case that n is not in the Σ_{4p+1} ∧ Π_{4p+1} set, an index in DB_{⟨p,q̄,0⟩} as required in Theorem 2.10.

Proof. Consider two Σ_{4p+1} formulas ϕ(n) and ψ(n). We want to construct a computable function f such that for every n

ϕ(n) & ¬ψ(n) ⟺ f(n) ∈ DB_{⟨p,2,0⟩}.

We start by finding a Π_{4p} formula ϕ̂(n, x) such that ϕ(n) ⟺ ∃xϕ̂(n, x), and such that if ϕ(n), then there is at most one x such that ϕ̂(n, x). Since ϕ ∈ Σ_{4p+1}, ϕ(n) = ∃x∀wϕ̄(n, x, w) for some ϕ̄ ∈ Σ_{4p−1}. Let ϕ̂(n, x) be the formula

x = ⟨y, z⟩ & ∀wϕ̄(n, y, w) & ∀y′ < y∃w ≤ z(¬ϕ̄(n, y′, w)) & ∀z′ < z∃y′ ≤ y∀w ≤ z′ϕ̄(n, y′, w) (1)

which has the desired properties. Indeed, it is clear that if ∃xϕ̂(n, x) then ϕ(n). Now suppose ϕ(n) holds. So ∃x∀wϕ̄(n, x, w). Choose y least such that ∀wϕ̄(n, y, w). Then for each y′ < y there is a minimal w such that ¬ϕ̄(n, y′, w). Let z be the maximum of these w. Then ϕ̂(n, ⟨y, z⟩) holds. Suppose also ϕ̂(n, ⟨ỹ, z̃⟩). Then the third condition in (1) gives y = ỹ and the fourth condition gives z = z̃.

We also define ψ̂(n, x) to be a Π_{4p} formula such that for all n, ψ(n) ⟺ ∃xψ̂(n, x), but if ψ(n), then there are exactly two x such that ψ̂(n, x). We define ψ̂ as we did with ϕ̂ but replace “x = ⟨y, z⟩” with “x = ⟨y, z⟩ ∨ x = ⟨y, z⟩ + 1”.

Let g be a computable function such that ∀n, x(ϕ̂(n, x) ⟹ g(n, x) ∈ DB_{⟨p,1,0⟩}) and ∀n, x(¬ϕ̂(n, x) ⟹ g(n, x) ∈ DB_{⟨p−1,ω,1⟩}). Such a g exists by Corollary 6.3. Let h do the same with ψ̂. Think of g(n, x) and h(n, x) as computable dense Boolean algebras, rather than as indices for such. For each n and x let B_{n,x} be g(n, \frac{x}{2}) if x is even and h(n, \frac{x−1}{2}) if x is odd. Let f(n) = ∏_{x∈ω}^{ω} B_{n,x}. If ϕ(n) & ¬ψ(n), then there is exactly one x such that ϕ̂(n, x), so along the even components of f(n) there is one copy of D_{⟨p,1,0⟩} with all others D_{⟨p−1,ω,1⟩}. As ∀x(¬ψ̂(n, x)), along the odd components there are copies of D_{⟨p−1,ω,1⟩}. Hence by the two observations about the product,

inv(f(n)) = inv(D_{⟨p−1,ω,1⟩} × … × D_{⟨p−1,ω,1⟩} × D_{⟨p,1,0⟩} × ∏_{x∈ω}^{ω} D_{⟨p−1,ω,1⟩})

= ⟨p − 1, ω, 1⟩ + ⋯ + ⟨p − 1, ω, 1⟩ + ⟨p, 1, 0⟩ + ⟨p, 1, 0⟩
= ⟨p, 2, 0⟩.

Moreover, the resulting product is dense by Observation 7.3 and Corollary 4.8. Similarly, if ¬ϕ(n) & ¬ψ(n), then we get only copies of D_{⟨p−1,ω,1⟩}, so inv(f(n)) = ⟨p, 1, 0⟩. If ϕ(n) & ψ(n), then we get three copies of D_{⟨p,1,0⟩}, the rest D_{⟨p−1,ω,1⟩}, so inv(f(n)) = ⟨p, 4, 0⟩, and if ϕ(n) & ψ(n), then we get two copies of D_{⟨p,1,0⟩}, the rest D_{⟨p−1,ω,1⟩}, so inv(f(n)) = ⟨p, 3, 0⟩. Again, in every case the resulting algebra is dense by Observation 7.3 and Corollary 4.8. Thus f has the desired properties.

8 The Π_{ω+1} case (Theorem 2.8)

We first prove that B_{ω} = B_{⟨ω,0,0⟩} is Π_{ω+1}^{0}-hard. As in the previous section we will need to define some operations on Boolean Algebras.

In 8.2 we will define a binary operation, ∗, on presentations of Boolean algebras that corresponds, via the Interval Algebra operator, to the usual product on linear orderings. The only properties we will use of ∗ are the following.

Proposition 8.1. Let B_{0} and B_{1} be Boolean algebras.

1. If inv(B_{0}) = ⟨p, 1, 0⟩ and inv(B_{1}) = ⟨p_{1}, q_{1}, r_{1}⟩, then inv(B_{0} ∗ B_{1}) = ⟨p + p_{1}, q_{1}, r_{1}⟩.

2. If inv(B_{0}) = ⟨p, ω, 0⟩, then inv(B_{0} ∗ B_{1}) = ⟨p, ω, 0⟩.

Moreover,

D_{⟨p,1,0⟩} ∗ D_{⟨p_{1},q_{1},r_{1}⟩} ≅ D_{⟨p+p_{1},q_{1},r_{1}⟩} and D_{⟨p,ω,0⟩} ∗ B_{1} ≅ D_{⟨p,ω,0⟩}.

We will prove Proposition 8.1 in subsection 8.2, but use it now to prove Theorem 2.8. We will also make use of the following uniform version of Theorem 5.6.

Proposition 8.2. ([AK00, 18.9]) For each k, let A_{k} and B_{k} be structures such that A_{k} ≤_{k} B_{k} and {A_{k}, B_{k}} is k-friendly, and let S_{k} be a Σ_{k}^{0} set, all uniformly in k. If f(n, k) is a computable function then there is a uniformly computable sequence {C_{n,k}}_{n∈ω,k∈ω} such that

C_{n,k} ≅ \begin{cases}A_{k} & if f(n, k) ∈ S_{k} \\ B_{k} & otherwise. \end{cases}

Theorem 8.3. B_{ω} is Π_{ω+1}^{0}-hard.

Proof. Suppose S ∈ Π_{ω+1}, and f is a computable function such that

n ∈ S ⟺ ∀j(f(n, j) ∉ 0^{(j)}).

We begin with a uniformly computable sequence ⟨A_{n,k} : n, k ∈ ω⟩ of dense Boolean algebras such that

• f(n, k) ∈ 0^{(k)} ⟹ A_{n,k} = D_{⟨k,ω,0⟩}, and

• f(n, k) ∉ 0^{(k)} ⟹ A_{n,k} = D_{⟨k,1,0⟩}

Such a sequence exists by Proposition 8.2, Theorem 6.1 and the comment after Corollary 6.2.

Now define K_{n,j} by recursion: K_{n,1} = A_{n,1} and K_{n,j+1} = K_{n,j} ∗ A_{n,j+1}. Let K_{n} = ∏_{j∈ω}^{ω} K_{n,j}. Let us next compute inv(K_{n}). First suppose that n ∈ S. Then, for every k, inv(A_{n,k}) = ⟨k, 1, 0⟩, and then by Proposition 8.1

inv(K_{n,j}) = inv(A_{n,1}) + ⋯ + inv(A_{n,j}) = ⟨1 + 2 + ⋯ + j, 1, 0⟩ = ⟨\frac{j(j + 1)}{2}, 1, 0⟩.

Therefore inv_{1}(K_{n}) ≥ inv_{1}(K_{n,j}) = \frac{j(j+1)}{2} for every j. So, inv(K_{n}) = ⟨ω, 0, 0⟩. On the other hand, if n ∉ S there is a first j_{0} such that f(n, j_{0}) ∈ 0^{(j_{0})}. Then, again by Proposition 8.1,

inv(K_{n,j_{0}}) = inv(A_{n,1}) + ⋯ + inv(A_{n,j_{0}−1}) + inv(A_{n,j_{0}}) = ⟨\frac{j_{0}(j_{0} + 1)}{2}, ω, 0⟩,

and for j ≥ j_{0}, inv(K_{n,j}) is constant and equal to ⟨\frac{j_{0}(j_{0}+1)}{2}, ω, 0⟩. Therefore, for every j,

K_{n,j}^{[ \frac{j_{0}(j_{0}+1)}{2} ]} is atomic. It is not hard to see that then K_{n}^{[ \frac{j_{0}(j_{0}+1)}{2} ]} is also atomic, and hence inv(K_{n}) = ⟨\frac{j_{0}(j_{0}+1)}{2}, ω, 0⟩.

An interesting corollary is the following one about the complexity of deciding whether two Boolean algebras are elementarily equivalent. White [Whi00, 6.2.4] showed that for arbitrary structures this problem is as complicated as it can be. We prove the same when the structures are restricted to be Boolean algebras. Let EE(BA) be the set of pairs ⟨i, j⟩ such that the computable Boolean algebras with indices i and j are elementarily equivalent. It clear that EE(BA) is Π_{ω+1}^{0} because

⟨i, j⟩ ∈ EE(BA) ⟺ ∀φ ∈ L^{BA}(B_{i} ⊧ φ ⟺ B_{j} ⊧ φ),

(where B_{i} and B_{j} are the computable Boolean algebras with indices i and j respectively and L^{BA} is the first order language of Boolean Algebras) and 0^{(ω)} can tell whether B_{i} ⊧ φ uniformly in i and φ.

Corollary 8.4. EE(BA) is Π_{ω+1}^{0} complete.

Proof. We already showed that EE(BA) is in Π_{ω+1}^{0}. We have to show that EE(BA) is Π_{ω+1}^{0}-hard. Consider S ∈ Π_{ω+1}. Let K_{n} be as in the proof of the theorem above and let k_{n} be a computable index for K_{n}. Let d_{ω} be a computable index for D_{⟨ω,0,0⟩}. Then

n ∈ S ⟺ inv(K_{n}) = ⟨ω, 0, 0⟩ ⟺ ⟨d_{ω}, k_{n}⟩ ∈ EE(BA).

8.1 (Σ_{ω+1}^{0}, Π_{ω+1}^{0}) ≤_{m} (DB_{⟨ω̄,ω,0⟩}, DB_{⟨ω,0,0⟩})

We now complete the proof of Theorem 2.10. We verify the last line of the table by improving the proof of Theorem 8.3 in which we showed that, given S ∈ Π_{ω+1}, there are Boolean algebras K_{n} such that n ∈ S ⟺ inv_{1}(K_{n}) = ω. The K_{n,j} as defined in the proof of Theorem 8.3 are dense because of Proposition 8.1. But when n ∈ S, K_{n} is not dense. We slightly modify the definition of K_{n} to make it dense.

Proposition 8.5. (Σ_{ω+1}^{0}, Π_{ω+1}^{0}) ≤_{m} (DB_{⟨ω̄,ω,0⟩}, DB_{⟨ω,0,0⟩}).

Proof. Let S and K_{n,j} be as in the proof of Theorem 8.3. Now, instead of taking a product over ω, we define a componentwise product over 2^{<ω}. For σ ∈ 2^{<ω} let K_{n,σ} = K_{n,|σ|}. Let

K̃_{n} = ∏_{σ∈2^{<ω}} K_{n,σ}

where ∏_{σ∈2^{<ω}} B_{σ} is the set of ⟨b_{σ} : σ ∈ 2^{<ω}⟩ ∈ Π_{σ∈2^{<ω}}B_{σ} such that for some n_{0} we have that for every σ ∈ 2^{n_{0}} either ∀τ ⊇ σ(b_{τ} = 0) or ∀τ ⊇ σ(b_{τ} = 1). The operations and constants for ∏_{σ∈2^{<ω}} B_{σ} are defined componentwise.

As in the proof of Theorem 8.3, if n ∉ S, then inv(K̃_{n}) = ⟨k, ω, 0⟩ for some k < ω, and if n ∈ S then inv(K̃_{n}) = ⟨ω, 0, 0⟩. If n ∉ S, then denseness follows immediately from componentwise denseness as in Observation 7.3. Suppose n ∈ S, and b ∈ K̃_{n}. Then, for each σ, inv(K_{n,σ}) = ⟨\frac{|σ|(|σ|+1)}{2}, 1, 0⟩, and hence, as in the proof of Theorem 8.3, if inv_{1}(b) < ω then for some n_{0}, for every σ ∈ 2^{n_{0}}, ∀τ ⊇ σ(b_{τ} = 0), and if inv_{1}(b) = ω then for some σ, ∀τ ⊇ σ(b_{τ} = 1). If inv_{1}(b) < ω, then the denseness conditions for b are satisfied as in Observation 7.3. Suppose inv(b) = ⟨ω, 0, 0⟩. Then, there is some σ ∈ 2^{<ω} such that ∀τ ⊇ σ(b_{τ} = 1). Now consider a defined by ∀τ ⊅ σ(a_{τ} = b_{τ}), ∀τ ⊇ σ 0(a_{τ} = 0), and ∀τ ⊇ σ 1(a_{τ} = 1). Observe that a ≤ b and inv(a) = inv(b − a) = ⟨ω, 0, 0⟩ as desired to prove the denseness condition for b.

8.2 Interval Algebras and the ∗ operation

In this subsection we will show how to obtain a Boolean algebra from a linear ordering and vice versa. This will allow us to use operations on linear orderings on the corresponding Boolean algebras. We refer the reader to Monk [Mon89, I.6.15] and Goncharov [Gon97, 1.6 and 3.2] for general information on interval algebras. The goal of this section is to define a computable operator ∗ satisfying Proposition 8.1.

Definition 8.6. If L is a linear ordering with a first element, IntAlg(L) is the Boolean algebra of finite unions of half open intervals [a, b) of L where b can be ∞. (The understanding here is that [a, ∞) = {x : x ≥ a}.)

It is clear that if L is computable then so is IntAlg(L). The converse is also true:

Lemma 8.7. [Gon97, 3.2.22] There is a computable operator Lin that, given a countable Boolean algebra B, returns a linear ordering Lin(B) such that B ≅ IntAlg(Lin(B)).

Definition 8.8. The product of linear orderings, L_{0} · L_{1}, is gotten by replacing each element of L_{1} by a copy of L_{0} (and so, it is the ordering on pairs ⟨x_{1}, y_{1}⟩ ∈ L_{0} × L_{1} given by ⟨x_{1}, y_{1}⟩ < ⟨x_{2}, y_{2}⟩ ⟺ y_{1} < y_{2} ∨ (y_{1} = y_{2} & x_{1} < x_{2})).

Given two Boolean algebras B_{0} and B_{1} we let

B_{0} ∗ B_{1} = IntAlg(Lin(B_{0}) · Lin(B_{1})).

Note that B_{0} ∗ B_{1} depends on the presentations of B_{0} and B_{1}.

Now we show how to describe the analysis of the Tarski invariants of IntAlg(L) in terms of L.

Definition 8.9. A subset S of L is convex if x, y ∈ S and x < z < y implies that z ∈ S. An equivalence relation ∼ on L is convex if every one of its equivalence classes is convex.

Proposition 8.10. [Gon97, 1.6,3.2][Mon89, I.6.15]There is a one-one correspondence between ideals I of IntAlg(L) and convex equivalence relations ∼ on L such that IntAlg(L)/I ≅ IntAlg(L/ ∼). Here L/ ∼ is the linear ordering of equivalence classes [x], [y] of ∼ given by [x] < [y] ⟺ ∀w ∼ x∀z ∼ y(w < z). The convention here is that if a final segment of L is collapsed to a single equivalence class, then it is removed from L/ ∼ and its role is taken by ∞. For a given ideal I, the corresponding equivalence relation ∼ is given by x ∼ y ⟺ [x, y) ∈ I for x ≤ y ∈ L.

Definition 8.11. We denote L/ ∼_{T} by L^{[1]} where ∼_{T} is the equivalence relation corresponding to I and so

IntAlg(L^{[1]}) ≅ IntAlg(L)/I(IntAlg(L)) = IntAlg(L)^{[1]}

The following lemma is key for the proof of Proposition 8.1. The sum over M, ∑_{i∈M} L_{i}, of linear orderings L_{i}, i ∈ M, is gotten by replacing each element i of M by a copy of L_{i}. Observe that when for every i, L_{i} ≅ L we have that ∑_{i∈M} L_{i} ≅ L · M.

Lemma 8.12. [Sho04, 5.8] If, for every i ∈ ω, inv_{1}(L_{i}) ≥ 1 for every L_{i} and L = ∑_{i∈M} L_{i} then L^{[1]} = Σ_{i∈M}L_{i}^{[1]}.

Corollary 8.13. If inv_{1}(K) ≥ 1 then (K · M)^{[1]} = K^{[1]} · M.

Lemma 8.14. Let B_{0} and B_{1} be Boolean algebras.

1. If B_{0} is the trivial Boolean algebra, i.e. inv(B_{0}) = ⟨0, 1, 0⟩, B_{0} ∗ B_{1} ≅ B_{1}.

2. If B_{0} is atomic and has infinitely many atoms, then B_{0} ∗ B_{1} is atomic and inv(B_{0} ∗ B_{1}) = ⟨0, ω, 0⟩.

3. If inv(B_{0}) = ⟨p, 1, 0⟩ and inv(B_{1}) = ⟨p_{1}, q_{1}, r_{1}⟩, then inv(B_{0} ∗ B_{1}) = ⟨p + p_{1}, q_{1}, r_{1}⟩.

4. If inv(B_{0}) = ⟨p, ω, 0⟩, then inv(B_{0} ∗ B_{1}) = ⟨p, ω, 0⟩.

Proof. For (1), if inv(B_{0}) = ⟨0, 1, 0⟩, then Lin(B_{0}) ≅ 1. Hence Lin(B_{0}) · Lin(B_{1}) ≅ Lin(B_{1}), and so B_{0} ∗ B_{1} ≅ B_{1}.

For (2), consider a non-zero [x, y) ⊆ Lin(B_{0}) · Lin(B_{1}). There is some non-zero [x_{0}, y_{0}) ⊆ [x, y) with [x_{0}, y_{0}) contained in a copy of Lin(B_{0}). As B_{0} is atomic, there is an atom below [x_{0}, y_{0}), and hence below [x, y). Thus B_{0} ∗ B_{1} is atomic. Since B_{0} has infinitely many atoms, so does B_{0} ∗ B_{1}, hence inv(B_{0} ∗ B_{1}) = ⟨0, ω, 0⟩.

For parts (3) and (4) we first make a general observation. If inv_{1}(B_{0}) = p, then

(B_{0} ∗ B_{1})^{[p]} = IntAlg(Lin(B_{0}) · Lin(B_{1}))^{[p]}
≅ IntAlg((Lin(B_{0}) · Lin(B_{1}))^{[p]})
= IntAlg((Lin(B_{0})^{[1]} · Lin(B_{1}))^{[p−1]})  (by Corollary 8.13)
= IntAlg((Lin(B_{0})^{[2]} · Lin(B_{1}))^{[p−2]})  (again by Corollary 8.13)
⋮
= IntAlg(Lin(B_{0})^{[p]} · Lin(B_{1}))

For (3), we have that Lin(B_{0})^{[p]} = 1, so (B_{0} ∗B_{1})^{[p]} = IntAlg(1·Lin(B_{1})) ≅ B_{1}. Hence inv(B_{0} ∗ B_{1}) = ⟨p + p_{1}, q_{1}, r_{1}⟩.

Finally, for (4), we have that (B_{0} ∗ B_{1})^{[p]} ≅ IntAlg(Lin(B_{0})^{[p]} ∗ Lin(B_{1})), and so, since B_{0}^{[p]} is atomic and has infinitely many atoms, Lin(B_{0})^{[p]} ∗ Lin(B_{1}) is also atomic and has infinitely many atoms as in part (2). The result follows.

The first part of Proposition 8.1 follows from the lemma above. This first part was all we used in the proof of Theorem 8.3. We now prove the second part, used to prove Proposition 8.5.

Lemma 8.15. 1. D_{⟨p,1,0⟩} ∗ D_{⟨p_{1},q_{1},r_{1}⟩} ≅ D_{⟨p+p_{1},q_{1},r_{1}⟩}.

2. D_{⟨p,ω,0⟩} ∗ B ≅ D_{⟨p,ω,0⟩}.

Proof. We have seen, by Lemma 8.14, that the invariants are as claimed, so it remains to check denseness. Consider B_{0} ∗ B_{1} where B_{0} is dense, and an element of the interval algebra b = [x, y) for which we want to verify the density conditions. If x and y belong to the same copy of Lin(B_{0}) in the product Lin(B_{0}) · Lin(B_{1}), then we are done by the assumed density of B_{0}. If they are in adjacent copies of Lin(B_{0}), then one of the two subintervals lying within single copies into which b can be decomposed is responsible for the hypothesis of the density condition holding and an application of density for that subinterval within its copy supplies the desired witness for density. Thus we may assume that there is a copy of Lin(B_{0}) between x and y.

For (1), B_{0} = D_{⟨p,1,0⟩}, and B_{1} = D_{⟨p_{1},q_{1},r_{1}⟩}, so Lin(B_{0})^{[p]} = 1 and so (Lin(B_{0}) · Lin(B_{1}))^{[p]} = Lin(B_{1}). We may assume that y is ∞ or the first element of some copy of Lin(B_{0}). In either case, inv_{1}(b) ≥ p and the image of b in (Lin(B_{0}) · Lin(B_{1}))^{[p]} is the interval of Lin(B_{1}) corresponding to the copies of Lin(B_{0}) starting with x and ending with y. We now take the witness for density in Lin(B_{1}) and pull it back to Lin(B_{0}) · Lin(B_{1}).

For (2), B_{0} = D_{⟨p,ω,0⟩}, and B_{1} = B. So Lin(B_{0})^{[p]} is atomic and has infinitely many atoms. Thus inv(b) = ⟨p, ω, 0⟩ and the required witnesses for the first and second denseness conditions can be found within a copy of Lin(B_{0}) contained in b.

References

[AK00] C.J. Ash and J. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Elsevier Science, 2000.

[Cal] Wesley Calvert. The isomorphism problem for computable abelian p-groups of bounded length. To appear.

[Dow97] Rodney G. Downey. On presentations of algebraic structures. In Complexity, logic, and recursion theory, volume 187 of Lecture Notes in Pure and Appl. Math., pages 157–205. Dekker, New York, 1997.

[Ers64] Yuri L. Ershov. Decidability of the elementary theory of distributive lattices with relative complements and the theory of filters. Algebra i Logika, 3:17–38, 1964.

[Fei67] L. J. Feiner. Orderings and Boolean algebras not isomorphic to recursive ones. PhD thesis, MIT, 1967.

[GK02] Sergei S. Goncharov and J. Knight. Computable structure and non-structure theorems. Algebra and Logic, 41:351–373, 2002.

[Gon97] Sergei S. Goncharov. Countable Boolean algebras and decidability. Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997.

[Hod93] Wilfred Hodges. Model Theory. Cambridge University Press, Cambridge, England, 1993.

[Mon89] J. Donald Monk, editor. Handbook of Boolean algebras, 3 vols. North-Holland Publishing Co., Amsterdam, 1989.

[Mor82] A. S. Morozov. Strong constructivizability of countable saturated Boolean algebras. Algebra i Logika, 21(2):193–203, 1982.

[OS89] S. P. Odintsov and V. L. Selivanov. The arithmetical hierarchy and ideals of enumerated Boolean algebras. Sibirsk. Mat. Zh., 30(6):140–149, 1989.

[Sel90] V. L. Selivanov. Index sets of classes of hyperhypersimple sets. Algebra i Logika, 29(2):220–240, 261, 1990.

[Sel91] V. L. Selivanov. The fine hierarchy and definable index sets. Algebra i Logika, 30(6):705–725, 771, 1991.

[Sel03] Victor Selivanov. Positive structures. In Computability and models, Univ. Ser. Math., pages 321–350. Kluwer/Plenum, New York, 2003.

[Sho04] Richard A. Shore. Invariants, Boolean algebras and ACA^{+}. Transactions of the American Mathematical Society, 2004. To appear.

[Soa87] Robert I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, Berlin, 1987.

[Tar49] Alfred Tarski. Arithmetical classes and types of boolean algebras. Bulletin of the American Mathematical Society, 55:63, 1949.

[Was74] Jan Waszkiewicz. ∀n-theories of Boolean algebras. Colloq. Math., 30:171–175, 1974.

[Whi00] Walker White. Characterizations for Computable Structures. PhD thesis, Cornell University, 2000.