Action congruences

The most useful tool of abstract algebra is a congruence. The appropriate categorical context to study the notion of a congruence is topoi theory. In particular, we want to study the congruences of actions. Let $(A,\alpha)$ be an $M$-set, then we say that $=_C$ is an action congruence provided that: $$\forall m \in M : \forall x,y \in A : x =_C y \implies \alpha_m x =_C \alpha_m y$$ The basic notion of a congruence is best understood by the topos of functions $Sets^{\to}$. When we are dealing with topoi of monoid actions on the other hand, we are dealing with a composite structure consisting of many different functions, and so we are dealing with the same concepts as in $Sets^{\to}$ but on a larger scale. In particular, a morphism in the topos of $M$-sets : $f : (A,\alpha) \to (B,\beta)$ defines a family of epimorphisms of functions $(f,f)$ for each $m \in M$:

By the correspondence between epimorphisms of functions and generalized congruences, it is not hard to see that $=_f$ is a congruence of each $m$ action on $A$. It follows that $=_f$ is then a congruence of the action on $A$. We now see the difference between the topos of functions and actions. The morphisms of functions define individual congruences, while morphisms of actions define congruences over a whole family of functions. This is characteristic of what happens in general as we move from primordial topoi to general topoi of set-valued functors.

Theorem. let $f : A \to B$ be an equivariant map of $M$-sets then the kernel $=_f$ is an action congruence of $A$

Proof. suppose that $f(x) = f(y)$ then by the fact that functions are identity-preserving we have that $\beta_m f(x) = \beta_m f(y)$. Then by equivariance it follows that both of these are also equal to $f(\alpha_m x) = f(\alpha_m y)$. $$x =_f y$$ $$\implies f(x) = f(y)$$ $$\implies \beta_m f(x) = \beta_m f(y)$$ $$\implies f(\alpha_m x) = \beta_m f(x) = \beta_m f(y) = f(\alpha_m y)$$ $$\implies f(\alpha_m x) = f(\alpha_m y)$$ $$\implies \alpha_m x = \alpha_m y$$ Then by the transitivity of the above diagram we have that $x =_f y() \implies \alpha_m x = \alpha_m y$ for each $m \in M$ which is what we wanted to show. Therefore, $=_f$ is an action congruence of $A$. $\square$

Topoi of monoid actions are concrete, and this classifies the kernels of the underlying morphisms of their functions. We can now define the quotient of a monoid action by an action congruence:

Definition. let $A$ be an $M$-set and $C$ an action congruence with respect to $A$ then $\frac{A}{C}$ is a quotient $M$-set of $C$ equivalence classes of $A$. As each $M$ action moves elements of $A$ between $C$ equivalence classes, the action of $M$ on $\frac{A}{C}$ moves $C$ equivalence classes to $C$ classes.

1. The objects of $\frac{A}{C}$ are all the $C$ equivalence classes of $A$
2. Then for each $m \in M$ and $c \in \frac{A}{C}$ there is an associated $C$ class $mc$
3. Then for each $m \in M$ and $c \in \frac{A}{C}$ there is a transition restriction map of $\alpha_m$ defined by $\alpha_m : c\to mc$ that maps elements of a $C$ class to its output $C$ class.

I now would like to show that we have a valid morphism $\pi_C : (A,\alpha) \to (\frac{A}{C},\beta)$ from an $M$-set to its quotient, and that this morphism satisfies the conditions of equivariance necessarily placed on each morphism of actions.

Theorem. the projection function $\pi_C : (A,\alpha) \to (\frac{A}{C},\beta)$ that maps a monoid action to its quotient is equivariant.

Proof. let $x \in A$ then we can get a $C$ class $\pi_C(x)$ associated to $x$. Let $m \in M$ then by condition (3) we can get a restriction map $\alpha_m : \pi_C(x) \to \beta_m\pi_C(x)$. Then we have that if $x \in \pi_C(x)$ we have that $\alpha_m x \in \beta_m\pi_C(x)$. Then by the fact that $\alpha_m x \in \beta_m\pi_C(x)$ we have that $\pi_C(\alpha_m x) = \beta_m(\pi_C(x))$. Therefore, $\pi_C$ is equivariant. $\square$

We can now consider quotients of monoid actions by action congruences to be determined categorically by epimorphisms. As is universally the case when dealing with congruences, the family of all congruences on a structure forms a lattice. In this case, this is the lattice of action congruences.

Lattices of action congruences:
Every object in algebra is associated with a twin pair of lattices: a lattice of subobjects and a lattice of congruences. Let $A$ be an $M$ set, then $Sub(A)$ is its distributive lattice of subobjects and $Con(A)$ is its lattice of action congruences.

Theorem. let $A$ be an $M$ set then (1) $A^2$ forms an action congruence and (2) action congruences are intersection closed.

Proof. (1) $A^2$ is the equivalence maximal congruence so we have trivially that $\top = x =_{A^2} y \implies mx =_{A^2} my = \top$ then for part (2) if $=_C$ and $=_D$ are action congruences then if $x =_C y \implies mx =_C mx$ and $x =_D y \implies mx =_D my$ then by combination of equivalences $x =_{C \cap D} y \implies mx =_{C \cap D} my$. $\square$

It follows from these two conditions that $Con(A)$ is a lattice. The specific property of intersection closure will be essential for further applications involving action congruences on monoid actions.

Example 1. let $C_2$ be the permutation group generated by the single permutation $(0,1),(2,3)$ then it has a lattice of action congruences of the form: \ The action congruence {{0,1},{2,3}} is equal to its orbit, and so all components of it are congruences. The other two congruences are not related to the orbit, and produce $C_2$ quotients determined by actions between the equivalence classes.

Example 2. let $C_4$ be the cyclic group generated by the single permutation $(0,1,2,3)$ then its lattice of action congruences is of the form: The only non-trivial action congruence of the cyclic group on four elements is {{0,2},{1,3}} which clearly has a $C_2$ quotient. This has no non-trivial identity congruences so it is transitive, but it has a non-trivial congruence so it is not primitive.

Example 3. primitive permutation groups are precisely the permutation groups that are action congruence free.

Another example that is worth considering is the smallest monoid action. Let $S$ be a set, and $M$ be the trivial monoid acting on it, then $Con(S)$ is the complete lattice of partitions $Part(S)$ and every equivalence relation is an action congruence. This can be converted into a theorem.

Theorem. let $M$ be the trivial monoid, and $S$ be an $M$-set then $Con(S) = Part(S)$.

Proof. let $=_P$ be an equivalence relation then in order for it to be an action congruence we must have $x =_P y \implies mx =_P my$ for all $m \in M$. As this is the trivial monoid, this reduces to $x =_P y \implies x =_P y$, which is a tautology $\top$ and so it is true for every $P \in Part(S)$. Therefore, every equivalence relation is a congruence of the trivial monoid. $\square$

In general, the topos of monoid actions of a trivial monoid is equivalent to the topos of sets, and so lattices of congruences reduce to the lattices of partitions of sets.

Theorem. let $A$ be an $M$ set and suppose $D$ is an action congruence of $\frac{A}{C}$ for some $C$, then $D$ induces an action congruence on $A$.

Proof. by the fact that quotients by action congruences are equivariant mappings, we can form the following morphism sequence in the topos of monoid actions: $$A \to \frac{A}{C} \to \frac{(\frac{A}{C})}{D}$$ By the fact that the kernels of equivariant maps are action congruences, we can form an action congruence of the composite of this mapping, which is a congruence on $A$. The resulting equivalence has more equal pairs then $C$.

Definition. the orbit of a monoid action is its equivalence minimal identity quotient congruence.

Corollary. let $M$ be a monoid action on $A$, $P$ its orbit, and $Q$ any equivalence relation with $P \subseteq Q$ then $Q$ is an action congruence.

Proof. (1) the quotient of any monoid action by its orbit is a trivial monoid action (2) all equivalences on trivial monoid actions are congruences (3) by the fact that action congruences on quotient actions induce action congruences we can produce an action congruence on $A$ to get each parent of $P$. $\square$

It follows that the lattice of action congruences with identity quotients is nothing more then a principal filter in the lattice of partitions $Part(A)$ induced by the orbit. It is therefore order isomorphic to a partition lattice.

For a trivial monoid action, every equivalence relation is an action congruence. Then for larger monoid actions, there are fewer congruences. This is formalized in the antitone relationship between subsemigroups and action congruences.

Theorem. let $T$ be a transformation semigroup acting on a set $S$ and let $Con : Sub(S) \to \wp(Part(S))$ be the map from the lattice of subsemigroups of $S$ to families of action congruences. Then $Con$ is antitone.

Proof. let $T_1 \subseteq T_2$ be transformation semigroups. Suppose that $C$ is an action congruence of $T_2$ then we have: $$\forall t \in T_2 : x =_C y \implies t(x) =_C t(y)$$ By the fact that $T_1 \subseteq T_1$ we have that $\forall t : t \in T_1 \implies t \in T_2$ and so it follows that: $$\forall t \in T_1 : t \in T_2 \implies (\forall x,y : x =_C y \implies t(x) =_C t(y))$$ It follows then that $C$ is an action congruence on $T_1$. Then by the fact that smaller subsemigroups have more congruences, the mapping $Con$ is antitone. $\square$

This is a useful means of relating the lattice of subsemigroups to lattices of congruences. In general, action congruences and semigroup congruences are not the same. The former is based upon topoi of monoid actions and the later is based upon topoi of functions.

Action congruences and subsemigroups:
A fundamental part of the theory of action congruences is how we can use them to form subsemigroups of a transformation monoid. If a transformation semigroup has an action congruence, then the mapping to its quotient produces a semigroup congruence.

Theorem. let $f,g : S \to S$ be transformations and suppose that $C$ i an action congruence for both of them. Then it is an action congruence for $g \circ f$.

Proof. by definition we have that $(x =_C y) \implies (f(x) =_C f(y))$ and $(x =_C y) \implies (g(x) =_C g(y))$. We can plug $(f(x) =_C f(y))$ into the later to get $g(f(x)) =_C g(f(x))$. This leads to the following chain of implications: $$x =_C y \implies f(x) =_C f(y) \implies g(f(x)) =_C g(f(y))$$ By transitvity we have that $x =C y \implies g(f(x)) =_C g(f(y))$. It follows that $C$ is action congruence of $g \circ f$. $\square$

The full transformation monoid on a set $End(S)$ is simply the endomorphism monoid of a topos. It is typically denoted by $T_S$. We can use the preceding theorem to acquire a transformation submonoid of $T_X$ determined by an equivalence relation $P$ that has $P$ as an action congruence.

Definition. let $S$ be a set partitioned by $P$ then $Acs(P)$ is the action congruence semigroup (ACS) determined by $P$ which is the set of all transformations with $P$ as an action congruence. By the previous theorem $Acs(P)$ is composition closed, and so it clearly forms a subsemigroup.

By the antitoneness of action congruences, we have that the set of all transformation semigroups with $C$ as a congruence is subsemigroup closed. By composition closure, we see that it is actually a principal ideal generated by $Acs(C)$. The inclusion map $f : Sub(Acs(C)) \to Sub(T_x)$ is then adjoint to the action congruence restriction function, which takes any transformation semigroup and produces the subset of its transformations that have $C$ as a congruence.

The family of all action congruence subsemigroups forms a suborder of $T_x$. Therefore, we can form transformation semigroups with a given set of action congruences, by the intersection of action congruence semigroups. The intersection of these subsemigroups is not equal to the action congruence generated by their intersection but we do have:

Corollary. $Acs(P) \cap Acs(Q) \subseteq Acs(P \cap Q)$.

Proof. let $T$ be a transformation with $P$ and $Q$ as action congruences. By the fact that action congruences form an intersection subsemilattice $T$ has $P \cap Q$ as an action congruence. $\square$

Much like categories, transformation semigroups are associated with an inherent dichotomy. There are two types of constituents of a transformation semigroup: elements $S$ and transformations $T$. These are associated with two different types of congruences on two different sets:

• Action congruences: partitions of the set of elements $S$
• Semigroup congruences: partitions of the set of transformations $T$

The two concepts are related because if a transformation semigroup $X$ has an action congruence $C$ associated with it, then we can form a semigroup congruence on it from the action congruence. This allows us to produce semigroup congruences from action congruences. The key to this is a semigroup homomorphism from $X$ to $\frac{X}{C}$.

Theorem. let $q : X \to \frac{X}{C}$ be a function from a transformation semigroup $X$ to $\frac{X}{C}$ that takes each $T \in X$ to its quotient transformation $\frac{T}{C}$. Then $q$ is a homomorphism of semigroups.

Proof. let $T_1, T_2$ be two transformations in $X$. We want to show that $\frac{T_2}{C} \circ \frac{T_1}{C} = \frac{T_2 \circ T_1}{C}$. Let $a$ be an element of the underlying set of elements $S$ of the transformation semigroup $X$. Then $a \in \pi_C(a)$ and $T_1(a) \in \pi_C(T_1(a))$. Let $C_1$ denote $\pi_C(a)$ and $C_2$ denote $\pi_C(T_1(a))$. Then by the definition of quotients we have: $$x \in C_1 \wedge T_1(x) \in C_2 \implies \frac{T_1}{C}(C_1) = C_2$$ Let $C_3$ denote $\pi(T_2(T_1(a))$. Then we have that $T_1(a) \in C_2$ and $T_2(T_1(a)) \in C_3$. Then by the same process we have: $$T_1(a) \in C_2 \wedge T_2(T_1(a)) \in C_3 \implies \frac{T_2}{C}(C_2) = C_3$$ By our first argument we have $\frac{T_1}{C}(C_1) = C_2$ and by our second we have $\frac{T_2}{C}(C_2) = C_3$ so by composition $\frac{T_2}{C}(\frac{T_1}{C}(x)) = C_3$. We also have that $T_2(T_1(x)) \in C_3$ so $\frac{T_2 \circ T_1}{C}(C_1) = C_3$. Therefore, for every $C_1 \in C$ we have that: $$\frac{T_2}{C}(\frac{T_1}{C}(C_1)) = C_3 = \frac{T_2 \circ T_1}{C}(C_1)$$ It follows from this that the quotient function $q : S \to \frac{S}{C}$ that takes each transformation to its quotient by $C$ is a semigroup homomorphism. $\square$

It is an immediate corollary of the first homomorphism theorem of semigroups that this produces a semigroup congruence from an action congruence. The semigroup congruence is the defined by the kernel of $q$. This congruence equates two transformations if they have equal quotient actions.

Corollary. let $X$ be a transformation semigroup with a set of elements $S$ and a set of transformations $T$. Let $C$ be an action congruence on $S$ then the equivalence relation $E$ that equates two transformations if they coincide as quotient actions on $C$ is a semigroup congruence on the set of transformations $T$.

Therefore, we can use action congruences to produce semigroup congruences. We can also use them to form subsemigroups in two different ways. The first is by composition of an inclusion map into a transformation semigroup, which by composition produces an inclusion map into its quotient semigroup. The second is by reflecting subsemigroups of the quotient semigroup $\frac{X}{C}$ back into $X$.

Lemma. let $f: A \to B$ be a semigroup homomorphism, then $f$ reflects subsemigroups.

Proof. let $S \subseteq B$ be a subsemigroup of $B$. Let $x, y \in A$ such that $f(x),f(y) \in S$. Then by the fact that $S$ is a subsemigroup $f(x)f(y) \in S$. Then $f(xy) = f(x)f(y) \in S$. It follows that $f^{-1}(S)$ is composition closed. $\square$

Let $X$ be a transformation semigroup, with action congruence $C$, and associated map $q : X \to \frac{X}{C}$. Then we can use any subsemigroup of the quotient semigroup to produce a subsemigroup of $X$ by inverse images. In particular, if we have the trivial subsemigroup of $\frac{X}{C}$ this yields orbit restrictions.

Definition. Let $P$ be a partition a set $S$ then $Acs(P)$ is a semigroup with $P$ as an action congruence. This yields a map $q : Acs(P) \to \frac{Acs(P)}{P}$. The orbit congruence semigroup $Ocs(P)$ is the inverse image by $q$ of the trivial subsemigroup. The orbit restriction of a transformation semigroup by $P$ is defined by intersection with $Ocs(P)$.

By the nature of reflections we obviously have $\forall P : Ocs(P) \subseteq Acs(P)$. The transformations of $Ocs(P)$ have $\forall T \in Ocs(P) : x =_P T(x)$. This means that the property $P$ is completely invariant under the actions of the semigroup. Invariance of $T$ with respect to $P$ simply means that $T$ has identity quotient by the action congruence $P$. These orbit congruence semigroups have an interesting property not shared by general action congruence semigroups.

Theorem. $Ocs(P) \cap Ocs(Q) = Ocs(P \cap Q)$

Proof. let $T \in Ocs(P) \cap Ocs(Q)$ then we have two equivalences which can be combined: $$x =_P T(x) \wedge x =_Q T(x)$$ $$x =_{P \cap Q} T(x)$$ Therefore, $x$ is invariant under $P \cap Q$. It follows that $Ocs(P) \cap Ocs(Q) \subseteq Ocs(P \cap Q)$. Recall that when an action is invariant under a given equivalence relation, it is larger under all larger equivalence relations. We have the following inclusions: $$P \cap Q \subseteq P, Q$$ Therefore, actions that preserve $P \cap Q$ preserve both $P$ and $Q$, and so transformations in $Ocs(P \cap Q)$ are in both $Ocs(P)$ and $Ocs(Q)$. Therefore, $Ocs(P \cap Q) \subseteq Ocs(P) \cap Ocs(Q)$. By combining these two inclusions we get that $Ocs(P) \cap Ocs(Q) = Ocs(P \cap Q)$. $\square$

This makes orbit congruence semigroups a lot easier to deal with and reason about. In particular, we immediately have the following result.

Corollary. $Ocs : Part(S) \to Sub(T_S)$ is a bounds preserving meet semilattice homomorphism.

Proof. the fact that it is a meet semilattice homomorphism is proved by the preceding theorem. Then let $M$ be the minimal equivalence $\{(x,y) : x=y\}$ and $S^2$ the maximal one. Then $Ocs(S^2)$ is the full transformation monoid, as the equivalence on $S^2$ collapses to nothing and $Ocs(M)$ is the trivial monoid, as only the trivial action preserves everything. $\square$

It is not hard to see that the image of this map is a lattice-ordered bounds-maintaining meet subsemilattice of subsemigroups. Then this family of subsemigroups is associated with a closure operation, which takes any transformation monoid and returns the largest transformation monoid with that given orbit.

In general, congruences are our essential guide to the theory of actions. We consider actions on a set and form transformation monoids of actions on it, primarily from action congruence semigroups with selected quotients. This most effectively allows us to create a theory of monoid actions.