×

zbMATH — the first resource for mathematics

Undecidability of theories of Boolean algebras with selected ideals. (English. Russian original) Zbl 0628.03004
Algebra Logic 25, 206-219 (1986); translation from Algebra Logika 25, No. 3, 326-346 (1986).
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\).
Reviewer: A.Ursini

MSC:
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Yu. L. Ershov, ”Decidability of the theory of distributive lattices with relative complements and the theory of filters,” Algebra Logika,3, No. 3, 17–39 (1964). · Zbl 0199.03103
[2] M. O. Rabin, ”Decidability of the second order theories and automata on infinite trees,” Trans. Am. Math. Soc.,141, 1–35 (1969). · Zbl 0221.02031
[3] A. S. Morozov, ”On decidability of theories of Boolean algebras with a selected ideal,” Sib. Mat. Zh.,23, No. 1, 199–201 (1982). · Zbl 0499.03030
[4] A. Tarski, ”Arithmetic classes and types of Boolean algebras,” Bull. Am. Math. Soc.,55, 64 (1949). · Zbl 0041.34502
[5] Yu. L. Ershov and E. A. Palyutin, Mathematical Logic [in Russian], Nauka, Moscow (1979).
[6] P.-F. Jurie and A. Touraille, ”Idéaux élémentairement equivalents dans une algébre booléienne,” C. R. Acad. Sci., Serie I,10, 415–418 (1984).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.