Action preorders

Transformations $f: S \to S$ are distinguished by the fact that they map a set back to itself. This induces an action on the set $S$. We can then define a minimal preorder which makes this action increasing. These action preorders can be defined on individual transformations, transformation semigroups, commutative semigroups, non-commutative semigroups, term rewriting systems, games, or any other structure that has actions associated with them. Each of these cases will be addressed.

Intuitively, these action preorders describe the direction a system is going in if any. A directed edge in an action preorder means that there is some action which moves the system from one state to the other, but for which there is no way to go back through the actions of the system. Action preorders therefore provide a measure of the irreversibility of a transformation or a system of them. Action preorders can also describe invariants uneffected by a system of actions.

Transformations:

We say that a transformation $f: (S,\leq) \to (S,\leq)$ is increasing if forall $x \in S$ we have that $x \leq f(x)$. This can be expressed in more set-theoretic notation using binary relations as $(x,f(x)) \in \leq$. Finally, note that $(x,f(x))$ is the expression of the transformation $f$ as a binary relation. Therefore, a transformation $f$ is increasing iff $f \subseteq \leq$. A transformation is increasing with respect to a preorder iff it is a subrelation, which suggests a natural way to define a preorder for any transformation.

Definition. The action preorder of a transformation $f : S \to S$ is the preorder closure of its expression as a single-valued binary relation.

The action of on a transformation on its action preorder is always increasing. This follows by the increasing nature of the closure operation itself, which implies that $f \subseteq cl_{Preorder}(f)$ which is an equivalent definition of increasing action. Further, this preorder is the minimal preorder for which the action of the transformation is increasing. The action preorder need not be a partial order, as demonstrated below.

Example 1. a transformation with antisymmetric action

Example 2. a transformation with symmetric action

The first example is an example of an increasing function on a partial order. Its partial order is a tree, and its action function moves each element up one in the tree. As it is moving up in the tree, it is an increasing function. In order for an action preorder to be partially ordered, its action must be acyclic. It is not hard to see that the preorder closure of a finite transformation is a upper forest preorder with distinguished non-root elements.

Transformation semigroups:

We have a means of establishing a preorder for any transformation. The next step is establishing preorders for sets of transformations, which describe their overall action on a set. The action preorder of a transformation is the smallest preorder over which it is increasing, so relatedly the action preorder of a family of transformations is the preorder that contains all of them. All the different transformations then have increasing actions on that preorder.

Definition. Let $S$ be a transformation semigroup on a set $A$. Let $Po(A)$ denote the lattice of preorders on $A$. Then we can define a map $f$ from $Sub(S)$ to $Po(A)$ which associates any family of transformations to its action preorder. \[ f : Sub(S) \to Po(A) \] The output of the function is defined by the preorder join of the preorder closures of each transformation. \[ f(s) = \vee_{t \in s} cl_{Preorder}(t) \] Proposition. $f : Sub(S) \to Po(A)$ is monotone

The join operation in any lattice is monotone with respect to the inclusion ordering. It follows that $f$ is monotone. $\square$

Proposition. group actions are symmetric

Proof. let $R$ be the preorder of the group action and let $(a,b) \in R$ then by definition there exists a transformation $t$ such that $t(a) = b$. By the definition of inverses in a group we have that $t^{-1}(b) = a$ which implies that $(b,a) \in R$. Therefore, group action is symmetric. $\square$

The lattice of equivalence relations $Part(A)$ is a sublattice of the lattice $Po(A)$. To see this, it is sufficient to demonstrate that the transitive closure of symmetric relations is symmetric. Let $(a,b) \in R$ and $(b,c) \in R$ then we have $(a,c) \in R$ by transitivity. But we also have $(c,b),(b,a) \in R$ which means $(c,a) \in R$ so transitive closure preserves symmetry. It follows that for group actions there is a monotone map from the lattice of subgroups to $Part(A)$ \[ f : Sub(S) \to Part(A) \] If we have a suborder $O$ of the lattice of subsemigroups $Sub(S)$ then the image of $f$ is a partially ordered family of preorders describing the different types of action preorders that can be created for the different types of actions in $O$. Therefore, it is common in the study of algebraic structures to use families of preorders to describe different actions.

Example 1. let $R$ be a binary relation, then the action preorder of $Aut(G)$ is the symmetric preorder defined by orbits. The subgroup generated by transpositions generates an equivalence subrelation of the orbit of the automorphism group. Transposability often provides a better measure of equality then the orbits of the automorphism group.

Example 2. let $G$ be a cyclic permutation of order $n$ then it generates the complete equivalence relation. Its cyclic subgroups generate the different partitions defined by equality modulus the divisors of $n$.

Commutative semigroups:

The action preorder:
A commutative semigroup $(S, \circ)$ induces a unique action on itself by each of its elements. As is the case with transformations, and in general, we want to define a preorder on the semigroup over which action is increasing. This is provided by the familiar factorisation preorder.

Definition. the action preorder of a commutative semigroup $(S,\circ)$ is defined by: \[x \sqsubseteq y \Leftrightarrow \exists z : zx = y \] There are many different ways of defining a preorder on a commutative semigroup, but the relevant aspect of this action preorder is that it makes action increasing. Semigroup action that is increasing in both arguments is also called biextensive, by analogy with bilinear maps.

Proposition. commutative semigroups are biextensive over their action preorders

Proof. let $z$ be an element, now we want to show that for any element $x \subseteq x \circ z$ to show that action by $z$ is increasing. In order to show that $x \subseteq x \circ z$ it sufficies to show that there is an element $y$ such that $x \circ y = x \circ z$. That element $y$ can be set to precisely $z$ itself. $\square$

Example 1. addition of non-negative integers is increasing over the total order

Example 2. multiplication of non-negative integers is increasing over divisibility

Example 3. union of sets is increasing with respect to inclusion

The naturality of the preorder of a commutative semigroup is realized in the fact that it has integer divisibility as a special case. This algebraic preorder, also known as the factorisation preorder, is characterized by the fact that it is the minimal preorder over which all actions are increasing.

Subsemigroup actions:
The mapping from any set of actions to its preorder is monotone, therefore subsemigroups produce smaller actions on themselves. It follows that each semigroup is associated to a family of action preorders corresponding to its lattice of subsemigroups.

Example. let $(\mathbb{N},+)$ be the commutative monoid of non-negative integers under addition. The factorisation preorder of this semigroup is the total order on the natural numbers. Each non-trivial monogenic subsemigroup $(n)$ splits up the total ordering into $n$ classes containing all the different numbers with different values modulo $n$. The action of adding by two for example, splits up the total order into two chains containing the evens and the odds, and so on for each different modulus partition.

The fewer numbers that you can add by, the fewer numbers that you can reach from any element. The fewer numbers you can reach from any element, the smaller the preorder.

Non-commutative semigroups:

Left and right action preorders:
The difference between commutative semigroups and non-commutative semigroups is that in non-commutative semigroups you have both left and right actions. These produce their own respective action preorders. The quintessential example is the free semigroup of sequences and concatenation, which has separate preorders for suffix and prefix subsequences.

If we fix an element $a$ then the left action of $a$ is equal to $f(x) = a \circ x$ and the right action is equal to $f(x) = x \circ a$. In the case of sequences, we can either add a sequence to the front or the back of another sequence which produces different actions. Adding to the front of the sequence is increasing with respect to the suffix ordering and adding to the back is increasing with respect to the prefix ordering. So the two different types of preorder are characterized by the different actions they are increasing over. As always, there is an overall action preorder that contains the two other preorders as special cases.

The action preorders of sequences can be generalized to any semigroup, which produces left and right action preorders. Its not hard to see how Green's relations emerge from the symmetric components of these preorders

Subgroup actions and cosets:
It was previously proved that group actions are symmetric. Its not hard then to see that the left and right coset families of a subgroup are simply the symmetric action preorders induced by the subgroup with respect to left or right action. The coset families of normal subgroups form congruences, so the fact that the mapping from $N$ to the lattice of congruences $Con(G)$ is monotone is a special case of the monotonicity of the mapping $f$. Group congruences are symmetric action preorders.

Ordered groups:

Let $S$ be an ordered commutative group such that $a \leq b$ implies that $a + c \leq b + c$ for all $a,b,c$. Then if $0 \le a$ we have that $c \le c + a$, which means that addition by $a$ is increasing. In the other direction if $0 \ge a$ then action by $a$ is decreasing. Therefore, there are two different action preorders which are created by action by positive and negative elements. Yet, even with these two partial orders the factorisation preorder of $S$ is still the complete relation $S^2$ because $S$ is a group. $S$ then contains $\leq$ and $\geq$ as subpreorders.

This is a general case of the fact that in torsion-free groups, each element has action that follows some partial order even though the overall collection is a group. The two different actions: increasing and decreasing together inverse one another, which makes the structure a group.

• Positive elements are increasing
• Negative elements are decreasing

All subgroup actions are symmetric, as previously described. However, the subsemigroup action of a cancellative subsemigroup of a group can be antisymmetric and even a partial order as demonstrated by ordered groups.

Representation of preorders:

We demonstrated how action preorders emerge throughout mathematics from various algebraic structures. Now we will turn to the inverse question of how algebraic structures can be related to preorders.

Theorem. every preorder is the action preorder of some transformation semigroup

Proof. Let $P$ be a preorder. For each edge (a,b) in the preorder define a transformation that fixes all non-a elements of $P$ and that sets $a$ equal to $b$. Then collect all transformations formed this way with the identity transformation, and these transformations together generate a transformation semigroup with action preorder equal to $P$. Composition of transformations on an element corresponds to the transitive composition of paths. $\square$

Corollary. every equivalence relation is the action preorder of some permutation group

Proof. to construct a permutation group corresponding to an equivalence relation $P$ simply define a transposition for each pair of equal elements. These transpositions generate by their actions the equivalence relation $P$. The resulting permutation group is an orbit-symmetric group. $\square$

Every preorder is carved out by the action of some transformation semigroup. This provides a perspective on what order theory is: order theory is the theory of possibilities of actions.