|
This article is cited in 3 scientific papers (total in 3 papers)
Mathematical logic, algebra and number theory
Atomless Boolean algebras computable in polynomial time
P. E. Alaev Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
Abstract:
We construct an example of atomless Boolean algebra $ {\mathfrak B} $, computable in polynomial time, that has no primitive recursive function $ f : B \to B $ such that $ 0 < f (a) < a $ for $ a \neq 0 $. In addition, we show that if two primitive recursive atomless Boolean algebras $ {\mathfrak B}_{1} $ and $ {\mathfrak B}_{2} $ have such functions, then there is an isomorphism $ g : {\mathfrak B}_{1} \to {\mathfrak B}_{2} $ such that $ g $ and $ g^{-1} $ are primitive recursive functions.
Keywords:
computable structure, Boolean algebra, primitive recursive structure, polynomial time computability, primitive recursive isomorphism.
Received October 10, 2016, published November 22, 2016
Citation:
P. E. Alaev, “Atomless Boolean algebras computable in polynomial time”, Sib. Èlektron. Mat. Izv., 13 (2016), 1035–1039
Linking options:
https://www.mathnet.ru/eng/semr732 https://www.mathnet.ru/eng/semr/v13/p1035
|
Statistics & downloads: |
Abstract page: | 182 | Full-text PDF : | 48 | References: | 38 |
|