Computability of Algebraic Structures

We investigate computability theoretic properties of algebraic structures. First we consider computable free groups. We give a characterization of the elements in a free group that satisfy the same universal sentences as the elements that are part of a basis. We then prove that the index set for the class of all free groups is m-complete Ì_åÊ04. We also consider bases for F̢蠁_, the countably generated free group. We show that every computable copy of F̢蠁_ has a Ì_åÊ02 basis, and that there exists a computable copy with no Ì_å£02 basis. Next we study the sets that can be coded into a computable abelian p-group. We show that for any non-computable Ì¢è 'Ê02 degree, there is an abelian p-group with a copy in that degree and no computable copy. We also show that there is an abelian p-group with no computable copy, but that can be computed by any degree in a set of degrees of measure 1. Finally, we study presentations of partial orders. Podzorov showed that any local lattice that has a Ì¢è 'Ê02 presentation also has a c.e. presentation. We show that his result does not extend to the class of all partial orders by coding a particular set into a partial order.