scientific article; zbMATH DE number 1421070

From MaRDI portal
Publication:4946095





It is known that every computable Boolean algebra is computably isomorphic to a polynomial-time Boolean algebra. The present paper studies the validity of this result in the case where the universe of the polynomial-time Boolean algebra is required to be in one of the following two forms: \(\text{Bin}(\omega)\), the set of natural numbers in binary representation, and \(\text{Tal}(\omega)\), the set of natural numbers in tally representation. The main results establish some conditions under which the computably isomorphim holds. For example, it is proved that if \(B\) is a countably infinite computable Boolean algebra such that both the set of atoms of \(B\) and the ideal generated by the atoms of \(B\) are computable, then \(B\) is computably isomorphic to a polynomial-time Boolean algebra with universe \(\text{Bin}(\omega)\) and to a polynomial-time Boolean algebra with universe \(\text{Tal}(\omega)\). For the entire collection see [Zbl 0923.00014].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4946095)