Complexity of index sets of computable lattices

Abstract

We analyze computable algebras in the sense of universal algebra and the index set complexity of properties of such algebras. We look at the difficulty of determining properties of Con(A), the congruence lattice of an algebra A. In particular, we introduce the notion of a class of algebras witnessing the complexity of a property of algebras and show that computable lattices witness the 02-completeness of being simple, as well as witnessing the 03-completeness of having finitely many congruences. Finally, in our main result, we show that the property "to be subdirectly irreducible" is 03-complete as well, and in the process show that computable lattices witness this.