# Automorphism groups of definable structures

We consider equality atoms , i.e., is a countable set with the equality relation. Recall that by definable set we mean a structure which can be defined (in a possibly nested fashion) from using finite unions, finite tuples, and set-builder expressions with first-order formulas ranging over , e.g. is definable using the parameter . A definable relational structure is a relational structure  where and each relation is a definable set. Up to isomorphism, definable structures are the same as structures which interpret in , using first-order interpretations (this correspondence preserves parameters), but sometimes using definable sets makes constructions easier.

The problem described in the previous post is to determine isomorphism between two definable structures. In this post, we describe this problem in terms of automorphism groups. This post is based on discussions with Manuel Bodirsky and Antoine Mottet.

# Graph isomorphism

Fix an -categorical structure . The simplest, and already interesting case is , the pure countable set.

We consider the definable graph isomorphism problem for graphs which are definable (equivalently, interpret in) :

Problem: DefGraphIso

Input: Two definable graphs

Output: Yes, if and are isomorphic, No otherwise.

Below we make some very basic observations concerning this problem.