Imaginaries in Boolean algebras.

Roman Wencel^{1}

Instytut Matematyczny Uniwersytetu Wrocławskiego

ABSTRACT

Given an infinite Boolean algebra B, we find a natural class of ∅-definable equivalence relations E_{B} such that every imaginary element from B^{eq} is interdefinable with an element from a sort determined by some equivalence relation from E_{B}. It follows that B together with the family of sorts determined by E_{B} admits elimination of imaginaries in a suitable multisorted language. The paper generalizes author’s earlier results concerning definable equivalence relations and weak elimination of imaginaries for Boolean algebras, obtained in [We3].

0 Introduction and preliminaries

Although no infinite Boolean algebra admits elimination of imaginaries, there exist infinite Boolean algebras admitting weak elimination of imaginaries. As proved in [We3], an infinite Boolean algebra B admits weak elimination of imaginaries iff the quotient Boolean algebra B/I(B) consists of at most two elements (here I(B) denotes the ideal of B consisting of all elements of the form a⊔b with a atomless and b atomic). A special case of this result (namely: weak elimination of imaginaries for infinite Boolean algebras with finitely many atoms) plays a crucial role in studying definable sets of partially ordered o-minimal structures with ordering derived from a Boolean algebra.

C. Toffalori in [To] introduced two notions of o-minimality for partially ordered first-order structures. A partially ordered structure M = (M, ≤, …) is called quasi o-minimal if every definable set X ⊆ M is a finite Boolean combination of sets defined by inequalities of the form x ≤ a and x ≥ b, where a, b ∈ M. If additionally the parameters appearing in these inequalities may be taken from the algebraic closure of the set of parameters needed to define X, then the structure M = (M, ≤, …) is called o-minimal. It is easy to see that in case the ordering ≤ is linear, these two notions are equivalent to the usual o-minimality. C. Toffalori observed that if M = (M, ≤, …) is quasi o-minimal and the ordering ≤ comes from some Boolean algebra B, then the number of atoms of B must be finite. By weak elimination of imaginaries for Boolean algebras with finitely atoms, the Toffalori’s notions of o-minimality and quasi o-minimality coincide in case of Boolean ordered structures.

A natural counterpart of o-minimality (called q-minimality) for expansions of arbitrary Boolean algebras was introduced in author’s PhD thesis. An expansion (B, …) of a Boolean algebra B to the language L ⊇ L_{BA} is said to be q-minimal iff every L-definable subset of B is L_{BA}-definable, where L_{BA} = {⊓, ⊔,′ , 0, 1} denotes the usual language of Boolean algebras. By results of [NW], for expansions of Boolean algebras with finitely many atoms, q-minimality coincides with Toffalori’s notions of quasi o-minimality and o-minimality. As the model theoretic results obtained in [NW],

[We1] and [We2] for Boolean ordered structures heavily rest on weak elimination of imaginaries of the underlying Boolean algebras, it is natural to expect that some form of elimination of imaginaries will be needed to investigate sets definable in q-minimal expansions of arbitrary Boolean algebras.

0Keywords: Boolean algebra, elimination of imaginaries.

1Research supported by a Marie Curie Intra-European Fellowship within the 6th European Community Framework Programme (contract number: MEIF-CT-2003-501326) and by the Polish Government grant N N201 545938.

In this paper, for every infinite Boolean algebra B, we find a natural multisorted language in which B admits elimination of imaginaries. The main theorem of the paper (i.e. Theorem 3.3) could be regarded as a preliminary step towards development of model theory of q-minimal expansions of arbitrary infinite Boolean algebras. Nevertheless, it might be also of independent interest. Research in this spirit has recently been conducted in the context of algebraically closed valued fields [HHM] and real closed valued fields [Me].

The paper is organized as follows. In §1 we introduce the most important tool of the paper, namely the notion of restricted elementary invariant of a Boolean algebra, and demonstrate its basic properties. In §2 we investigate certain equivalence relations in Boolean algebras and generalize Lemmas 2.2, 3.2 and 4.4 from [We3].

§3 contains the main result of the paper (Theorem 3.3). For a given infinite Boolean algebra B and a definable set X ⊆ B^{n}, we find an L_{BA}-formula ψ(\overline{x}, \overline{z}) such that Y := \{\overline{d} ∈ B^{|\overline{z}|} : X = ψ(B, \overline{d})\} is a non-empty set of partitions of 1_{B}, and for any tuples \overline{d} = d_{0} … d_{m} and \overline{e} = e_{0} … e_{m} from Y, there is a unique permutation σ of the set \{0, …, m\} such that the tuple d_{σ(0)} … d_{σ(m)} is “roughly equal” to e_{0} … e_{m}. By “roughly equal” we mean here that for any i ≤ m and d ∈ {d_{i}, e_{i} : i ≤ m}, there is a number α < ω for which d ⊓ ((d_{σ(i)} ⊓ e′_{i}) ⊔ (d′_{σ(i)} ⊓ e_{i})) belongs to the α-th elementary ideal I_{α}(B), while d ∉ I_{α}(B). The proof extends author’s methods from [We3] used in case of Boolean algebras with |B/I(B)| ≤ 2.

The class of formulas of the form ψ(\overline{x}, \overline{z}) obtained in the proof of Theorem 3.3 and enjoying the properties described above determines a class E_{B} of ∅-definable equivalence relations on sets of partitions of 1_{B}. From Theorem 3.3 and the subsequent propositions we derive the fact that the multisorted structure B(E_{B}), obtained by adjoining to B all the sorts determined by equivalence relations from E_{B}, admits elimination of imaginaries in a suitable multisorted language.

For the basics of model theory we refer the reader to [ChK] and to the first chapter of [Pi]; for elementary properties of Boolean algebras to the eighth chapter of [HBA].

Our notation concerning Boolean algebras is consistent with [We3]. We use the symbols ⊓ (meet), ⊔ (join), ′ (complement), 0_{B} and 1_{B} to denote the Boolean operations and Boolean constants in a Boolean algebra B. Moreover, a + b denotes the symmetric difference of elements a, b ∈ B. The language of Boolean algebras is L_{BA} = {⊓, ⊔,′ , 0, 1}. For a ∈ B we consider the Boolean algebra B|a := ([0, a]^{B}, ⊓, ⊔,^{′a} , 0_{B}, a), where b^{′a} := b′ ⊓ a, and call it B restricted to a. Symbols a^{+} and a^{−} denote a and a′ respectively. If Aa := A ∪ {a} ⊆ B, by a ⊓ A we mean {a ⊓ b : b ∈ A}. Similarly we define a + A. In case b_{≤n} := b_{0} … b_{n} is a tuple of elements of B, by a ⊓ b_{≤n} we denote the tuple ⟨a ⊓ b_{i} : i ≤ n⟩. For n < ω, η ∈ {+, −}^{n+1} and a_{≤n} ⊆ B we define a_{≤n}^{η} := a_{0}^{η(0)} ⊓ … ⊓ a_{n}^{η(n)}. An element a ∈ B is called atomic, if for every b ∈ (0_{B}, a] there is an atom c such that c ≤ b; a is said to atomless if there are no atoms b ≤ a. For instance, 0_{B} is always atomic and atomless. A Boolean algebra B is called atomic [atomless] is 1_{B} is atomic [atomless]. The set of all atoms of B is denoted by At(B).

For every n < ω, we define the Boolean algebra B^{(n)} and an ideal I_{n}(B) ⊆ B by the following conditions: I_{0}(B) = {0_{B}}, B^{(n)} = B/I_{n}(B) and I_{n+1}(B) = π_{n}^{−1}(I(B^{(n)})), where π_{n} : B ⟶ B^{(n)} denotes the canonical projection. The elementary invariant of B (notation: Inv(B)) is a triple ⟨α, β, γ⟩ defined as follows:

α = min ({k < ω : B^{(k)} is trivial} ∪ {ω}) ,
β = \{ \begin{matrix}0 & if α ∈ \{0, ω\} or (0 < α < ω and B^{(α−1)} is atomic) \\ 1 & otherwise, \end{matrix}

γ = \{ \begin{matrix}0 & if α ∈ \{0, ω\} \\ min(|At(B^{(α−1)})|, ω) & otherwise. \end{matrix}

The set of all triples ⟨α, β, γ⟩ such that ⟨α, β, γ⟩ = Inv(B) for some Boolean algebra B is equal to

INV := {⟨0, 0, 0⟩, ⟨ω, 0, 0⟩} ∪ {⟨α, β, γ⟩ : 0 < α < ω, β ∈ {0, 1}, γ ≤ ω and β + γ > 0}.

If \overline{a}\overline{b} = a_{≤n} ⊆ B, then tp(\overline{a}/\overline{b}) is completely determined by the elementary invariants of Boolean algebras B|d, where d is an atom in the Boolean subalgebra generated by \overline{a}\overline{b}. Two Boolean algebras B_{1} and B_{2} are elementarily equivalent iff Inv(B_{1}) = Inv(B_{2}).

Let B be a Boolean algebra. For every a ∈ B and n < ω we define the (possibly empty) set Π_{n}(a) of n + 1-partitions as follows:

Π_{n}(a) = {b_{≤n} ⊆ (0_{B}, a] : b_{0} ⊔ … ⊔ b_{n} = a and b_{i} ⊓ b_{j} = 0_{B} for i < j ≤ n} .

We say that \overline{b} is a partition of a ∈ B iff \overline{b} ∈ Π_{n}(a) for some n < ω.

If j < ω and 1 ≤ s < ω, then there are L_{BA}-formulas ε_{j}(x), ψ_{j,s}(x) and at_{j}(x) such that for every Boolean algebra B and every element a ∈ B, the following conditions hold (see [HBA], p. 292):

• B ⊧ ε_{j}(a) iff a ∈ I_{j}(B) iff (B|a)^{(j)} is trivial,

• B ⊧ ψ_{j,s}(a) iff (B|a)^{(j)} contains at least s atoms,

• B ⊧ at_{j}(a) iff (B|a)^{(j)} is atomic.

Lemma 0.1 [HBA, Lemma 18.8] For every ⟨α, β, γ⟩ ∈ INV, there is a (possibly infinite) set of L_{BA}-formulas Σ_{α,β,γ}(x) such that

• every formula in Σ_{α,β,γ}(x) is of the form ε_{j}(x), ¬ε_{j}(x), ψ_{j,s}(x), ¬ψ_{j,s}(x), at_{j}(x) or ¬at_{j}(x), where j < ω and 1 ≤ s < ω, and

• for every Boolean algebra B and an element a ∈ B,

B ⊧ Σ_{α,β,γ}(a) if and only if Inv(B|a) = ⟨α, β, γ⟩.

Lemma 0.2 Assume that B is an infinite Boolean algebra, \overline{a} = a_{≤r} is a partition of 1_{B} and φ(x_{≤n}, y_{≤r}) ∈ L_{BA} (x_{≤n} and y_{≤r} are abbreviations for x_{0} … x_{n} and y_{0} … y_{r} respectively). Then φ(B, \overline{a}) is a finite Boolean combination of sets defined by formulas of the form: ε_{j}(a_{i} ⊓ x_{≤n}^{η}), ψ_{j,s}(a_{i} ⊓ x_{≤n}^{η}), at_{j}(a_{i} ⊓ x_{≤n}^{η}), where i ≤ r, η ∈ {+, −}^{n+1}, j < ω and 1 ≤ s < ω.

Proof. Assume that B, a_{≤r} and φ(x_{≤n}, y_{≤r}) satisfy assumptions of the lemma. For every b_{≤n} ⊆ B, tp(b_{≤n}/a_{≤r}) is determined by the elementary invariants Inv(B|a_{i} ⊓ b_{≤n}^{η}), where i ≤ r and η ∈ {+, −}^{n+1}. From this and Lemma 0.1 our assertion follows.

Acknowledgements. Part of the work on this paper was done while the author stayed at the University of Leeds as a Marie Curie fellow. The author also expresses his gratitude towards the referee, whose detailed comments helped to improve the presentation of results.

1 Restricted elementary invariants

For every Boolean algebra B and a triple ⟨α, β, γ⟩ ∈ INV, the set Σ_{α,β,γ}(B) from Lemma 0.1 is type-definable, but not necessarily definable. This means that in certain cases it is not possible to express all elementary properties of an element of a Boolean algebra using a single formula. For example, if B is the Boolean algebra of all subsets of ω, then the set

{a ∈ B : B|a, B|a′ are infinite} = {a ∈ B : Inv(B|a) = Inv(B|a′) = ⟨1, 0, ω⟩}

is not definable. In spite of this obstacle, in §3 of [We3] we were able to prove weak elimination of imaginaries for infinite atomic Boolean algebras counting the number of atoms below elements up to a certain level determined by the formula under consideration.

In the proof of Theorem 3.3, given an infinite Boolean algebra B and a set X ⊆ B^{n} definable over a tuple \overline{a} ⊆ B, we give a canonical construction of an \overline{a}-definable family of partitions of 1_{B} such that over each of them the given set is definable. To ensure that such a class is definable over \overline{a} and not too large, a single formula expressing a sufficient amount of its elementary properties could be useful. In order to realize this idea, in the following definition we introduce the concept of a restricted elementary invariant of a Boolean algebra.

Definition 1.1 Assume that B is a Boolean algebra with Inv(B) = ⟨α, β, γ⟩ and α_{0}, γ_{0} are positive integers. We define the restricted ⟨α_{0}, γ_{0}⟩-elementary invariant of B as follows:

Inv_{α_{0},γ_{0}}(B) := \{ \begin{matrix}⟨α, β, min(γ, γ_{0})⟩ & for & α ≤ α_{0}, \\ ⟨α_{0} + 1, 0, 0⟩ & for & α > α_{0}. \end{matrix}

The set of all restricted ⟨α_{0}, γ_{0}⟩-elementary invariants of Boolean algebras will be denoted by INV_{α_{0},γ_{0}}. It is easy to see that

INV_{α_{0},γ_{0}} = {⟨0, 0, 0⟩, ⟨α_{0} + 1, 0, 0⟩} ∪ {⟨α, β, γ⟩ : 1 ≤ α ≤ α_{0}, β ∈ {0, 1}, γ ≤ γ_{0} and β + γ > 0}.

The crucial difference between elementary invariants and their restricted counterpart is that in the latter case for every Boolean algebra B, the set of elements a ∈ B such that B|a has a given restricted elementary invariant is definable (in fact, ∅-definable).

Lemma 1.2 If α_{0}, γ_{0} ∈ ℕ_{+} and ⟨α, β, γ⟩ ∈ INV_{α_{0},γ_{0}}, then there is an L_{BA}-formula σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(x) such that

• σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(x) is a conjunction of formulas of the form ε_{j}(x_{≤n}^{η}), ¬ε_{j}(x_{≤n}^{η}), ψ_{j,s}(x_{≤n}^{η}), ¬ψ_{j,s}(x_{≤n}^{η}), at_{j}(x_{≤n}^{η}) and ¬at_{j}(x_{≤n}^{η}), where j ≤ α_{0}, s ≤ γ_{0} and η ∈ {+, −}^{n+1}, and

• for every Boolean algebra B and every element a ∈ B,

B ⊧ σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(a) iff Inv_{α_{0},γ_{0}}(B|a) = ⟨α, β, γ⟩.

Proof. Assume that 1 ≤ α_{0}, γ_{0} < ω. Below, for every ⟨α, β, γ⟩ ∈ INV_{α_{0},γ_{0}} we define the formula σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(x) satisfying our demands.

σ_{⟨0,0,0⟩}^{α_{0},γ_{0}}(x) = ε_{0}(x) = (x = 0),
σ_{⟨α_{0}+1,0,0⟩}^{α_{0},γ_{0}}(x) = ¬ε_{α_{0}}(x).

For 1 ≤ α ≤ α_{0} we define:

σ_{⟨α,1,0⟩}^{α_{0},γ_{0}}(x) = ε_{α}(x) ∧ ¬ε_{α−1}(x) ∧ ¬at_{α−1}(x) ∧ ¬ψ_{α−1,1}(x),
σ_{⟨α,1,γ_{0}⟩}^{α_{0},γ_{0}}(x) = ε_{α}(x) ∧ ¬ε_{α−1}(x) ∧ ¬at_{α−1}(x) ∧ ψ_{α−1,γ_{0}}(x), and
σ_{⟨α,0,γ_{0}⟩}^{α_{0},γ_{0}}(x) = ε_{α}(x) ∧ ¬ε_{α−1}(x) ∧ at_{α−1}(x) ∧ ψ_{α−1,γ_{0}}(x).

Finally, in case 1 ≤ α ≤ α_{0} and 1 ≤ γ < γ_{0} we define:

σ_{⟨α,0,γ⟩}^{α_{0},γ_{0}}(x) = ε_{α}(x) ∧ ¬ε_{α−1}(x) ∧ at_{α−1}(x) ∧ ψ_{α−1,γ}(x) ∧ ¬ψ_{α−1,γ+1}(x),
σ_{⟨α,1,γ⟩}^{α_{0},γ_{0}}(x) = ε_{α}(x) ∧ ¬ε_{α−1}(x) ∧ ¬at_{α−1}(x) ∧ ψ_{α−1,γ}(x) ∧ ¬ψ_{α−1,γ+1}(x).

Every tuple in a Boolean algebra B determines a partition of 1_{B}. Sometimes we will consider tuples of restricted elementary invariants of B restricted to elements of such a partition.

Definition 1.3 Assume that B is a Boolean algebra, a_{≤n} ⊆ B and α_{0}, γ_{0} ∈ ℕ_{+}. The restricted ⟨α_{0}, γ_{0}⟩-elementary invariant of a_{≤n} is defined as follows:

Inv_{α_{0},γ_{0}}(a_{≤n}) = ⟨Inv_{α_{0},γ_{0}}(B|a_{≤n}^{η}) : η ∈ {+, −}^{n+1}⟩.

In particular, Inv_{α_{0},γ_{0}}(a) = ⟨Inv_{α_{0},γ_{0}}(B|a), Inv_{α_{0},γ_{0}}(B|a′)⟩.

Lemma 1.4 Assume that α_{0}, γ_{0} ∈ ℕ_{+} and for every η ∈ {+, −}^{n+1}, ⟨α_{η}, β_{η}, γ_{η}⟩ is a triple from INV_{α_{0},γ_{0}}. Then there is an L_{BA}-formula φ(x_{≤n}) such that

• φ(x_{≤n}) is a conjunction of formulas of the form ε_{j}(x_{≤n}^{η}), ¬ε_{j}(x_{≤n}^{η}), ψ_{j,s}(x_{≤n}^{η}), ¬ψ_{j,s}(x_{≤n}^{η}), at_{j}(x_{≤n}^{η}) and ¬at_{j}(x_{≤n}^{η}), where j ≤ α_{0}, s ≤ γ_{0} and η ∈ {+, −}^{n+1}, and

• for every Boolean algebra B and a_{≤n} ⊆ B,

B ⊧ φ(a_{≤n}) iff Inv_{α_{0},γ_{0}}(B|a_{≤n}^{η}) = ⟨α_{η}, β_{η}, γ_{η}⟩ for η ∈ {+, −}^{n+1}.

Proof. The formula

φ(x_{≤n}) = ⋀_{η∈{+,−}^{n+1}} σ_{⟨α_{η},β_{η},γ_{η}⟩}^{α_{0},γ_{0}}(x_{≤n}^{η})

satisfies our demands.

In the following two lemmas we outline some of the basic properties of restricted elementary invariants.

Lemma 1.5 Assume that α_{0}, α_{1}, γ_{0}, γ_{1} are positive integers, B is a Boolean algebra and a, b ∈ B. (a) If Inv(B|a) = Inv(B|b), then Inv_{α_{0},γ_{0}}(B|a) = Inv_{α_{0},γ_{0}}(B|b).

(b) If ⟨α_{0}, γ_{0}⟩ ≤ ⟨α_{1}, γ_{1}⟩, where ≤ denotes the lexicographic ordering of ℕ_{+} × ℕ_{+}, then

Inv_{α_{1},γ_{1}}(B|a) = Inv_{α_{1},γ_{1}}(B|b) ⟹ Inv_{α_{0},γ_{0}}(B|a) = Inv_{α_{0},γ_{0}}(B|b).

Lemma 1.6 Assume that α_{0}, γ_{0} are positive integers, B is a Boolean algebra, a, b, c, d ∈ B, and a_{≤n}, b_{≤n} ⊆ B.

(a) If a_{≤n} is a partition of 1_{B}, then Inv_{α_{0},γ_{0}}(a ⊓ a_{≤n}) is completely determined by the sequence ⟨Inv_{α_{0},γ_{0}}(B|a ⊓ a_{i}) : i ≤ n⟩.

(b) If Inv_{α_{0},γ_{0}}(B|a) = ⟨α_{1}, β_{1}, γ_{1}⟩, Inv_{α_{0},γ_{0}}(B|b) = ⟨α_{2}, β_{2}, γ_{2}⟩ and a ⊓ b = 0_{B}, then

Inv_{α_{0},γ_{0}}(B|a ⊔ b) = \{ \begin{matrix}⟨α_{1}, β_{1}, γ_{1}⟩ & if & α_{1} > α_{2} \\ ⟨α_{1}, max(β_{1}, β_{2}), min(γ_{0}, γ_{1} + γ_{2})⟩ & if & α_{1} = α_{2} \\ ⟨α_{2}, β_{2}, γ_{2}⟩ & if & α_{1} < α_{2}. \end{matrix}

(c) If a⊓b = 0_{B}, Inv_{α_{0},γ_{0}}(B|a⊓c) = Inv_{α_{0},γ_{0}}(B|a⊓d) and Inv_{α_{0},γ_{0}}(B|b⊓c) = Inv_{α_{0},γ_{0}}(B|b⊓d), then Inv_{α_{0},γ_{0}}(B|(a ⊔ b) ⊓ c) = Inv_{α_{0},γ_{0}}(B|(a ⊔ b) ⊓ d).

(d) If a⊓b = 0_{B}, Inv_{α_{0},γ_{0}}(a⊓a_{≤n}) = Inv_{α_{0},γ_{0}}(a⊓b_{≤n}) and Inv_{α_{0},γ_{0}}(b⊓a_{≤n}) = Inv_{α_{0},γ_{0}}(b⊓b_{≤n}), then Inv_{α_{0},γ_{0}}((a ⊔ b) ⊓ a_{≤n}) = Inv_{α_{0},γ_{0}}((a ⊔ b) ⊓ b_{≤n}).

2 Equivalence relations in Boolean algebras

Consider an infinite Boolean algebra B and elements a, b, c ∈ B such that a⊓c, b⊓c > 0_{B}, c ≤ a⊔b and a ⊓ b = 0_{B}. In [We3] we were dealing with the problem of obtaining one partition of a ⊔ b from another by a finite series of modifications below a, b or c. Lemmas 2.2 and 3.2 from [We3] could be expressed in the form of the following statement.

Fact 2.1 Assume that γ_{0} ∈ ℕ_{+}, Inv(B|a ⊔ b) ∈ {⟨1, 1, 0⟩, ⟨1, 0, ω⟩}, a_{≤n}, b_{≤n} ⊆ B, for every η ∈ {+, −}^{n+1}, Inv_{1,γ_{0}}((a ⊔ b) ⊓ a_{≤n}^{η}) = Inv_{1,γ_{0}}((a ⊔ b) ⊓ b_{≤n}^{η}), and (a ⊔ b)′ ⊓ a_{≤n} = (a ⊔ b)′ ⊓ b_{≤n}. There there are tuples a_{≤n}^{0} = a_{≤n}, a_{≤n}^{1}, …, a_{≤n}^{k} = b_{≤n} ⊆ B such that

• (∀i < k)(∃d ∈ {a, b, c})(d′ ⊓ a_{≤n}^{i} = d′ ⊓ a_{≤n}^{i+1}) and

• (∀i < k)(∀d ∈ {a, b, c})(Inv_{1,γ_{0}}(d ⊓ a_{≤n}^{i}) = Inv_{1,γ_{0}}(d ⊓ a_{≤n}^{i+1})).

It turns out that an analogical result cannot be obtained in case c ∈ I_{α}(B) and a, b ∉ I_{α}(B) for some α < ω. Informally speaking, there is too little space below c to transform one tuple into another by modifying it only below a, b or c. Lemma 4.4 from [We3] deals with modifications of tuples below elements in Boolean algebras of elementary invariant equal to ⟨2, 0, 1⟩, in which case one needs additional assumptions. In this section we isolate some reasonable conditions on a, b, c under which analogues of Lemmas 2.2, 3.2 and 4.4 from [We3] can be proved in arbitrary Boolean algebras and relevant methods generalized.

Definition 2.2 Assume that B is a Boolean algebra and a, b ∈ B. We say that a is large in b iff

(∀n < ω)(a ⊓ b ∈ I_{n}(B) ⟺ b ∈ I_{n}(B)).

Lemma 2.3 Assume that B is a Boolean algebra and a, b, c ∈ B.

(a) If a ≥ b, then a is large in b.

(b) 0_{B} is large in a iff a = 0_{B}.

(c) If a ≤ b ≤ c, a is large in b and b is large in c, then a is large in c.

(d) If b is large in 1_{B}, then a is large in b iff b is large in a.

(e) If b is not large in a, then Inv(B|a) = Inv(B|a ⊓ b′), and consequently, B|a ≡ B|a ⊓ b′.

(f) If a > 0_{B} and b_{≤n} ∈ Π_{n}(1_{B}), then b_{i} is large in a for some i ≤ n.

Lemma 2.4 Assume that α_{0}, γ_{0} ∈ ℕ_{+} and a, b, d are elements of a Boolean algebra B such that a is large in b, d is not large in b, and b > a, d. Then there is an element e < a such that e is not large in a and Inv_{α_{0},γ_{0}}(B|d) = Inv_{α_{0},γ_{0}}(B|e).

Proof. Let Inv(B|a) = ⟨α_{1}, β_{1}, γ_{1}⟩, Inv(B|b) = ⟨α_{2}, β_{2}, γ_{2}⟩ and Inv(B|d) = ⟨α_{3}, β_{3}, γ_{3}⟩. Our assumptions guarantee that α_{1} = α_{2} > α_{3}, so α := max(α_{0}, α_{3}) < ω. Define γ := max(γ_{0}, γ_{3}) for γ_{3} < ω and γ := γ_{0} in case γ_{3} = ω. Let Inv_{α,γ}(B|d) = ⟨α′, β′, γ′⟩. Note that a′ ⊓ d is not large in a ⊔ d. By Lemma 2.3(e), Inv(B|a ⊔ d) = Inv(B|a) and B|a ⊔ d ≡ B|a. Since B|a ⊔ d ⊧ σ_{⟨α′,β′,γ′⟩}^{α,γ}(d) ∧ ε_{α_{3}}(d), there is e < a such that B|a ⊧ σ_{⟨α′,β′,γ′⟩}^{α,γ}(e) ∧ ε_{α_{3}}(e). Hence e is not large in a, and Inv_{α_{0},γ_{0}}(B|d) = Inv_{α_{0},γ_{0}}(B|e).

For n < ω and 0 < α_{0}, γ_{0} < ω we denote by E_{n,α_{0},γ_{0}}(u_{≤n}, v_{≤n}, z) the following L_{BA}-formula.

E_{n,α_{0},γ_{0}}(u_{≤n}, v_{≤n}, z) = ⋀_{η∈{+,−}^{n+1}} [ ⋀_{j≤α_{0}} (ε_{j}(z ⊓ u_{≤n}^{η}) ⟷ ε_{j}(z ⊓ v_{≤n}^{η})) ∧

⋀_{j≤α_{0}} ⋀_{s≤γ_{0}} (ψ_{j,s}(z ⊓ u_{≤n}^{η}) ⟷ ψ_{j,s}(z ⊓ v_{≤n}^{η})) ∧

⋀_{j≤α_{0}} (at_{j}(z ⊓ u_{≤n}^{η}) ⟷ at_{j}(z ⊓ v_{≤n}^{η}))] ∧ z′ ⊓ u_{≤n} = z′ ⊓ v_{≤n}.

It is clear that for every a ∈ B, E_{n,α_{0},γ_{0}}(u_{≤n}, v_{≤n}, a) defines an equivalence relation E_{n,α_{0},γ_{0}}^{a} on B^{n+1}. Note that E_{n,α_{0},γ_{0}}^{0_{B}} is the equality on B^{n+1}.

Definition 2.5 Assume that α_{0}, γ_{0} ∈ ℕ_{+}, a is a non-zero element of a Boolean algebra B and a_{≤n}b_{≤n} ⊆ B. A tuple b_{≤n} ⊆ B is said to be an ⟨α_{0}, γ_{0}⟩-modification of a_{≤n} below a iff

a′ ⊓ a_{≤n} = a′ ⊓ b_{≤n} and Inv_{α_{0},γ_{0}}(a ⊓ a_{≤n}) = Inv_{α_{0},γ_{0}}(a ⊓ b_{≤n}).

Note that in the setting of the above definition, b_{≤n} is an ⟨α_{0}, γ_{0}⟩-modification of a_{≤n} below a iff B ⊧ E_{n,α_{0},γ_{0}}(a_{≤n}, b_{≤n}, a). If b_{≤n} is an ⟨α_{0}, γ_{0}⟩-modification of a_{≤n} below a and b ≥ a, then it is also an ⟨α_{0}, γ_{0}⟩-modification of a_{≤n} below b.

Definition 2.6 A non-zero element a of a Boolean algebra B is called simple iff one of the following conditions hold.

• (B|a)^{(m)} is non-trivial and atomless for some m < ω,

• (B|a)^{(m)} is non-trivial and atomic for some m < ω,

• Inv(B|a) = ⟨ω, 0, 0⟩.

Note that an element a of a Boolean algebra B is simple iff

Inv(B|a) ∈ {⟨ω, 0, 0⟩} ∪ {⟨α, 1, 0⟩ : 0 < α < ω} ∪ {⟨α, 0, γ⟩ : 0 < α < ω, 0 < γ ≤ ω}.

Lemma 2.7 Assume that a, b, c are non-zero elements of an infinite Boolean algebra B (a) If a ≥ b, and b is large in a, then a is simple iff b is simple.

(b) If a, b, c are simple, a ⊓ b = 0_{B}, c is large both in a and b, and a ⊔ b is large in c, then a ⊔ b is simple.

Proof. Since (a) is easy, we only prove (b). Let a, b, c be simple elements of a Boolean algebra B such that a ⊓ b = 0_{B}, c is large both in a and b, and a ⊔ b is large in c. We consider three cases.

Case 1. Inv(B|c) = ⟨ω, 0, 0⟩. Since a ⊔ b is large in c, also Inv(B|(a ⊔ b) ⊓ c) = ⟨ω, 0, 0⟩. Hence Inv(B|a ⊔ b) = ⟨ω, 0, 0⟩.

Case 2. Inv(B|c) = ⟨α, 1, 0⟩, where 0 < α < ω. The element a ⊔ b is large in c, so Inv(B|(a ⊔ b) ⊓ c) = ⟨α, 1, 0⟩. But then Inv(B|a ⊓ c) = ⟨α, 1, 0⟩ or Inv(B|b ⊓ c) = ⟨α, 1, 0⟩. Suppose for instance that the first possibility holds.

As c is large in a, we get Inv(B|a) = ⟨α, 1, 0⟩. Note that either Inv(B|b ⊓ c) = ⟨α, 1, 0⟩ or b ⊓ c ∈ I_{α}(B). In the first case Inv(B|b) = ⟨α, 1, 0⟩. If b ⊓ c ∈ I_{α}(B), then (since c is large in b) also b ∈ I_{α}(B). In both cases Inv(B|a ⊔ b) = ⟨α, 1, 0⟩.

Case 3. Inv(B|c) = ⟨α, 0, γ⟩, where 0 < α < ω and 0 < γ ≤ ω. An argument similar to that used in Case 2 yields that Inv(B|a ⊔ b) = ⟨α, 0, γ⟩.

In all possible cases the element a ⊔ b is simple. This finishes the proof.

Theorem 2.8 Assume that n < ω, a, b, c are simple non-zero elements of a Boolean algebra B, a ⊓ b = 0_{B}, c ≤ a ⊔ b and c is large in each of the elements a, b. Denote by ⟨α_{1}, β_{1}, γ_{1}⟩ and ⟨α_{2}, β_{2}, γ_{2}⟩ the elementary invariants of B|a and B|b respectively and let α_{0}, γ_{0} be positive integers satisfying the following conditions.

• For i=1,2: if α_{i} < ω, then α_{0} ≥ α_{i}.

• For i=1,2: if α_{i} < ω, β_{i} = 0 and γ_{i} < ω, then γ_{0} ≥ γ_{i}.

• If α_{1} = α_{2} < ω, β_{1} = β_{2} = 0 and γ_{1}, γ_{2} < ω, then γ_{0} ≥ γ_{1} + γ_{2}.

Then the following conditions hold.

(a) If ∼ is an equivalence relation on B^{n+1} containing E_{n,α_{0},γ_{0}}^{a} ∪ E_{n,α_{0},γ_{0}}^{b} ∪ E_{n,α_{0},γ_{0}}^{c} and a_{≤n} ∈ B^{n+1}, then there is b_{≤n} ∼ a_{≤n} such that for every η ∈ {+, −}^{n+1}, a ⊓ b_{≤n}^{η} = 0_{B} or a_{≤n}^{η} is large in a.

(b) Any equivalence relation on B^{n+1} containing E_{n,α_{0},γ_{0}}^{a} ∪E_{n,α_{0},γ_{0}}^{b} ∪E_{n,α_{0},γ_{0}}^{c} contains E_{n,α_{0},γ_{0}}^{a⊔b}.

Proof. Note that by Lemma 2.7, the element a ⊔ b is simple. Throughout the proof, for the sake of notational simplicity, ⟨α_{0}, γ_{0}⟩-modifications will be called shortly ”modifications”.

(a) Let ∼ be an equivalence relation on B^{n+1} containing E_{n,α_{0},γ_{0}}^{a} ∪ E_{n,α_{0},γ_{0}}^{b} ∪ E_{n,α_{0},γ_{0}}^{c}. Define

E = {η ∈ {+, −}^{n+1} : a_{≤n}^{η} is not large in a}.

By Lemma 2.4, there are pairwise disjoint elements d_{η} ∈ [0_{B}, a ⊓ c), η ∈ E such that for every η ∈ E, Inv_{α_{0},γ_{0}}(B|d_{η}) = Inv_{α_{0},γ_{0}}(B|a ⊓ a_{≤n}^{η}) and d_{η} is not large in a ⊓ c. Let d := ⨆_{η∈E} d_{η} and let

η_{1} ∈ {+, −}^{n+1} be such that a_{≤n}^{η_{1}} is large in a. We define the tuple a_{≤n}^{1} by the following conditions:

• a′ ⊓ a_{≤n}^{1} = a′ ⊓ a_{≤n},

• a ⊓ (a_{≤n}^{1})^{η} = d_{η} for η ∈ E,

• a ⊓ (a_{≤n}^{1})^{η_{1}} = a ⊓ d′ ⊓ (a_{≤n}^{η_{1}} ⊔ ⨆_{η∈E} a_{≤n}^{η}),

• a ⊓ (a_{≤n}^{1})^{η} = a ⊓ d′ ⊓ a_{≤n}^{η} for η ∉ E ∪ {η_{1}}. a_{≤n}^{1} is a modification of a_{≤n} below a, and for every η ∈ {+, −}^{n+1}, if (a_{≤n}^{1})^{η} is not large in a, then a ⊓ (a_{≤n}^{1})^{η} < a ⊓ c. Repeating this argument with a and a ⊓ c replaced by c and b ⊓ c (respectively), we obtain b_{≤n}, a modification of a_{≤n}^{1} below c satisfying our demands.

(b) Let ∼ be an equivalence relation on B^{n+1} containing E_{n,α_{0},γ_{0}}^{a} ∪ E_{n,α_{0},γ_{0}}^{b} ∪ E_{n,α_{0},γ_{0}}^{c}.

Without loss of generality we can assume that b is large in a ⊔ b. Let a_{≤n}, b_{≤n} ⊆ B be tuples such that (a ⊔ b)′ ⊓ a_{≤n} = (a ⊔ b)′ ⊓ b_{≤n} and Inv_{α_{0},γ_{0}}((a ⊔ b) ⊓ a_{≤n}) = Inv_{α_{0},γ_{0}}((a ⊔ b) ⊓ b_{≤n}). We have to show that a_{≤n} ∼ b_{≤n}. We will obtain b_{≤n} from a_{≤n} in a series of modifications of a_{≤n} below a, b or c. We consider 5 cases.

Case 1. There is m < ω such that (B|a)^{(m)} and (B|b)^{(m)} are both non-trivial and atomless.

Note that the elementary invariant of each of the Boolean algebras B|a, B|b, B|c, B|a ⊔ b, B|a ⊓ c and B|b ⊓ c is equal to ⟨m + 1, 1, 0⟩. Our assumptions guarantee that α_{0} ≥ m + 1, so the restricted ⟨α_{0}, γ_{0}⟩-elementary invariant of each of the listed Boolean algebras is also equal to ⟨m + 1, 1, 0⟩.

There is η_{0} ∈ {+, −}^{n+1} such that a_{≤n}^{η_{0}} is large in a ⊔ b. Then also b_{≤n}^{η_{0}} is large in a ⊔ b. By (a), without loss of generality we can assume that for every η ∈ {+, −}^{n+1}, either a ⊓ a_{≤n}^{η} = 0_{B} or a_{≤n}^{η} is large in a. There is a_{≤n}^{1}, a modification of a_{≤n} below a or below b such that (a_{≤n}^{1})^{η_{0}} is large in c. If for example a_{≤n}^{η_{0}} is large in a and not large in c, then there is an η_{1} ∈ {+, −}^{n+1} \ {η_{0}} such that a_{≤n}^{η_{1}} is large in a ⊓ c, and the tuple a_{≤n}^{1} may be defined by the following conditions: a′ ⊓ a_{≤n}^{1} = a′ ⊓ a_{≤n}, a ⊓ (a_{≤n}^{1})^{η_{0}} = a ⊓ a_{≤n}^{η_{1}}, a ⊓ (a_{≤n}^{1})^{η_{1}} = a ⊓ a_{≤n}^{η_{0}} and a ⊓ (a_{≤n}^{1})^{η} = a ⊓ a_{≤n}^{η} for η ∉ {η_{0}, η_{1}}.

In this situation, using the fact that the Boolean algebras (B|a)^{(m)} and (B|b)^{(m)} are atomless, we easily obtain tuples a_{≤n}^{2}, a_{≤n}^{3}, a_{≤n}^{4} ⊆ B such that

• a_{≤n}^{2} is a modification of a_{≤n}^{1} below c, (a_{≤n}^{2})^{η_{0}} is large both in a ⊓ c and b ⊓ c, and for every η ∈ {+, −}^{n+1}, either a ⊓ (a_{≤n}^{2})^{η} = 0_{B} or (a_{≤n}^{2})^{η} is large in a.

• a_{≤n}^{3} is a modification of a_{≤n}^{2} below a, a ⊓ c′ < (a_{≤n}^{3})^{η_{0}} and (a_{≤n}^{3})^{η_{0}} is large in a ⊓ c.

• a_{≤n}^{4} is a modification of a_{≤n}^{3} below c, a < (a_{≤n}^{4})^{η_{0}} and (a_{≤n}^{4})^{η_{0}} is large in b ⊓ c (so in b).

The tuples a_{≤n} and a_{≤n}^{4} are ∼-equivalent. Similarly we can find b_{≤n}^{1} ∼ b_{≤n} such that (b_{≤n}^{1})^{η_{0}} is large in b and (b_{≤n}^{1})^{η_{0}} > a. Now, b_{≤n}^{1} is clearly a modification of a_{≤n}^{4} below b, so a_{≤n} ∼ b_{≤n}.

Case 2. There is m < ω such that (B|a)^{(m)}, (B|b)^{(m)} are both finite, non-trivial and atomic.

Note that Inv(B|a) = ⟨m + 1, 0, k⟩ and Inv(B|b) = ⟨m + 1, 0, l⟩ for some k, l ∈ ℕ_{+}. Our assumptions guarantee that α_{0} ≥ m + 1 and γ_{0} ≥ k + l. There is a tuple c_{<k+l} ⊆ (0_{B}, a ⊔ b] of pairwise disjoint elements such that

• Inv(B|c_{i}) = ⟨m + 1, 0, 1⟩ for every i < k + l,

• (∀i < k + l)(∃η_{0}, η_{1} ∈ {+, −}^{n+1})(c_{i} ≤ a_{≤n}^{η_{0}} ⊓ b_{≤n}^{η_{1}}), and

• (∀i < k + l − 1)(c_{i} ⊔ c_{i+1} ≤ a or c_{i} ⊔ c_{i+1} ≤ b or c_{i} ⊔ c_{i+1} ≤ c).

Then (c_{0} ⊔ … ⊔ c_{k+l−1})′ is not large in a ⊔ b and there is a unique permutation σ of the set {0, …, k + l − 1} such that for any i < k + l and η ∈ {+, −}^{n+1},

c_{i} ≤ a_{≤n}^{η} iff c_{σ(i)} ≤ b_{≤n}^{η}.

σ = τ_{1}∘…∘τ_{s}, where τ_{1}, …, τ_{s} are transpositions of the form (i, i+1), i < k+l−1. Let a_{≤n}^{0} = a_{≤n} and let a_{≤n}^{r} for 1 ≤ r ≤ s be the tuple defined by the following conditions:

• (c_{0} ⊔ … ⊔ c_{k+l−1})′ ⊓ a_{≤n}^{r} = (c_{0} ⊔ … ⊔ c_{k+l−1})′ ⊓ a_{≤n} and

• for any i < k + l and η ∈ {+, −}^{n+1}, c_{i} ≤ a_{≤n}^{η} iff c_{(τ_{s−r+1}∘...∘τ_{s})(i)} ≤ (a_{≤n}^{r})^{η}. Our choice of c_{<k+l} guarantees that for every r < s, a_{≤n}^{r+1} is a modification of a_{≤n}^{r} below a, b or c. Thus a_{≤n} ∼ a_{≤n}^{s} and for every η ∈ {+, −}^{n+1}, (a_{≤n}^{s})^{η} + b_{≤n}^{η} is not large in a ⊔ b. By (a) we can find a_{≤n}^{s+1} ∼ a_{≤n}^{s} and b_{≤n}^{1} ∼ b_{≤n} such that for every η ∈ {+, −}^{n+1},

• a ⊓ (a_{≤n}^{s+1})^{η} = 0_{B} or (a_{≤n}^{s+1})^{η} is large in a, and

• a ⊓ (b_{≤n}^{s+1})^{η} = 0_{B} or (b_{≤n}^{1})^{η} is large in a. b_{≤n}^{1} is a modification of a_{≤n}^{s+1} below b. Therefore a_{≤n} ∼ b_{≤n}.

Case 3. There is m < ω such that (B|a)^{(m)}, (B|b)^{(m)} are both non-trivial and atomic, and (B|a ⊔ b)^{(m)} is infinite.

Without loss of generality we can assume that (B|b)^{(m)} is infinite. Note that

Inv(B|a) = ⟨m + 1, 0, k⟩ and Inv(B|b) = ⟨m + 1, 0, ω⟩,

where k is a positive integer or ω. Our assumptions guarantee that α_{0} ≥ m + 1 and if k < ω, then γ_{0} ≥ k. There is η_{0} ∈ {+, −}^{n+1} such that the Boolean algebra (B|b ⊓ b_{≤n}^{η_{0}})^{(m)} is infinite. Then

Inv(B|b ⊓ b_{≤n}^{η_{0}}) = Inv(B|(a ⊔ b) ⊓ b_{≤n}^{η_{0}}) = ⟨m + 1, 0, ω⟩ and

Inv_{α_{0},γ_{0}}(B|b ⊓ b_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|(a ⊔ b) ⊓ b_{≤n}^{η_{0}}) = ⟨m + 1, 0, γ_{0}⟩.

If Inv_{α_{0},γ_{0}}(B|b⊓a_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|b⊓b_{≤n}^{η_{0}}), then there is a_{≤n}^{5}, a modification of a_{≤n} below b such that the Boolean algebra B|b ⊓ (a_{≤n}^{5})^{η_{0}} is infinite. If Inv_{α_{0},γ_{0}}(B|b ⊓ a_{≤n}^{η_{0}}) ≠ Inv_{α_{0},γ_{0}}(B|b ⊓ b_{≤n}^{η_{0}}), then a_{≤n}^{η_{0}} is large in a. There is a_{≤n}^{1} ⊆ B, a modification of a_{≤n} below a such that (a_{≤n}^{1})^{η_{0}} is large in a ⊓ c. Similarly, there are tuples a_{≤n}^{2}, a_{≤n}^{3} ⊆ B such that

• a_{≤n}^{2} is a modification of a_{≤n}^{1} below b,

• ((a_{≤n}^{2})^{η_{0}})′ is large in b ⊓ c

• a_{≤n}^{3} is a modification of a_{≤n}^{2} below c,

• |At((B|b ⊓ (a_{≤n}^{3})^{η_{0}})^{(m)})| = |At((B|b ⊓ (a_{≤n}^{2})^{η_{0}})^{(m)})| + 1.

Repeating this procedure, after ≤ γ_{0} steps we can obtain a_{≤n}^{4} ∼ a_{≤n}^{3} such that

Inv_{α_{0},γ_{0}}(B|b ⊓ (a_{≤n}^{4})^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|b ⊓ b_{≤n}^{η_{0}}).

There is a_{≤n}^{5}, a modification of a_{≤n}^{4} below b such that the Boolean algebra (B|b ⊓ (a_{≤n}^{5})^{η_{0}})^{(m)} is infinite.

Now, we will show that there is a_{≤n}^{10} ∼ a_{≤n}^{5} such that the Boolean algebra (B|a⊓((a_{≤n}^{10})^{η_{0}})′)^{(m)} is finite. This is trivial in case At((B|a)^{(m)}) is finite. If Inv_{α_{0},γ_{0}}(B|a ⊓ (a_{≤n}^{5})^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|(a ⊔ b)⊓(a_{≤n}^{5})^{η_{0}}), then a_{≤n}^{10} is a result of a single modification of a_{≤n}^{5} below a. If (B|a)^{(m)} is infinite and Inv_{α_{0},γ_{0}}(B|a ⊓ (a_{≤n}^{5})^{η_{0}}) ≠ Inv_{α_{0},γ_{0}}(B|(a ⊔ b) ⊓ (a_{≤n}^{5})^{η_{0}}), then there are tuples a_{≤n}^{6}, a_{≤n}^{7}, a_{≤n}^{8} ⊆ B such that

• a_{≤n}^{6} is a modification of a_{≤n}^{5} below a and ((a_{≤n}^{6})^{η_{0}})′ is large in a ⊓ c,

• a_{≤n}^{7} is a modification of a_{≤n}^{6} below b and (a_{≤n}^{7})^{η_{0}} is large in b ⊓ c,

• a_{≤n}^{8} is a modification of a_{≤n}^{7} below c,

• |At((B|a ⊓ (a_{≤n}^{8})^{η_{0}})^{(m)})| = |At((B|a ⊓ (a_{≤n}^{7})^{η_{0}})^{(m)})| + 1, and

• At((B|b ⊓ (a_{≤n}^{8})^{η_{0}})^{(m)}) is infinite

Repeating this procedure, after ≤ γ_{0} steps we can find a_{≤n}^{9} ∼ a_{≤n}^{8} such that Inv_{α_{0},γ_{0}}(B|a ⊓ (a_{≤n}^{9})^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|(a⊔b)⊓(a_{≤n}^{9})^{η_{0}}) and the Boolean algebra (B|b⊓(a_{≤n}^{9})^{η_{0}})^{(m)} is infinite. Then there is a_{≤n}^{10}, a modification of a_{≤n}^{9} below a, such that the Boolean algebra (B|a ⊓ ((a_{≤n}^{10})^{η_{0}})′)^{(m)} is finite.

A similar argument yields a_{≤n}^{11} ∼ a_{≤n}^{10} such that ((a_{≤n}^{11})^{η_{0}})′ is not large in a. By (a) there is a_{≤n}^{12} ∼ a_{≤n}^{11} such that (a_{≤n}^{12})^{η_{0}} > a and (B|b ⊓ a_{≤n}^{12})^{(m)} is infinite.

Similarly we can find b_{≤n}^{1} ∼ b_{≤n} such that (b_{≤n}^{1})^{η_{0}} > a and (B|b ⊓ (b_{≤n}^{1})^{η_{0}})^{(m)} is infinite. It is easy to see that b_{≤n} is a modification of a_{≤n}^{12} below b. Thus a_{≤n} ∼ b_{≤n}.

Case 4. Inv(B|a) = Inv(B|b) = ⟨ω, 0, 0⟩.

Note that

Inv(B|a ⊔ b) = Inv(B|a ⊓ c) = Inv(B|b ⊓ c) = Inv(B|c) = ⟨ω, 0, 0⟩.

There is η_{0} ∈ {+, −}^{n+1} such that b_{≤n}^{η_{0}} is large in b. Then

Inv(B|b ⊓ b_{≤n}^{η_{0}}) = ⟨ω, 0, 0⟩ and Inv_{α_{0},γ_{0}}(B|b ⊓ b_{≤n}^{η_{0}}) = ⟨α_{0} + 1, 0, 0⟩.

If Inv_{α_{0},γ_{0}}(B|b ⊓ a_{≤n}^{η_{0}}) = ⟨α_{0} + 1, 0, 0⟩, then there is a_{≤n}^{2}, a modification of a_{≤n} below b such that (a_{≤n}^{2})^{η_{0}} is large in b. So assume that Inv_{α_{0},γ_{0}}(B|b⊓a_{≤n}^{η_{0}}) ≠ ⟨α_{0}+1, 0, 0⟩. Then Inv_{α_{0},γ_{0}}(B|a⊓a_{≤n}^{η_{0}}) = ⟨α_{0} + 1, 0, 0⟩, and there is a_{≤n}^{1}, a modification of a_{≤n} below a such that (a_{≤n}^{1})^{η_{0}} is large in a ⊓ c. Similarly, there is a_{≤n}^{2}, a modification of a_{≤n}^{1} below c such that (a_{≤n}^{2})^{η_{0}} is large in a ⊓ c and large in b ⊓ c.

Now, modifying a_{≤n}^{2} below a we obtain a_{≤n}^{3} such that (a_{≤n}^{3})^{η_{0}} is large in a ⊓ c and (a_{≤n}^{3})^{η_{0}} > a ⊓ c′. A modification of a_{≤n}^{3} below c gives a_{≤n}^{4} such that (a_{≤n}^{4})^{η_{0}} is large in b ⊓ c and (a_{≤n}^{4})^{η_{0}} > a.

In a similar manner one can find b_{≤n}^{1} ∼ b_{≤n} such that (b_{≤n}^{1})^{η_{0}} is large in b and (b_{≤n}^{1})^{η_{0}} > a. Note that b_{≤n}^{1} is a modification of a_{≤n}^{4} below b. Therefore a_{≤n} ∼ b_{≤n}.

Case 5. There is m < ω such that a ∈ I_{m+1}(B) \ I_{m}(B) and b ∉ I_{m+1}(B). Let Inv(B|b) = ⟨α, β, γ⟩. Our assumptions guarantee that

• α_{0} ≥ m + 1, α ≥ m + 2,

• exactly one of β, γ is equal 0,

• if α < ω, then α_{0} ≥ α,

• if (B|a)^{(m)} is finite, then γ_{0} ≥ |At((B|a)^{(m)})|,

• if α < ω and (B|b)^{(α−1)} is finite, then γ_{0} ≥ |At((B|b)^{(α−1)})|, and

• Inv(B|b) = Inv(B|a ⊔ b). There is η_{0} ∈ {+, −}^{n+1} such that b_{≤n}^{η_{0}} is large in b. Then a ⊓ b_{≤n}^{η_{0}} is not large in (a ⊔ b) ⊓ b_{≤n}^{η_{0}} and

Inv_{α_{0},γ_{0}}(B|b ⊓ b_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|(a ⊔ b) ⊓ b_{≤n}^{η_{0}}).

Since Inv_{α_{0},γ_{0}}(B|(a⊔b)⊓a_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|(a⊔b)⊓b_{≤n}^{η_{0}}), (a⊔b)⊓a_{≤n}^{η_{0}} ∉ I_{m+1}(B) and a⊓a_{≤n}^{η_{0}} is not large in (a⊔b)⊓a_{≤n}^{η_{0}}. Hence Inv_{α_{0},γ_{0}}(B|b⊓a_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|(a⊔b)⊓a_{≤n}^{η_{0}}) and Inv_{α_{0},γ_{0}}(B|b⊓a_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|b⊓b_{≤n}^{η_{0}}). There is a_{≤n}^{1}, a modification of a_{≤n} below b, such that b⊓c⊓(a_{≤n}^{1})^{η_{0}} ∉ I_{m+1}(B).

Now, we are ready to show that there is c_{≤n} ∼ a_{≤n}^{1} such that c_{≤n}^{η_{0}} > a and Inv_{α_{0},γ_{0}}(B|b⊓c_{≤n}^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|b ⊓ (a_{≤n}^{1})^{η_{0}}). Obviously, if (a_{≤n}^{1})^{η_{0}} > a, then we can take c_{≤n} := a_{≤n}^{1}. If for every η_{1} ≠ η_{0}, (a_{≤n}^{1})^{η_{1}} is not large in a, then c_{≤n} exists by (a). So assume that there is η_{1} ≠ η_{0} such that (a_{≤n}^{1})^{η_{1}} is large in a. Let a_{≤n}^{2} be a modification of a_{≤n}^{1} below a such that (a_{≤n}^{2})^{η_{1}} is large in a ⊓ c.

Case 5a: (B|a)^{(m)} is atomless. By (a) without loss of generality we can assume that

Inv(B|a ⊓ (a_{≤n}^{2})^{η}) = Inv(B|a) = Inv(B|a ⊓ c) = ⟨m + 1, 1, 0⟩ for every η ∈ {+, −}^{n+1} with a ⊓ (a_{≤n}^{2})^{η} > 0_{B}.

Let d = a ⊓ c ⊓ (a_{≤n}^{2})^{η_{1}} and let e ∈ (0_{B}, b ⊓ c ⊓ (a_{≤n}^{2})^{η_{0}}) be an element such that Inv(B|e) = ⟨m + 1, 1, 0⟩. Define a_{≤n}^{3}, a modification of a_{≤n}^{2} below c by the following conditions:

• (d ⊔ e)′ ⊓ a_{≤n}^{3} = (d ⊔ e)′ ⊓ a_{≤n}^{2},

• (d ⊔ e) ⊓ (a_{≤n}^{3})^{η_{0}} = d, and

• (d ⊔ e) ⊓ (a_{≤n}^{3})^{η_{1}} = e.

There is a_{≤n}^{4}, a modification of a_{≤n}^{3} below a such that (a_{≤n}^{3})^{η_{0}} > a ⊓ c′ and (a_{≤n}^{3})^{η_{0}} is large in a ⊓ c. Repeating our previous argument we find a_{≤n}^{5}, a modification of a_{≤n}^{4} below c such that (a_{≤n}^{5})^{η_{0}} > a and Inv_{α_{0},γ_{0}}(B|b ⊓ (a_{≤n}^{5})^{η_{0}}) = Inv_{α_{0},γ_{0}}(B|b ⊓ (a_{≤n}^{1})^{η_{0}}). So c_{≤n} := a_{≤n}^{5} satisfies our demands.

Case 5b: (B|a)^{(m)} is atomic.

Choose d ∈ (0_{B}, a ⊓ c ⊓ (a_{≤n}^{2})^{η_{1}}] and e ∈ (0_{B}, b ⊓ c ⊓ (a_{≤n}^{2})^{η_{0}}) such that Inv(B|d) = Inv(B|e) = ⟨m + 1, 0, 1⟩. Define a_{≤n}^{3}, a modification of a_{≤n}^{2} below c by the following conditions:

• (d ⊔ e)′ ⊓ a_{≤n}^{3} = (d ⊔ e)′ ⊓ a_{≤n}^{2},

• (d ⊔ e) ⊓ (a_{≤n}^{3})^{η_{0}} = d, and

• (d ⊔ e) ⊓ (a_{≤n}^{3})^{η_{1}} = e.

If (B|a)^{(m)} is finite, then, repeating this procedure, one can find a_{≤n}^{4} ∼ a_{≤n}^{3} such that ((a_{≤n}^{4})^{η_{0}})′ is not large in a. Then, by (a) there is c_{≤n} satisfying our demands.

If (B|a)^{(m)} is infinite, then again, repeating the procedure, one can find a_{≤n}^{4} ∼ a_{≤n}^{3} such that (B|a ⊓ (a_{≤n}^{4})^{η_{0}})^{(m)} has at least γ_{0} atoms. There is a_{≤n}^{5}, a modification of a_{≤n}^{4} below a such that the Boolean algebra (B|a ⊓ ((a_{≤n}^{4})^{η_{0}})′)^{(m)} is finite. As previously, there are: a_{≤n}^{6} ∼ a_{≤n}^{5} such that ((a_{≤n}^{6})^{η_{0}})′ is not large in a, and (by (a)) there is c_{≤n} ∼ a_{≤n}^{6} satisfying our demands.

By arguments similar to those applied above, we can find b_{≤n}^{1} ∼ b_{≤n} such that (b_{≤n}^{1})^{η_{0}} is large in b and (b_{≤n}^{1})^{η_{0}} > a. It is clear that b_{≤n}^{1} is a modification of a_{≤n}^{6} below b. So b_{≤n} ∼ a_{≤n}.

3 The main theorem

In [We3], given an infinite Boolean algebra B with |B/I(B)| ≤ 2 and a consistent formula φ(\overline{x}, \overline{a}) ∈ L_{BA}(B), we demonstrated how to find a formula ψ(\overline{x}, z_{≤m}) ∈ L_{BA} for which \{d_{≤m} : φ(B, \overline{a}) = ψ(B, d_{≤m})} is a non-empty and finite subset of Π_{m}(1_{B}). In the proofs of Lemmas 2.3, 3.3, 4.3 and 4.5 in [We3], we obtained the mentioned result for Boolean algebras with elementary invariants ⟨1, 1, n⟩ (n < ω), ⟨1, 0, ω⟩, ⟨1, 1, ω⟩ and ⟨2, 0, 1⟩ respectively. In this section we generalize our caseby-case analysis to arbitrary Boolean algebras. The following lemmas will be used in the proof of the main theorem.

Lemma 3.1 Assume that B is a non-trivial Boolean algebra and d_{≤m}, e_{≤m} are partitions of 1_{B}. Then the following conditions are equivalent.

(a) There is a unique permutation σ of the set {0, …, m} such that

(∀i ≤ m)(∀d ∈ d_{≤m}e_{≤m})(d_{σ(i)} + e_{i} is not large in d).

(b) (a) without uniqueness of σ.

(c) For every i ≤ m, e_{i} is large in at most one element from d_{≤m} and d_{i} is large in at most one element from e_{≤m}.

Proof. For m = 0 the lemma holds trivially, so assume that m ≥ 1 and suppose that the lemma holds in all Boolean algebras for tuples of length m.

(b)⟹(c). Suppose for a contradiction that there are i, j, l ≤ m, j ≠ l such that e_{i} is large both in d_{j} and in d_{l}. Let σ be a permutation of the set {0, …, m}. If σ(i) = j, then d_{σ(i)} + e_{i} = d_{j} + e_{i} ≥ d_{l} ⊓ e_{i}, so d_{σ(i)} + e_{i} is large in d_{l}. Similarly, if σ(i) = l, then d_{σ(i)} + e_{i} is large in d_{j}. If σ(i) ∉ {j, l}, then d_{σ(i)} + e_{i} ≥ (d_{j} ⊔ d_{l}) ⊓ e_{i} and d_{σ(i)} + e_{i} is large both in d_{j} and d_{l}.

(c)⟹(a) Fix a Boolean algebra B and d_{≤m}, e_{≤m} ⊆ B, partitions of 1_{B} for which (c) holds. Choose i_{0} ≤ m such that e_{i_{0}} is large in 1_{B}. There is a unique j_{0} ≤ m such that d_{j_{0}} is large in e_{i_{0}}. Then e_{i_{0}} is the only element of the partition e_{≤m} which is large in d_{j_{0}}. Thus d_{j_{0}} +e_{i_{0}} is not large in d_{j_{0}} nor in e_{i_{0}}. (c) guarantees that d_{j_{0}} is not large in e_{i} for i ≠ i_{0}. Note that (d_{j_{0}} +e_{i_{0}})⊓e_{i} = d_{j_{0}} ⊓e_{i} for i ≠ i_{0}. Consequently, d_{j_{0}} + e_{i_{0}} is not large in e_{i} for i ≠ i_{0}. Similarly we prove that d_{j_{0}} + e_{i_{0}} is not large in d_{j} for j ≠ j_{0}. In this way have shown that if d ∈ d_{≤m}e_{≤m}, then d_{j_{0}} + e_{i_{0}} is not large in d.

Now, for i, j ≤ m, i ≠ i_{0}, j ≠ j_{0} we define:

d_{j}^{1} = (d_{j_{0}} ⊔ e_{i_{0}})′ ⊓ d_{j} and e_{i}^{1} = (d_{j_{0}} ⊔ e_{i_{0}})′ ⊓ e_{i}.

The tuples \overline{d} := ⟨d_{i}^{1} : i ≤ m, i ≠ i_{0}⟩ and \overline{e} := ⟨e_{j}^{1} : j ≤ m, j ≠ j_{0}⟩ are partitions of (d_{j_{0}} ⊔ e_{i_{0}})′. If i ≠ i_{0} and j ≠ j_{0}, then

d_{j}^{1} ⊓ e_{i}^{1} = (d_{j_{0}} ⊔ e_{i_{0}})′ ⊓ d_{j} ⊓ e_{i} = d_{j} ⊓ e_{i}.

So for any i, j ≤ m, i ≠ i_{0}, j ≠ j_{0},

d_{j}^{1} is large in e_{i}^{1} iff d_{j} is large in e_{i},

and similarly

e_{i}^{1} is large in d_{j}^{1} iff e_{i} is large in d_{j}.

This implies that

• for every i ≤ m, i ≠ i_{0}, e_{i}^{1} is large in at most one element from ⟨d_{j}^{1} : j ≤ m, j ≠ j_{0}⟩, and

• for every j ≤ m, j ≠ j_{0}, d_{j}^{1} is large in at most one element from ⟨e_{i}^{1} : i ≤ m, i ≠ i_{0}⟩.

Therefore, by the inductive hypothesis applied to the Boolean algebra B|(d_{j_{0}} ⊔ e_{i_{0}})′, there is a bijection

τ : {i ≤ m : i ≠ i_{0}} ⟶ {j ≤ m : j ≠ j_{0}}

such that d_{τ(i)}^{1} + e_{i}^{1} is not large in c whenever i ≤ m, i ≠ i_{0} and c ∈ \overline{d}\overline{e}.

We know that if i ≤ m and i ≠ i_{0}, then none of the elements d_{j_{0}}, d_{τ(i)}^{1} + e_{i}^{1} is large in e_{i}, in which case

(d_{τ(i)} + e_{i}) ⊓ e_{i} = ((d_{τ(i)}^{1} + e_{i}^{1}) ⊓ e_{i}) ⊔ (d_{j_{0}} ⊓ e_{i}).

So d_{τ(i)} + e_{i} is not large in e_{i}.

We also know that d′_{j_{0}} is not large in e_{i_{0}}. Moreover, if i ≤ m and i ≠ i_{0}, then

(d_{τ(i)} + e_{i}) ⊓ e_{i_{0}} = d_{τ(i)} ⊓ e_{i_{0}} ≤ d′_{j_{0}} ⊓ e_{i_{0}}.

Hence, d_{τ(i)} + e_{i} is not large in e_{i_{0}}.

If i, l are distinct numbers from {0, …, m} \ {i_{0}}, then

(d_{τ(i)} + e_{i}) ⊓ e_{l} = (d_{τ(i)}^{1} + e_{i}^{1}) ⊓ e_{l}.

But d_{τ(i)}^{1} + e_{i}^{1} is not large in e_{l}, so d_{τ(i)} + e_{i} is not large in e_{l}.

In this way we have shown that d_{τ(i)} + e_{i} is not large in e_{l} whenever i, l ≤ m and i ≠ i_{0}. Similarly one can prove that d_{τ(i)} + e_{i} is not large in d_{j} for i, j ≤ m and j ≠ j_{0}. Let σ be a permutation of the set {0, …, m} defined by the conditions:

σ(i_{0}) = j_{0} and σ(i) = τ(i) for i ∈ {0, …, m} \ {i_{0}}.

Our above arguments combined together show that d_{σ(i)} + e_{i} is not large in d whenever i ≤ m and d ∈ d_{≤m}e_{≤m}. For the uniqueness of σ, observe that if j ≠ σ(i), then e_{i} is not large in d_{j}, and d_{j} + e_{i} is large in d_{j}. This finishes the proof.

Lemma 3.2 Assume that B is a Boolean algebra and d_{≤m}, e_{≤m} ⊆ B are partitions of 1_{B} such that at least one of the following conditions (a), (b) holds.

(a) There are i, j, l ≤ m, j ≠ l such that e_{i} is large both in d_{j} and d_{l}.

(b) There are i, j, l ≤ m, j ≠ l such that d_{i} is large both in e_{j} and e_{l}.

Then at least one of the following conditions (a’), (b’) holds.

(a’) There are i′, j′, l′ ≤ m, j′ ≠ l′ such that e_{i′} is large both in d_{j′} and d_{l′}, and d_{j′} ⊔ d_{l′} is large in e_{i′}.

(b’) There are i′, j′, l′ ≤ m, j′ ≠ l′ such that d_{i′} is large both in e_{j′} and e_{l′}, and e_{j′} ⊔ e_{l′} is large in d_{i′}.

Proof. Suppose for example that (a) holds and let i_{0} = i. If d_{j} ⊔ d_{l} is not large in e_{i_{0}}, then there is j_{0} ≤ m, j_{0} ≠ j, l such that d_{j_{0}} is large in e_{i_{0}}. If e_{i_{0}} is large in d_{j_{0}}, then (a’) holds for i′ := i_{0}, j′ := j and l′ := j_{0}. Otherwise, there is i_{1} ≤ m, i_{1} ≠ i_{0} such that e_{i_{1}} is large in d_{j_{0}}. If d_{j_{0}} is large in e_{i_{1}}, then (b’) holds for i′ := j_{0}, j′ := i_{0} and i′ := i_{1}. Continuing this construction, after finitely many steps we obtain i′, j′, l′ ≤ m for which (a’) or (b’) holds.

Theorem 3.3 Assume that B is an infinite Boolean algebra, φ(\overline{x}, \overline{y}) ∈ L_{BA}, \overline{x} = x_{≤n}, \overline{y} = y_{≤r}, \overline{a} = a_{≤r} ⊆ B and φ(B, \overline{a}) ≠ ∅. There is an L_{BA}-formula ψ(\overline{x}, z_{≤m}) such that

• \{d_{≤m} ∈ B^{m+1} : φ(B, \overline{a}) = ψ(B, d_{≤m})\} is a non-empty subset of Π_{m}(1_{B}), and

• for any d_{≤m}, e_{≤m} ⊆ B, if ψ(B, d_{≤m}) = ψ(B, e_{≤m}) = φ(B, \overline{a}), then d_{≤m}, e_{≤m} ∈ Π_{m}(1_{B}) and there is a unique permutation σ of the set {0, …, m} such that for any l ≤ m and d ∈ d_{≤m}e_{≤m}, the element d_{σ(l)} + e_{l} is not large in d.

Proof. Suppose that B, φ(\overline{x}, \overline{y}) and \overline{a} = a_{≤r} satisfy our assumptions. Without loss of generality we can assume that a_{≤r} is a partition of 1_{B} whose all elements are simple. By Lemma 0.2, we can also assume that φ(\overline{x}, \overline{a}) is a finite Boolean combination of formulas of the form

ε_{j}(a_{i} ⊓ x_{≤n}^{η}), ψ_{j,s}(a_{i} ⊓ x_{≤n}^{η}) and at_{j}(a_{i} ⊓ x_{≤n}^{η}),

where i ≤ r, η ∈ {+, −}^{n+1}, j < ω and 1 ≤ s < ω. For every i ≤ r, denote by ⟨α^{i}, β^{i}, γ^{i}⟩ the elementary invariant of the Boolean algebra B|a_{i}. Fix positive integers α_{0} and γ_{0} so that the following conditions are satisfied.

• If j > α_{0}, then the formulas ε_{j}, at_{j} do not occur in φ(\overline{x}, \overline{a}).

• If j > α_{0} or s > γ_{0}, then ψ_{j,s} does not occur in φ(\overline{x}, \overline{a}).

• For every i ≤ r, if α^{i} < ω, then α_{0} ≥ α^{i} and γ_{0} ≥ ∑_{{s:α^{s}=α^{i},γ^{s}<ω}} γ^{i}.

Define the following formula:

θ(z, \overline{y}) = ∀u_{≤n}∀v_{≤n} [E_{n,α_{0},γ_{0}}(u_{≤n}, v_{≤n}, z) ⟶ (φ(u_{≤n}, \overline{y}) ⟷ φ(v_{≤n}, \overline{y}))] .

Of course, by our choice of α_{0} and γ_{0}, B ⊧ θ(a_{i}, \overline{a}) for every i ≤ r. Fix c_{≤m}, a partition of 1_{B}, satisfying the following conditions:

• if i ≤ r, then a_{i} ≤ c_{l} for some l ≤ m,

• B ⊧ θ(c_{l}, \overline{a}) for every l,

• for every l ≤ m, c_{l} is simple,

• if l_{1} < l_{2} ≤ m and B ⊧ θ(c_{l_{1}} ⊔ c_{l_{2}}, \overline{a}), then c_{l_{1}} ⊔ c_{l_{2}} is not simple.

For every tuple \overline{d} ∈ B^{n+1} we define a function

f\overline{d} : \{+, −\}^{n+1} × \{0, …, m\} ⟶ INV_{α_{0},γ_{0}}

as follows:

f\overline{d}(η, l) = Inv_{α_{0},γ_{0}}(B|a_{l} ⊓ d_{≤n}^{η}),

where η ∈ {+, −}^{n+1} and l ≤ m. Let

\{f_{0}, …, f_{t}\} = \{f\overline{d} : \overline{d} ∈ B^{n+1} and B ⊧ φ(\overline{d}, \overline{a})\},

and for every i ≤ t define the following L_{BA}-formula:

ϱ^{i}(x_{≤n}, z_{≤m}) = ⋀_{η∈{+,−}^{n+1}} ⋀_{l≤m} σ_{f_{i}(η,l)}^{α_{0},γ_{0}}(z_{l} ⊓ x_{≤n}^{η}).

It is easy to see that

B ⊧ ϱ^{i}(\overline{d}, c_{≤m}) iff f\overline{d} = f_{i}

for every i ≤ t and \overline{d} ∈ B^{n+1}. Let

ϱ(x_{≤n}, z_{≤m}) = ⋁_{i≤t} ϱ^{i}(x_{≤m}, z_{≤m}).

Claim 1. ϱ(B, c_{≤m}) = φ(B, \overline{a}).

Proof of Claim 1. Fix a tuple \overline{d} = d_{≤n} ∈ B^{n+1} and suppose that B ⊧ φ(\overline{d}, \overline{a}). Then f\overline{d} = f_{i} for some i ≤ t. For every η ∈ {+, −}^{n+1}, l ≤ m and ⟨α, β, γ⟩ ∈ INV_{α_{0},γ_{0}} we have that

f_{i}(η, l) = f\overline{d}(η, l) = ⟨α, β, γ⟩ ⟺ B ⊧ σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(c_{l} ⊓ d_{≤m}^{η}).

This means that

B ⊧ σ_{f_{i}(η,l)}^{α_{0},γ_{0}}(c_{l} ⊓ d_{≤m}^{η})

for every η ∈ \{+, −\}^{n} and l ≤ m. Hence B ⊧ ϱ^{i}(\overline{d}, c_{≤m}) and B ⊧ ϱ(\overline{d}, c_{≤m}).

In this way we have shown that φ(B, \overline{a}) ⊆ ϱ(B, c_{≤m}). To prove the reverse inclusion, suppose that B ⊧ ϱ(\overline{d}, c_{≤m}). Then B ⊧ ϱ^{i}(d_{≤n}, c_{≤m}) for some i ≤ t, which means that f\overline{d} = f_{i}. Choose a tuple \overline{e} ∈ B^{n+1} such that f_{i} = f\overline{e} and B ⊧ φ(\overline{e}, \overline{a}). The equality f\overline{d} = f\overline{e} implies that

B ⊧ ⋀_{l≤m} ⋀_{η∈\{+,−\}^{n+1}} ⋀_{⟨α,β,γ⟩∈INV_{α_{0},γ_{0}}} (σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(c_{l} ⊓ \overline{d}^{η}) ⟷ σ_{⟨α,β,γ⟩}^{α_{0},γ_{0}}(c_{l} ⊓ \overline{e}^{η})) .

Define the tuples \overline{d}_{0}, …, \overline{d}_{m+1} by the following conditions:

• \overline{d}_{0} = \overline{d},

• c_{l} ⊓ \overline{d}_{l+1} = c_{l} ⊓ \overline{e} for every l ≤ m and

• c′_{l} ⊓ \overline{d}_{l+1} = c′_{l} ⊓ \overline{d}_{l} for every l ≤ m.

It is clear that \overline{d}_{m+1} = \overline{e} and B ⊧ E_{n,α_{0},γ_{0}}(\overline{d}_{l}, \overline{d}_{l+1}, c_{l}) for every l ≤ m. Hence B ⊧ φ(\overline{d}_{l}, \overline{a}) ⟷ φ(\overline{d}_{l+1}, \overline{a}) for l ≤ m. Since B ⊧ φ(\overline{d}_{m+1}, \overline{a}), we infer that B ⊧ φ(\overline{d}, \overline{a}), which finishes the proof of Claim 1.

Let

θ′(z, z_{≤m}) = ∀u_{≤n}∀v_{≤n} [E_{n,α_{0},γ_{0}}(u_{≤n}, v_{≤n}, z) ⟶ (ϱ(u_{≤n}, z_{≤m}) ⟷ ϱ(v_{≤n}, z_{≤m}))] .

It is evident from Claim 1 that θ′(B, c_{≤m}) = θ(B, \overline{a}). Put

ψ(\overline{x}, z_{≤m}) = ϱ(\overline{x}, z_{≤m}) ∧ z_{≤m} ∈ Π_{m}(1) ∧ ⋀_{l≤m} θ′(z_{l}, z_{≤m}) ∧

⋀_{{l_{1}<l_{2}≤m:c_{l_{1}} ⊔c_{l_{2}} is simple }} ¬θ′(z_{l_{1}} ⊔ z_{l_{2}}, z_{≤m}) ∧ ⋀_{l≤m} σ_{Inv_{α_{0},γ_{0}} (B|c_{l})}^{α_{0},γ_{0}}(z_{l}).

Obviously, ψ(B, c_{≤m}) = ϱ(B, c_{≤m}) = φ(B, \overline{a}). The definition of ψ(\overline{x}, z_{≤m}) assures that for every d_{≤m} ∈ B^{m+1}, if φ(B, \overline{a}) = ψ(B, d_{≤m}), then d_{≤m} ∈ Π_{m}(1_{B}).

Claim 2. If d_{≤m} ∈ B^{m+1} and φ(B, \overline{a}) = ψ(B, d_{≤m}), then each element of the tuple d_{≤m} is simple.

Proof of claim 2. The claim is obvious if Inv(B) ≠ ⟨ω, 0, 0⟩, because then α_{0} ≥ max(α^{0}, …, α^{m}) and Inv_{α_{0},γ_{0}}(c_{≤m}) = Inv_{α_{0},γ_{0}}(d_{≤m}). So assume that Inv(B) = ⟨ω, 0, 0⟩ and let

J = {i ≤ m : Inv(B|c_{i}) = ⟨ω, 0, 0⟩},
J′ = {i ≤ m : Inv(B|d_{i}) = ⟨ω, 0, 0⟩}.

Again, our assumptions guarantee that if j ∉ J, then α_{0} ≥ α^{j} and Inv_{α_{0},γ_{0}}(B|c_{j}) = Inv_{α_{0},γ_{0}}(B|d_{j}) whenever j ∉ J. This implies that if j ∉ J, then d_{j} is simple and Inv(B|d_{j}) ≠ ⟨ω, 0, 0⟩, so J′ ⊆ J. To finish the proof of the claim, we only have to show that J′ = J. This is clear if |J| = 1. Suppose that |J| ≥ 2 and J′ ⊊ J. Then there are i ∈ J′ and j, l ∈ J, j ≠ l such that d_{i} is large in c_{j} and in c_{l}. The element c_{j} ⊔ c_{l} is simple and B ⊧ ¬θ(c_{j} ⊔ c_{l}, \overline{a}). Define an equivalence relation ∼ on B^{n+1} as follows:

g_{≤n} ∼ h_{≤n} ⟺ B ⊧ φ(g_{≤n}, \overline{a}) ⟷ φ(h_{≤n}, \overline{a}).

Since B ⊧ θ(c_{j}, \overline{a}) ∧ θ(c_{l}, \overline{a}), ∼ contains E_{n,α_{0},γ_{0}}^{c_{j}} ∪ E_{n,α_{0},γ_{0}}^{c_{l}}. We know that ψ(B, d_{≤m}) = φ(B, \overline{a}), so θ′(B, d_{≤m}) = θ(B, \overline{a}). Since B ⊧ θ′(d_{i}, d_{≤m}), we have that B ⊧ θ(d_{i}, \overline{a}), and ∼ contains E_{n,α_{0},γ_{0}}^{d_{i}}. Hence ∼ contains E_{n,α_{0},γ_{0}}^{d_{i}⊓(c_{j}⊔c_{l})}. By Lemma 2.8, ∼ contains E_{α_{0},γ_{0}}^{c_{j}⊔c_{l}}, which means that B ⊧ θ(c_{j} ⊔ c_{l}, \overline{a}), a contradiction.

Now assume that d_{≤m}, e_{≤m} ∈ B^{n+1} and φ(B, \overline{a}) = ψ(B, d_{≤m}) = ψ(B, e_{≤m}). Then the tuples d_{≤m}, e_{≤m} are partitions of 1_{B} into simple elements. By Lemma 3.1, we will be done if we prove the following claim.

Claim 3. There is a permutation σ of the set {0, …, m} such that for any i ≤ m and d ∈ d_{≤m}e_{≤m}, d_{σ(i)} + c_{i} is not large in d.

Proof of Claim 3. The claim is trivial for m = 0, so let m ≥ 1 and suppose for a contradiction that the claim does not hold for m. Then, by Lemma 3.1, there are i, j, l ≤ m, j ≠ l such that e_{i} is large in d_{j} and in d_{l}, or d_{i} is large in e_{j} and in e_{l}. By Lemma 3.2, without loss of generality we can assume that e_{i} is large in d_{j} and in d_{l}, and d_{j} ⊔ d_{l} is large in e_{i}. Since d_{j}, d_{l}, e_{i} are all simple, by Lemma 2.7, also d_{j} ⊔ d_{l} is simple. As in the proof of Claim 2 we have that

B ⊧ θ(d_{j}, \overline{a}) ∧ θ(d_{l}, \overline{a}) ∧ θ(e_{i} ⊓ (d_{j} ⊔ d_{l}), \overline{a}) ∧ ¬θ(d_{j} ⊔ d_{l}, \overline{a}).

Let ∼ be the equivalence relation on B^{n+1} defined as in the proof of Claim 2. The relation ∼ contains E_{n,α_{0},γ_{0}}^{d_{j}} ∪ E_{α_{0},γ_{0}}^{d_{l}} ∪ E_{α_{0},γ_{0}}^{(d_{j}⊔d_{l})⊓e_{i}}. By Theorem 2.8 for a := d_{j}, b := d_{l} and c := (d_{j} ⊔ d_{l}) ⊓ e_{i}, ∼ contains also E_{n,α_{0},γ_{0}}^{d_{j}⊔d_{l}}, which means that B ⊧ θ(d_{j} ⊔ d_{l}, \overline{a}), a contradiction.

This finishes the proof of the theorem.

Proposition 3.4 Assume that B is an infinite Boolean algebra and n ∈ ℕ_{+}. Then the following conditions are equivalent.

(a) |B/I_{n}(B)| ≤ 2.

(b) If r ∈ ℕ_{+} and X ⊆ B^{r} is a non-empty definable set, then there is an L_{BA}-formula ψ(\overline{x}, z_{≤m}) such that

• {d_{≤m} ∈ B^{m+1} : X = ψ(B, d_{≤m})} is a nonempty subset of Π_{m}(1_{B}), and

• for any d_{≤m}, e_{≤m} ∈ B^{m+1}, if X = ψ(B, d_{≤m}) = ψ(B, e_{≤m}), then there is a unique permutation σ of the set {0, …, m} such that d_{σ(i)} + e_{i} ∈ I_{n−1}(B) and d_{σ(i)} + e_{i} is not large in d whenever i ≤ m and d ∈ d_{≤m}e_{≤m}.

Proof. (a)⟹(b). Let B be an infinite Boolean algebra with |B/I_{n}(B)| ≤ 2, r ∈ ℕ_{+} and X ⊆ B^{r} a non-empty definable set. Fix an L_{BA}-formula ψ(\overline{x}, z_{≤m}) satisfying the assertion of Theorem 3.3 and partitions d_{≤m}, e_{≤m} of 1_{B} for which X = ψ(B, d_{≤m}) = ψ(B, e_{≤m}). Denote by σ the unique permutation of the set {0, …, m} such that for any i ≤ m and d ∈ d_{≤m}e_{≤m}, the element d_{σ(i)} + e_{i} is not large in d. Below we consider two cases.

Case 1. B = I_{n}(B). For any i, j ≤ m, (d_{σ(i)} + e_{i}) ⊓ d_{j} ∈ I_{n−1}(B). So d_{σ(i)} + e_{i} ∈ I_{n−1}(B). Case 2. |B/I_{n}(B)| = 2. In this case there are a unique i_{0} ≤ m such that e_{i_{0}} ∉ I_{n}(B), and a

unique j_{0} ≤ m such that d_{j_{0}} ∉ I_{n}(B). We claim that σ(i_{0}) = j_{0}. Suppose for a contradiction that this is not true. Then (d_{σ(i_{0})} + e_{i_{0}}) ⊓ d_{j_{0}} ∉ I_{n}(B), which means that d_{σ(i_{0})} + e_{i_{0}} is large in d_{j_{0}} contradicting Theorem 3.3. So σ(i_{0}) = j_{0}.

The element d_{j_{0}} + e_{i_{0}} is not large in e_{i} for i ≤ m. Thus, if i ≠ i_{0}, then (d_{j_{0}} + e_{i_{0}}) ⊓ e_{i} ∈ I_{n−1}(B). This implies that d_{j_{0}} ⊓ e′_{i_{0}} = (d_{j_{0}} + e_{i_{0}}) ⊓ e′_{i_{0}} ∈ I_{n−1}(B). A similar argument shows that d′_{j_{0}} ⊓ e_{i_{0}} ∈ I_{n−1}(B). Hence d_{j_{0}} + e_{i_{0}} ∈ I_{n−1}(B).

Now, let l ≤ m and l ≠ i_{0}. As previously, (d_{σ(l)} + e_{l}) ⊓ e_{i} ∈ I_{n−1}(B) for i ≠ i_{0}. Also

(d_{σ(l)} + e_{l}) ⊓ e_{i_{0}} = d′_{j_{0}} ⊓ d_{σ(l)} ⊓ e_{i_{0}} ≤ d′_{j_{0}} ⊓ e_{i_{0}} ∈ I_{n−1}(B).

Hence d_{σ(l)} + e_{l} ∈ I_{n−1}(B).

(b)⟹(a). Let B be a Boolean algebra with |B/I_{n}(B)| ≥ 4 and a ∈ B an element for which a + I_{n}(B) is not ∅-definable. We can assume that a satisfies the following additional conditions.

• In case B/I_{n}(B) is atomic, a + I_{n}(B) is an atom of B/I_{n}(B).

• In case B/I_{n}(B) is not atomic, a+I_{n}(B) is atomless as an element of B/I_{n}(B) and a′+I_{n}(B) is not atomic as an element of B/I_{n}(B).

Our choice of a guarantees that the elements 0_{B}, a, a′, 1_{B} belong to distinct cosets of I_{n}(B). In particular, a, a′ ∉ I_{n}(B). Consider the following {a}-definable set:

X = {c ∈ B : a + c ∈ I_{n}(B)} = {c ∈ B : B ⊧ ε_{n}(a + c)}.

Fix an L_{BA}-formula ψ(\overline{x}, z_{≤m}) such that \{e_{≤m} ∈ B^{m+1} : X = ψ(B, e_{≤m})\} is a nonempty subset of Π_{m}(1_{B}) and a partition d_{≤m} ∈ Π_{m}(1_{B}) for which X = ψ(B, d_{≤m}). Since X is not ∅-definable, m ≥ 1. We will show how to find a partition e_{≤m} ∈ Π_{m}(1_{B}) such that X = ψ(B, e_{≤m}) and for every permutation σ of the set {0, …, m}, there are i ≤ m and d ∈ d_{≤m}e_{≤m} such that d_{σ(i)} + e_{i} is large in d or d_{σ(i)} + e_{i} ∉ I_{n−1}(B). We consider three cases.

Case 1. There is i ≤ m such that d_{i} ⊓ a, d′_{i} ⊓ a ∉ I_{n}(B) or d_{i} ⊓ a′, d′_{i} ⊓ a′ ∉ I_{n}(B).

Assume for example that the first alternative holds. Fix i < j ≤ m such that d_{i} ⊓ a, d_{j} ⊓ a ∉ I_{n}(B). There is d ∈ (0_{B}, a ⊓ d_{i}) such that d ∈ I_{n}(B) \ I_{n−1}(B). Then

Inv(B|a ⊓ d_{i} ⊓ d′) = Inv(B|a ⊓ d_{i}) and Inv(B|a ⊓ (d_{j} ⊔ d)) = Inv(B|a ⊓ d_{j}).

Define e_{i} = d′_{i} ⊓ d′, e_{j} = d_{j} ⊔ d and e_{l} = d_{l} for l ∉ {i, j}. The tuple e_{≤m} is a partition of 1_{B} and tp(e_{≤m}/a) = tp(d_{≤m}/a). Consequently, X = ψ(B, e_{≤m}). Let σ be a permutation of the set {0, … m}. If σ(i) = i, then

d_{σ(i)} + e_{i} = d_{i} + (d_{i} ⊓ d′) = d ∉ I_{n−1}(B).

If σ(i) = j, then

d_{σ(i)} + e_{i} = d_{j} + (d_{i} ⊓ d′) > d_{j}, so d_{σ(i)} + e_{i} ∉ I_{n−1}(B).

Finally, if σ(i) ∉ {i, j}, then

d_{σ(i)} + e_{i} = d_{l} + e_{i} > e_{i}, so d_{σ(i)} + e_{i} ∉ I_{n−1}(B).

Case 2. There is i ≤ m such that d′_{i} ∈ I_{n}(B).

Fix j ≤ m, j ≠ i. Let c = a ⊔ d_{j}. Then a + c = d_{j} ⊓ a′ ∈ I_{n}(B) and the formula ε_{n}(c + x) defines X. There is d ∈ (0_{B}, (a ⊓ d_{i}) ⊔ d_{j}) such that Inv(B|d) = Inv(B|d_{j}) and the elements d ⊓ d′_{j} and d′ ⊓ d_{j} are both large in d ⊔ d_{j}. Define: e_{i} = (d_{i} ⊔ d_{j}) ⊓ d′, e_{j} = d and e_{l} = d_{l} for l ∉ {i, j}. The tuple e_{≤m} is a partition of 1_{B} and tp(cd_{≤m}) = tp(ce_{≤m}). Consequently, X = ψ(B, e_{≤m}). Let σ be a permutation of the set {0, …, m}. If σ(j) = j, then d_{σ(j)} + e_{j} = d_{j} + d > d′ ⊓ d_{j}, so d_{σ(j)} + e_{j} is large in d_{j}. If σ(j) = i, then d_{σ(j)} + e_{j} = d_{i} + d > d′ ⊓ d_{i}, so d_{σ(j)} + e_{j} is large in d_{i}. If σ(j) = l ∉ {i, j}, then d_{σ(j)} + e_{j} = d_{l} + d > d_{l}, so d_{σ(j)} + e_{j} is large in d_{l}.

Case 3. There are i < j ≤ m such that d_{i} + a ∈ I_{n}(B) and d_{j} + a′ ∈ I_{n}(B).

There is d ∈ (0_{B}, a⊓d_{i}) such that d ∈ I_{n}(B)\I_{n−1}(B). Define c = a⊓d′, e_{i} = d′ ⊓d_{i}, e_{j} = d_{j} ⊔d and e_{l} = d_{l} for l ∉ {i, j}. Then e_{≤m} is a partition of 1_{B} and tp(ad_{≤m}) = tp(ce_{≤m}). Consequently, the set defined by the formula ε_{n}(c + x) is equal to ψ(B, e_{≤m}). Since a + c ∈ I_{n}(B), the formula ε_{n}(x + c) defines X and X = ψ(B, e_{≤m}). Proceeding as in Case 1, one can show that if σ is a permutation of the set {0, …, m} and l ≤ n, then d_{σ(l)} + e_{l} ∉ I_{n−1}(B).

Corollary 3.5 [We3, Theorem 4.8] Assume that B is an infinite Boolean algebra. Then the following conditions are equivalent.

(a) |B/I(B)| ≤ 2.

(b) If r ∈ ℕ_{+} and X ⊆ B^{r} is a non-empty definable set, then there is an L_{BA}-formula ψ(\overline{x}, z_{≤m}) such that

• {d_{≤m} ∈ B^{m+1} : X = ψ(B, d_{≤m})} is a nonempty subset of Π_{m}(1_{B}), and

• for any d_{≤m}, e_{≤m} ∈ B^{m+1}, if X = ψ(B, d_{≤m}) = ψ(B, e_{≤m}), d_{≤m} is a permutation of e_{≤m}.

Proposition 3.6 Assume that B is an infinite Boolean algebra with Inv(B) = ⟨ω, 0, 0⟩, r ∈ ℕ_{+} and X ⊆ B^{r} is a definable set. Then there are a positive integer α and an L_{BA}-formula ψ(\overline{x}, z_{≤m}) such that

• {d_{≤m} ∈ B^{m+1} : X = ψ(B, d_{≤m})} is a nonempty subset of Π_{m}(1_{B}), and

• for any d_{≤m}, e_{≤m} ∈ B^{m+1}, if X = ψ(B, d_{≤m}) = ψ(B, e_{≤m}), then there is a unique permutation σ of the set {0, …, m} such that for any i ≤ m and d ∈ d_{≤m}e_{≤m}, d_{σ(i)} + e_{i} is not large in d and d_{σ(i)} + e_{i} ∈ I_{α}(B).

Proof. Fix a nonempty set X ⊆ B^{r} defined by φ(\overline{x}, \overline{a}) ∈ L_{BA}(B). Let ψ(\overline{x}, z_{≤m}) be the formula obtained as in proof of Theorem 3.3. We claim that ψ(\overline{x}, z_{≤m}) satisfies the assertion of Proposition 3.6. Assume for a contradiction that for every positive integer α, there are partitions d_{≤m}^{α}, e_{≤m}^{α} ∈ Π_{m}(1_{B}) such that

• X = ψ(B, d_{≤m}^{α}) = ψ(B, e_{≤m}^{α}) and

• for every permutation σ of the set {0, …, m}, there are i ≤ m and d ∈ d_{≤m}^{α}e_{≤m}^{α} such that d_{σ(i)}^{α} + e_{i}^{α} ∉ I_{α}(B).

Then there are B_{1} ≻ B and partitions d_{≤m}, e_{≤m} ∈ Π_{m}(1_{B_{1}}) such that ψ(B_{1}, \overline{a}) = ψ(B_{1}, d_{≤m}) = ψ(B_{1}, e_{≤m}) and for every permutation σ of {0, … m}, there are i ≤ m and d ∈ d_{≤m}e_{≤m} such that Inv(B|d ⊓ (d_{σ(i)} + e_{i})) = ⟨ω, 0, 0⟩. The latter means that d_{σ(i)} + e_{i} is large in d, which contradicts Theorem 3.3.

4 Elimination of imaginaries

Assume that M is a multisorted structure for a multisorted language L and let n ∈ ℕ_{+}. For any finite collection M_{0}, …, M_{n} of sorts in M, any ∅-definable set X ⊆ M_{0} × … × M_{n} and any ∅-definable equivalence relation E on X, denote by S_{E} the set of all equivalence classes of E and by f_{E} the function from X onto S_{E} sending \overline{a} ∈ X to [\overline{a}]_{E}. In case E is the equality on a sort N from M, we identify N with N/E. The structure M together with all sorts S_{E} and functions f_{E} will be denoted by M^{eq}. If E is a family of ∅-definable equivalence relations on ∅-definable subsets of products of finite collections of sorts in M, then M(E) denotes the multisorted structure M together with all sorts S_{E} and functions f_{E}, where E ∈ E. The multisorted language of M(E) will be denoted by L(E).

We say that a multisorted structure M admits elimination of imaginaries iff for any finite collection M_{0}, …, M_{n} of sorts in M, any ∅-definable set X ⊆ M_{0} × … × M_{n} and any ∅-definable equivalence relation E on X, there is a ∅-definable function f from X into a product of some finite collection of sorts in M such that for any \overline{a}, \overline{b} ∈ X, M ⊧ E(\overline{a}, \overline{b}) iff f(\overline{a}) = f(\overline{b}). We say that a complete theory for a multisorted language admits elimination of imaginaries iff every model of T does. Clearly, for any multisorted structure M, if T h(M) admits elimination of imaginaries, then also M does.

Proposition 4.1 Assume that M is a multisorted L-structure and E is a family of ∅-definable equivalence relations on ∅-definable subsets of products of finite collections of sorts in M. Then the following conditions are equivalent.

(a) M(E) admits elimination of imaginaries.

(b) If M_{0}, …, M_{n} is a collection of sorts in M, X ⊆ M_{0} × … × M_{n} is a ∅-definable (in M) set and E is a ∅-definable (in M) equivalence relation on X, then there exist a collection of sorts N_{0}, …, N_{k} in M(E) and a ∅-definable (in M(E)) function f : X ⟶ N_{0} × … × N_{k} such that for any \overline{a}, \overline{b} ∈ X,

M ⊧ E(\overline{a}, \overline{b}) iff f(\overline{a}) = f(\overline{b}).

Proof. The implication from (a) to (b) is trivial. To prove that (b) implies (a), assume that E is a family of ∅-definable (in M) equivalence relations on ∅-definable (in M) subsets of products of finite collections of sorts in M. Fix a finite collection M_{0}, …, M_{n} of sorts in M(E), a ∅-definable (in M(E)) set X ⊆ M_{0} × … × M_{n} and a parameter-free formula E(x_{0}, …, x_{n}, y_{0}, …, y_{n}) ∈ L(E) defining an equivalence relation E on X. Then, for every i ≤ n, we can find a finite collection M_{i,0}, …, M_{i,l_{i}} of sorts in M, a ∅-definable (in M) set X_{i} ⊆ M_{i,0} × … × M_{i,l_{i}} and a ∅-definable (in M) equivalence relation E_{i} on X_{i} such that M_{i} = X_{i}/E_{i} = f_{E_{i}}[X_{i}], where f_{E_{i}}(\overline{x}) = [\overline{x}]_{E_{i}} whenever \overline{x} ∈ X_{i}. Let

Z = \{\overline{a}_{0} … \overline{a}_{n} ∈ X_{0} × … × X_{n} : ⟨f_{E_{0}}(\overline{a}_{0}), …, f_{E_{n}}(\overline{a}_{n})⟩ ∈ X\}.

Clearly, the set Z is ∅-definable in M. There is an L-formula ψ(\overline{u}_{0}, …, \overline{u}_{n}, \overline{v}_{0}, …, \overline{v}_{n}) such that for every i ≤ n, |\overline{u}_{i}| = |\overline{v}_{i}| = l_{i} + 1 and for any \overline{a}_{≤n}, \overline{b}_{≤n} ∈ Z,

M ⊧ ψ(\overline{a}_{≤n}, \overline{b}_{≤n}) iff M(E) ⊧ E(f_{E_{0}}(\overline{a}_{0}), …, f_{E_{n}}(\overline{a}_{n}), f_{E_{0}}(\overline{b}_{0}), …, f_{E_{n}}(\overline{b}_{n})).

The formula ψ(\overline{u}_{≤n}, \overline{v}_{≤n}) defines an equivalence relation F on Z. By (b) there is a collection N_{0}, …, N_{k} of sorts in M(E) and a ∅-definable (in M(E)) function

g : Z ⟶ N_{0} × … × N_{k}

such that for any \overline{a}, \overline{b} ∈ Z, M ⊧ ψ(\overline{a}, \overline{b}) iff g(\overline{a}) = g(\overline{b}).

Now, define a function f : X ⟶ N_{0} × … × N_{k} by the following condition: f(\overline{a}) = \overline{b} iff there is \overline{u}_{≤n} ∈ X_{0} × … × X_{n} such that \overline{a} = ⟨f_{E_{0}}(\overline{u}_{0}), …, f_{E_{n}}(\overline{u}_{n})⟩ and g(\overline{u}_{≤n}) = \overline{b}. Note that f is ∅-definable in M(E) and for any \overline{a}_{1}, \overline{a}_{2} ∈ X, f(\overline{a}_{1}) = f(\overline{a}_{2}) iff M(E) ⊧ E(\overline{a}_{1}, \overline{a}_{2}). This finishes the proof.

Assume that B is an infinite Boolean algebra. The proof of Theorem 3.3 provides us with an algorithm how, given an L_{BA}-formula φ(\overline{x}, \overline{y}) ∈ L_{BA} together with a tuple of parameters \overline{a} ∈ B^{|\overline{y}|}, to find a canonical L_{BA}-formula ψ_{φ,\overline{a}}(\overline{x}, \overline{z}) and a tuple of parameters \overline{c} ∈ B^{|\overline{z}|} such that φ(B, \overline{a}) = ψ(B, \overline{c}) and \overline{c} is a partition of 1_{B} determined up to almost a permutation (see the definition below).

Definition 4.2 Assume that B is an infinite Boolean algebra, m < ω and d_{≤m}, e_{≤m} are partitions of 1_{B}. We say that e_{≤m} is almost a permutation of d_{≤m} if there exists a unique permutation σ of the set {0, …, m} such that for any l ≤ m and any d ∈ d_{≤m}e_{≤m}, the element d_{σ(l)} + e_{l} is not large in d.

For every L_{BA}-formula ψ_{φ,\overline{a}}(\overline{x}, \overline{z}) obtained in the way described above, denote by E_{ψ_{φ,\overline{a}}} the ∅-definable equivalence relation on B^{|\overline{z}|} defined by the following condition.

The tuples d_{≤m}, e_{≤m} ∈ B^{m+1} are F_{ψ_{φ,\overline{a}}}-equivalent iff either d_{≤m}, e_{≤m} ∉ Π_{m}(1_{B}), or
d_{≤m}, e_{≤m} ∈ Π_{m}(1_{B}) and ψ_{φ,\overline{a}}(B, d_{≤m}) = ψ_{φ,\overline{a}}(B, e_{≤m}).

Let E_{B} be the family of all equivalence relations F_{ψ_{φ,\overline{a}}} on cartesian powers of B appearing as a result of the above procedure for all possible L_{BA}-formulas φ(\overline{x}, \overline{y}) and all tuples \overline{a} ∈ B^{|\overline{y}|}.

After these introductory definitions and remarks, we are in a position to state and prove our concluding result.

Theorem 4.3 Let B be an infinite Boolean algebra. The multisorted structure B(E_{B}), where E_{B} denotes the family of ∅-definable equivalence relations on cartesian powers of B defined above, admits elimination of imaginaries.

Proof. It is enough to show that B and B(E_{B}) satisfy condition (b) of Proposition 4.1.

Suppose that n ∈ ℕ_{+}, X ⊆ B^{n} is a ∅-definable set and E(\overline{x}, \overline{y}) is an L_{BA}-formula defining an equivalence relation E on X. By Theorem 3.3, Proposition 3.4 and Proposition 3.6, for every \overline{a} ∈ X, we can find an L_{BA}-formula ψ_{E,\overline{a}}(\overline{x}, z_{≤m(\overline{a})}) and such that

• \{d_{≤m(\overline{a})} ∈ B^{m(\overline{a})+1} : E(B, \overline{a}) = ψ_{E,\overline{a}}(B, d_{≤m(\overline{a})})\} is a non-empty subset of Π_{m(\overline{a})}(1_{B}), and

• for any d_{≤m(\overline{a})}, e_{≤m(\overline{a})} ∈ Π_{m(\overline{a})}(1_{B}), if φ(B, \overline{a}) = ψ_{E,\overline{a}}(B, d_{≤m(\overline{a})}) = ψ_{E,\overline{a}}(B, e_{≤m(\overline{a})}), then e_{≤m(\overline{a})} is almost a permutation of d_{≤m(\overline{a})}; moreover, if Inv(B) = ⟨α, 0, 1⟩, where 2 ≤ α < ω, then d_{σ(l)} + e_{l} ∈ I_{α−2}(B).

For every \overline{a} ∈ X, denote by X(\overline{a}) the set of all tuples \overline{b} ∈ X for which the following conditions hold.

• \{d_{≤m(\overline{a})} ∈ B^{m(\overline{a})+1} : E(B, \overline{b}) = ψ_{E,\overline{a}}(B, d_{≤m(\overline{a})})\} is a non-empty subset of Π_{m}(1_{B}), and

• for any d_{≤m(\overline{a})}, e_{≤m(\overline{a})} ∈ Π_{m(\overline{a})}(1_{B}), if E(B, \overline{b}) = ψ_{E,\overline{a}}(B, d_{≤m(\overline{a})}) = ψ_{E,\overline{a}}(B, e_{≤m(\overline{a})}), then e_{≤m(\overline{a})} is almost a permutation of d_{≤m(\overline{a})}.

For every \overline{a} ∈ X, X(\overline{a}) is a ∅-definable subset of X containing \overline{a}. Moreover, X(\overline{a}) is a union of some equivalence classes of E. For \overline{a} ∈ X, we consider the ∅-definable equivalence relation F_{ψ_{E,\overline{a}}} on B^{m(\overline{a})+1} defined before Theorem 4.3. Let f\overline{a} : X(\overline{a}) ⟶ B^{m(\overline{a})+1}/F_{ψ_{E,\overline{a}}} denote the function defined as follows:

f\overline{a}(\overline{b}) = \overline{c}/F_{ψ_{E,\overline{a}}} iff E(B, \overline{b}) = ψ_{E,\overline{a}}(B, \overline{c}).

Obviously, for any \overline{b}_{1}, \overline{b}_{2} ∈ X(\overline{a}),

f\overline{a}(\overline{b}_{1}) = f\overline{a}(\overline{b}_{2}) iff B ⊧ E(\overline{b}_{1}, \overline{b}_{2}).

Since the formula ψ_{E,\overline{a}}(\overline{x}, z_{≤m(\overline{a})}) constructed in the proof of Theorem 3.3 for the formula E and \overline{a} ∈ X depends only on E and Inv(\overline{a}), by an elementary compactness argument there are \overline{a}_{0}, …, \overline{a}_{k} ∈ X such that X = X(\overline{a}_{0}) ∪ … ∪ X(\overline{a}_{k}). Define a partition X_{0}, …, X_{k} of X as follows: X_{0} = X(\overline{a}_{0}) and X_{i} = X(\overline{a}_{i}) \ (X(\overline{a}_{0}) ∪ … ∪ X(\overline{a}_{i−1})) for 1 ≤ i ≤ k (without loss of generality the sets X_{0}, …, X_{k} are non-empty). Define a map

f : X ⟶ B^{m(\overline{a_{0}})+1}/F_{ψ_{E,\overline{a}_{0}}} × … × B^{m(\overline{a}_{k})+1}/E_{ψ_{E,\overline{a}_{k}}}

as follows: if \overline{b} ∈ X, then f(\overline{b}) = ⟨f_{0}(\overline{b}), …, f_{k}(\overline{b})⟩, where

f_{i}(\overline{b}) = \{ \begin{matrix}f_{\overline{a}_{i}}(\overline{b}) & if \overline{b} ∈ X_{i} \\ ⟨0, …, 0⟩/F_{ψ_{E,\overline{a}_{i}}} & otherwise \end{matrix}

for any i ≤ k. It is clear that f is ∅-definable in B(E_{B}) and for any \overline{b}_{1}, \overline{b}_{2} ∈ X,

B ⊧ E(\overline{b}_{1}, \overline{b}_{2}) iff f(\overline{b}_{1}) = f(\overline{b}_{2}).

In this way we have shown that B and E_{B} satisfy condition (b) of Proposition 4.1. Hence the multisorted L(E_{B})-structure B(E_{B}) admits elimination of imaginaries.

References

[ChK] C. C. Chang and H. J. Keisler, Model Theory (3rd ed.), North Holland, Amsterdam 1990.

[HBA] Handbook of Boolean algebras (J. D. Monk and R. Bonnet, editors), North Holland, Amsterdam 1989.

[HHM] D. Haskell, E. Hrushovski, D. Macpherson, Definable sets in algebraically closed valued fields. Part I: elimination of imaginaries, J. Reine Angew. Math. 597 (2006), 175-236.

[Me] T. Mellor, Imaginaries in real closed valued fields, PhD thesis, University of Leeds, Department of Pure Mathematics, 2002.

[NW] L. Newelski and R. Wencel, Definable sets in Boolean ordered o-minimal structures. I, J. Symb. Logic 66 (2001), 1821-1836.

[Pi] A. Pillay, Geometric Stability Theory, Oxford University Press, New York 1996.

[To] C. Toffalori, Lattice ordered o-minimal structures, Notre Dame J. Formal Logic 39 (1998), 447-463.

[We1] R. Wencel, Small theories of Boolean ordered o-minimal structures, J. Symb. Logic 67 (2002), 1385-1390.

[We2] R. Wencel, Definable sets in Boolean ordered o-minimal structures. II, J. Symb. Logic 68 (2003), 35-51.

[We3] R. Wencel, Weak elimination of imaginaries for Boolean algebras, Ann. Pure Appl. Logic 132 (2005), 247-270.

Mailing address: Instytut Matematyczny

Uniwersytetu Wrocławskiego

Pl. Grunwaldzki 2/4, 50-384 Wrocław Poland

E-mail:  rwenc@math.uni.wroc.pl