Computable Isomorphisms of Boolean Algebras with Operators
by
Bakhadyr M. Khoussainov
Computer Science Department, The University of Auckland, New Zealand.
Coauthors: Tomasz Kowalski (JAIST, Japan)

In computable algebra and model theory computable isomorphism types of structures have been studied intensively over almost three decades. These include a number of natural classes of structures, such as Boolean algebras, Abelian groups, and lattices. The Handbook of Recursive Mathematics is a good source of results in the area. Here we present two results about computable isomorphisms of Boolean algebras with operators (BAOs).

A computable BAO A is one whose domain is a computable subset of N, and whose Boolean operations and the operators are computable functions. If a BAO B is isomorphic to a computable BAO A then B is called computably presentable and A is a computable copy of B. A computable function that sets up an isomorphism between computable BAOs A and B is a computable isomorphism, in which case A and B have the same computable isomorphism types.

A central definition in the study of computable isomorphism is one of computable dimension. The computable dimension of a BAO A, denoted by dim(A), is the number of its computable isomorphism types. If dim(A) = 1 then A is called computably categorical.

In mid 70s Goncharov and independently Remmel showed that any computable Boolean algebra B is either computably categorical or has infinite computable dimension. Moreover, dim(B) = 1 iff B has finitely many atoms. The following two theorems describe computable dimensions of BAOs and show that the situation for computable BAO is very different in comparison to computable Boolean algebras without operators.

Theorem 1. For every natural number n there exists a BAO whose computable dimension is n.

The next theorem shows that extending BAO with a finite number of constants affects the computable isomorphism types of the original BAO.

Theorem 2. For any natural number n there exists a computably categorical BAO B such that the expansion of B by any constant atom c has computable dimension n.

Theorem 1 codes the family of computably enumerable sets constructed in [1]. Theorem 2 uses the family of pairs of computably enumerable sets constructed in [2].

References.

[1]

S. Goncharov. Computable Univalent Numerations, Algebra and Logic 19, N 5, p. 507-551, 1980.

[2]

P. Cholak, S. S. Goncharov, B. Khoussainov, and R. A. Shore. Computably categorical structures and expansions by constants, J. Symbolic Logic 64 (1999) 13-37.

[3]

Handbook of Recursive Mathematics, Vol 1, 2. eds: Goncharov, Nerode, et al. North-Holland, 1998.

Date received: December 30, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caig-29.