Previously, we talked about groups with additonal structure. A more general concept is that of a category with additional structure, the most important example of which is a pre-additive category. Pre-additive categories are categories whose hom classes are commutative groups, such that the group distributes over composition. A (not necessarily commutative) ring is a pre-additive category with a single object.
Non-commutative rings of actions:
Let $C$ be a concrete category and $X \in Ob(C)$ then $End(X)$ is a monoid action on the underlying set of $X$. A wide variety of different monoid actions emerge from concrete categories like posets, graphs, etc. We can also explore the endomorphism monoid of a commutative group. In this case, pre-additive categories add additional perspective to the theory of commutative groups.
By taking the category of commutative groups to be an abelian category, we get that $End(G)$ for any commutative group is an endomorphism ring. Therefore the actions which previously only took on the structure of a monoid, now have the structure of a ring. This is the basic context in which non-commutative rings emerge and become indispensible. We naturally consider rings to be commutative starting with the ring of integers $\mathbb{Z}$, but here we see how some non-commutative rings emerge even in problems of commutative algebra.
Let $R$ be a ring, then the category of $R$-modules is an abelian category. In this case, for any $R$-module $M$ we have that $End(M)$ is the matrix ring of the module $M$. A more familiar case might be the matrix ring of a vector space over a field. These matrix rings are amongst the most important non-commutative rings, and they emerge as rings of actions on a set. Therefore, non-commutative rings are an indispensible part of the modern algebraic theory of actions.
Concrete rings:
A concrete pre-additive category is a pre-additive category $C$ with a faithful set-valued functor $F : C \to Sets$. This makes it so that all the elements of the ring are functions acting on a set. In this case, we have a multiplicative monoid action on the underlying set of the concrete ring. We see that the matrix ring $End(V)$ is a concrete ring whose elements are functions acting on the underlying set of vectors. Concrete rings proide a natural categorical description of non-commutative rings of actions.
Links:
Preadditive and additive categories
Sunday, April 25, 2021
Sunday, April 11, 2021
Congruences of structured groups
If we have a group $G$ then all congruences of $G$ can be determined by its sublattice of normal subgroups. This is determined by the action preorders of normal subgroups, which are symmetric preorders (equivalence relations), and congruences of $G$ by normality.
Suppose that $(S,+,...)$ is a group $(S,+)$ with some additional structure $(...)$ on it. Then we can use the same procedure to get group congruence of $+$ from normal subgroups but these congruences need not be congruences of $S$. In order to get full congruences of the structured group, we need a special subset of congruence-forming normal subgrops. These are the subset of normal subgroups that produce congruences by their cosets.
Definition. let $(S,+,...)$ be a group with additional structure. Then a congruence-producing normal subgroup is a normal subgroup of $+$ whose cosets are a congruence of the entire structure $S$.
We can use this to formalize the congruencization mapping \[f: (K \subseteq Sub(S)) \to Con(S) \] by setting $K$ equal to the family of all congruence-producing normal subgroups of the structured group. Then this converts the normal subgroup into its congruence by taking cosets. In the opposite direction we have a monomorphism: \[ g : Con(S) \to Sub(S) \] This monomorphism is an order-embedding from the lattice of congruences into the lattice of subalgebras. In the simplest case of a group, the lattice of congruences of the group can be embedded in the sublattice of normal subgroups. The function of the monomorphism $g$ is determined by taking the kernel subalgebra of the congruence, which is the unique additive identity element in the quotient algebra.
In commutative algebra we have that ideals form congruences. On the other hand, in non-commutative algebra we have that two-sided ideals (distinguished from right and left ideals by non-commutativity) form congruences. Likewise, submodules determine congruences.
Groups, commutative rings, non-commutative rings, modules, vector spaces, etc are all examples of structured groups. Categories of structured groups are distinguished by the existence of kernel representations of congruences. Most abelian categories in homological algebra for example emerge from structured groups like R-modules. Even in the case of sheaves of commutative groups, the abelian category is constructed from some underlying group structure.
The need to form a separate theory of congruences emerges when considering semigroups, semirings, and other semi-structures that don't have any group operations assigned to them. Classical abstract algebra avoids this by assigning a group to everything, but a particularly interesting new direction is the general theory of structured categories. General structured categories require a separate theory of congruences. Monoid actions are another application of congruences, which can play a central role in the algebraic theory of computation.
Previously:
Subalgebra related congruences
Suppose that $(S,+,...)$ is a group $(S,+)$ with some additional structure $(...)$ on it. Then we can use the same procedure to get group congruence of $+$ from normal subgroups but these congruences need not be congruences of $S$. In order to get full congruences of the structured group, we need a special subset of congruence-forming normal subgrops. These are the subset of normal subgroups that produce congruences by their cosets.
Definition. let $(S,+,...)$ be a group with additional structure. Then a congruence-producing normal subgroup is a normal subgroup of $+$ whose cosets are a congruence of the entire structure $S$.
We can use this to formalize the congruencization mapping \[f: (K \subseteq Sub(S)) \to Con(S) \] by setting $K$ equal to the family of all congruence-producing normal subgroups of the structured group. Then this converts the normal subgroup into its congruence by taking cosets. In the opposite direction we have a monomorphism: \[ g : Con(S) \to Sub(S) \] This monomorphism is an order-embedding from the lattice of congruences into the lattice of subalgebras. In the simplest case of a group, the lattice of congruences of the group can be embedded in the sublattice of normal subgroups. The function of the monomorphism $g$ is determined by taking the kernel subalgebra of the congruence, which is the unique additive identity element in the quotient algebra.
In commutative algebra we have that ideals form congruences. On the other hand, in non-commutative algebra we have that two-sided ideals (distinguished from right and left ideals by non-commutativity) form congruences. Likewise, submodules determine congruences.
Groups, commutative rings, non-commutative rings, modules, vector spaces, etc are all examples of structured groups. Categories of structured groups are distinguished by the existence of kernel representations of congruences. Most abelian categories in homological algebra for example emerge from structured groups like R-modules. Even in the case of sheaves of commutative groups, the abelian category is constructed from some underlying group structure.
The need to form a separate theory of congruences emerges when considering semigroups, semirings, and other semi-structures that don't have any group operations assigned to them. Classical abstract algebra avoids this by assigning a group to everything, but a particularly interesting new direction is the general theory of structured categories. General structured categories require a separate theory of congruences. Monoid actions are another application of congruences, which can play a central role in the algebraic theory of computation.
Previously:
Subalgebra related congruences
Sunday, March 28, 2021
Visualisation of Young diagrams in Clojure
This takes a Young diagram expressed as an additive partition and converts it into an image using the Java standard library. Then it creates a Swing frame for you to display the image. Young diagrams are important in a wide variety of mathematical contexts from number theory to abstract algebra.
(import java.awt.image.BufferedImage)
(import javax.swing.JFrame)
(import javax.swing.JLabel)
(import javax.swing.ImageIcon)
(defn determine-coordinates
[coll]
(let [sorted-seq (sort > (seq coll))]
(apply
concat
(map-indexed
(fn [x v]
(map
(fn [y]
[x y])
(range 0 v)))
sorted-seq))))
(defn signature-image
[sig block-size]
(let [coords (determine-coordinates sig)
sig-width (count sig)
sig-height (if (empty? sig) 0 (apply max sig))
padding-size (int (/ block-size 2))
img-width (+ (* block-size (inc sig-width)))
img-height (+ (* block-size (inc sig-height)))
img (BufferedImage.
img-width
img-height
BufferedImage/TYPE_INT_RGB)
g (.createGraphics img)]
(.setColor g java.awt.Color/WHITE)
(.fillRect g 0 0 img-width img-height)
(.setColor g java.awt.Color/BLACK)
(doseq [coord coords]
(let [[x y] coord]
(.drawRect
g
(+ padding-size (* x block-size))
(- img-height
(+ padding-size
(* (inc y) block-size)))
block-size
block-size)))
img))
(defn display-image
[img]
(let [f (JFrame.)]
(.add (.getContentPane f)
(JLabel.
(ImageIcon. img)))
(.pack f)
(.setVisible f true)))Saturday, March 27, 2021
Image equivalence classes
The image endofunctor of the category of sets $Im : Sets \to Sets$ maps any function $f: A \to B$ to $Im(f) : \wp(A) \to \wp(B)$. The image of $Im(f)$ is a power set equal to $\wp(I)$ where I is the image of $f$. The image is therefore just another power set. On the other hand, the equivalence classes of $Im(f)$ are a type of set system which you may not have seen before.
Proposition. the equivalence classes of $Im(f) : \wp(A) \to \wp(B)$ are upper bounded convex sets whose minima are the maximal cliques of a cocluster graph.
The family of maximal representatives of $Im(f)$ forms a partition topology, and so these equivalence classes are equivalent to those of the closure of a partition topology. If we treat a partition as a cluster graph, then clearly the minimal generators of any image are maximal independent sets because equivalence-equal elements are redundant.
By complementation, they are maximal cliques of a cocluster graph. Which means that the minimal sets are a maximal clique family. This is interesting because not all sperner families are maximal clique families. The upper boundedness of image equivalence classes is a special case of the fact that $Im(f)$ is the lower adjoint of a monotone Galois connection. The partition topology of maximal representatives is the image of the inverse image which is an upper adjoint.
Example 1.
Example 2.
Example 3.
Proposition. the equivalence classes of $Im(f) : \wp(A) \to \wp(B)$ are upper bounded convex sets whose minima are the maximal cliques of a cocluster graph.
The family of maximal representatives of $Im(f)$ forms a partition topology, and so these equivalence classes are equivalent to those of the closure of a partition topology. If we treat a partition as a cluster graph, then clearly the minimal generators of any image are maximal independent sets because equivalence-equal elements are redundant.
By complementation, they are maximal cliques of a cocluster graph. Which means that the minimal sets are a maximal clique family. This is interesting because not all sperner families are maximal clique families. The upper boundedness of image equivalence classes is a special case of the fact that $Im(f)$ is the lower adjoint of a monotone Galois connection. The partition topology of maximal representatives is the image of the inverse image which is an upper adjoint.
Example 1.
Friday, March 26, 2021
Actions on posets
Preorders and monoid actions are deeply related. Starting with a monoid action, we can get a preorder. This preorder then determines the lattice of subobjects of the monoid action. In the other direction, when considering actions on preorders we can get additional types of monoid actions. This leads to the following ontology of posetal actions, all of which form monoids:
Typically, when considering the endomorphisms monoid $End(X)$ of an object $X$ of a category $C$ we can create a full theory of actions, but posets are different because their strong link with actions. In order to continue further, it is useful to add a posetal structure on the hom classes of posetal transformations.
Definition. let $(P, \subseteq), (Q, \subseteq)$ be partially ordered sets then we can partially order the hom class $Hom(P,Q)$ so that $f, g \in Hom(P,Q)$ have $f \subseteq g$ iff $\forall x : f(x) \subseteq g(x)$.
Let $(P, \subseteq)$ be a poset, then this can even be applied to $T_P$ the set of all transformations on $P$. Then we have taht a transformation $f$ is increasing iff $id_P \subseteq f$ and it is decreasing iff $f \subseteq id_P$. It follows that increasing transformations are the principal filter of the identity function $id_P$ in the pointwise ordering, and decreasing transformations are its principal filter. The only transformation that is both increasing and decreasing is therefore the identity $id_P$.
Theorem. The monoid of increasing actions on a poset is R-trivial.
Proof. Suppose that we have $f,g$ that are R-related then we have that $af = g$ and that $bg = f$. By the fact that each action is increasing we have that $\forall x : x \subseteq f(x) \subseteq a(f(x)) = g(x)$. In the other direction, we have that $\forall x : x \subseteq g(x) \subseteq b(g(x)) = f(x)$. The statement that $f(x) \subseteq g(x)$ and $g(x) \subseteq f(x)$ contradicts antisymmetry, so $f,g$ cannot be R-related. $\square$
Although it is the case that increasing actions on a poset are R-trivial, we cannot get that they are L-trivial in general, however, in the restricted case of increasing monotone actions then we can get L-triviality.
Theorem. The monoid of increasing monotone actions is D-trivial
Proof. Suppose that $f \subseteq_L g$ then $\exists a : fa = g$. We have that $\forall x : x \subseteq a(x) \subseteq f(a(x))$. By monotonicity, $x \subseteq a(x)$ implies $f(x) \subseteq f(a(x))$ now since $f(a(x)) = g(x)$ this implies $f(x) \subseteq g(x)$. So therefore, if $f,g$ are in the same L class then we have $f(x) \subseteq g(x)$ and $g(x) \subseteq f(x)$ which contradicts antisymmetry. Therefore, the monoid of increasing monotone actions is L-trivial. It is already R-trivial, so if it is both L-trivial and R-trivial then it is D-trivial. $\square$
One corollary that is worth mentioning, is that the poset of monoid actions is group-free. This distinguishes increasing actions from monotone ones which can include the group of automorphisms.
Corollary. The monoid of increasing actions is group-free
Proof. R-trivial $\implies$ H-trivial $\implies$ group-free $\square$
Let $C$ be the category of partial orders and monotone maps. Then we can easily make the following observation about the group of automorphisms $Aut(P)$ of a finite poset $P$.
Theorem. Let $P$ be a finite poset. Then $Aut(P)$ is never increasing/decreasing.
Proof. We can rank the elements of $P$ in the following form: $R(x)$ is equal to the maximum height of the principal ideal of $x$. Then if we have $x \subset y$ we must have that $R(x) \lt R(y)$. Permutable elements must have the same invariant rank, therefore they must be incomparable. $\square$
It is wrong to assume that $Aut(P)$ is never increasing/decreasing in general because it may not always be possible to rank elements of a poset. In particular, there are order-automorphisms of the dense total order $(\mathbb{Q}, \subseteq)$ because no well-ordered ranking can be established on it.
Corollary. The orbits of the group action of a finite partially ordered set $Aut(P)$ are an equivalence subrelation of the partition of $P$ into co-connected components.
The automorphism group of a finite weak order is an orbit symmetric group, and the orbits of the group action coincide with the connected components of the complement of the comparability graph.
Definition. let $(P, \subseteq), (Q, \subseteq)$ be partially ordered sets then we can partially order the hom class $Hom(P,Q)$ so that $f, g \in Hom(P,Q)$ have $f \subseteq g$ iff $\forall x : f(x) \subseteq g(x)$.
Let $(P, \subseteq)$ be a poset, then this can even be applied to $T_P$ the set of all transformations on $P$. Then we have taht a transformation $f$ is increasing iff $id_P \subseteq f$ and it is decreasing iff $f \subseteq id_P$. It follows that increasing transformations are the principal filter of the identity function $id_P$ in the pointwise ordering, and decreasing transformations are its principal filter. The only transformation that is both increasing and decreasing is therefore the identity $id_P$.
Theorem. The monoid of increasing actions on a poset is R-trivial.
Proof. Suppose that we have $f,g$ that are R-related then we have that $af = g$ and that $bg = f$. By the fact that each action is increasing we have that $\forall x : x \subseteq f(x) \subseteq a(f(x)) = g(x)$. In the other direction, we have that $\forall x : x \subseteq g(x) \subseteq b(g(x)) = f(x)$. The statement that $f(x) \subseteq g(x)$ and $g(x) \subseteq f(x)$ contradicts antisymmetry, so $f,g$ cannot be R-related. $\square$
Although it is the case that increasing actions on a poset are R-trivial, we cannot get that they are L-trivial in general, however, in the restricted case of increasing monotone actions then we can get L-triviality.
Theorem. The monoid of increasing monotone actions is D-trivial
Proof. Suppose that $f \subseteq_L g$ then $\exists a : fa = g$. We have that $\forall x : x \subseteq a(x) \subseteq f(a(x))$. By monotonicity, $x \subseteq a(x)$ implies $f(x) \subseteq f(a(x))$ now since $f(a(x)) = g(x)$ this implies $f(x) \subseteq g(x)$. So therefore, if $f,g$ are in the same L class then we have $f(x) \subseteq g(x)$ and $g(x) \subseteq f(x)$ which contradicts antisymmetry. Therefore, the monoid of increasing monotone actions is L-trivial. It is already R-trivial, so if it is both L-trivial and R-trivial then it is D-trivial. $\square$
One corollary that is worth mentioning, is that the poset of monoid actions is group-free. This distinguishes increasing actions from monotone ones which can include the group of automorphisms.
Corollary. The monoid of increasing actions is group-free
Proof. R-trivial $\implies$ H-trivial $\implies$ group-free $\square$
Let $C$ be the category of partial orders and monotone maps. Then we can easily make the following observation about the group of automorphisms $Aut(P)$ of a finite poset $P$.
Theorem. Let $P$ be a finite poset. Then $Aut(P)$ is never increasing/decreasing.
Proof. We can rank the elements of $P$ in the following form: $R(x)$ is equal to the maximum height of the principal ideal of $x$. Then if we have $x \subset y$ we must have that $R(x) \lt R(y)$. Permutable elements must have the same invariant rank, therefore they must be incomparable. $\square$
It is wrong to assume that $Aut(P)$ is never increasing/decreasing in general because it may not always be possible to rank elements of a poset. In particular, there are order-automorphisms of the dense total order $(\mathbb{Q}, \subseteq)$ because no well-ordered ranking can be established on it.
Corollary. The orbits of the group action of a finite partially ordered set $Aut(P)$ are an equivalence subrelation of the partition of $P$ into co-connected components.
The automorphism group of a finite weak order is an orbit symmetric group, and the orbits of the group action coincide with the connected components of the complement of the comparability graph.
Wednesday, March 24, 2021
Self-induced actions
It is common to represent a semigroup, monoid, or group by action on some set, but in the case where an action is not given to us we can recover one by the action of the semigroup on itself. This process can even be applied to magmas, to get the action of a magma on itself. In that case, the lack of associativity means that the self-induced actions need not be complete, which produces a subset of a semigroup. This leads to an interesting connection between semigroup theory and magma theory.
Let $S$ be a set, $* : S^2 \to S$ be a magma, and $T_{S}$ be the complete transformation monoid on $S$, whose members are actions $f: S \to S$. Then we can define the left and right actions of elements by mappings: \[ L : S \to T_{S} \] \[ L(a) = \lambda(x) (a*x) \] \[ R : S \to T_{S} \] \[ R(a) = \lambda(x) (x*a) \] The following elementary observations are immediate from these definitions:
The image of the L,R mappings are both subsets of $T_{S}$. For general magmas, these action systems $Im(L),Im(R)$ do not need to be semigroups, however, they are always subsets of a semigroup and partial semigroups. Their closures are the $L,R$ action semigroups.
Equal actions:
The L,R mappings don't need to be mono, instead they can produce equal actions for different values. This produces ${=}L, {=}R$ equivalence relations on $S$.
Example 1. in a constant semigroup all L,R actions are equal and so both the L,R mappings are constant.
The special case of semigroups:
In the special case of semigroups, $L,R$ are actually semigroup homomorphisms. Their image action systems are semigroups and the equivalence relations ${=}L,{=}R$ are congruences. This is clarified in the following theorem. By the first isomorphism theorem, we have isomorphisms $\frac{S}{{=}L} \cong Im(L)$ and $\frac{S}{{=}R} \cong Im(R)$.
Theorem. $L : S \to T_S$ and $R : S \to T_S^{Op}$ are semigroup homomorphisms.
Proof. By definition $L(ab) = \lambda(x) (ab)x$ by associativity $(ab)x = a(bx)$ but then $a(bx)$ is equal to $(L(a) \circ L(b))(x)$. Therefore, $L(ab) = L(a) \circ L(b)$. In other direction, $R(ab) = \lambda (x) x(ab)$. Then by associativity $x(ab) = (xa)b$. This is then equal to $(R(b) \circ R(a))(x)$. $R(ab) = R(b) \circ R(a)$ which is a homomorphism in the opposite direction.
Remarks. the distinction between $T_S$ and $T_S^{Op}$ doesn't really matter and is dependent upon our notation for composition. All that matters is that $L$ and $R$ are opposite directions, so their corresponding semigroups homomorphisms are opposite to one another.
In the case of semigroups, $L$ and $R$ can be seen as reducing semigroups to their faithful counterparts. The fact that group's are faithful directly leads to Cayley's theorem which is the representation of any group by the group action defined by $L$.
The special case of groups:
The action of a group on itself is simply transitive, which means that all elements are contained in the same orbit and all stabilizers are trivial. The former is a consequence of the existence of inverses and the later is a consequence of cancellativity.
The images $Im(L),Im(R)$ of the L and R mappings are both subsets of the semigroup $T_S$. Their closures are therefore both members of $Sub(T_S)$. They both must therefore have a semigroup join, which contains all actions both left and right.
Definition. the $J$ semigroup is the semigroup join of the $L$ and $R$ action semigroups, which are defined as the closures of the images of the $L$ and $R$ mappings.
$J$ is the ultimate semigroup defining actions of a magma, semigroup, or other related structure on itself.
Inclusions:
The three semigroups $L,R,J$ form a three element suborder of $Sub(T_S)$ with $L,R \subseteq J$. The intersection $L \cap R$ contains at least all actions by central elements.
Example 1. consider the following non-commutative monogenic magma
In the other direction we get the semigroup {[1,2],[2,2]} which is a subsemigroup, therefore this semigroup is R action composition closed. This semigroup action is the total order semilattice on two elements.
Example 2. let $\mathbb{Z}_+$ be the positive integers then $^ : \mathbb{Z}_+^2 \to \mathbb{Z}_+$ is a magma.
The right actions of exponentation are composition closed because $(a^x)^y = a^{xy}$. In this case, the operation is not associative so composition is determined by an operation other then exponentation itself. In this case, we have a semigroup homomorphism $Im(R) \to *$.
The left actions of exponentation on the other hand are not composition closed. When we have $a^(b^x)$ there is no way to reduce it to a single exponentation. Left actions are not composable at all unless one of them is equal to one, which is the trivial case. The semigroup closure of left actions is the set of all exponentation towers closed under composition.
As $Im(L)$ is a subset of a semigroup, we can form a Cayley digraph of it consisting of all pairs of elements $(a,b)$ such that there exists some $c$ such that $c^a = b$. We can call this the 'base of' binary relation, as elements are related provided that the first is a base of the other with respect to some exponent. This binary relation is not transitive because 3 is a base of 9, 9 is a base of 512, and 3 is not a base of 512.
Left and right actions:
Introduction:Let $S$ be a set, $* : S^2 \to S$ be a magma, and $T_{S}$ be the complete transformation monoid on $S$, whose members are actions $f: S \to S$. Then we can define the left and right actions of elements by mappings: \[ L : S \to T_{S} \] \[ L(a) = \lambda(x) (a*x) \] \[ R : S \to T_{S} \] \[ R(a) = \lambda(x) (x*a) \] The following elementary observations are immediate from these definitions:
- An element is L/R cancellative, unital, or zero if its corresponding L/R actions are mono, unital, or constant.
- The centralizer of an element is the equalizer of its left and right actions.
- An element is central if its left and right actions coincide.
The image of the L,R mappings are both subsets of $T_{S}$. For general magmas, these action systems $Im(L),Im(R)$ do not need to be semigroups, however, they are always subsets of a semigroup and partial semigroups. Their closures are the $L,R$ action semigroups.
Equal actions:
The L,R mappings don't need to be mono, instead they can produce equal actions for different values. This produces ${=}L, {=}R$ equivalence relations on $S$.
Example 1. in a constant semigroup all L,R actions are equal and so both the L,R mappings are constant.
[[1 1 1] [1 1 1] [1 1 1]]Example 2. in the following pure rectangular band $L$ is mono and always maps to a different constant function and $R$ is constant and always maps to the same identity action.
[[1 1 1] [2 2 2] [3 3 3]]In general semigroups there are often equal actions, as demonstrated in the above actions but that doesn't need to be the case. A magma is called left faithful or right faithful, provided that the left and right self actions $L,R$ are monomorphisms. Groups are clearly left and right faithful because if they had equal actions that would violate cancellativity.
The special case of semigroups:
In the special case of semigroups, $L,R$ are actually semigroup homomorphisms. Their image action systems are semigroups and the equivalence relations ${=}L,{=}R$ are congruences. This is clarified in the following theorem. By the first isomorphism theorem, we have isomorphisms $\frac{S}{{=}L} \cong Im(L)$ and $\frac{S}{{=}R} \cong Im(R)$.
Theorem. $L : S \to T_S$ and $R : S \to T_S^{Op}$ are semigroup homomorphisms.
Proof. By definition $L(ab) = \lambda(x) (ab)x$ by associativity $(ab)x = a(bx)$ but then $a(bx)$ is equal to $(L(a) \circ L(b))(x)$. Therefore, $L(ab) = L(a) \circ L(b)$. In other direction, $R(ab) = \lambda (x) x(ab)$. Then by associativity $x(ab) = (xa)b$. This is then equal to $(R(b) \circ R(a))(x)$. $R(ab) = R(b) \circ R(a)$ which is a homomorphism in the opposite direction.
Remarks. the distinction between $T_S$ and $T_S^{Op}$ doesn't really matter and is dependent upon our notation for composition. All that matters is that $L$ and $R$ are opposite directions, so their corresponding semigroups homomorphisms are opposite to one another.
In the case of semigroups, $L$ and $R$ can be seen as reducing semigroups to their faithful counterparts. The fact that group's are faithful directly leads to Cayley's theorem which is the representation of any group by the group action defined by $L$.
The special case of groups:
The action of a group on itself is simply transitive, which means that all elements are contained in the same orbit and all stabilizers are trivial. The former is a consequence of the existence of inverses and the later is a consequence of cancellativity.
Two sided actions:
The J semigroup:The images $Im(L),Im(R)$ of the L and R mappings are both subsets of the semigroup $T_S$. Their closures are therefore both members of $Sub(T_S)$. They both must therefore have a semigroup join, which contains all actions both left and right.
Definition. the $J$ semigroup is the semigroup join of the $L$ and $R$ action semigroups, which are defined as the closures of the images of the $L$ and $R$ mappings.
$J$ is the ultimate semigroup defining actions of a magma, semigroup, or other related structure on itself.
Inclusions:
The three semigroups $L,R,J$ form a three element suborder of $Sub(T_S)$ with $L,R \subseteq J$. The intersection $L \cap R$ contains at least all actions by central elements.
Magma theory:
The $L,R$ mappings produce a connection between semigroup theory and magma theory that is worth examining. In particular, magmas correspond to subsets of semigroups, because their $L,R$ images don't need to be closed.Example 1. consider the following non-commutative monogenic magma
[[2,1] [2,2]]Then we have the following left actions: {[2,1],[2,2]}. This is a subset of $T_2$ but it is not closed, which demonstrates that the images of $L$ don't need to be closed for magmas. Its closure is ${[1,2],[2,1],[1,1],[2,2]}$ which is an upper invariant swapper semigroup because the half invariant upper constant elements are acted upon by their predecessor group. This is a first example of a semigroup constructed from a magma.
In the other direction we get the semigroup {[1,2],[2,2]} which is a subsemigroup, therefore this semigroup is R action composition closed. This semigroup action is the total order semilattice on two elements.
Example 2. let $\mathbb{Z}_+$ be the positive integers then $^ : \mathbb{Z}_+^2 \to \mathbb{Z}_+$ is a magma.
The right actions of exponentation are composition closed because $(a^x)^y = a^{xy}$. In this case, the operation is not associative so composition is determined by an operation other then exponentation itself. In this case, we have a semigroup homomorphism $Im(R) \to *$.
The left actions of exponentation on the other hand are not composition closed. When we have $a^(b^x)$ there is no way to reduce it to a single exponentation. Left actions are not composable at all unless one of them is equal to one, which is the trivial case. The semigroup closure of left actions is the set of all exponentation towers closed under composition.
As $Im(L)$ is a subset of a semigroup, we can form a Cayley digraph of it consisting of all pairs of elements $(a,b)$ such that there exists some $c$ such that $c^a = b$. We can call this the 'base of' binary relation, as elements are related provided that the first is a base of the other with respect to some exponent. This binary relation is not transitive because 3 is a base of 9, 9 is a base of 512, and 3 is not a base of 512.
Green's relations:
It is clear that Green's preorders is a special type of action preorder and now we can directly construct monoid actions whose action preorders correspond to the Green's preorders of a semigroup.- $\subseteq_L$ is the action preorder of $Im(L)$
- $\subseteq_R$ is the action preorder of $Im(R)$
- $\subseteq_J$ is the action preorder of the $J$ semigroup
Tuesday, March 23, 2021
Subsets of semigroups
In this post, we will examine subsets of semigroups that are not necessarily subsemigroups. Let $S$ be a set, $* : S^2 \to S$ be a semigroup on $S$, and $T$ be a subset of $S$. Then we can form a restriction binary operation $*_{T^2} : T^2 \to S$, but this restricted binary operation may produce values that are not in $T$. We can restrict the semigroup further by a composability binary operation, which creates a partial operation.
Composability:
The composability binary relation of a subset $T$ of a semigroup has a pair of elements related to one another provided that their composition is in $T$.
Definition. let $(S,*)$ then composability $C(T) : \wp\{S\} \to \wp\{S^2\}$ is a map from subsets of $S$ to relations of $S$ defined by $\{ (x,y) \in T^2: x*y \in T \}$
By restricting to $C(T)$ instead of $T^2$ we get a partial binary operation because now it is defined on a subset of the cartesian product $T^2$, which is a partial binary operation.
Partial semigroups:
Let $* : R \to S$ be a partial binary operation with domain $R \subseteq S^2$. Suppose that we have an ordered triple $(x,y,z)$ of elements of $S$ then the compositions $(xy)z$ and $x(yz)$ need not exist. There is a nine-element existence lattice that determines the extent to which they do exist.
This defines the ontology of associatity conditions of partial binary operations. Given any existence condition, we can require that $(xy)z$ and $x(yz)$ exist and that they coincide.
Proposition. $*_{C(T)} : C(T) \to T$ is a partial semigroup
It follows that we can form partial semigroups from any subset of a semigroup. A common technique is to take a partial semigroup and adjoin a zero element to it, so that all compositions that don't exist instead map to the zero element. This can be used to construct semigroups from certain partial semigroups. For example, given an ideal $I$ then its rees quotient is produced by adjoining a zero to the partial semigroup $I^C$.
Induced relations:
Recall that there is a monotone map from subsemigroups to action preorders. When we are dealing with general subsets, the lack of composition closure corresponds to a lack of transitivity. This leads to left/right Cayley relations $\Gamma$, which can be defined for any semigroup. Given a subset $T$ of a semigroup $(S,*)$ then $(x,y) \in \Gamma$ if $\exists t \in T: y = xt$. If the subset is composition closed, then this action relation is a preorder.
References:
[1] The Theory of Partial Algebraic Operations (Mathematics and Its Applications (414))
Composability:
The composability binary relation of a subset $T$ of a semigroup has a pair of elements related to one another provided that their composition is in $T$.
Definition. let $(S,*)$ then composability $C(T) : \wp\{S\} \to \wp\{S^2\}$ is a map from subsets of $S$ to relations of $S$ defined by $\{ (x,y) \in T^2: x*y \in T \}$
By restricting to $C(T)$ instead of $T^2$ we get a partial binary operation because now it is defined on a subset of the cartesian product $T^2$, which is a partial binary operation.
Partial semigroups:
Let $* : R \to S$ be a partial binary operation with domain $R \subseteq S^2$. Suppose that we have an ordered triple $(x,y,z)$ of elements of $S$ then the compositions $(xy)z$ and $x(yz)$ need not exist. There is a nine-element existence lattice that determines the extent to which they do exist.
- * is strongly associative if $xy, yz$ exists implies associativity
- * is left pre-associative if $(xy)z, yz$ exists implies associativity
- * is right pre-associative if $x(yz), xy$ exists implies associativity.
- * is a partial semigroup if $(xy)z, x(yz)$ exists implies associativity.
Proposition. $*_{C(T)} : C(T) \to T$ is a partial semigroup
It follows that we can form partial semigroups from any subset of a semigroup. A common technique is to take a partial semigroup and adjoin a zero element to it, so that all compositions that don't exist instead map to the zero element. This can be used to construct semigroups from certain partial semigroups. For example, given an ideal $I$ then its rees quotient is produced by adjoining a zero to the partial semigroup $I^C$.
Induced relations:
Recall that there is a monotone map from subsemigroups to action preorders. When we are dealing with general subsets, the lack of composition closure corresponds to a lack of transitivity. This leads to left/right Cayley relations $\Gamma$, which can be defined for any semigroup. Given a subset $T$ of a semigroup $(S,*)$ then $(x,y) \in \Gamma$ if $\exists t \in T: y = xt$. If the subset is composition closed, then this action relation is a preorder.
References:
[1] The Theory of Partial Algebraic Operations (Mathematics and Its Applications (414))
Subscribe to:
Comments (Atom)