Undecidability of theories of Boolean algebras with selected ideals (Q1092889): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Aldo Ursini / rank | |||
Property / reviewed by | |||
Property / reviewed by: Aldo Ursini / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5596792 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decidability of Second-Order Theories and Automata on Infinite Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3964551 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5802110 / rank | |||
Normal rank |
Latest revision as of 12:46, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Undecidability of theories of Boolean algebras with selected ideals |
scientific article |
Statements
Undecidability of theories of Boolean algebras with selected ideals (English)
0 references
1986
0 references
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\).
0 references
recursive axiomatizability
0 references
decidability
0 references
countable Boolean algebra
0 references
selected ideal
0 references