These are some short notes concerning model-complete cores, based on an exposition of Manuel Bodirsky. In particular, he proved that every 
-categorical structure has a unique (up to isomorphism) model-complete core. We pose the question whether the model-complete core of a definable structure (say, over the equality atoms) is again definable.
Tag Archives: equality atoms
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.
Orbit-finite groupoids
Orbit-finite groups are finite, and therefore not very interesting from the perspective of sets with atoms. It turns out that orbit-finite groupoids form interesting structures. They will be useful in the study of orbit-finite semigroups in the following post.
Can orbit-finite semigroups be straightened?
A straight set is an equivariant set which is equivariantly isomorphic to a disjiont union of sets of the form 
. A straight semigroup is an equivariant semigroup whose universe is a straight set. We raise the following:
Question 1: is every equivariant, orbit-finite semigroup an image of some orbit-finite, straight semigroup under an equivariant mapping?
We show some simple preliminary observations towards the above question.
Orbit-finite systems of linear equations
Consider the following decision problem, over the equality symmetry.
Input: an orbit-finite system of linear equations 
over 
Decide: does have a solution (not necessarily finitely-supported)?
Inspired by Eryk’s beautiful solution of this problem, we present another solution, using an amazing theorem from topological dynamics.
Orbit-finite bijections can be smoothed
In his recent post Bartek demonstrated an example of two equivariant sets with atoms that are related by a finitely supported bijection, but not by any equivariant bijection. We show that if the sets are orbit-finite then this situation is impossible.
Proposition. Let 
and 
be two orbit-finite equivariant sets with atoms. If there exists a finitely supported bijection 
then there exists an equivariant bijection 
.
Continue reading
Some bijections cannot be smoothed
It can happen that two equivariant sets with atoms are related by a finitely supported bijection, but not by an equivariant bijection.
Bipartite graphs without bipartite partition
In the equality symmetry, there is a single-orbit graph 
with the property that is bipartite in the classical sense (equivalently, has no odd-length cycle) but has no partition into two parts which are finitely supported and not inter-connected. In other words, the graph maps to the single-edge graph via a infinitely-supported homomorphism, but not via a finitely-supported one. And here’s the graph: its nodes are pairs of distinct atoms, and there is an edge from 
to 
, whenever 
are distinct atoms. That’s it.
The Rum Conjecture is refuted
A conjecture I posted a while ago, concerning reachability of states in automata with atoms after a Brzozowski phase, has been refuted by Mikołaj Bojańczyk.