Mikołaj Bojańczyk

Let us fix an infinite set \atoms, which we will call the atoms. Consider the set of all permutations of the atoms, which is a group.  An action of the group of permutations of atoms on a set X is a function

    \[(\pi \mbox{ a permutation of atoms}, x \in X) \qquad \mapsto \qquad \pi(x)\]

which is consistent with the group structure in the sense that

    \[\pi(\sigma(x)) = (\pi \circ \sigma)(x).\]

Given such an action, we say that a set of atoms S supports some x \in X if \pi(x) is uniquely determined by the values of \pi on atoms from S. In other words,

    \[\big( \forall a \in S\ \pi(a) = \sigma(a) \big) \quad \mbox{implies} \quad \pi(x)=\sigma(x)\]

Define a set with atoms to be a set X equipped with an action of permutations of atoms such that every element x \in X has some finite support.

Equivariance. If X is a set with atoms, call a subset Y \subseteq X equivariant if the subset is invariant under renaming atoms, i.e.

    \[x \in Y \qquad \mbox{iff} \qquad \pi(x) \in Y\]

holds for every x \in X and every permutation of the atoms \pi.  A function f : X \to Y is called equivariant if

    \[f(\pi(x)) = \pi(f(x))\]

holds for every x \in X and every permutation of the atoms \pi. These definitions are compatible in the sense that: a subset is equivariant if and only if its characteristic function is equivariant, and a function is equivariant if and only if its graph is an equivariant relation.

Orbit-finiteness. If X is a set with atoms, we say that x,y \in X are in the same orbit if some permutation of the atoms takes x to y. This is an equivalence relation, and its equivalence classes are called orbits. A set with atoms is called orbit-finite if it has finitely many orbits. The motivation for this notion is that the state space, input alphabet and all other components in a register automaton  are orbit-finite sets with atoms.


 

Lemma 1. Let f : X \to Y be an equivariant function. If a set of atoms supports x \in X, then it also supports f(x) \in Y.

Proof. From the definition: if \pi is a permutation of atoms which fixes x, then it also fixes f(x) by equivariance. \Box

 


 

A representation theorem.

Let us write \atoms^{(n)} for the set of non-repeating n-tuples of atoms. This is a single-orbit set with atoms. On the set \atoms^{(n)}, we can define an action of permutations of  \set{1,\ldots,n} as follows:

    \[\pi(a_1,\ldots,a_n) = (a_{\pi(1)},\ldots,a_{\pi(n)})\]

  Note that we have two groups acting on \atoms^{(n)}, permutations of the atoms, and permutations of the coordinates. These actions commute with each other in the following sense: if \pi is a permutation of the coordinates and \sigma is a permutation of the atoms, then

    \[\pi ( \sigma (a_1,\ldots,a_n)) = \sigma ( \pi (a_1,\ldots,a_n)).\]

If G is a subgroup of all permutations of \set{1,\ldots,n}, then we define 

    \[\atoms^{(n)} /_G\]

to be \atoms^{(n)} modulo the equivalence relation which identifies two tuples if they are in the same orbit with respect to the action of G. The following theorem shows that this is essentially the only possible construction for sets with atoms.

Theorem 1. Every set with atoms is isomorphic (where isomorphisms are equivariant bijections) to a disjoint union of sets of the form

    \[\atoms^{(n)} /_G\]

where n is a natural number and G is a subgroup of the permutation group on \set{1,\ldots,n}.

Proof. It suffices to prove the theorem for single orbit sets, because every set with atoms is isomorphic to the disjoint union of its orbits. Let then X be a single-orbit set. Choose some x \in X, and let \set{a_1,\ldots,a_n} be the least support of x, in some order. Consider the relation

    \[\set{ \pi(a_1,\ldots,a_n) , \pi(x)} \subseteq \atoms^{(n)} \times X,\]

which is equivariant by definition. Because a_1,\ldots,a_n supports x, the above is actually an equivariant function, call it

    \[f : \atoms^{(n)} \to X.\]

 Consider the inverse image f^{-1}(x), and define G to be the permutations of \set{1,\ldots,n} such that

    \[f(\pi(a_1,\ldots,a_n)) = f(a_1,\ldots,a_n)\]

The set G is easily seen to  be a subgroup. To conclude the proof, we make the following claim, which implies that X is isomorphic to \atoms^{(n)} /_G.

Claim. The following conditions are equivalent for every \bar b, \bar c \in \atoms^{(n)}:
1) f(\bar b) = f (\bar c)
2) there is some \pi \in G such that \bar c = \pi(\bar b).

2) implies 1) Assume 2) holds for some \pi \in G. By definition of f, we have

    \[f(\bar a) = f(\pi(\bar a))\]

Let \sigma be some permutation of the atoms such that \sigma(\bar a) = \bar b, which exists because there is only one orbit of non-repeating tuples. Applying \sigma to both sides of the equality above, we get

    \[\sigma(f(\bar a)) = \sigma(f(\pi(\bar a)))\]

By equivariance of f, we have

    \[f(\sigma(\bar a)) = f(\sigma(\pi(\bar a)))\]

Because permutations with atoms commute with permutations of coordinates, we have

    \[f(\sigma(\bar a))=f(\pi(\sigma(\bar a))).\]

By choice of \sigma, the above is

    \[f(\bar b)=f(\pi(\bar b))=f(\bar c).\]

 

1) implies 2) Suppose f(\bar b) = f(\bar c). Let \sigma be some permutation of the atoms such that \sigma(\bar b) = \bar a. By equivariance of f, we have

    \[f(\bar a) = f(\sigma(\bar b)) = f(\sigma(\bar c)).\]

By Lemma 1, the tuple \sigma(\bar c) supports f(\bar a). By the least support theorem, the set of atoms in \sigma(\bar c) must be equal to \set{a_1,\ldots,a_n}, i.e. there must be some permutation \pi of coordinates such that

    \[ \sigma(\bar c) =\pi(\bar a)\]

Since \sigma(\bar c) has the same image under f as \bar a, it follows that \pi \in G. Therefore,

    \[\bar c = \sigma^{-1}(\pi(\bar a)) = \pi(\sigma^{-1}(\bar a)) = \pi(\bar b)\]

which completes the proof of the claim and therefore also of the theorem. \Box

 

Leave a Reply

Your email address will not be published.