Structures and partial computable automorphisms
Valentina Harizanov, Eric Ufferman · 2006
We consider only structures for finite languages. Such a structure is computable if its domain is computable and its relations and operations are computable. For a structure, the set of all partial automorphisms forms an inverse semigroup under function composition. The set of finite partial automorphisms is an inverse subsemigroup of that structure. We consider inverse subsemigroups of the inverse semigroup of all partial automorphisms that contain all of the finite partial automorphisms, and determine what information we can recover about the original structures. We show that for equivalence structures, the isomorphism type of the structure may be recovered from the isomorphism type of any such semigroup; and the first-order theory of the structure may be recovered from the first-order theory of any such semigroup. From the first-order theory of the inverse semigroup of finite partial automorphisms of an equivalence structure, we may actually recover the original structure up to isomorphism. For partial orders, we show that from the isomorphism type of any inverse subsemigroup of partial automorphisms that contains all the finite partial automorphisms, we may recover the isomorphism type of the partial order up to reversal of the order. The result holds with first-order theory in place of isomorphism type. For a computable structure, we also consider the inverse semigroup of all partial automorphisms which are partial computable. We establish that for certain computable Boolean algebras and computable relatively complemented distributive lattices, the isomorphism of these inverse semigroups implies that the corresponding structures are also isomorphic, even by a computable isomorphism. For computable equivalence structures, the elementary equivalence of these inverse semigroups implies that the structures are computably isomorphic.