9. Sets with atoms

Mikołaj Bojańczyk

zajęcia / courses

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$

zajęcia / courses

9. Sets with atoms

9. Sets with atoms

Leave a Reply