Undecidability of theories of Boolean algebras with selected ideals
type: Item
instance of: scholarly article
title: Undecidability of theories of Boolean algebras with selected ideals
zbMATH Open document ID: 0628.03004
DOI: 10.1007/BF01988801
author: D. E. Pal'chunov
published in: Algebra and Logic
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/187353
review text: 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\).
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 4021097
zbMATH Keywords: recursive axiomatizability
zbMATH Keywords: decidability
zbMATH Keywords: countable Boolean algebra
zbMATH Keywords: selected ideal
reviewed by: Aldo Ursini
MaRDI profile type: Publication
cites work: Q5596792
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Q3964551
cites work: Q5802110
description: scientific article; zbMATH DE number 4021097