Undecidability of theories of Boolean algebras with selected ideals (Q1092889): Difference between revisions

Main result: Let (A,I) be a countable Boolean algebra with a selected ideal I. Then the theory of (A,I) is decidable iff A is superatomic. To prove necessity, it is shown how to obtain in an atomless B, for any \(k\in \omega\) a formula \(\psi_ k(z)\), in the language of Boolean algebras with a selected ideal, and for any (infinite) set \(A\subseteq \omega\) an ideal \(I_ A\) of B, such that \((B,I_ A)\vDash \exists z \psi_ k(z)\) iff \(k\in A.\) As to sufficiency, it is shown that the theory of (A,I), when A is superatomic, is (recursively) axiomatizable. The main tool is the construction of three mappings \(r_ 1,r_ 2,r_ 3\) from A into \(\omega\cup \{\infty \}\) with the properties: i) For \(x\in A\), \(x\in I\) iff \(r_ 3(x)\leq 1\); ii) for \(x\in A\), there are x', x'' such that \(x=x'\vee x''\), \(x'\wedge x''=0\) and \(r_ 2(x')=r_ 2(x'')=0\); iii) each statement \(``r_ j(\ell_ A)=n_ j''\) \((j=1,2,3)\) is equivalent to a r.e. set of formulas. It is shown that if (A,I) and (A',I') are both atomic and satisfy i) and ii), then they are elementary equivalent iff \(r_ j(\ell_ A)=r_ j(\ell_{A'})\) for \(j=1,2,3\).