Before we dive into the relation with automata, we will define the notion of nominal sets.

\startdefinition
Fix a countable, infinite set $\atoms = \{ a, b, \ldots \}$ of \emph{names} (sometimes called \emph{atoms}).
The elements of $\atoms$ bare no relationship to natural numbers, or other standard mathematical entities.

Define $\Pm = \{ \pi \colon \atoms \to \atoms \mid \pi \text{ is bijective} \}$ to be the set of permutations of names.
Together with function composition, $\Pm$ forms a \emph{group}.
For two elements $a$ and $b$ we define a particular bijection $\swap{a}{b} \in \Pm$ which swaps $a$ and $b$ and leaves all other elements fixed.
\stopdefinition

It is good to stress that the set of names has no other structure defined on it.
The names are abstract entities which can be compared for equality, but nothing else.
\footnote{We can have more structure on the set of atoms, this is discussed in \in{Section}[].}
This also means that although $a$ and $b$ are distinct names, they are interchangeable.
If we write $a \in \atoms$, then $a$ can stand for any of the names.
So if we write $a, b \in \atoms$, then $a$ and $b$ can refer to the same name, i.e., $a = b$.
In other words, we do not adapt the permutative convention by \citet[?].

As alluded to before, we want to have permutations act on objects constructed from names, such as words, states in an automaton and languages.
The notion of a group action captures exactly this.
In most cases we are interested in the group $\Pm$.
However, in order to be general enough for the next chapters, we introduce group actions for an arbitrary group $G$.
\todo{Notatie $1$ is groepseenheid, ${\cdot}$ is vermenigvuldiging en werking.}

\startdefinition
Let $X$ be a set.
A (left)
\footnote{Many authors use left actions.
However, we note that \citet[BojanczykKL14] use a right action.
For them to have a well-defined group action, their group multiplication has to be defined as $g \cdot f = f \circ g$ (i.e., reverse function composition).}
\emph{$G$-action} is a function ${\cdot} \colon G \times X \to X$ satisfying:
\startformula\startalign[n=3]
\NC 1 \cdot x            \NC = x                    \NC \quad \forall x \in X \NR
\NC (g \cdot h) \cdot x  \NC = g \cdot (h \cdot x)  \NC \quad \forall x \in X, \forall g,h \in G \NR
\stopalign\stopformula
A set together with a $G$-action, $(X, {\cdot})$, is called a \emph{$G$-set}.
\stopdefinition

It is worth noting that we generally fix $G$ but we consider many sets with a $G$-action.
In a way all these sets will have the same symmetries (namely $G$).
Instead of writing $g \cdot x$ we will often write the group action by juxtaposition $g x$.
We will often write $X$ instead of $(X, {\cdot})$ when the intended action is clear from the context.
\footnote{One should be cautious, as a set often allows for many different $G$-actions.}

\startexample
We list several examples of group actions.
Many of them will be used later in this thesis.
\startitemize
\item
The set $\atoms$ itself admits a natural $\Pm$-action, defined by
\startformula \pi \cdot a = \pi(a). \stopformula
The two requirements are easily verified by a routine calculation.
We will also omit this verification for the upcoming examples.
\item
The set of words $\atoms^{*}$ has a $\Pm$-action which is defined point-wise:
\startformula \pi \cdot a_1 a_2 \ldots a_k = \pi(a_1) \pi(a_2) \ldots \pi(a_k) \stopformula
\item
Similarly, the set of infinite words $\atoms^{\omega}$ has such a $\Pm$-action:
\startformula \pi \cdot a_1 a_2 \ldots = \pi(a_1) \pi(a_2) \ldots \stopformula
\item
The empty set always admits a unique $G$-action for any $G$.
(This is unique since the domain $G \times \emptyset = \emptyset$.)
\startformula {\cdot} \colon G \times \emptyset \to \emptyset \stopformula
\item
The singleton set always admits a unique $G$-action for any $G$.
(This is unique since the codomain only has just one element.)
\startformula {\cdot} \colon G \times \{*\} \to \{*\} \stopformula
\item
For any set $X$, we can define a $G$-action by defining
\startformula g \cdot x = x \stopformula
for all the elements $x \in X$.
Such an action is called \emph{trivial}.
Note that the action on $\emptyset$ and $\{*\}$ are trivial, but the $\Pm$-actions on $\atoms$, $\atoms^{*}$ and $\atoms^{\omega}$ are not trivial.
\stopitemize
\stopexample

In the above examples, the non-trivial $\Pm$-sets are all infinite.
Yet, in a sense, the set $\atoms^{*}$ is bigger than the set $\atoms$.
To be able to quantify this, we introduce the notion of an orbit.

\startdefinition
Given a $G$-set $(X, {\cdot})$ and an element $x \in X$, we define the \emph{orbit of $x$} as the set
\startformula \orb(x) = \{ g x \mid g \in G \}. \stopformula
\stopdefinition

If for two elements $x, y \in X$ we have $\orb(x) = \orb(y)$, then we say that $x$ and $y$ are in the same orbit.
This precisely happens if there exists a $g$ such that $g x = y$.
The relation of \quotation{being in the same orbit} is an equivalence relation (it is reflexive as a group has an identity element, symmetric because of the inverses and transitive because of composition).
This relation partitions the set $X$ in a collection of orbits:
\startformula X = \bigcup_{x \in X} \orb(x). \stopformula

We can picture orbits in the following way.
\todo{PLAATJE}
As we wish to represent such sets (in order to run algorithms on them), we are especially interested in orbit-finite sets.
For such sets, we can represent the whole set by a collection of its orbits.
What remains to be represented are the orbits themselves.
An easy way to do is, is to choose a representative of the orbit $x \in \orb(x)$. (Any element will do as the other elements can be constructed via the group action.)
\todo{PLAATJE}

\startexample
We will describe the orbits for some $\Pm$-sets.
\startitemize
\item
For a trivial $G$-set $X$, each element defines its own orbit, since $\orb(x) = \{ g x \mid g \in G \}$ is a singleton set.
\item
The $\Pm$-set $\atoms$ only has \emph{one orbit}.
To see this, take two (distinct) elements $a, b \in \atoms$ and consider the bijection $\pi = \swap{a}{b}$.
Then we see that $\pi \cdot a = b$, meaning that $a$ and $b$ are in the same orbit.
So $\atoms$ is a single-orbit set.
\item
Before we tackle $\atoms^{*}$, we will analyse $\atoms^{2}$.
The set consists of exactly \emph{two orbits}:
\startformula\startalign
\NC \{ (a, a) \NC \mid a \in \atoms \} \NR
\NC \{ (a, b) \NC \mid a, b \in \atoms, a \neq b \} \NR
\stopalign\stopformula
This is because a bijection $\pi \in \Pm$ can never send an element of the form $(a, b)$ to an element of the form $(a, a)$ or vice versa.
It can, however send any element $(a, b)$ to $(c, d)$ and so on.
\item
The set $\atoms^{*}$ has \emph{countably many orbits}.
Since the action preserves the length of a word, we will show that the set has finitely many orbits for each length.
So consider the set $\atoms^{k}$ with the point-wise action.
An orbit of $\atoms^{k}$ is precisely determined by specifying which of the $k$ elements are equal to each other.
This is a partition of $k$ elements, and there exactly $B_k$, the $k$th Bell number, such partitions.
(As we have seen for $k = 2$, the second Bell number is $B_2 = 2$.
This quantity grows exponential in $k$.)
This shows that the set $\atoms^{*} = \bigcup_k \atoms^{k}$ has countably many orbits.
\stopitemize
\stopexample

Having finitely many orbits is not enough for a finite representation which we can use algorithmically.
We need an additional finiteness on the elements of a $G$-set,
namely the existence of a \emph{finite support}.
In order to define this, we need the notion of a data symmetry.

\startdefinition
A \emph{data symmetry} is a pair $(\mathcal{D}, G)$, where $\mathcal{D}$ is a structure and $G \leq \Sym(\mathcal{D})$ is a subgroup of the automorphism group of $\mathcal{D}$.
\stopdefinition

\startdefinition
Let $X$ be a $G$-set and $x \in X$.
A set $C \subset \mathcal{D}$ \emph{supports} $x$ if for all $g \in G$ with $g|_C = \id|_C$ we have $g \cdot x = x$.

A $G$-set $X$ is called \emph{nominal} if every element has a finite support.
\stopdefinition

In a way, if an element is supported by a finite set $C$, it means that the element is somehow constructed from only the elements in $C$.
We can see this from the definition, as changing any element outside of $C$ will leave the element $x$ fixed.

\startexample
\startitemize
\item
The sets $\atoms$, $\atoms^{k}$, $\atoms^{*}$ are all nominal.
For an element $a_1 a_2 \ldots a_k \in \atoms^{*}$, its support is simply given by $\{a_1, a_2, \ldots, a_k\}$.
\stopitemize
\stopexample

These examples show that being orbit-finite and nominal are orthogonal properties.
\todo{Een voorbeeld is uitgesteld.}
There are $G$-sets which are orbit-finite, but non-nominal.
Conversely, there are nominal sets which are not orbit-finite.


\stopsubsection
\startsubsection
  [title={Nominal automata}]

\todo{Model the example above as nominal automata}


\stopsubsection
\startsubsection
  [title={More interesting examples of nominal sets}]

The set $\atoms^{\omega}$ has \emph{uncountably many orbits}.
To see this, fix two distinct elements $a, b \in \atoms$.
Now, let $\sigma \in 2^{\omega}$ be an element of the Cantor space.
We define the following sequence $x^{\sigma} \in \atoms^{\omega}$:
\startformula\startalign
\NC x^{\sigma}_0     \NC = a \NR
\NC x^{\sigma}_{i+1} \NC =
  \startmathcases
  \NC a, \NC if $\sigma(i) = 0$ \NR
  \NC b, \NC if $\sigma(i) = 1$ \NR
  \stopmathcases \NR
\stopalign\stopformula
Now for two distinct elements $\sigma, \tau \in 2^{\omega}$, the elements $x^{\sigma}$ and $x^{\tau}$ are different.
More importantly, their orbits $\orb(x^{\sigma})$ and $\orb(x^{\tau})$ are different too.
This shows that there is an injective map from $2^{\omega}$ to the orbits of $\atoms^{\omega}$.
This concludes that $\atoms^{\omega}$ has uncountably many orbits.

The set $\atoms^{\omega}$ is \emph{not} nominal.
To see this, let us order the elements of $\atoms$ as $\atoms = \{ a_1, a_2, a_3, \ldots \}$.
Now the element $a_1 a_2 a_3 \in \atoms^{\omega}$ is not finitely supported.
\todo{fs subset van $\atoms^{\omega}$?}

The set $\{ X \subset \atoms \mid X \text{ is not finite nor co-finite} \}$ (with the group action given by direct image) is a single orbit set, but it is not a nominal set.

The last example above needs a bit more clarification.
In the book of \citet[Pitts13], the group of permutations is defined to be
\startformula
G_{< \omega} = \{ \pi \in \Perm \mid \pi(x) \neq x \text{ for finitely many } x \}.
\stopformula
This is the subgroup of $\Pm$ of \emph{finite} permutation.
The set $\{ X \subset \atoms \mid X \text{ is not finite nor co-finite} \}$ has infinitely many orbits when considered as a $G_{< \omega}$-set, but only one orbit as a $\Pm$-set.
This poses the question which group we should consider (for example, \citet[BojanczykKL14] use the whole group $\Pm$).
For nominal sets, there is no difference: nominal $G_{< \omega}$-sets and nominal $\Pm$-sets are equivalent, as shown by \citet[Pitts13].
It is only for non-nominal sets that we can distinguish them.
We will mostly work with the set of all permutations $\Pm$.

Another interesting non-trivial example is the set $\Pm$ itself.
There are three different interesting actions one can define:
\startformula\startalign
\NC \pi \cdot_{l} \sigma \NC = \pi \sigma \NR
\NC \pi \cdot_{r} \sigma \NC = \sigma \pi^{-1} \NR
\NC \pi \cdot_{c} \sigma \NC = \pi \sigma \pi^{-1} \NR
\stopalign\stopformula
Here the group multiplication is written by juxtaposition.
The first two actions are \emph{left-multiplication} and \emph{right-multiplication} respectively.
The latter is called \emph{conjugation}.
For each of them, one can verify the requirements.
\