Categoricity for Primitive Recursive and Polynomial Boolean Algebras

Abstract

We define a class \( \mathbb{K} \)_Σ of primitive recursive structures whose existential diagram is decidable with primitive recursive witnesses. It is proved that a Boolean algebra has a presentation in \( \mathbb{K} \)_Σ iff it has a computable presentation with computable set of atoms. Moreover, such a Boolean algebra is primitive recursively categorical with respect to \( \mathbb{K} \)_Σ iff it has finitely many atoms. The obtained results can also be carried over to Boolean algebras computable in polynomial time.