- Subobjects: total subobjects can be determined from any morphism set
- Congruences: thin congruences can be determined from any output partition
See also:
Subobjects and quotients of thin quivers
External links:
Duality
Quivers
Showing posts with label subalgebras. Show all posts
Showing posts with label subalgebras. Show all posts
Saturday, October 8, 2022
Total subobjects of quivers
Subobjects are categorically dual to quotients. In this context, if we were to dualize the idea of the lattice of thin congruences of a quiver, then its counterpart would have to be total subobjects. Let $Q$ be a quiver then a total quiver is one in which every object $o \in Ob(X)$ has at least one morphism going in to it $f : x \to o$ or going out of it $g : o \to y$. This produces the following duality:
See also:
Subobjects and quotients of thin quivers
External links:
Duality
Quivers
See also:
Subobjects and quotients of thin quivers
External links:
Duality
Quivers
Wednesday, October 5, 2022
Subobjects and quotients of thin quivers
Thin quivers are an important special case in presheaf topos theory. Suppose that we have a thin quiver $Q$ then we can form and consider its subobject and congruence lattices $Sub(Q)$ and $Con(Q)$ normally, but far more interesting is to consider subobjects and congruences of a thin quiver that remain thin.
Theorem 1. let $Q$ be a thin quiver, then every subobject of $Q$ is thin.
Proof. Thinness is a non-existence condition stating that there do not exist morphisms $m: A \to B$ and $n : A \to B$. Non-existence conditions are subset closed. $\square$
It is rather trivial that thin quivers are subobject closed, and that the subobjects of thin quivers are again thin. Of course, it also follows that any subcategory of a thin category is again thin. Far more interesting is the case of congruences of quivers that have thin quotients.
Lemma 1. let $Q$ be a thin quiver. Then $Q$ has no congruences that collapse two morphisms $m: A \to B$ and $n : C \to D$ without also equating two objects. $Q$ has a unique object-preserving partition.
Proof. $Q$ is a thin quiver it therefore follows that for the two morphisms $m$ and $n$ we must have either $A \not= C$ or $B \not= D$. Suppose that $A \not= C$ then we would have to equate $A$ and $C$ under the congruence so that would produce an equal pair of objects. Likewise, if $B \not= D$ then we would have to equate $B$ and $D$ also producing an equal pair of objects. So no two non-parallel morphisms can be equated under a thin quiver congruence. $\square$
This is the base case, which is that there is a unique congruence for the object partition that preserves all objects. Our goal is to show that there is a unique quiver congruence associated to every object partition.
Lemma 2. let $Q$ be a quiver, then the equivalence minimal congruence that turns $Q$ into a thin quiver $Thin(Q)$ is the congruence that equates all parallel pairs of morphisms in $Q$ and no objects. All other morphisms $f: Q \to T$ from $Q$ to a thin quiver factor through $Thin(Q)$.
Proof. let $Q$ be a quiver. Then in order for $Q$ to be thin there must not be any pairs of morphisms $m$ and $n$ with the property that $s(m) = s(n)$ and $t(m) = t(n)$. Thusly, to make $Q$ thin we can equate all such pairs of morphisms $m$ and $n$ to get the congruence $Thin(Q)$. This has as a quotient a thin quiver because it can not have any pairs $m$ and $n$ with $s(m) = s(n)$ and $t(m) = t(n)$ for if it did it would contradict the fact that we collapsed them. Then to see minimality, consider that any other congruence $C$ of $Q$ must also collapse all such pairs $m$ and $n$. It follows that $Thin(Q)$ is the minimal thin congruence. $\square$
With these two lemmas we now have have the means we need to prove our main theorem, which is that the thin congruences of a quiver are fully determined by object partitions.
Theorem 2. Let $Q$ be a quiver and $B$ a partition of its objects. Then there is a unique quiver congruence of $Q$ with $B$ its object partition that has a thin quotient.
Proof. there is always a unique quiver congruence associated to any object partition $B$ of a quiver $Q$: the congruence that collapses all objects in $B$ but no morphisms. We can always form this congruence by the pair $(id,B)$. Then the quotient of this congruence need not be thin. So by lemma 2 we can form a partition $A$ of the morphism set $E$ by equating all parallel edges which turns $\frac{Q}{(id,B)}$ into a thin quiver. This forms the following commutative diagram:
Then also by lemma one, we see that every morphism from $Q$ to a thin quiver $T$ that goes through $B$ must filter through $\frac{Q}{(A,B)}$. However, by lemma one we know that no such further congruence can exist without further equating the objects of $B$. So $\frac{Q}{(A,B)}$ is the only thin quiver produced by a congruence with object partition $B$. It follows that thin congruences are fully determined by their object partitions. $\square$
If by theorem 2, we have that each object partition is uniquely associated to a thin congruence, then there is a one to one mapping $U : Con(Ob(Q)) \to Con(Q)$ that maps any object partition into a thin congruence.
Corollary. let $Q$ be a quiver then the suborder of $Con(Q)$ consisting of all thin congruences is isomorphic to the partition lattice $Con(Ob(Q))$ of partitions of the object set $Ob(Q)$.
It follows from this that the lattice of thin congruences of $Q$ is simply a partition lattice. We can further consider the thin mapping we defined in lemma 2 to be a closure operation on $Con(Q)$.
Corollary. $Thin: Con(Q) \to Con(Q)$ is a closure operation on the lattice of congruences of a quiver $Con(Q)$ that maps any congruence to its thin component.
The relevance of this result is that we can understand the epi-mono factorisations in the full subcategory of the topos $Quiv$ of thin quivers. We see from this that every morphism of directed graphs is determined by a vertex partition on the one hand a subset of vertices and edges on the other. The interesting thing about this is that it produces a dichotomy between congruences and subobjects, where only the later requires both object and morphism components.
Of particular interest is the application of this theory to considering subobjects and congruences of binary operations, which can simply be considered to be quivers with an algebraic function operation adjoined to them in the topos $Sets^{T_{2,3}}$ of ternary quivers. This leads into a more advanced topos theoretic theory of algebraic operations and their subobjects and congruences, which will be helpful in defining the topos theoretic foundations of algebra.
We see that topos theory provides the best foundation for combinatorics because topoi like $Quiv$ let you reason logically about graphs, digraphs, etc. $Sets^{[1,2]}$ lets you reason about hypergraphs. In order to make it the best foundation for abstract algebra we need to consider other topoi like $Sets^{T_{2,3}}$. In order to use topoi in geometry, as was originally intended, we can consider topoi of sheaves $Sh(X)$ of topological spaces. Every branch has its own topoi available for further study, which makes topos theory such an exciting field for further research and analysis.
References:
Quiver in nlab
Topoi: The Categorial Analysis of Logic
Theorem 1. let $Q$ be a thin quiver, then every subobject of $Q$ is thin.
Proof. Thinness is a non-existence condition stating that there do not exist morphisms $m: A \to B$ and $n : A \to B$. Non-existence conditions are subset closed. $\square$
It is rather trivial that thin quivers are subobject closed, and that the subobjects of thin quivers are again thin. Of course, it also follows that any subcategory of a thin category is again thin. Far more interesting is the case of congruences of quivers that have thin quotients.
Lemma 1. let $Q$ be a thin quiver. Then $Q$ has no congruences that collapse two morphisms $m: A \to B$ and $n : C \to D$ without also equating two objects. $Q$ has a unique object-preserving partition.
Proof. $Q$ is a thin quiver it therefore follows that for the two morphisms $m$ and $n$ we must have either $A \not= C$ or $B \not= D$. Suppose that $A \not= C$ then we would have to equate $A$ and $C$ under the congruence so that would produce an equal pair of objects. Likewise, if $B \not= D$ then we would have to equate $B$ and $D$ also producing an equal pair of objects. So no two non-parallel morphisms can be equated under a thin quiver congruence. $\square$
This is the base case, which is that there is a unique congruence for the object partition that preserves all objects. Our goal is to show that there is a unique quiver congruence associated to every object partition.
Lemma 2. let $Q$ be a quiver, then the equivalence minimal congruence that turns $Q$ into a thin quiver $Thin(Q)$ is the congruence that equates all parallel pairs of morphisms in $Q$ and no objects. All other morphisms $f: Q \to T$ from $Q$ to a thin quiver factor through $Thin(Q)$.
Proof. let $Q$ be a quiver. Then in order for $Q$ to be thin there must not be any pairs of morphisms $m$ and $n$ with the property that $s(m) = s(n)$ and $t(m) = t(n)$. Thusly, to make $Q$ thin we can equate all such pairs of morphisms $m$ and $n$ to get the congruence $Thin(Q)$. This has as a quotient a thin quiver because it can not have any pairs $m$ and $n$ with $s(m) = s(n)$ and $t(m) = t(n)$ for if it did it would contradict the fact that we collapsed them. Then to see minimality, consider that any other congruence $C$ of $Q$ must also collapse all such pairs $m$ and $n$. It follows that $Thin(Q)$ is the minimal thin congruence. $\square$
With these two lemmas we now have have the means we need to prove our main theorem, which is that the thin congruences of a quiver are fully determined by object partitions.
Theorem 2. Let $Q$ be a quiver and $B$ a partition of its objects. Then there is a unique quiver congruence of $Q$ with $B$ its object partition that has a thin quotient.
Proof. there is always a unique quiver congruence associated to any object partition $B$ of a quiver $Q$: the congruence that collapses all objects in $B$ but no morphisms. We can always form this congruence by the pair $(id,B)$. Then the quotient of this congruence need not be thin. So by lemma 2 we can form a partition $A$ of the morphism set $E$ by equating all parallel edges which turns $\frac{Q}{(id,B)}$ into a thin quiver. This forms the following commutative diagram:
Then also by lemma one, we see that every morphism from $Q$ to a thin quiver $T$ that goes through $B$ must filter through $\frac{Q}{(A,B)}$. However, by lemma one we know that no such further congruence can exist without further equating the objects of $B$. So $\frac{Q}{(A,B)}$ is the only thin quiver produced by a congruence with object partition $B$. It follows that thin congruences are fully determined by their object partitions. $\square$
If by theorem 2, we have that each object partition is uniquely associated to a thin congruence, then there is a one to one mapping $U : Con(Ob(Q)) \to Con(Q)$ that maps any object partition into a thin congruence.
Corollary. let $Q$ be a quiver then the suborder of $Con(Q)$ consisting of all thin congruences is isomorphic to the partition lattice $Con(Ob(Q))$ of partitions of the object set $Ob(Q)$.
It follows from this that the lattice of thin congruences of $Q$ is simply a partition lattice. We can further consider the thin mapping we defined in lemma 2 to be a closure operation on $Con(Q)$.
Corollary. $Thin: Con(Q) \to Con(Q)$ is a closure operation on the lattice of congruences of a quiver $Con(Q)$ that maps any congruence to its thin component.
The relevance of this result is that we can understand the epi-mono factorisations in the full subcategory of the topos $Quiv$ of thin quivers. We see from this that every morphism of directed graphs is determined by a vertex partition on the one hand a subset of vertices and edges on the other. The interesting thing about this is that it produces a dichotomy between congruences and subobjects, where only the later requires both object and morphism components.
Of particular interest is the application of this theory to considering subobjects and congruences of binary operations, which can simply be considered to be quivers with an algebraic function operation adjoined to them in the topos $Sets^{T_{2,3}}$ of ternary quivers. This leads into a more advanced topos theoretic theory of algebraic operations and their subobjects and congruences, which will be helpful in defining the topos theoretic foundations of algebra.
We see that topos theory provides the best foundation for combinatorics because topoi like $Quiv$ let you reason logically about graphs, digraphs, etc. $Sets^{[1,2]}$ lets you reason about hypergraphs. In order to make it the best foundation for abstract algebra we need to consider other topoi like $Sets^{T_{2,3}}$. In order to use topoi in geometry, as was originally intended, we can consider topoi of sheaves $Sh(X)$ of topological spaces. Every branch has its own topoi available for further study, which makes topos theory such an exciting field for further research and analysis.
References:
Quiver in nlab
Topoi: The Categorial Analysis of Logic
Thursday, February 10, 2022
Preservation and reflection of subsemigroups
The functoriality of the Alexandrov topology of a thin category is a good first example of the broad theme of functorially produced set systems of algebraic structures. In order to continue along these lines we need to generalize from the category $Top$ of topological spaces and continuous maps to the categories of hypergraphs and either reflecting or preserving maps respectively. These produce functors that can be defined, for example over the category of semigroups.
Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ preserves subsemigroups.
Proof. let $A \subseteq S$ then $\forall a_1,a_2 \in A: a1_a2 \in A$. So consider the image $f(A)$ and let $t_1,t_2 \in f(A)$ then there exists $a, b$ such that $f(a) = t_1$ and $f(b) = t_2$. Now consider the product $f(a)f(b)$ then by the definition of semigroup homomorphisms this is equal to $f(ab)$ but we have that $ab \in A$ so $t_1t_2 = f(ab) \in f(A)$ so that $f(A)$ is composition closed. $\square$
Theorem. let $f: S \to T$ be a morphism of semigroups. Then $f$ reflects subsemigroups.
Proof. let $B \subseteq T$ then $f^{-1}(B)$ is a subset of $S$. Suppose that $x,y \in f^{-1}(B)$ then $f(x) \in B$ and $f(y) \in B$. The product $f(xy)$ is equal to $f(x)f(y)$ by the definition of semigroup homomorphisms. Then since $f(x)$ is in $B$, $f(y)$ is in $B$ and $B$ is composition closed $f(xy) = f(x)f(y)$ is in $B$ which implies that $f^{-1}(B)$ is composition closed. $\square$
Theorem. let $f: M \to N$ be a morphism of monoids. Then $f$ preserves and reflect submonoids.
Proof. (1) let $S \subseteq M$ be a submonoid of $M$ then $1 \in S$ and by the definition of monoid homomorphisms $f(1)$ is the identity of $M$ so $1 \in f(S)$. (2) In the other direction, suppose that $S \subseteq M$ is a submonoid so that $1_N \in S$ then by the definition of monoid homomorphisms $f(1_M) = 1_M$ so that $1_M \in f^{-1}(S)$ so that monoid maps reflect identities. (3) then since $f$ preserves and reflects identities as well as subsemigroups it necessarily must also do so for submonoids as well. $\square$
Theorem. let $f: G \to H$ be a group homomorphism. Then $g$ preserves and reflects subgroups.
Proof. (1) let $S \subseteq G$ be a subgroup. Then for all $s \in S$ we have that $-s \in S$. Then consider $f(S)$ if $h$ is in $f(S)$ then we have that there exists $g$ such that $f(g) = h$. Then consider $-h$ by the definition of group homomorphisms $f(-g) = -h$ but then $-g$ is in $S$ because $S$ is a subgroup and therefore inverse closed. It follows that $f(-g) = -h$ is in $f(S)$ so that the image is a subgroup.
(2) in the other direction suppose that $S \subseteq H$ is a subgroup. Then $\forall s \in S : -s \in S$. Suppose that $g \in G$ and $f(g) \in S$. Then $f(-g) = -f(g)$ by the definition of group homomorphisms. By the fact that $S$ is a subgroup and $f(g)$ is in $S$ we have that $-f(g)$ is in $S$ which implies that $f^{-1}(S)$ is inverse closed for all $g \in f^{-1}(S)$. It follows that it is a subgroup. $\square$
We saw that monotone maps reflect ideals over thin categories. A generalization of this which is applicable to semigroups involves the reflection of semigroup ideals, which can be either left, right, or two sided. This produces a functor from the category of semigroups to the category of topological spaces.
Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects left, right, or two sided ideals.
Proof. let $I$ be a left ideal of $T$ then we have that for all $i \in I$ and $t \in T$ it holds that $it \in T$. So consider $f^{-1}(I)$ then if we have $x \in f^{-1}(I)$ it follows that $f(x) \in I$. Let $s \ in S$ then $f(sx) = f(s)f(x)$ and since $f(x)$ is in $I$ and $I$ is a left ideal $f(s)f(x)$ is in $I$. So $f$ reflects left ideals and by dualizing it reflects right ideals. By combining this $f$ reflects two sided ideals. $\square$
It is not enough for us to show that semigroup homomorphisms reflect subsemigroups. We would also like to know that they reflect prime ideals. This will then allow us to reproduce the familiar theorems of ring theory dealing with prime ideals.
Theorem. let $f : A \to B$ be a morphism of semigroups then $f$ reflects prime subsemigroups.
Proof. let $P \subseteq B$ be a prime subsemigroup then we have that $Q = B-P$ is a subsemigroup and in total we have $P,Q$ are subsemigroups with $P \cup Q = B$ and $P \cap Q = \emptyset$. Every element of $A$ produces some image, so by the fact that inverse images are lattice homomorphisms we have $f^{-1}(P) \cup f^{-1}(Q) = A$ and $f^{-1}(P) \cap f^{-1}(Q) = \emptyset$. So by the fact that $f$ reflects subsemigroups it follows that $f^{-1}(P)$ is a subsemigroup with complement subsemigroup $f^{-1}(Q)$. $\square$
Corollary. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects prime ideals.
The one other class of ideals we are really interested in are the radical ideals, especially in commutative algebra because of theri relationship to algebraic varieties under Hilbert'z nullstellensatz. There is a corresponding notion for semigroups, and so by considering that we will get closer to solving some problems related to radical subsemigroups and ideals.
Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects radical subsemigroups.
Proof. let $B \subseteq T$ be a radical subsemigroup. Then $f^{-1}(B)$ is a subsemigroup of $S$ because $f$ reflects subsemigroups, so it remains to show that $f^{-1}(B)$ is a radical subsemigroup. Let $x \in f^{-1}(B)$ and suppose that $y^n = x$ Then we can apply $f$ to both sides to get $f(y^n) = f(x)$ and expanding this $f(y)^n = f(x)$. Now since, $f(x)$ is in $B$ and $B$ is radical this implies that $f(y) \in B$. So to sum up this means that $f^{-1}(B)$ is a radical subsemigroup. $\square$
Corollary. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects semigroup radical ideals.
We can apply these semigroup theorems to our favourite algebraic structures, all of which are constructed out of semigroups. Like lattices (thin categories with all products and coproducts), semirings, and rings. In particular, this is enough to recover that the pre image of a prime ideal of a ring is a prime ideal.
Corollaries.
Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ preserves subsemigroups.
Proof. let $A \subseteq S$ then $\forall a_1,a_2 \in A: a1_a2 \in A$. So consider the image $f(A)$ and let $t_1,t_2 \in f(A)$ then there exists $a, b$ such that $f(a) = t_1$ and $f(b) = t_2$. Now consider the product $f(a)f(b)$ then by the definition of semigroup homomorphisms this is equal to $f(ab)$ but we have that $ab \in A$ so $t_1t_2 = f(ab) \in f(A)$ so that $f(A)$ is composition closed. $\square$
Theorem. let $f: S \to T$ be a morphism of semigroups. Then $f$ reflects subsemigroups.
Proof. let $B \subseteq T$ then $f^{-1}(B)$ is a subset of $S$. Suppose that $x,y \in f^{-1}(B)$ then $f(x) \in B$ and $f(y) \in B$. The product $f(xy)$ is equal to $f(x)f(y)$ by the definition of semigroup homomorphisms. Then since $f(x)$ is in $B$, $f(y)$ is in $B$ and $B$ is composition closed $f(xy) = f(x)f(y)$ is in $B$ which implies that $f^{-1}(B)$ is composition closed. $\square$
Theorem. let $f: M \to N$ be a morphism of monoids. Then $f$ preserves and reflect submonoids.
Proof. (1) let $S \subseteq M$ be a submonoid of $M$ then $1 \in S$ and by the definition of monoid homomorphisms $f(1)$ is the identity of $M$ so $1 \in f(S)$. (2) In the other direction, suppose that $S \subseteq M$ is a submonoid so that $1_N \in S$ then by the definition of monoid homomorphisms $f(1_M) = 1_M$ so that $1_M \in f^{-1}(S)$ so that monoid maps reflect identities. (3) then since $f$ preserves and reflects identities as well as subsemigroups it necessarily must also do so for submonoids as well. $\square$
Theorem. let $f: G \to H$ be a group homomorphism. Then $g$ preserves and reflects subgroups.
Proof. (1) let $S \subseteq G$ be a subgroup. Then for all $s \in S$ we have that $-s \in S$. Then consider $f(S)$ if $h$ is in $f(S)$ then we have that there exists $g$ such that $f(g) = h$. Then consider $-h$ by the definition of group homomorphisms $f(-g) = -h$ but then $-g$ is in $S$ because $S$ is a subgroup and therefore inverse closed. It follows that $f(-g) = -h$ is in $f(S)$ so that the image is a subgroup.
(2) in the other direction suppose that $S \subseteq H$ is a subgroup. Then $\forall s \in S : -s \in S$. Suppose that $g \in G$ and $f(g) \in S$. Then $f(-g) = -f(g)$ by the definition of group homomorphisms. By the fact that $S$ is a subgroup and $f(g)$ is in $S$ we have that $-f(g)$ is in $S$ which implies that $f^{-1}(S)$ is inverse closed for all $g \in f^{-1}(S)$. It follows that it is a subgroup. $\square$
We saw that monotone maps reflect ideals over thin categories. A generalization of this which is applicable to semigroups involves the reflection of semigroup ideals, which can be either left, right, or two sided. This produces a functor from the category of semigroups to the category of topological spaces.
Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects left, right, or two sided ideals.
Proof. let $I$ be a left ideal of $T$ then we have that for all $i \in I$ and $t \in T$ it holds that $it \in T$. So consider $f^{-1}(I)$ then if we have $x \in f^{-1}(I)$ it follows that $f(x) \in I$. Let $s \ in S$ then $f(sx) = f(s)f(x)$ and since $f(x)$ is in $I$ and $I$ is a left ideal $f(s)f(x)$ is in $I$. So $f$ reflects left ideals and by dualizing it reflects right ideals. By combining this $f$ reflects two sided ideals. $\square$
It is not enough for us to show that semigroup homomorphisms reflect subsemigroups. We would also like to know that they reflect prime ideals. This will then allow us to reproduce the familiar theorems of ring theory dealing with prime ideals.
Theorem. let $f : A \to B$ be a morphism of semigroups then $f$ reflects prime subsemigroups.
Proof. let $P \subseteq B$ be a prime subsemigroup then we have that $Q = B-P$ is a subsemigroup and in total we have $P,Q$ are subsemigroups with $P \cup Q = B$ and $P \cap Q = \emptyset$. Every element of $A$ produces some image, so by the fact that inverse images are lattice homomorphisms we have $f^{-1}(P) \cup f^{-1}(Q) = A$ and $f^{-1}(P) \cap f^{-1}(Q) = \emptyset$. So by the fact that $f$ reflects subsemigroups it follows that $f^{-1}(P)$ is a subsemigroup with complement subsemigroup $f^{-1}(Q)$. $\square$
Corollary. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects prime ideals.
The one other class of ideals we are really interested in are the radical ideals, especially in commutative algebra because of theri relationship to algebraic varieties under Hilbert'z nullstellensatz. There is a corresponding notion for semigroups, and so by considering that we will get closer to solving some problems related to radical subsemigroups and ideals.
Theorem. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects radical subsemigroups.
Proof. let $B \subseteq T$ be a radical subsemigroup. Then $f^{-1}(B)$ is a subsemigroup of $S$ because $f$ reflects subsemigroups, so it remains to show that $f^{-1}(B)$ is a radical subsemigroup. Let $x \in f^{-1}(B)$ and suppose that $y^n = x$ Then we can apply $f$ to both sides to get $f(y^n) = f(x)$ and expanding this $f(y)^n = f(x)$. Now since, $f(x)$ is in $B$ and $B$ is radical this implies that $f(y) \in B$. So to sum up this means that $f^{-1}(B)$ is a radical subsemigroup. $\square$
Corollary. let $f : S \to T$ be a morphism of semigroups. Then $f$ reflects semigroup radical ideals.
We can apply these semigroup theorems to our favourite algebraic structures, all of which are constructed out of semigroups. Like lattices (thin categories with all products and coproducts), semirings, and rings. In particular, this is enough to recover that the pre image of a prime ideal of a ring is a prime ideal.
Corollaries.
- Lattice homomorphisms preserve and reflect sublattices
- Semigroup homomorphisms preserve and reflect subsemirings
- Ring homomorphisms preserve and reflect subrings
- Ring homomorphisms reflect left, right, and two sided ideals, prime ideals, and radical ideals
Thursday, November 11, 2021
Subobject and quotient lattices of functions
Let $f: A \to B$ be a function. Then the topos of functions $Sets^{\to}$ associates $f$ with subobject and quotient lattices. The distributive subobject lattice describes subobjects and functions, and the quotient lattice describes I/O relationships which generalize congruences.
The study of I/O relationships of functions, which is described by topos theory, demonstrates that congruences don't simply belong to abstract algebra but also to set theory and mathematical foundations because they are applicable to any function. We've talked a lot about these lattices associated to functions, but we haven't presented any diagrams of them yet. With the help of clojure and graphviz I can now do that.
A notable aspect of the subobject and quotient lattices of functions, is that they tend to expand really quickly, just like power sets which are the subobject lattices of the topos of sets. At the same time, they are trivial for the smallest functions. So a simple function like {:x 1 :y 2 :z 3} is at the sweet spot where its lattice diagrams are not to big or too small.
Subobject lattice:
Congruence lattice:
A notable property that we can infer from the subobject and quotient lattices of a function, from visual inspection is that the smallest subobjects and congruences of functions are determined by relations on the image rather then on the domain. This is because an inherent property of the subobjects and congruences of functions is that they must preserve set and equivalence images.
The atoms in the subobject lattice are elements of the codomain and the atoms in the congruence lattice are equal isations of pairs in the codomain. Only once an element in the codomain has been selected for its inclusion can its fibers in the domain be included into the subobject. Likewise, only once a pair in the codomain has been an equalized can the fibers of its respective element be equalized in the domain partition.
These diagrams are presented for education and research in topos theory, the undoubted foundation of math. Topos theory resolves all the issues of universal algebra, such as the theory of subobjects and congruences, on the level of individual functions. At the same time, it opens up exciting new ground in the theory of I/O relations of functions which have applications in the mathematical dataflow analysis of computation.
The study of I/O relationships of functions, which is described by topos theory, demonstrates that congruences don't simply belong to abstract algebra but also to set theory and mathematical foundations because they are applicable to any function. We've talked a lot about these lattices associated to functions, but we haven't presented any diagrams of them yet. With the help of clojure and graphviz I can now do that.
(mapfn {:x 1 :y 2 :z 3})
Given a SetFunction object in the topos of functions, we can produce its subobject and quotient lattices as well as perform out operation of computational topos theory like products and coproducts. Towards that end, I have created subobject and quotient lattices of a simple function, which demonstrates that these concepts of universal algebra are applicable even to individual functions.
A notable aspect of the subobject and quotient lattices of functions, is that they tend to expand really quickly, just like power sets which are the subobject lattices of the topos of sets. At the same time, they are trivial for the smallest functions. So a simple function like {:x 1 :y 2 :z 3} is at the sweet spot where its lattice diagrams are not to big or too small.
Subobject lattice:
Congruence lattice:
A notable property that we can infer from the subobject and quotient lattices of a function, from visual inspection is that the smallest subobjects and congruences of functions are determined by relations on the image rather then on the domain. This is because an inherent property of the subobjects and congruences of functions is that they must preserve set and equivalence images.
The atoms in the subobject lattice are elements of the codomain and the atoms in the congruence lattice are equal isations of pairs in the codomain. Only once an element in the codomain has been selected for its inclusion can its fibers in the domain be included into the subobject. Likewise, only once a pair in the codomain has been an equalized can the fibers of its respective element be equalized in the domain partition.
These diagrams are presented for education and research in topos theory, the undoubted foundation of math. Topos theory resolves all the issues of universal algebra, such as the theory of subobjects and congruences, on the level of individual functions. At the same time, it opens up exciting new ground in the theory of I/O relations of functions which have applications in the mathematical dataflow analysis of computation.
Monday, September 6, 2021
Chain conditions on commutative semigroups
The chain conditions on commutative semigroups can occur on either subalgebras, ideals, or principal ideals. The stongest of these are the chain conditions on subalgebras.
Theorem. let $S$ be a commutative semigroup for which $Sub(S)$ satisfies both the ACC and the DCC then $S$ is finite.
Proof. (1) the ACC on subalgbras means that $S$ is finitely generated, for if it were not then an infinite gneerating set for it would create an infinite ascending chain (2) the DCC on subalgebras means that $S$ is monofinite, meaning that for each $x$ in $S$ the principal subalgebra $(x)$ is finite. If it were not finite, then $(x)$ would generate a $(\mathbb{Z}_+,+)$ semigroup which has an infinite descending chain of subalgebras (3) $S$ is finitely generated, each element generates a finite number of elements, and $S$ is commutative so $S$ is finite. $\square$
The situation with respect to $\mathbb{Z}$-modules is a bit different. In that case, there is no distinction between subalgebras, ideals, and principal ideals: there are only submodules. An analogous result shows that $\mathbb{Z}$ modules satisfying both the ACC and DCC on subalgebras are finite. This theorem is in the same vein of the following familiar theorem from commutative algebra:
Proposition. let $M$ be a module satisfying both the ACC and the DCC then $M$ has finite length. [1]
This is one case in which commutativity is necessary. We have that finitely generated commutative semigroups in which each element has a finite principal subalgebra are finite, but the converse does not need to be the case for non-commutative semigroups or groups. It has been shown that there is a finitely generated torsion group that is not finite for example [2].
References:
[1] Commutative algebra volume one Zariski and Samuel
[2] Burnside problem
Theorem. let $S$ be a commutative semigroup for which $Sub(S)$ satisfies both the ACC and the DCC then $S$ is finite.
Proof. (1) the ACC on subalgbras means that $S$ is finitely generated, for if it were not then an infinite gneerating set for it would create an infinite ascending chain (2) the DCC on subalgebras means that $S$ is monofinite, meaning that for each $x$ in $S$ the principal subalgebra $(x)$ is finite. If it were not finite, then $(x)$ would generate a $(\mathbb{Z}_+,+)$ semigroup which has an infinite descending chain of subalgebras (3) $S$ is finitely generated, each element generates a finite number of elements, and $S$ is commutative so $S$ is finite. $\square$
The situation with respect to $\mathbb{Z}$-modules is a bit different. In that case, there is no distinction between subalgebras, ideals, and principal ideals: there are only submodules. An analogous result shows that $\mathbb{Z}$ modules satisfying both the ACC and DCC on subalgebras are finite. This theorem is in the same vein of the following familiar theorem from commutative algebra:
Proposition. let $M$ be a module satisfying both the ACC and the DCC then $M$ has finite length. [1]
This is one case in which commutativity is necessary. We have that finitely generated commutative semigroups in which each element has a finite principal subalgebra are finite, but the converse does not need to be the case for non-commutative semigroups or groups. It has been shown that there is a finitely generated torsion group that is not finite for example [2].
References:
[1] Commutative algebra volume one Zariski and Samuel
[2] Burnside problem
Friday, September 3, 2021
Subgroups form a sublattice
Every group $G$ is associated with a lattice of subgroups $Sub(G,*,1,/)$ but it also associated with a lattice of submonoids $Sub(G,*,1)$. By this, we will see that the subgroups lattice of $G$ is a sublattice of the submonoid lattice.
Lemma 1. let $G$ be a group and $S$ an inverse-closed subset then composition closure $cl(S)$ is inverse closed.
Proof. let $a,b \in S$ then by composition closure $ab \in cl(S)$. By inverse closure $a^{-1} \in S$ and $b^{-1} \in S$. So by composition closure, $b^{-1}a^{-1} \in cl(S)$, but this is equal to $(ab)^{-1}$ so $(ab)^{-1} \in cl(S)$. It follows that $cl(S)$ is inverse closed. $\square$
Theorem. let $G$ be a group then the lattice of subgroups $Sub(G,*,1,/)$ is a sublattice of the lattice of submonoids $Sub(G,*,1)$.
Proof. let $A,B$ be subgroups of $G$. Then $A,B$ are inverse closed, so $A \cup B$ is inverse closed. By lemma 1, $cl(A \cup B)$ is a subgroup. With respect to the lattice of submonoids $A \vee B$ coincides with $cl(A \cup B)$ so the monoid join of subgroups is a group. It follows that subgroups are a sublattice of submonoids. $\square$
By extending previous results we get the following chain of sublattices: normal subgroups $\subseteq$ groups $\subseteq$ monoids $\subseteq$ subsemigroups. Previously we also saw that the lattice of partitions $Part(A)$ is a sublattice of the lattice of preorders. With similar results from both order theory and semigroup theory, it is reasonable to assume that this can be extended to categories.
This is indeed possible using lattice of subcategories, but for now I am interested in applications of this approad to semigroup theory. A significant result to that effect is that if $S$ is a finitely generated cancellative submonoid of a group $G$ then its subgroup closure is finitely generated as well.
Lemma 2. let $G$ be a group and $S$ a submonoid then if $S$ is finitely generated its group closure $H$ is a finitely generated as well.
Proof. let $X$ be the finite generating set of $S$. Then since $X$ is finite $X \cup -X$ is finite as well. By lemma 1, $X \cup -X$ is a finite generating set for $H$, so $H$ is finitely generated as well. $\square$
Theorem. finitely generated commutative cancellative torsion-free J-trivial monoids are affine
Proof. let $S$ be a finitely generated commutative cancellative J-trivial monoid. Then let $G$ be its Grothendeick group, then since $S$ is J-trivial $G$ is torsion-free. Since $S$ is finitely generated, $G$ is as well. By the classification of torsion-free finitely generated commutative groups, $G$ is isomorphic to $\mathbb{Z}^d$ for some $d$. $\square$
It is very easy to construct affine semigroups, by taking subsets of $\mathbb{Z}^d$. However, it is harder to determine when a given commutative cancellative semigroup is affine. This is a partial result to that effect.
Lemma 1. let $G$ be a group and $S$ an inverse-closed subset then composition closure $cl(S)$ is inverse closed.
Proof. let $a,b \in S$ then by composition closure $ab \in cl(S)$. By inverse closure $a^{-1} \in S$ and $b^{-1} \in S$. So by composition closure, $b^{-1}a^{-1} \in cl(S)$, but this is equal to $(ab)^{-1}$ so $(ab)^{-1} \in cl(S)$. It follows that $cl(S)$ is inverse closed. $\square$
Theorem. let $G$ be a group then the lattice of subgroups $Sub(G,*,1,/)$ is a sublattice of the lattice of submonoids $Sub(G,*,1)$.
Proof. let $A,B$ be subgroups of $G$. Then $A,B$ are inverse closed, so $A \cup B$ is inverse closed. By lemma 1, $cl(A \cup B)$ is a subgroup. With respect to the lattice of submonoids $A \vee B$ coincides with $cl(A \cup B)$ so the monoid join of subgroups is a group. It follows that subgroups are a sublattice of submonoids. $\square$
By extending previous results we get the following chain of sublattices: normal subgroups $\subseteq$ groups $\subseteq$ monoids $\subseteq$ subsemigroups. Previously we also saw that the lattice of partitions $Part(A)$ is a sublattice of the lattice of preorders. With similar results from both order theory and semigroup theory, it is reasonable to assume that this can be extended to categories.
This is indeed possible using lattice of subcategories, but for now I am interested in applications of this approad to semigroup theory. A significant result to that effect is that if $S$ is a finitely generated cancellative submonoid of a group $G$ then its subgroup closure is finitely generated as well.
Lemma 2. let $G$ be a group and $S$ a submonoid then if $S$ is finitely generated its group closure $H$ is a finitely generated as well.
Proof. let $X$ be the finite generating set of $S$. Then since $X$ is finite $X \cup -X$ is finite as well. By lemma 1, $X \cup -X$ is a finite generating set for $H$, so $H$ is finitely generated as well. $\square$
Theorem. finitely generated commutative cancellative torsion-free J-trivial monoids are affine
Proof. let $S$ be a finitely generated commutative cancellative J-trivial monoid. Then let $G$ be its Grothendeick group, then since $S$ is J-trivial $G$ is torsion-free. Since $S$ is finitely generated, $G$ is as well. By the classification of torsion-free finitely generated commutative groups, $G$ is isomorphic to $\mathbb{Z}^d$ for some $d$. $\square$
It is very easy to construct affine semigroups, by taking subsets of $\mathbb{Z}^d$. However, it is harder to determine when a given commutative cancellative semigroup is affine. This is a partial result to that effect.
Wednesday, August 4, 2021
Topos theory and universal algebra
The techniques of universal algebra, to be truly universal should be applicable on both the lowest level as well as the highest. It should be applicable to both functions as well as other structures built out of many functions. It should be compositional so that the smallest components like sets and functions that build up the properties of the larger ones.
In particular, I have in mind the generalization of the properties of universal algebra to individual functions. In total, these are some of the properties I would like to see from a model of functions:
The problem with the set of ordered pairs account is that does not address the different properties of functions. If functions were just sets, algebra wouldn't be a different branch of mathematics distinguished from set theory. Yet it is, and that can be addressed with the topos $Sets^{\to}$.
This account is different from other earlier categorical accounts of universal algebra like Lawvere theories, because I explicitly intend for it to be done from the ground up. Before setting out into abstract algebra, I want to first figure out what functions are, and then we can use that to account for the properties of structures built out of them.
Isomorphisms:
Two functions $f : A \to B, g : C \to D$ in $Sets^{\to}$ are isomorphic, provided that the distribution of cardinalities of their fibers are the same.
Automorphisms:
Let $f: A \to B$ be a function, then $Aut(f)$ is its group of automorphisms. A function is associated with a kernel, which is the equivalence relation determined on inputs of $f$ and an image in $B$. The image in turn determines a complement of non-image values. $Aut(f)$ is the direct product of the automorphism group of the kernel equivalence relation and the symmetric group on the complement of the image. It is therefore a direct product of wreath products of symmetric groups by symmetric groups.
Set images:
The subalgebras of a function are defined with respect to images, so that $(S,T)$ is a subobject provided that $f(A) \subseteq B$. In particular, the covariant power set functor associates to any function its image function $\wp(f) : \wp(A) \to \wp(B)$.
Set inverse images:
The dual operation for functions is the contravariant inverse image function. This takes $f : A \to B$ to $\overline{\wp}(f) : \wp(B) \to \wp(A)$. It is the largest set which produces a given image.
Lattice of subalgebras:
Let $f: A \to B$ be a function, then $Sub(f)$ is a distributive lattice of subobjects of $f$ consisting of all ordered pairs $(S,T)$ for which $f(A) \subseteq T$. Then this distributive lattice is associated to a closure operation by the image.
Subobject classifier:
As a topos, functions are associated with a trivalent logic. Let $f : A \to B$ be a function and $(S,T)$ be a subobject. Then its input truth value for $a \in A$ is zero if $f(a) \not\in T$, $\frac{1}{2}$ if $f(a) \in T \wedge a \not \in S$ and $1$ if $a \in S$. Its output truth value is $1$ if $b \in T$ and zero otherwise. The input and output truth values form an ordered pair $(i,o)$ which is the characteristic function of a function.
In this setting, a congruence of a function captures the intuitive idea that pieces of information mapped by a function can determine pieces of information about the output. This distinguishes functions from sets of ordered pairs, because it explicitly uses the fact that functions are specific types of maps from inputs to outputs.
Information image:
The dual of the subset image, which determines the congruences of a function is the information image. It takes a partition of the input set, and it produces an output partition so that the two form a congruence. Let $f: A \to B$ be a function and $P$ a partition of $A$. Then define a partition $Q$ of $B$ by: \[ x =_Q y \Leftrightarrow \exists a_1, a_2 \in A : a =_P b \wedge f(a) = x \wedge f(b) = y \] Information inverse image:
We can also dualize the concept of a subset inverse image, in order to form an inverse image function for the lattice of partitions. This is the smallest piece of information that produces a given output. Let $f : A \to B$ be a function and $Q$ a partition of $B$ then define a partition $P$ of $A$ by: \[ a =_P b \Leftrightarrow f(a) =_Q f(b) \] Lattice of congruences:
Let $f : A \to B$ be a function, then its lattice of congruences $Con(f)$ consists of all ordered pairs $(P,Q)$ for which $a =_P b \Rightarrow f(a) =_Q f(b)$. In other words, it consists of all $(P,Q)$ for which $Q$ is a larger equivalence relation then $f(P)$.
Quotients:
Let $f: A \to B$ be a function and $(P,Q)$ a congruence of $f$. Then $\frac{f}{(P,Q)}: P \to Q$ is the function which associates each $P$ class to its unique $Q$ along $f$. This means that we can form quotients of individual functions by congruences.
Products:
Let $f: A \to B, g : C \to D$ be functions. Then their product is $f \times g : A \times C \to B \times D$. With $(f \times g)(a,b) = (f(a),g(b))$. It is clear that $(first,first)$ and $(second,second)$ form congruences of the product function, producing the two underlying functions as quotients.
Coproducts:
Let $f : A \to B$ and $g : C \to D$ be functions. Then $f+g : A + C \to B + D$ is their coproduct. Then the two functions $f$ and $g$ are both subobjects defined by restriction to $(A,B)$ or $(C,D)$.
Other limits and colimits:
Equalizers and coequalizers can be defined piecewise. Then any other limits/colimits can be defined from them and coproducts/coproducts.
Magmas aren't just any pair of a set and a function. A magma $(S,*)$ is a set $S$ any a function $*$ specifically with the signature $* : S^2 \to S$. We can form a full subcategory of $Sets \times Sets^{\to}$ of objects of this form, but this doesn't recover the algebraic category: morphisms must take the form $(f, (f^2,f))$. This yields the following commutative diagram:
If we have a function $f: (S,*) \to (T,*)$ then this commutative diagram yields an expression of the form: $f(a*b) = f(a)*f(b)$. This means that a homomorphism of magmas is simply a special type of morphism of functions. So the topos $Sets^{\to}$ is truly a building block of magmas.
Magma is a subcategory of $Sets\times Sets^{to}$ consisting of objects $(S,* : S^2 \to S)$ and morphisms $(f,(f^2,f))$. This can be seen to be a subcategory because $(f,(f^2,f)) \circ (g,(g^2,g))$ is equal to $(f \circ g, (f^2 \circ g^2, f \circ g))$ and $f^2 \circ g^2$ can be rewritten as $(f \circ g)^2$ to get $(f \circ g, ((f \circ g)^2, f \circ g)$. This yields to an algebraic embedding of magma in a topos.
Semigroups are then a full subcategory of magmas. The basic point of this approach is that algebraic categories are constructed from the ground up from their constitutient topoi. It will be seen that topoi provide a more powerful logic then their subcategories, yielding all kinds of possibilities which wouldn't be available otherwise.
Missing from this construction is all partial magmas, which are a special type of subobject which could be constructed from non-closed sets. Likewise, out of semigroups we can construct partial semigroups. This demonstrates that the subalgebras constructed in algebraic subcategories are only a subset of what is possible.
Missing is the commutative part of a magma. Let $(M,* : M^2 \to M)$ be a magma. Define an equivalence relation $E$ on $M^2$ that identifies dual pairs $(a,b)$ and $(b,a)$ together. Then form the information image of $E$ to get an ordered pair $(E,Im(E))$. This ordered pair forms a generalized congruence of $*$, and so its quotient is the commutative quotient of the magma.
In categorical parlance, any other property that is invariant under reordering filters through the commutative quotient. As an example, the characteristic polynomial is invariant under change in ordering of matrix multiplication $p(AB) = p(BA)$. This means that it filters through the commutative quotient.
Additional quotients can be formed by the information images of the first and second parts of the ordered pair of the input of the magma operation, or any other equivalence relation of ordered pairs. The topos settings invites you to consider all kinds of non-standard of subalgebras and congruences like these that wouldn't be possible otherwise.
Algebraic categories like the category of magmas emerge by restricting the full power of a topos, yielding a subset of possible morphisms, subalgebras, congruences, and so on. The category of magmas has the restriction that its subobjects and quotients must again be magmas.
Topoi are the perfect categories, but much like with how suborders of a lattice need not be lattices, subcategories of topoi don't need to be topoi. Nonetheless, we can use category theory to study special cases and restrictions of topoi, which themselves don't need to be topoi anymore.
The signature not only tells you what a topos to be embedd an algebra in, but how to do it as well. The parent topos is simply determined by the number of terms in the signature. A number of algebraic structures composed of sets and functions can be built up this way:
As these topoi are simply constructed from sets and functions, they are not that far from foundations. To get to something a little bit more advanced, let $R$ be a unital ring then its category of R-modules can also be associated to a topos of monoid actions.
References:
Topoi categorical analysis of logic
Robert Goldblatt
In particular, I have in mind the generalization of the properties of universal algebra to individual functions. In total, these are some of the properties I would like to see from a model of functions:
- It should be close to the set theoretic model of functions as sets of ordered pairs, even though it is not necessarily the same as it.
- The various aspects of universal algebra should be applicable to it: homomorphisms, subalgebras, congruences, products, varieties, etc.
The problem with the set of ordered pairs account is that does not address the different properties of functions. If functions were just sets, algebra wouldn't be a different branch of mathematics distinguished from set theory. Yet it is, and that can be addressed with the topos $Sets^{\to}$.
This account is different from other earlier categorical accounts of universal algebra like Lawvere theories, because I explicitly intend for it to be done from the ground up. Before setting out into abstract algebra, I want to first figure out what functions are, and then we can use that to account for the properties of structures built out of them.
Functions as algebraic structures:
Universal algebra is concerned with the properties of algebraic structures built of functions, and so a starting point for the theory of universal algebra is the theory of individual functions $f : A \to B$. The properties of algebraic structures that are truly universal, should be applicable to these individual functions.Homomorphisms:
Let $f : A \to B, g : C \to D$ be functions. Then a homomorphism $h : f \to g$ of functions is an ordered pair of functions $(i : A \to C, o : B \to D)$ that satisfies the following commutative diagram:
Isomorphisms:Two functions $f : A \to B, g : C \to D$ in $Sets^{\to}$ are isomorphic, provided that the distribution of cardinalities of their fibers are the same.
Automorphisms:
Let $f: A \to B$ be a function, then $Aut(f)$ is its group of automorphisms. A function is associated with a kernel, which is the equivalence relation determined on inputs of $f$ and an image in $B$. The image in turn determines a complement of non-image values. $Aut(f)$ is the direct product of the automorphism group of the kernel equivalence relation and the symmetric group on the complement of the image. It is therefore a direct product of wreath products of symmetric groups by symmetric groups.
Subalgebras:
Let $f : A \to B$ be a function then subalgebras of $f$ are simply restrictions $(S,T) \subseteq (A,B)$ that respect images. It is in this setting, that the old idea of a function as a set of ordered pairs is partially restored, but there is more to functions then that as demonstrated by their congruences.Set images:
The subalgebras of a function are defined with respect to images, so that $(S,T)$ is a subobject provided that $f(A) \subseteq B$. In particular, the covariant power set functor associates to any function its image function $\wp(f) : \wp(A) \to \wp(B)$.
Set inverse images:
The dual operation for functions is the contravariant inverse image function. This takes $f : A \to B$ to $\overline{\wp}(f) : \wp(B) \to \wp(A)$. It is the largest set which produces a given image.
Lattice of subalgebras:
Let $f: A \to B$ be a function, then $Sub(f)$ is a distributive lattice of subobjects of $f$ consisting of all ordered pairs $(S,T)$ for which $f(A) \subseteq T$. Then this distributive lattice is associated to a closure operation by the image.
Subobject classifier:
As a topos, functions are associated with a trivalent logic. Let $f : A \to B$ be a function and $(S,T)$ be a subobject. Then its input truth value for $a \in A$ is zero if $f(a) \not\in T$, $\frac{1}{2}$ if $f(a) \in T \wedge a \not \in S$ and $1$ if $a \in S$. Its output truth value is $1$ if $b \in T$ and zero otherwise. The input and output truth values form an ordered pair $(i,o)$ which is the characteristic function of a function.
Congruences:
It often appears in applications that the classical definition of congruences is too restrictive. In order to handle generalized congruences in their appropriate context we need to have ordered pairs of equivalence relations $(P,Q)$. An ordered pair $(P,Q)$ of a function $f: A \to B$ is a congruence provided that: \[ x =_P y \Rightarrow f(x) =_Q f(y) \] We can consider equivalence relations as stores of information. For example, each function is associated with an equivalence relation in which $x =_f y$ when $f(x) = f(y)$ which determines the information provided by the function.In this setting, a congruence of a function captures the intuitive idea that pieces of information mapped by a function can determine pieces of information about the output. This distinguishes functions from sets of ordered pairs, because it explicitly uses the fact that functions are specific types of maps from inputs to outputs.
Information image:
The dual of the subset image, which determines the congruences of a function is the information image. It takes a partition of the input set, and it produces an output partition so that the two form a congruence. Let $f: A \to B$ be a function and $P$ a partition of $A$. Then define a partition $Q$ of $B$ by: \[ x =_Q y \Leftrightarrow \exists a_1, a_2 \in A : a =_P b \wedge f(a) = x \wedge f(b) = y \] Information inverse image:
We can also dualize the concept of a subset inverse image, in order to form an inverse image function for the lattice of partitions. This is the smallest piece of information that produces a given output. Let $f : A \to B$ be a function and $Q$ a partition of $B$ then define a partition $P$ of $A$ by: \[ a =_P b \Leftrightarrow f(a) =_Q f(b) \] Lattice of congruences:
Let $f : A \to B$ be a function, then its lattice of congruences $Con(f)$ consists of all ordered pairs $(P,Q)$ for which $a =_P b \Rightarrow f(a) =_Q f(b)$. In other words, it consists of all $(P,Q)$ for which $Q$ is a larger equivalence relation then $f(P)$.
Quotients:
Let $f: A \to B$ be a function and $(P,Q)$ a congruence of $f$. Then $\frac{f}{(P,Q)}: P \to Q$ is the function which associates each $P$ class to its unique $Q$ along $f$. This means that we can form quotients of individual functions by congruences.
Limits and colimits:
The basic operations of universal algebra are homomorphisms, subalgebras, congruences, and products. As it happens, products can also be defined on the level of individual functions.Products:
Let $f: A \to B, g : C \to D$ be functions. Then their product is $f \times g : A \times C \to B \times D$. With $(f \times g)(a,b) = (f(a),g(b))$. It is clear that $(first,first)$ and $(second,second)$ form congruences of the product function, producing the two underlying functions as quotients.
Coproducts:
Let $f : A \to B$ and $g : C \to D$ be functions. Then $f+g : A + C \to B + D$ is their coproduct. Then the two functions $f$ and $g$ are both subobjects defined by restriction to $(A,B)$ or $(C,D)$.
Other limits and colimits:
Equalizers and coequalizers can be defined piecewise. Then any other limits/colimits can be defined from them and coproducts/coproducts.
Equational classes:
The definition of subobjects, quotients, and products of functions means that we can define equational classes. In particular, a pseudovariety of functions is a class of functions closed under subobjects, quotients, and finite products. An example is constant functions: the product of constant functions is constant, as is any subobject or quotient.Composite structures:
Composite algebraic structures will be created from the ground-up from simpler components like sets and functions. This is done with product topoi.Homomorphisms:
Take magmas as an example: a magma is a set $S$ with a function $*$ or an ordered pair $(S,*)$. Then magmas are members of the product topos $Sets \times Sets^{\to}$, containing simpler components of a set and a function. A momorphism of $Sets \times Sets^{\to}$ is a morphism of a set and a function both.Magmas aren't just any pair of a set and a function. A magma $(S,*)$ is a set $S$ any a function $*$ specifically with the signature $* : S^2 \to S$. We can form a full subcategory of $Sets \times Sets^{\to}$ of objects of this form, but this doesn't recover the algebraic category: morphisms must take the form $(f, (f^2,f))$. This yields the following commutative diagram:
If we have a function $f: (S,*) \to (T,*)$ then this commutative diagram yields an expression of the form: $f(a*b) = f(a)*f(b)$. This means that a homomorphism of magmas is simply a special type of morphism of functions. So the topos $Sets^{\to}$ is truly a building block of magmas.
Magma is a subcategory of $Sets\times Sets^{to}$ consisting of objects $(S,* : S^2 \to S)$ and morphisms $(f,(f^2,f))$. This can be seen to be a subcategory because $(f,(f^2,f)) \circ (g,(g^2,g))$ is equal to $(f \circ g, (f^2 \circ g^2, f \circ g))$ and $f^2 \circ g^2$ can be rewritten as $(f \circ g)^2$ to get $(f \circ g, ((f \circ g)^2, f \circ g)$. This yields to an algebraic embedding of magma in a topos.
Semigroups are then a full subcategory of magmas. The basic point of this approach is that algebraic categories are constructed from the ground up from their constitutient topoi. It will be seen that topoi provide a more powerful logic then their subcategories, yielding all kinds of possibilities which wouldn't be available otherwise.
Subalgebras:
Let $(M,*)$ be a magma and $S$ a closed subset of $M$. Then a subalgebra of $M$ can be defined as a subobject of its set and of its function $(S,*|_{(S^2,S)})$. This a special type of subobject of $Sets \times Sets^{\to}$ but as magma is a subcategory, not all subobjects are revealed this way.Missing from this construction is all partial magmas, which are a special type of subobject which could be constructed from non-closed sets. Likewise, out of semigroups we can construct partial semigroups. This demonstrates that the subalgebras constructed in algebraic subcategories are only a subset of what is possible.
Congruences:
Let $(M,*)$ be a magma and $C$ an equivalence relation on $M$. Then it is a congruence provided that $(C^2,C)$ is a generalized congruence of the function $*$. Congruences of this from $(C^2,C)$ yield a subset of the possible congruences and quotients.Missing is the commutative part of a magma. Let $(M,* : M^2 \to M)$ be a magma. Define an equivalence relation $E$ on $M^2$ that identifies dual pairs $(a,b)$ and $(b,a)$ together. Then form the information image of $E$ to get an ordered pair $(E,Im(E))$. This ordered pair forms a generalized congruence of $*$, and so its quotient is the commutative quotient of the magma.
In categorical parlance, any other property that is invariant under reordering filters through the commutative quotient. As an example, the characteristic polynomial is invariant under change in ordering of matrix multiplication $p(AB) = p(BA)$. This means that it filters through the commutative quotient.
Additional quotients can be formed by the information images of the first and second parts of the ordered pair of the input of the magma operation, or any other equivalence relation of ordered pairs. The topos settings invites you to consider all kinds of non-standard of subalgebras and congruences like these that wouldn't be possible otherwise.
Algebraic categories like the category of magmas emerge by restricting the full power of a topos, yielding a subset of possible morphisms, subalgebras, congruences, and so on. The category of magmas has the restriction that its subobjects and quotients must again be magmas.
Topoi are the perfect categories, but much like with how suborders of a lattice need not be lattices, subcategories of topoi don't need to be topoi. Nonetheless, we can use category theory to study special cases and restrictions of topoi, which themselves don't need to be topoi anymore.
Algebraic categories:
It can easily be seen that the construction applied to magmas can be generalized to any algebraic structure addressed in universal algebra. Monoids can be embedded in $Sets \times (Sets^{\to})^2$, the identity is defined by an element function. Morphisms have the following form: $(f, (f^2,f),(f^0,f))$. Groups are embedded in $Sets \times (Sets^{\to})^3$.The signature not only tells you what a topos to be embedd an algebra in, but how to do it as well. The parent topos is simply determined by the number of terms in the signature. A number of algebraic structures composed of sets and functions can be built up this way:
- Ring with identity: $Sets \times (Sets^{\to})^5$
- Semiring with identity : $Sets \times (Sets^{\to})^4$
- Lattice : $Sets \times (Sets^{\to})^2$
- Lattice ordered semigroup: $Sets \times (Sets^{\to})^3$
- Residuated lattice: $Sets \times (Sets^{\to})^6$
As these topoi are simply constructed from sets and functions, they are not that far from foundations. To get to something a little bit more advanced, let $R$ be a unital ring then its category of R-modules can also be associated to a topos of monoid actions.
References:
Topoi categorical analysis of logic
Robert Goldblatt
Wednesday, July 28, 2021
Centralizer lattices of graphs
The commutativity necessary subalgebras of a semigroup or semiring form a lattice: the centralizer lattice of the commuting graph. Let $G$ be a graph and let $S,T$ be subsets of $G$ then $S$ and $T$ are said to be strongly adjacent provided that every vertex of $S$ is adjacent to every vertex of $T$.
Definition. Let $G$ be a graph then subsets $S$ and $T$ are strongly adjacent iff \[ \forall s \in S, t \in T: s \sim t \] Let $\wp(S)^2$ be the product lattice of the power set of $S$. Then it can shown that strong adjacency is hereditary within this lattice.
Proposition. let $(A,B) \subseteq (C,D)$ then $C \sim D \Rightarrow A \sim B$.
Proof. $ (a,b) \in (A,B) \implies (a,b) \in (C,D) \implies a \sim b $ $\square$
The centralizer of a set $S$ is merely the largest set that is strongly adjacent to it. Thusly, we have the following two identities on strong adjacency:
Proposition. let $A \sim B$ then $A \subseteq Centralizer(B)$ and $B \subseteq Centralizer(A)$.
The centralizer is the intersection of all centralizers of individual elements, so it is a semilattice homomorphism from unions to intersections.
Lemma 1. $A \subseteq Centralizer(Centralizer(A))$
Proof. the centralizer of a set is the largest set that forms a strongly adjacent pair with it. Therefore, $(A,Centralizer(A))$ form a strongly adjacent pair. The centralizer of a set must be larger then any set that forms a strongly adjacent pair with it so $A \subseteq Centralizer(Centralizer(A))$. $\square$
Lemma 2. the centralizer : $\wp(G) \to \wp(G)$ is antitone.
Proof. let $S \subseteq T$ be subsets of $G$ then \[ Centralizer(T) = Centralizer(S) \cap Centralizer(T-S) \subseteq Centralizer(S) \] Therefore, $Centralizer(T) \subseteq Centralizer(S)$. $\square$
Lemma 3. $Centralizer(Centralizer(Centralizer(A))) \subseteq Centralizer(A)$.
Proof. by lemma 1 we have that $A \subseteq Centralizer(Centralizer(A))$. By lemma two, application of centralizer to both sides reverses this inequality. $\square$
These three basic lemmas are the building blocks for the characterization theorem of the centralizer function and its associated centralizer lattice.
Definition. let $Centralizer : \wp(A) \to \wp(A)$ be the centralizer function. The the centralizer lattice $L$ is the image of this function.
The centralizer function can clearly be restricted to the centralizer lattice, which produces a special action which is the subject of our theorem today.
Theorem. the edges of the centralizer function on $L$ are the maximal strongly adjacent pairs of $G$
Proof. (1) let $(A,B)$ be a maximal strongly adjacent pair, then $A \subseteq Centralizer(B)$ and $B \subseteq Centralizer(A)$ by the definition of centralizers. By maximality, $Centralizer(B) \subseteq A$ and $Centralizer(A) \subseteq B$. Thusly, $Centralizer(A) = B$ and $Centralizer(B) = A$ so that $A$ and $B$ are both centralizers of one another.
(2) let $L$ be the centralizer lattice and let $C \in L$. It will be shown that $(C,Centralizer(C))$ forms a strongly adjacent pair. By the fact that $C$ is a centralizer there exists $A$ such that $C=Centralizer(A)$. Then consider the pair $(Centralizer(A),Centralizer(Centralizer(A))$. The later of these is maximal by the definition of the centralizer. The former is maximal by lemma three. $\square$
Not only does this describe the effect of the centralizer function, it describes it on the level of individual edges and it relates it to strong adjacency. By the fact that strong adjacency is hereditary, we could expect that it was fully determined by its maximal elements. These are precisely the edges of the centralizer action on the centralier lattice.
The relation of strong adjacency is symmetric, so the set of all maximal strongly adjacent pairs is symmetric. The centralizer action merely switches between the two elements of a strongly adjacent pair. It follows that it is an involution. As the centralizer is antitone, it forms a isomorphism from $L$ to its dual.
Corollary. the centralizer lattice is self-dual
This is the one thing we can say for sure about the centralizer lattices of graphs in general. The centralizer lattice is generated by all element centralizers, so one other issue worthy of examination is the meet irreducibles of a centralizer lattice.
Proposition. let $centralizer(a) = centralizer(B)$ then a is a lower bound of each $B$ in the adjacency preorder.
Proof. let $b \in B$ then by the fact that the centralizer is antitone, $centralizer(B) \subseteq centralizer(b)$ so by simple substitution $centralizer(a) \subseteq centralizer(b)$ whence $a \subseteq b$ with respect to the adjacency preordering. $\square$
Corollary. let $G$ be a graph with upper forest adjacency preorder, then the element centralizers are all meet irreducible elements of the centralizer lattice
Obvious examples where this is the case include triangle free graphs without leaf nodes and trivially perfect graphs. The key to constructing centralizer lattices of trivially perfect graphs is the following construction.
Definition. let $F$ be a family of lattices then the lattice theoretic disjoint union of $F$ is simply the lattice completion of the disjoint union of $F$ as posets.
The lattice congruence constructed by all identifying all the connected components and bounds separately has a height three lattice quotient.
Proposition. the centralizer lattices of trivially perfect graphs are precisely the graphs constructed from the single element lattice and repeated application of the lattice theoretic disjoint union.
Example. the following graph
has a centralizer lattice of the form
The centralizer lattices of trivially perfect graphs are planar. The centralizer lattices of graphs constructed from graph joins, like cographs can also be computed but they don't have as nice of depictions as they grow much faster. The centralizers in product graphs can also be determined componentwise.
See also:
Intersection semilattices of maximal cliques
Definition. Let $G$ be a graph then subsets $S$ and $T$ are strongly adjacent iff \[ \forall s \in S, t \in T: s \sim t \] Let $\wp(S)^2$ be the product lattice of the power set of $S$. Then it can shown that strong adjacency is hereditary within this lattice.
Proposition. let $(A,B) \subseteq (C,D)$ then $C \sim D \Rightarrow A \sim B$.
Proof. $ (a,b) \in (A,B) \implies (a,b) \in (C,D) \implies a \sim b $ $\square$
The centralizer of a set $S$ is merely the largest set that is strongly adjacent to it. Thusly, we have the following two identities on strong adjacency:
Proposition. let $A \sim B$ then $A \subseteq Centralizer(B)$ and $B \subseteq Centralizer(A)$.
The centralizer is the intersection of all centralizers of individual elements, so it is a semilattice homomorphism from unions to intersections.
Lemma 1. $A \subseteq Centralizer(Centralizer(A))$
Proof. the centralizer of a set is the largest set that forms a strongly adjacent pair with it. Therefore, $(A,Centralizer(A))$ form a strongly adjacent pair. The centralizer of a set must be larger then any set that forms a strongly adjacent pair with it so $A \subseteq Centralizer(Centralizer(A))$. $\square$
Lemma 2. the centralizer : $\wp(G) \to \wp(G)$ is antitone.
Proof. let $S \subseteq T$ be subsets of $G$ then \[ Centralizer(T) = Centralizer(S) \cap Centralizer(T-S) \subseteq Centralizer(S) \] Therefore, $Centralizer(T) \subseteq Centralizer(S)$. $\square$
Lemma 3. $Centralizer(Centralizer(Centralizer(A))) \subseteq Centralizer(A)$.
Proof. by lemma 1 we have that $A \subseteq Centralizer(Centralizer(A))$. By lemma two, application of centralizer to both sides reverses this inequality. $\square$
These three basic lemmas are the building blocks for the characterization theorem of the centralizer function and its associated centralizer lattice.
Definition. let $Centralizer : \wp(A) \to \wp(A)$ be the centralizer function. The the centralizer lattice $L$ is the image of this function.
The centralizer function can clearly be restricted to the centralizer lattice, which produces a special action which is the subject of our theorem today.
Theorem. the edges of the centralizer function on $L$ are the maximal strongly adjacent pairs of $G$
Proof. (1) let $(A,B)$ be a maximal strongly adjacent pair, then $A \subseteq Centralizer(B)$ and $B \subseteq Centralizer(A)$ by the definition of centralizers. By maximality, $Centralizer(B) \subseteq A$ and $Centralizer(A) \subseteq B$. Thusly, $Centralizer(A) = B$ and $Centralizer(B) = A$ so that $A$ and $B$ are both centralizers of one another.
(2) let $L$ be the centralizer lattice and let $C \in L$. It will be shown that $(C,Centralizer(C))$ forms a strongly adjacent pair. By the fact that $C$ is a centralizer there exists $A$ such that $C=Centralizer(A)$. Then consider the pair $(Centralizer(A),Centralizer(Centralizer(A))$. The later of these is maximal by the definition of the centralizer. The former is maximal by lemma three. $\square$
Not only does this describe the effect of the centralizer function, it describes it on the level of individual edges and it relates it to strong adjacency. By the fact that strong adjacency is hereditary, we could expect that it was fully determined by its maximal elements. These are precisely the edges of the centralizer action on the centralier lattice.
The relation of strong adjacency is symmetric, so the set of all maximal strongly adjacent pairs is symmetric. The centralizer action merely switches between the two elements of a strongly adjacent pair. It follows that it is an involution. As the centralizer is antitone, it forms a isomorphism from $L$ to its dual.
Corollary. the centralizer lattice is self-dual
This is the one thing we can say for sure about the centralizer lattices of graphs in general. The centralizer lattice is generated by all element centralizers, so one other issue worthy of examination is the meet irreducibles of a centralizer lattice.
Proposition. let $centralizer(a) = centralizer(B)$ then a is a lower bound of each $B$ in the adjacency preorder.
Proof. let $b \in B$ then by the fact that the centralizer is antitone, $centralizer(B) \subseteq centralizer(b)$ so by simple substitution $centralizer(a) \subseteq centralizer(b)$ whence $a \subseteq b$ with respect to the adjacency preordering. $\square$
Corollary. let $G$ be a graph with upper forest adjacency preorder, then the element centralizers are all meet irreducible elements of the centralizer lattice
Obvious examples where this is the case include triangle free graphs without leaf nodes and trivially perfect graphs. The key to constructing centralizer lattices of trivially perfect graphs is the following construction.
Definition. let $F$ be a family of lattices then the lattice theoretic disjoint union of $F$ is simply the lattice completion of the disjoint union of $F$ as posets.
The lattice congruence constructed by all identifying all the connected components and bounds separately has a height three lattice quotient.
Proposition. the centralizer lattices of trivially perfect graphs are precisely the graphs constructed from the single element lattice and repeated application of the lattice theoretic disjoint union.
Example. the following graph
has a centralizer lattice of the form
The centralizer lattices of trivially perfect graphs are planar. The centralizer lattices of graphs constructed from graph joins, like cographs can also be computed but they don't have as nice of depictions as they grow much faster. The centralizers in product graphs can also be determined componentwise.
See also:
Intersection semilattices of maximal cliques
Friday, July 23, 2021
Intersection semilattices of maximal cliques
Let $G$ be a graph, then the maximal cliques of the graph form a sperner family whose meet subsemilattice closure is the semilattice $M(G)$ of intersections of maximal cliques.
Example. let $A$ be a semigroup, ring, semigroup, or semiring then the maximal commuting clique intersections form a meet subsemilattice of $Sub(A)$.
The intersections of maximal cliques of $A$ are precisely the commutative subalgebras determined by the commuting graph. They produce a number of examples of commutative subalgebras in noncommutative algebra. Additionally, $M(G)$ provides an important order-theoretic account of graph properties.
Definition. let $a$,$b$ be elements of a poset then we say that $a \sim b$ provided that $\exists z: a \subseteq z \text{ and } b \subseteq z$.
Theorem. let $L$ be a meet semilattice, then it is a semilattice of intersections of the maximal cliques of a graph iff it satisfies the following two conditions:
Neccessity of condition (2): let $C_1,C_2 \in M(G)$ such that $C_1 \sim C_2$, then $C_1$ and $C_2$ are contained in some common clique $D$, which means that $C_1$ and $C_2$ are adjacent. Let $F$ be a family of cliques of $M(G)$ that pairwise share upper bounds, then $F$ is pairwise adjacent, so that $\cup F$ forms a clique. There must be at least one maximal clique $\cup F \subseteq Z$ such that $\forall C \in F : C \subseteq Z$.
Constructive proof of sufficiency: let $L$ be a meet semilattice that satisfies these conditions. Then let $F$ be the maximal principal ideals of $L$. By condition (1) $F$ forms a sperner family. We can reconstruct the primal graph of the set system $F$ by $x \sim y$ if $\exists S \in F : \{x,y\} \subseteq S$, but this is precisely the upper bound sharing graph of $L$.
Let $C$ be any maximal clique of the upper bound sharing graph, then by condition (2) there is some clique $Z$ in $F$ that contains $C$ so that $C \subseteq Z$. It follows that any $\sim$ clique is a clique in $F$. Let $S \in F$ then $S$ is a $\sim$ clique, because $S$ is contains any pair of its own elements, and it is maximal because it is in a family $F$ that contains all its own cliques. Therefore, $F$ forms a maximal cliques family. $\square$
Theorem. the join irreducibles (excluding the minimal element as the empty join) of $M(G)$ are necessarily adjacency principal filters.
Proof. let $S \in M(G)$ be a clique in $M(G)$. Then suppose that $S$ is not an adjacency principal filter, then $S$ doesn't have any elements unique to itself, so it is the union of all its predecessors. As it is a union it is join reducible. Then suppose that a join irreducible element that is not an adjacency principal filter, then it is union irreducible which means it is join irreducible which is a contradiction. $\square$
We have the following bounds the suborder of the adjacency principal filters of $M(G)$: (1) the filters must contain all join irreducibles and (2) they can include up to the entire set $G$. The suborder of $M(G)$ consisting of adjacency principal filters is an important source of information, because it determines a graph up to adjacency equality.
Theorem. let $L$ be a semilattice with subset $S$ consisting of adjacency principal filters. Then all graphs having $S$ as a suborder of $M(G)$ equal to $L$ have the same condensation.
Proof. let $\uparrow : G \to L$ be the principal adjacency filter function for the semilattice $L$. Then we can recover $M(G)$ by recursion. \[ f(l) = \uparrow^{-1}(l) \cup \bigcup_{i \subset l} f(i)\] Then since the graph $G$ can be recovered by its maximal cliques, every graph $G$ can then be defined by its $\uparrow$ function. The adjacency equality of $G$ is the kernel of $\uparrow$, which has no effect up to condensation. Condensed graphs are therefore determined by the image of $\uparrow$ which is a suborder of $M(G)$. $\square$
Corollary. the condensation types of graphs are determined by the images of $\uparrow$, which are subobjects of the semilattice $L$.
There are generally multiple condensation types associated to a given order type $L$. This is demonstrated below.
Example 1. the cyclic graph $C_4$
it has a maximal cliques intersection semilattice of the following form, with the adjacency principal filters highlighted:
the following larger graph has the same intersection order type
but it has a different set of principal adjacency filters
Example 2. the path graph $P_4$
has an intersection semilattice that looks like this
the following larger graph
has a semilattice with more adjacency principal filters
In fact, every graph of with this semilattice order type has the condensation of either a path, gem, bull, or the above larger graph.
Theorem. let $G$ be a graph then $G$ is trivially perfect (e.g $P_4,C_4$-free) iff $M(G)$ is a lower tree
Proof. let $G$ be a trivially perfect graph, then removal of the center always disconnects the graph into connected components. The class of trivially perfect graphs is hereditary, so this can be applied recursively to get a lower tree decomposition of $G$. In the other direction, if the minimal element of $M(G)$ is a cut vertex, it can be removed to get connected components. In a lower tree this can be applied again recursively, to get a trivially perfect graph. $\square$
We can recover the clique graph of a graph, provided that we have the order type of $M(G)$ and its suborder of adjacency principal filters.
Proposition. let $G$ be a graph, with $M(G)$ its semilattice of intersections of maximal cliques, with $S$ its set of adjacency principal filters. Then if the minimal element of $M(G)$ is in $S$ the clique graph is a complete graph, otherwise it is equal to the independence graph of the maximal elements: two elements are independent provided they meet at the minimal element.
A graph is a clique graph provided that it has a Helly edge covering of its cliques. The Helly property of the independence graph of any semilattice $M(G)$ follows from the upper bound sharing property.
Proposition. the clique number of $G$ is equal to the rank of $M(G)$
A quick look at some of the set-theoretic properties of a selected assortment of classes of graphs is presented below:
In a cluster graph, the maximal cliques correspond to connected components so that $M(G)$ is a pairwise disjoint family. In a cocluster graph, the cocluster is the graph join of empty graphs, which means that is convex from the maximal cliques of $G$ to the center.
Another case where we might want to compute $M(G)$ is when dealing with a $G$ composed from certain basic graph operations:
References:
[1] Clique graphs
[2] Trivially perfect graphs
Example. let $A$ be a semigroup, ring, semigroup, or semiring then the maximal commuting clique intersections form a meet subsemilattice of $Sub(A)$.
The intersections of maximal cliques of $A$ are precisely the commutative subalgebras determined by the commuting graph. They produce a number of examples of commutative subalgebras in noncommutative algebra. Additionally, $M(G)$ provides an important order-theoretic account of graph properties.
Order theoretic properties of the intersection semilattice
The order types of the intersection semilattices $M(G)$ generated by maximal cliques have a complete order-theoretic classification.Definition. let $a$,$b$ be elements of a poset then we say that $a \sim b$ provided that $\exists z: a \subseteq z \text{ and } b \subseteq z$.
Theorem. let $L$ be a meet semilattice, then it is a semilattice of intersections of the maximal cliques of a graph iff it satisfies the following two conditions:
- $L$ is generated by its maximal elements
- $L$ satisfies the upper bound sharing property: let $C$ be any clique in the upper bound sharing graph $\sim$ then $\exists z : \forall c \in C : c \subseteq z$.
Neccessity of condition (2): let $C_1,C_2 \in M(G)$ such that $C_1 \sim C_2$, then $C_1$ and $C_2$ are contained in some common clique $D$, which means that $C_1$ and $C_2$ are adjacent. Let $F$ be a family of cliques of $M(G)$ that pairwise share upper bounds, then $F$ is pairwise adjacent, so that $\cup F$ forms a clique. There must be at least one maximal clique $\cup F \subseteq Z$ such that $\forall C \in F : C \subseteq Z$.
Constructive proof of sufficiency: let $L$ be a meet semilattice that satisfies these conditions. Then let $F$ be the maximal principal ideals of $L$. By condition (1) $F$ forms a sperner family. We can reconstruct the primal graph of the set system $F$ by $x \sim y$ if $\exists S \in F : \{x,y\} \subseteq S$, but this is precisely the upper bound sharing graph of $L$.
Let $C$ be any maximal clique of the upper bound sharing graph, then by condition (2) there is some clique $Z$ in $F$ that contains $C$ so that $C \subseteq Z$. It follows that any $\sim$ clique is a clique in $F$. Let $S \in F$ then $S$ is a $\sim$ clique, because $S$ is contains any pair of its own elements, and it is maximal because it is in a family $F$ that contains all its own cliques. Therefore, $F$ forms a maximal cliques family. $\square$
Suborder of adjacency principal filters:
Let $x \in G$. Then the intersection of all cliques of $M(G)$ containing $x$ is the adjacency principal filter $\uparrow x$ of $x$. This is the smallest member of $M(G)$ containing $x$. \[ \uparrow : G \to M(G) \] The image of $\uparrow$ is the subset of $M(G)$ consisting of all adjacency principal filters. The kernel of $\uparrow$ is the adjacency equality relation of $G$. The condensation of $G$ is the quotient of $G$ with respect to adjacency equality.Theorem. the join irreducibles (excluding the minimal element as the empty join) of $M(G)$ are necessarily adjacency principal filters.
Proof. let $S \in M(G)$ be a clique in $M(G)$. Then suppose that $S$ is not an adjacency principal filter, then $S$ doesn't have any elements unique to itself, so it is the union of all its predecessors. As it is a union it is join reducible. Then suppose that a join irreducible element that is not an adjacency principal filter, then it is union irreducible which means it is join irreducible which is a contradiction. $\square$
We have the following bounds the suborder of the adjacency principal filters of $M(G)$: (1) the filters must contain all join irreducibles and (2) they can include up to the entire set $G$. The suborder of $M(G)$ consisting of adjacency principal filters is an important source of information, because it determines a graph up to adjacency equality.
Theorem. let $L$ be a semilattice with subset $S$ consisting of adjacency principal filters. Then all graphs having $S$ as a suborder of $M(G)$ equal to $L$ have the same condensation.
Proof. let $\uparrow : G \to L$ be the principal adjacency filter function for the semilattice $L$. Then we can recover $M(G)$ by recursion. \[ f(l) = \uparrow^{-1}(l) \cup \bigcup_{i \subset l} f(i)\] Then since the graph $G$ can be recovered by its maximal cliques, every graph $G$ can then be defined by its $\uparrow$ function. The adjacency equality of $G$ is the kernel of $\uparrow$, which has no effect up to condensation. Condensed graphs are therefore determined by the image of $\uparrow$ which is a suborder of $M(G)$. $\square$
Corollary. the condensation types of graphs are determined by the images of $\uparrow$, which are subobjects of the semilattice $L$.
There are generally multiple condensation types associated to a given order type $L$. This is demonstrated below.
Example 1. the cyclic graph $C_4$
it has a maximal cliques intersection semilattice of the following form, with the adjacency principal filters highlighted:
the following larger graph has the same intersection order type
but it has a different set of principal adjacency filters
Example 2. the path graph $P_4$
has an intersection semilattice that looks like this
the following larger graph
has a semilattice with more adjacency principal filters
In fact, every graph of with this semilattice order type has the condensation of either a path, gem, bull, or the above larger graph.
Theorem. let $G$ be a graph then $G$ is trivially perfect (e.g $P_4,C_4$-free) iff $M(G)$ is a lower tree
Proof. let $G$ be a trivially perfect graph, then removal of the center always disconnects the graph into connected components. The class of trivially perfect graphs is hereditary, so this can be applied recursively to get a lower tree decomposition of $G$. In the other direction, if the minimal element of $M(G)$ is a cut vertex, it can be removed to get connected components. In a lower tree this can be applied again recursively, to get a trivially perfect graph. $\square$
We can recover the clique graph of a graph, provided that we have the order type of $M(G)$ and its suborder of adjacency principal filters.
Proposition. let $G$ be a graph, with $M(G)$ its semilattice of intersections of maximal cliques, with $S$ its set of adjacency principal filters. Then if the minimal element of $M(G)$ is in $S$ the clique graph is a complete graph, otherwise it is equal to the independence graph of the maximal elements: two elements are independent provided they meet at the minimal element.
A graph is a clique graph provided that it has a Helly edge covering of its cliques. The Helly property of the independence graph of any semilattice $M(G)$ follows from the upper bound sharing property.
Graph theoretic properties:
The intersection semilattice has an order type and a suborder of adjacency principal filters, but it also contains additional data as a set system such as the clique number of the graph, which would not be recordered otherwise.Proposition. the clique number of $G$ is equal to the rank of $M(G)$
A quick look at some of the set-theoretic properties of a selected assortment of classes of graphs is presented below:
| $G$ | $M(G)$ |
|---|---|
| Empty graph | Rank one family |
| Complete graph | Unique family |
| Cluster graph | Pairwise disjoint family |
| Cocluster graph | Convex family |
| Triangle free graph | Rank two family |
| Cotriangle free graph | Cotriangle free maxima intersections |
| Trivially perfect graph: | Lower tree ordered family |
Another case where we might want to compute $M(G)$ is when dealing with a $G$ composed from certain basic graph operations:
- Graph coproducts: $M(C_1 + C_2) = M(C_1) \cup M(C_2) \cup \{\emptyset\}$.
- Graph join: $M(\overline{\overline{C_1} + \overline{C_2}} ) = \{x \cup y: x \in C_1, y \in C_2\}$
- Graph products: $M(G \times H) = \{ C_1 \times C_2 : C_1 \in M(G), C_2 \in M(H) \}$
References:
[1] Clique graphs
[2] Trivially perfect graphs
Friday, July 2, 2021
Lattices of subcategories
Every structure is characterized by its component parts. In the case of categories, a locally small category $C$ can be considered to be a special type of structured set. The parts of a category are determined by subsets of its underlying set. Subcategories are parts of categories which are themselves categories.
We define the elements of a category to be either its objects or morphisms. It follows that the underlying set of a category is the coproduct of its object and morphism sets. This produces a combined ontology of categorical elements containing both objects and morphisms as special cases.
The characterization of categories as structured sets produces a corresponding ontology of sets of elements of categories. These sets of categorical elements are called categorical systems, and they form a broad generalization of both object systems and morphism systems. Subcategories are merely a special case.
As a first step toward subcategories, we can require that a categorical system have all the objects of its morphisms. This produces the lattice of subquivers of a category, which forms a distributive lattice. This distributive lattice characterizes the fact that categorical elements have a dependency ordering in which morphisms are dependent on the objects they refer to.
The requirement that a categorical system preserves identities still produces a distributive lattice, in this case with identity morphisms equivalent to the objects they refer to. It is the condition of composition closure that makes the lattice of subcategories $Sub(C)$ of a category $C$ lose distributivity. The lattice of subsemigroupoids, which also has composition closure, also doesn't need to be distributive.
A number of special cases of categorical systems emerge from the various object and morphism preorders of a category. These are essentially the ideals of a category, commonly known as either sieves or cribles. These lattices, as lattices of ideals, are naturally distributive. An ontology of categorical systems like these is presented below.
A special case is the lattice of subgroupoids which is used in groupoid theory. The lattice of subcategories $Sub(C)$ contains a number of sublattices. The lattice of discrete subcategories is an example of a boolean sublattice. The lattice of wide subcategories consists of the interval of subcategories with the maximal discrete subcategory as its minimal element. Wide subgroupoids emerge from the combination of the two conditions.
The first special case we will be considering are hom complete subcategories. These correspond naturally to subpreorders of the morphic preordering, so they naturally produce a link between categories and order theory. This will further illuminate the order-theoretic nature of categories.
Theorem. the morphic preordering $R : Cat \to Ord$ is an epifunctor from the category of categories to the category of preorders and monotone maps. It takes each category its underlying preorder, and each functor to its underlying monotone map.
Proof. (1) let $f : C \to D$ be a functor and $R(f) : R(C) \to R(D)$ its underlying object map between preorders. Then if $A \subseteq B$ in $R(C)$ that means $\exists m \in C : m : A \to B$. Then the output of $f$ on $m$ has signature $f(m) : f(A) \to f(B)$. Which means that $\exists f(m) \in Arrows(D)$ such that $f(m)$ has signature $f(A) \to f(B)$. Therefore, $f(A) \subseteq f(B)$ in $R(D)$. It follows that $R(f)$ is monotone.
(2) Let $1_C : C \to C$ be the identity endofunctor, then its underlying monotone map is $1_{R(C)} : R(C) \to R(C)$ which is an identity of preorders. Therefore, $R(C)$ preserves identities.
(3) Let $f : A \to B$ and $g : B \to C$ be functors. Then $R(f \circ g)$ takes $Ob(A) \to Ob(C)$ by $f \circ g$. Therefore, $R(f \circ g)(x) = f(g(x))$. This is equal to $R(f) \circ R(g)$ so $R(fg) = R(f) \circ R(g)$. $\square$
By presenting any preorder as a thin category, we can also get a functor that maps any category to its underlying preorder. This maps objects to objects and morphisms to edges in the preorder.
Theorem. let $C$ be a category and $\pi : C \to R(C)$ the map from $C$ to its morphic preordering. Then $\pi$ is an epimorphism of categories.
Proof. let $f,g \in Arrows(C)$ with $f : A \to B$ and $g : B \to C$. Then $\pi(f) = (A,B)$, $\pi(g) = (B,C)$ and $\pi(g \circ f) = (A,C) = (A,B) \circ (A,C)$. Therefore, $\pi(f \circ g) = \pi(f) \circ \pi(g)$ so $\pi$ is a functor. $\square$
Lemma. let $F : C \to D$ be a functor, then $f$ reflects subcategories.
Proof. Let $S$ be a subcategory of $D$. Then this can be proven in three stages.
(1) let $let f \in Arrows(C)$ with $f : A \to B$ such that $F(f) \in S$. Then $F(f) : F(A) \to F(B)$ so by the fact that $S$ is a subcategory, $F(A),F(B) \in S$. It follows that $F^{-1}(S)$ is at least a subquiver.
(2) let $X \in Ob(C)$ such that $F(X) \in S$ then $F(1_X) = 1_{F(X)}$. By the fact that $S$ is a subcategory, and $F(X) \in S$ we have that $1_{F(X)} \in S$. It follows that $F^{-1}(S)$ is identity closed.
(3) let $f : A \to B$ and $g : B \to C$ such that $f,g \in Arrows(C)$ and $F(f),F(g) \in S$. Then $F(g \circ f) = F(g) \circ F(f)$. By the fact that $S$ is a subcategory, and that $F(g) \in S$ and $F(f) \in S$ we have that $F(g) \circ F(f) \in S$. It follows that $F^{-1}(S)$ is composition closed. $\square$
We can precede these previous two lemmas to get that the map $\pi$ reflects subcategories, so the following corollary follows immediately.
Corollary. $\pi$ reflects subcategories
We can now define the suborders of a category to the subcategories produced by reflection of the $\pi$ functor, which maps each category to its underlying preorder.
Definition. let $C$ be a category with a suborder $S$ of its morphic preordering $R$. The suborder of the corresponding category is the reflection of $S$ with respect to the functor $\pi : C \to R$.
The lattice of preorders can be denoted $Po(R)$. Then clearly the lattice of preorders of $R$ is clearly equal to the lattice of categories of $R$ presented as a thin category. At this point, we have a lattice monomorphism from the lattice of preorders $Po(R)$ to the lattice of subcategories of any category $C$. \[ s : Po(R) \to Sub(C) \] Every suborder of a category is hom-complete, meaning that for any hom class in the subcategory $S$ every morphism in the same hom class in $C$ is in $S$. This leads the notion of hom completion, which completes a category by adding all morphisms in hom classes of the parent category to it. Therefore, the image of this lattice monomorphism is the lattice of hom complete subcategories of a category.
The lattice of preorders doesn't appear as much as its special case: the lattice of equivalence relations $Part(A)$. This lattice is clearly a suborder of the lattice of preorders, and we will also show that it is a sublattice.
Lemma. let $R$ be a symmetric relation, then its transitive closure is symmetric
Proof. if we have $(A,B),(B,C) \in R$ then we have $(A,C)$ by transitivity. By symmetry we have $(B,A),(C,B)$ are in $R$ as well so $(C,A)$ is in $R$ so transitive closure preserves symmetry. $\square$
Theorem. $Part(A)$ is a sublattice of $Po(R)$
Proof. (1) the intersection of equivalence relations is an equivalence relation so it is clearly a meet subsemilattice (2) the union of reflexive, symmetric relations is symmetric and reflexive so in order to prove join closure all we need is to demonstrate that transitive closure preserves symmetry, by the previous lemma it does so $Part(A)$ is a sublattice. $\square$
We can express this in categorical terms, by replacing the symmetric relations with groupoids. Equivalence relations are then equivalent to thin groupoids.
Theorem. $Part(A)$ is the sublattice of wide subgroupids of the subcategory lattice of the complete thin groupoid.
A special case of a suborder is an induced suborder, which is a subset of a preorder based upon a set of vertices in which all edges between the vertices are included in the suborder. The corresponding categorical notion is a full subcategory. This produces a lattice monomorphism from subsets of $Ob(C)$ to $Sub(C)$, which is weaker then the suborder morphism. \[ f : \wp(Ob(C)) \to Sub(C) \] The corresponding type of category for which all subcategories are full is the class of discrete categories. Then the subcategory lattice of a discrete category is a boolean algebra of sets. We therefore have a characterization of $\wp(S)$ and $Part(A)$ in terms of subcategory lattices.
Theorem. let $C$ be a category, then the categories of monos, epis, bis, split epis, split monos, isos, endos, and autos are all subcatgories.
Proof. (1) let $f$ and $g$ be monos. Then $fx = fy \Rightarrow x=y$. Therefore, if we have $g(fx) = g(fy)$ this implies that $fx = fy$ which implies $x=y$ so mononess is composition closed. Dually for epis, then bis are simply the intersection of epis and monos.
(2) Let $f,g$ be split epimorphisms then the inverse of $g \circ f$ is equal to $f^{-} \circ g^{-1}$ because $g \circ f \circ f^{-1} \circ g^{-1}$ which clearly cancels to the identity. In the other direction, if we have $f,g$ as split monomorphisms then $g \circ f$ has inverse $f^{-1} \circ g^{-1}$ so that $f^{-1} \circ g^{-1} \circ g \circ f$ clearly cances to the identity. The composition closure of isomorphisms follows from the intersection of split monos and split epis.
(3) Endomorphisms are clearly composition closed, and they are hom-complete so they are also the suborder produced by the coreflexive relation on $Ob(C)$. $\square$
Let $C$ be a category, then the subcategory of morphisms of one of these types is a subcategory. This can be applied to get the underlying groupoid of a category.
Definition. Let $C$ be a category, then the subcategory generated by its isomorphisms is the underlying groupoid of $C$.
We can get the underlying subgroupoid of a subcategory. In general, for any class of morphisms that generates types of subcategories, we can get an action on $Sub(C)$. \[ f : Sub(C) \to Sub(C) \] This construction of an action on the lattice of subcategories invites us to consider the effect of taking subcategories on the different types of morphisms.
It is self-evident that ideals of form subcategories, because they are closed under composition with respect to morphisms from the overall category $C$. An interesting construction occurs where in we can change the category of morphisms acting on $I$ to some other subcategory $S$. This produces a family of three types of monotone maps from the lattice of subcategories to the lattice of preorders: \[ L : Sub(C) \to Po(Ob(C)) \] \[ R : Sub(C) \to Po(Ob(C)) \] \[ J : Sub(C) \to Po(Ob(C)) \] As these preorders are constructed from the actions of subcategories, their ideals don't need to be subcategories. An important example is an isomorphism ideal, which is an ideal with respect to two sided action of the underlying groupoid. Subcategories that are also closed under underlying groupoid action are called replete.
Repletion forms a closure action on the lattice of subcategories $Sub(C)$, and so the family of all replete subcategories forms a lattice determined by the skeleton of the category. Action preorders can also be formed by the mono and epi subcategories.
The monotonicity of the map from subcategories to preorders means that smaller subcategories can only have smaller preorders of subobjects and quotients. This is translated to the language of subobject and quotient posets by the condensation which produces partial orders from preorders.
A category with non-trivial connected components admits a coproduct decomposition, and so this leads to the following theorem which characterizes the lattice of subcategories of a coproduct category in terms of product lattices.
Theorem. $Sub(C + D) = Sub(C) \times Sub(D)$.
Proof. This can be proven by a one to one map. Let $C$ and $D$ be connected components of the category $C + D$ and let $S$ and $T$ be subcategories of $C$ and $D$ respectively. Then by the fact that $C$ and $D$ are prime subcategories $S \cup T$ is a subcategory of $C + D$ so the union leads to an injective map from $Sub(C) \times Sub(D)$ to $Sub(C + D)$. In the other direction, any subcategory of $C+D$ can be decomposed into a subcategory of $C$ and a subcategory of $D$ by taking full subcategories with respect to $Ob(C)$ and $Ob(D)$. $\square$
This simple construction allows us to determine the lattices of subcategories of antichain categories from the lattices of subcategories of the endomorphism monoids of the category.
Lower sets:
If $F$ is a subalgebra closed family of categories, then the family of all subcategories of $C$ in $F$ forms a lower set of $Sub(C)$. For example, the family of all thin subcategories of a category is a lower set as is the lattice of all discrete subcategories.
Closure systems:
The families of subgropoids, the various ideal-related construction on categories like replete subcategories, and so on all form closure systems. These are upper bound maintaining meet subsemilattices of $Sub(C)$.
Sublattices:
Besides the lattice of discrete subcategories, the lattice of subgroupoids forms a sublattice of the lattice of subcategories of a groupoid. This can be proven in the following theorem.
Theorem. let $G$ be a groupoid and let $A,B \subseteq G$ be subgroupoids. Then the subcategory join $A \vee B$ is a subgroupoid.
Proof. the subcategory join $A \vee B$ consists of all words of the form $a_1 b_1 a_2 b_2 a_3 b_3 ... $. This simply has inverse $b_3^{-1} a_3^{-1} b_2^{-1} a_2^{-1} b_1^{-1} a_1^{-1}$. The words of $A \vee B$ have inverses, so join preserves inverses. The fact that the subcategory join of subgroupoids is a subgroupoid means that the lattice of subgroupoids is a sublattice of the lattice of subcategories.
We define the elements of a category to be either its objects or morphisms. It follows that the underlying set of a category is the coproduct of its object and morphism sets. This produces a combined ontology of categorical elements containing both objects and morphisms as special cases.
The characterization of categories as structured sets produces a corresponding ontology of sets of elements of categories. These sets of categorical elements are called categorical systems, and they form a broad generalization of both object systems and morphism systems. Subcategories are merely a special case.
As a first step toward subcategories, we can require that a categorical system have all the objects of its morphisms. This produces the lattice of subquivers of a category, which forms a distributive lattice. This distributive lattice characterizes the fact that categorical elements have a dependency ordering in which morphisms are dependent on the objects they refer to.
The requirement that a categorical system preserves identities still produces a distributive lattice, in this case with identity morphisms equivalent to the objects they refer to. It is the condition of composition closure that makes the lattice of subcategories $Sub(C)$ of a category $C$ lose distributivity. The lattice of subsemigroupoids, which also has composition closure, also doesn't need to be distributive.
A number of special cases of categorical systems emerge from the various object and morphism preorders of a category. These are essentially the ideals of a category, commonly known as either sieves or cribles. These lattices, as lattices of ideals, are naturally distributive. An ontology of categorical systems like these is presented below.
A special case is the lattice of subgroupoids which is used in groupoid theory. The lattice of subcategories $Sub(C)$ contains a number of sublattices. The lattice of discrete subcategories is an example of a boolean sublattice. The lattice of wide subcategories consists of the interval of subcategories with the maximal discrete subcategory as its minimal element. Wide subgroupoids emerge from the combination of the two conditions.
The first special case we will be considering are hom complete subcategories. These correspond naturally to subpreorders of the morphic preordering, so they naturally produce a link between categories and order theory. This will further illuminate the order-theoretic nature of categories.
Suborders of a category
Categories can be characterized as sorts of generalized posets. This is formalized by the functor of categories that takes any category to its underlying morphic preorder, and a functor to its underlynig monotone map. This functor reflects subcategories, which produces our notion of suborders of a category.Theorem. the morphic preordering $R : Cat \to Ord$ is an epifunctor from the category of categories to the category of preorders and monotone maps. It takes each category its underlying preorder, and each functor to its underlying monotone map.
Proof. (1) let $f : C \to D$ be a functor and $R(f) : R(C) \to R(D)$ its underlying object map between preorders. Then if $A \subseteq B$ in $R(C)$ that means $\exists m \in C : m : A \to B$. Then the output of $f$ on $m$ has signature $f(m) : f(A) \to f(B)$. Which means that $\exists f(m) \in Arrows(D)$ such that $f(m)$ has signature $f(A) \to f(B)$. Therefore, $f(A) \subseteq f(B)$ in $R(D)$. It follows that $R(f)$ is monotone.
(2) Let $1_C : C \to C$ be the identity endofunctor, then its underlying monotone map is $1_{R(C)} : R(C) \to R(C)$ which is an identity of preorders. Therefore, $R(C)$ preserves identities.
(3) Let $f : A \to B$ and $g : B \to C$ be functors. Then $R(f \circ g)$ takes $Ob(A) \to Ob(C)$ by $f \circ g$. Therefore, $R(f \circ g)(x) = f(g(x))$. This is equal to $R(f) \circ R(g)$ so $R(fg) = R(f) \circ R(g)$. $\square$
By presenting any preorder as a thin category, we can also get a functor that maps any category to its underlying preorder. This maps objects to objects and morphisms to edges in the preorder.
Theorem. let $C$ be a category and $\pi : C \to R(C)$ the map from $C$ to its morphic preordering. Then $\pi$ is an epimorphism of categories.
Proof. let $f,g \in Arrows(C)$ with $f : A \to B$ and $g : B \to C$. Then $\pi(f) = (A,B)$, $\pi(g) = (B,C)$ and $\pi(g \circ f) = (A,C) = (A,B) \circ (A,C)$. Therefore, $\pi(f \circ g) = \pi(f) \circ \pi(g)$ so $\pi$ is a functor. $\square$
Lemma. let $F : C \to D$ be a functor, then $f$ reflects subcategories.
Proof. Let $S$ be a subcategory of $D$. Then this can be proven in three stages.
(1) let $let f \in Arrows(C)$ with $f : A \to B$ such that $F(f) \in S$. Then $F(f) : F(A) \to F(B)$ so by the fact that $S$ is a subcategory, $F(A),F(B) \in S$. It follows that $F^{-1}(S)$ is at least a subquiver.
(2) let $X \in Ob(C)$ such that $F(X) \in S$ then $F(1_X) = 1_{F(X)}$. By the fact that $S$ is a subcategory, and $F(X) \in S$ we have that $1_{F(X)} \in S$. It follows that $F^{-1}(S)$ is identity closed.
(3) let $f : A \to B$ and $g : B \to C$ such that $f,g \in Arrows(C)$ and $F(f),F(g) \in S$. Then $F(g \circ f) = F(g) \circ F(f)$. By the fact that $S$ is a subcategory, and that $F(g) \in S$ and $F(f) \in S$ we have that $F(g) \circ F(f) \in S$. It follows that $F^{-1}(S)$ is composition closed. $\square$
We can precede these previous two lemmas to get that the map $\pi$ reflects subcategories, so the following corollary follows immediately.
Corollary. $\pi$ reflects subcategories
We can now define the suborders of a category to the subcategories produced by reflection of the $\pi$ functor, which maps each category to its underlying preorder.
Definition. let $C$ be a category with a suborder $S$ of its morphic preordering $R$. The suborder of the corresponding category is the reflection of $S$ with respect to the functor $\pi : C \to R$.
The lattice of preorders can be denoted $Po(R)$. Then clearly the lattice of preorders of $R$ is clearly equal to the lattice of categories of $R$ presented as a thin category. At this point, we have a lattice monomorphism from the lattice of preorders $Po(R)$ to the lattice of subcategories of any category $C$. \[ s : Po(R) \to Sub(C) \] Every suborder of a category is hom-complete, meaning that for any hom class in the subcategory $S$ every morphism in the same hom class in $C$ is in $S$. This leads the notion of hom completion, which completes a category by adding all morphisms in hom classes of the parent category to it. Therefore, the image of this lattice monomorphism is the lattice of hom complete subcategories of a category.
The lattice of preorders doesn't appear as much as its special case: the lattice of equivalence relations $Part(A)$. This lattice is clearly a suborder of the lattice of preorders, and we will also show that it is a sublattice.
Lemma. let $R$ be a symmetric relation, then its transitive closure is symmetric
Proof. if we have $(A,B),(B,C) \in R$ then we have $(A,C)$ by transitivity. By symmetry we have $(B,A),(C,B)$ are in $R$ as well so $(C,A)$ is in $R$ so transitive closure preserves symmetry. $\square$
Theorem. $Part(A)$ is a sublattice of $Po(R)$
Proof. (1) the intersection of equivalence relations is an equivalence relation so it is clearly a meet subsemilattice (2) the union of reflexive, symmetric relations is symmetric and reflexive so in order to prove join closure all we need is to demonstrate that transitive closure preserves symmetry, by the previous lemma it does so $Part(A)$ is a sublattice. $\square$
We can express this in categorical terms, by replacing the symmetric relations with groupoids. Equivalence relations are then equivalent to thin groupoids.
Theorem. $Part(A)$ is the sublattice of wide subgroupids of the subcategory lattice of the complete thin groupoid.
A special case of a suborder is an induced suborder, which is a subset of a preorder based upon a set of vertices in which all edges between the vertices are included in the suborder. The corresponding categorical notion is a full subcategory. This produces a lattice monomorphism from subsets of $Ob(C)$ to $Sub(C)$, which is weaker then the suborder morphism. \[ f : \wp(Ob(C)) \to Sub(C) \] The corresponding type of category for which all subcategories are full is the class of discrete categories. Then the subcategory lattice of a discrete category is a boolean algebra of sets. We therefore have a characterization of $\wp(S)$ and $Part(A)$ in terms of subcategory lattices.
Subcategory producing functions:
The most important types of morphisms like monomorphisms, epimorphisms, isomorphisms, and endomorphisms are composition closed. This means all these types of morphisms are associated to types of subcategories of any category $C$.Theorem. let $C$ be a category, then the categories of monos, epis, bis, split epis, split monos, isos, endos, and autos are all subcatgories.
Proof. (1) let $f$ and $g$ be monos. Then $fx = fy \Rightarrow x=y$. Therefore, if we have $g(fx) = g(fy)$ this implies that $fx = fy$ which implies $x=y$ so mononess is composition closed. Dually for epis, then bis are simply the intersection of epis and monos.
(2) Let $f,g$ be split epimorphisms then the inverse of $g \circ f$ is equal to $f^{-} \circ g^{-1}$ because $g \circ f \circ f^{-1} \circ g^{-1}$ which clearly cancels to the identity. In the other direction, if we have $f,g$ as split monomorphisms then $g \circ f$ has inverse $f^{-1} \circ g^{-1}$ so that $f^{-1} \circ g^{-1} \circ g \circ f$ clearly cances to the identity. The composition closure of isomorphisms follows from the intersection of split monos and split epis.
(3) Endomorphisms are clearly composition closed, and they are hom-complete so they are also the suborder produced by the coreflexive relation on $Ob(C)$. $\square$
Let $C$ be a category, then the subcategory of morphisms of one of these types is a subcategory. This can be applied to get the underlying groupoid of a category.
Definition. Let $C$ be a category, then the subcategory generated by its isomorphisms is the underlying groupoid of $C$.
We can get the underlying subgroupoid of a subcategory. In general, for any class of morphisms that generates types of subcategories, we can get an action on $Sub(C)$. \[ f : Sub(C) \to Sub(C) \] This construction of an action on the lattice of subcategories invites us to consider the effect of taking subcategories on the different types of morphisms.
- Monos,epis, and bis are preserved under subcategories
- Iso are preserved by preserved under extensions.
- Endos are preserved under both subcategories and extensions.
Ideals theory:
Categories are certain types of partial semigroups on edge sets of quivers, so its not hard to see why the ideals theory of categories is essentially the same as that of semigroups. We have three different types of preorder inherent to any category:- Input action preorder: $f \subseteq g$ means $\exists h : f \circ h = g$
- Output action preorder: $f \subseteq g$ means $\exists h : h \circ f = g$
- Two sided action preorder: $f \subseteq g$ means $\exists h_1,h_2 : h_1 \circ f \circ h_2 = g$
It is self-evident that ideals of form subcategories, because they are closed under composition with respect to morphisms from the overall category $C$. An interesting construction occurs where in we can change the category of morphisms acting on $I$ to some other subcategory $S$. This produces a family of three types of monotone maps from the lattice of subcategories to the lattice of preorders: \[ L : Sub(C) \to Po(Ob(C)) \] \[ R : Sub(C) \to Po(Ob(C)) \] \[ J : Sub(C) \to Po(Ob(C)) \] As these preorders are constructed from the actions of subcategories, their ideals don't need to be subcategories. An important example is an isomorphism ideal, which is an ideal with respect to two sided action of the underlying groupoid. Subcategories that are also closed under underlying groupoid action are called replete.
Repletion forms a closure action on the lattice of subcategories $Sub(C)$, and so the family of all replete subcategories forms a lattice determined by the skeleton of the category. Action preorders can also be formed by the mono and epi subcategories.
- The preorder of subobjects is the input action preorder of the mono subcategory.
- The preorder of quotients is the output action preorder of the epi subcategory.
The monotonicity of the map from subcategories to preorders means that smaller subcategories can only have smaller preorders of subobjects and quotients. This is translated to the language of subobject and quotient posets by the condensation which produces partial orders from preorders.
Connected components:
The underlying morphic preorder on the objects of a category induces a partition of $Ob(C)$ into weakly connected components. The resulting partition topology on the objects of the category consisting of all connectivity closed object systems then induces a boolean algebra of full subcategories each of which is clearly a prime two-sided ideals of $C$.A category with non-trivial connected components admits a coproduct decomposition, and so this leads to the following theorem which characterizes the lattice of subcategories of a coproduct category in terms of product lattices.
Theorem. $Sub(C + D) = Sub(C) \times Sub(D)$.
Proof. This can be proven by a one to one map. Let $C$ and $D$ be connected components of the category $C + D$ and let $S$ and $T$ be subcategories of $C$ and $D$ respectively. Then by the fact that $C$ and $D$ are prime subcategories $S \cup T$ is a subcategory of $C + D$ so the union leads to an injective map from $Sub(C) \times Sub(D)$ to $Sub(C + D)$. In the other direction, any subcategory of $C+D$ can be decomposed into a subcategory of $C$ and a subcategory of $D$ by taking full subcategories with respect to $Ob(C)$ and $Ob(D)$. $\square$
This simple construction allows us to determine the lattices of subcategories of antichain categories from the lattices of subcategories of the endomorphism monoids of the category.
Families of subcategories:
If we take $Sub(C)$ to be the lattice of subcategories of a category $C$, then a family of subcategories is simply one of its suborders. These suborders come in a number of forms.Lower sets:
If $F$ is a subalgebra closed family of categories, then the family of all subcategories of $C$ in $F$ forms a lower set of $Sub(C)$. For example, the family of all thin subcategories of a category is a lower set as is the lattice of all discrete subcategories.
Closure systems:
The families of subgropoids, the various ideal-related construction on categories like replete subcategories, and so on all form closure systems. These are upper bound maintaining meet subsemilattices of $Sub(C)$.
Sublattices:
Besides the lattice of discrete subcategories, the lattice of subgroupoids forms a sublattice of the lattice of subcategories of a groupoid. This can be proven in the following theorem.
Theorem. let $G$ be a groupoid and let $A,B \subseteq G$ be subgroupoids. Then the subcategory join $A \vee B$ is a subgroupoid.
Proof. the subcategory join $A \vee B$ consists of all words of the form $a_1 b_1 a_2 b_2 a_3 b_3 ... $. This simply has inverse $b_3^{-1} a_3^{-1} b_2^{-1} a_2^{-1} b_1^{-1} a_1^{-1}$. The words of $A \vee B$ have inverses, so join preserves inverses. The fact that the subcategory join of subgroupoids is a subgroupoid means that the lattice of subgroupoids is a sublattice of the lattice of subcategories.
Friday, June 25, 2021
Ideals theory of commutative semigroups
Commutative algebra, going back to Krull, was originally known as ideals theory. Ideals play such an important role in commutative algebra because they determine congruences. Ideals don't play such a central role in semigroup theory, but the resolution of questions involving ideals on the semigroup level could shed light on some questions in commutative algebra.
The subject of this post will be the ideals theory of commutative semigroups. A quantale of ideals will be constructed for commutative semigroups, similar to commutative rings. Ideal multiplication in the context of semigroups will be briefly discussed. Finaly, the ideals of commutative semigroups will be related to the two most important structural decompositions of commutative semigroups: condensation and semilattice decompositions.
Let $M$ be a magma with a Moore family of closed sets $F$ formed by a closure operator $cl_F$. Then we can form a lattice ordered magma on $F$ by \[ ST = cl_F(\{st : s \in S, t \in T\}) \] A lattice ordered magma, is a magma that is internal to the category of partial orders and monotone maps. Therefore, it only remains to show that $(F,*)$ is order compatible.
Proposition. (F,*) is a lattice ordered magma
Proof. Let $S_1,T_1,S_2,T_2 \in F$ such that $S_1 \subseteq S_2$ and $T_1 \subseteq T_2$. Then $S_1T_1 = \{st : s \in S_1, t \in T_1 \}$. Then by $s \in S_2$ and $t \in T_2$ so $st \in S_2T_2$. Therefore, $S_1T_1 \subseteq S_2T_2$, now by the fact that closure operators are monotone we have $cl_F(S_1T_1) \subseteq cl_F(S_2T_2)$. $\square$
Properties preserved by subset multiplication:
Let $M$ be a magma then $\wp(M)$ is a lattice ordered magma. In order to show it is a lattice ordered semigroup, all it remains is to preserve associativity. In fact, associativity is just one of the properties preserved by $\wp(M)$.
Proposition. let $M$ be a magma then $\wp(M)$ preserves the associativity and commutativity of $M$.
Proof. (1) let $A,B,C \subseteq S$ then it remains to show that $(AB)C = A(BC)$. Let $x \in (AB)C$ then $x$ can be factored as $(a_1b_1)c_1$. By associativity this equals $a_1(b_1c_1)$ which is in $A(BC)$. The reverse cases follow in the same way.
(2) let $A,B \subseteq S$ then if $ab \in AB$ by commutativity $ab = ba \in BA$ Likewise, if $ba \in BA$ then $ba = ab \in AB$. Therefore, $AB = BA$ so subset multiplication commutes.$\square$
It follows from this that if $S$ is a commutative semigroup, then $\wp(S)$ is a commutative semigroup as well.
Subsemigroup multiplication in the commutative case:
Let $S$ be a semigroup, then $Sub(S)$ always forms a lattice ordered magma. It need not be the case that $Sub(S)$ is a lattice ordered semigroup, which would follow if $Sub(S)$ were a subsemigroup of $\wp(S)$. The product of subsemigroups is a subsemigroup if they permute, so we do have that $Sub(S)$ is a lattice ordered semigroup in the commutative case.
Theorem. let $S$ be a commutative semigroup, then $(Sub(S),*)$ is a subsemigroup of $(\wp(S),*)$.
Proof. let $A,B \in Sub(S)$ then $AB = \{ab : a \in A, b \in B \}$. Let $a_1b_1, a_2b_2 \in AB$ then it remains to show that their product is in $AB$. The product of $a_1b_1$ and $a_2b_2$ is $a_1b_2a_2b_2$. Then $A$ and $B$ commute by the fact that $S$ is a commutative semigroup, so we can rewrite this as $(a_1a_2)(b_1b_2)$. By the fact that $A,B$ are subsemigroups we have $a_1a_2 \in A$ and $b_1b_2 \in B$ so $(a_1a_2)(b_1b_2) \in AB$. It follows that $Sub(S)$ is a subsemigroup of $\wp(S)$.
Subalgebras form more then just lattices:
Let $A$ be an any algebraic structure, then $Sub(A)$ is always more then just a lattice, because the algebraic operations on elements of a set always pass on to their subalgebras. It may be that $Sub(S)$ is merely a magma, and so it lacks desired properties like associativity, but it is always the case that an algebraic structure is there. Therefore, $Sub(S)$ must always be considered an ordered algebraic structure.
Let $S$ be a commutative semigroup, then we saw that $\wp(S)$ is a lattice ordered semigroup. In order to show that it is a quantale, it only remains to show that the product distributes over unions. Then $(\wp(S),\vee,*)$ will form a commutative semiring, and $\wp(S)$ will be a quantale.
Theorem. let $S$ be a commutative semiring and $A,B,C \in \wp(S)$. Then $A(B \cup C) = AB \cup AC$.
Proof. the expression $A(B \cup C)$ can be broken down in the following manner: \[ A(B \cup C) \] \[ = \{ax : a \in A, x \in B \lor x \in C \}\] \[ = \{ax : a \in A, x \in B\} \cup \{ax : a \in A, x \in C \} \] \[ = AB \cup AC \] The first and last expressions combined yield $A(B \cup C) = AB \cup AC$. $\square$
The quantale of subsets is associated with a residual operation $A:B$ which is the largest subset that whose product with a given set $B$ is less then $A$. \[ A:B = \{ c : aB \subseteq A \} \] This can clearly be seen to be a residual so that if $C = A:B$ then $AD \subseteq B$ implies $D \subseteq C$. The residual property of this expression clearly follows from the residual properties of quantales.
Join decompositions of quantales:
The distributivity property of quantales, allows you to express any product of elements of a quantale in terms of products of join components of each element. Let $a,b \in Q$ and suppose we have join decompositions $a = x_1 \vee ... \vee x^n$ and $b = y_1 \vee ... \vee y^m$. Then we can express the product $ab$ as: \[ ab \] \[ = (x_1 \vee ... \vee x_n)(y_1 \vee ... \vee y_m) \] \[ = \bigvee_{1 \leq i \leq n, 1 \leq j \leq m} x_i y_j\] It follows that in a quantale, a product can always be reduced to a combination of the join irreducible components of each element. This generalizes how the product of sets is determined by the elements of each set. Quantales are therefore generalizations of operations like products of sets.
Quantale of ideals:
Let $S$ be a commutative semigroup, then the ideals of $S$ are all two sided. The product of ideals of $S$ is always again an ideal, so $Ideals(S)$ forms a subsemigroup.
Theorem. let $I,J$ be ideals of $S$ then the product of $I$ and $J$ as sets $IJ$ is an ideal.
Proof. let $ij \in IJ$, and let $x \in S$. Then the product $x(ij)$ is equal to $(xi)j$. By the fact that $I$ is an ideal, $xi \in I$. Therefore, $(xi)j \in IJ$. $\square$
It is a basic fact that ideals of a semigroup are closed under unions and intersections. The preceding theorem demonstrates that they are also closed under the operation of taking products. Taken together, this means that $Ideals(S)$ is a sub-quantale of the quantale of subset multiplication.
Corollary. $Ideals(S)$ is a subquantale of $\wp(S)$
A similar sort of construction applies for left and right ideals of a semigroup, but for now we can use this to understand ideals of commutative semigroups. Most constructions including the residual are inherited from the quantale of sets. The residual of ideals is the same as the residual used to define the subobject classifier in the topos of monoid actions.
Rees semigroup congruences:
The ideals of a commutative ring form a quantale, which also has a quotient operation that produces ring objects. In order to make commutative semigroups more analagous to rings, we also need a quotient operation. That is where Rees semigroup congruences come in. By a Rees semigroup congruence, we can associate a semigroup object to any semigroup ideal. \[ q : Ideals(S) \to Ob(Sgrp) \] The addition of this final component makes the ideals of commutative semigroups analogous to those of commutative rings. They are quantales with associated quotient objects.
Let $S$ be a semigroup, then we can form a map $\pi : S \to \frac{S}{H}$ that maps the elements of any given semigroup to its corresponding $H$ class. We want to show that this maps both reflects and preserves ideals, which would mean that ideals can be fully determined by the condensation.
Lemma. let $f : S \to T$ be a commutative semigroup epimorphism. Then $f$ preserves ideals.
Proof. let $I$ be an ideal of $S$ and $f(I)$ its image in $T$. Let $x \in f(I)$. This means that there exists $i \in I$ such that $f(i) = x$. Let $t \in T$. By the fact that $f$ is an epimorphism, there exists $s$ such that $t = f(s)$. Then the product $xt$ is equal to $f(i)f(s)$. By the fact that $f$ is a morphism of semigroups, we have $f(i)f(s) = f(is)$. $I$ is an ideal and $i \in I$, so $is \in I$. Finally, $is \in I$ and $xt = f(is)$ implies that $xt \in f(I)$. This holds for all $x \in f(I)$ and $t \in T$ so $f(I)$ is an ideal. $\square$
Lemma. let $f : S \to T$ be a commutative semigroup epimorphism. Then $f$ reflects ideals.
Proof. let $I \subset T$ be an ideal. Then consider $f^{-1}(I) \subseteq S$. Let $x \in f^{-1}(I)$ then $f(x) \in I$. Let $y \in S$. Then by the fact that $f$ is a morphism of semigroups $f(xy) = f(x)f(y)$. We have that $f(x) \in I$ and $I$ is an ideal so $f(x)f(y) \in I$. Since $f(x)f(y) = f(xy)$ this means $f(xy) \in I$. It follows that $xy \in f^{-1}(I)$. Finally, this means that $f^{-1}(I)$ is an ideal. $\square$
Lemma. the induced map $\pi: Ideals(S) \to Ideals(\frac{S}{H})$ is one to one and onto.
Proof. (1) let $I$ be an ideal, then $I$ is clearly $H$ closed. Therefore, any two semigroup ideals must have different sets of $H$ classes, which means the map to their $H$ classes $\pi$ is injective.
(2) the map $\pi$ both preserves and reflects ideals, so for any ideal in $I \in Ideals(\frac{S}{H})$, we have a corresponding ideal $f^{-1}(I)$ with image $I$. $\square$
Lemma. $\pi : S \to \frac{S}{H}$ induces a semigroup homomorphism from $(Ideals(S),*)$ to $(Ideals(\frac{S}{H}),*)$.
Proof. let $I,J$ be ideals in $Ideals(S)$. Then their product is the set of products of elements of both, and $\pi(IJ)$ is the H classes of the products of each element. Then by the fact that $H$ is a congruence, this can be decomposed into a product of the $H$ classes of $i$ and $j$ which makes this a semigroup homomorphism. \[ \pi(IJ) \] \[ = \pi(\{ij: i I, j \in J\}) \] \[ = \{(ij)_H : i \in I, j \in J\} \] \[ = \{i_H j_H : i \in I, j \in J \} \] \[ \pi(I)\pi(J) \] Then by the fact that for all ideals $I,J$ we have $\pi(IJ) = \pi(I)\pi(J)$ we have that $\pi$ is a semigroup homomorphism of ideal multiplication semigroups. $\square$
We can clearly combine these four lemmas to get a quantale isomorphism from $S$ to $\frac{S}{H}$. The first three lemmas produce a lattice isomorphism, and the final one relates the product of the two quantales.
Theorem. $\pi : S \to \frac{S}{H}$ induces a quantale isomorphism: \[Im(\pi) : Ideals(S) \leftrightarrow Ideals(\frac{S}{H}) \] The special case of the ideal quantale of a PID is essentially dealt with by using the condensation, and by noting that the quantale of ideals of a PID can be completely recovered from its multiplication semigroup. This allows us to create a general ideal theory of commutative semigroups based upon the condensation $\frac{S}{H}$.
Radical ideals and semilattice decompositions:
The ideals of a commutative semigroup are determined by its condensation. It would be nice if the radical ideals would be determined by its semilattice decomposition, which is the second most important quotient associated to any commutative semigroup. We will show that this is the case, thereby creating a full theory of both ideals and radical ideals of commutative semigroups.
Lemma. radical ideals are Archidemean closed
Proof. let $S$ be a semigroup with radical ideal $I$. Let $x \in I$ and suppose $x,y$ are in the same archimedean component, then $\exists n \in \mathbb{Z}_+, z \in S: y^n = xz$. By the fact that $x \in I$ and $I$ is an ideal, $xz \in I$. By the fact that $I$ is radical, $y$ is in $I$, so $I$ is Archimedean closed. $\square$
Lemma. Archimedean closed ideals are radical
Proof. let $I$ be an Archimedean closed ideal and suppose there exists $x \not\in I$ and $y \in I$ such that $x^n \in I$. Then by the fact that $I$ is Archimedean closed, $x$ belongs in a separate Archimedean component $C$ from $y$, but then since Archimedean components form a congruence with semilattice quotient, $C^2$ should equal $C$, but we have an element $x \in C$ such that $x^n \not\in C$, which contradicts semilattice decompositions. So, the Archimedean closed ideals must be radical. $\square$
Theorem. $\pi : S \to \frac{S}{\gamma}$ induces a one to one and onto map of radical ideals
Proof. (1) by the fact that radical ideals are Archimedean closed, $\pi$ always produces different image radical ideals from different input ideals. Therefore, $\pi$ is one to one.
(2) By the fact that Archidemean closed ideals are radical, the inverse image of a radical ideal $I$ is a radical ideal $f^{-1}(I)$ which has $I$ as an image. As every radical ideal of $\frac{S}{\gamma}$ is the image of some radical ideal of $S$, we have that $\pi$ is onto. $\square$
The radical ideals of a commutative semigroup are isomorphic to the ideals of its semilattice decomposition. Ideal lattices are always distributive, because they are lattices of subobjects of a topos. So this implies that the lattice of radical ideals of a commutative semigroup is distributive.
Corollary. the lattice of radical ideals of a commutative semigroup is distributive
The induced map of ideals of the condensation was one to one. In the case of semilattice condensation, it is merely a monotone Galois connection, whose closed sets are the radical ideals of the semigroup and whose adjoint is a Galois insertion that inserts a radical ideal into the ideals lattice of the semigroup.
Overview and comparison:
It was known by Dedekind that the lattice of ideals of a commutative ring is modular. The lattice of radical ideals is not only distributive, it is dual to a spatial locale which is why we can construct the spectrum $Spec(R)$. The lattice of ideals of a commutative semigroup is clearly distributive, because it is a subobject lattice of a topos. The lattice of radical ideals of a commutative semigroup is distributive by basically the same reason.
The ideals of a commutative ring, and the ideals of a commutative subsemigroup both form sublattices of the lattice of subalgebras $Sub(A)$. A stronger condition is that ring ideals are a sublattice of additive subgroups, which is why the join of ring ideals can also be expressed by addition. Ideals in both semigroups and rings form quantales, which are ubiquitous in abstract algebra.
References:
The Algebraic Theory of Semigroups
By A.H Clifford
The subject of this post will be the ideals theory of commutative semigroups. A quantale of ideals will be constructed for commutative semigroups, similar to commutative rings. Ideal multiplication in the context of semigroups will be briefly discussed. Finaly, the ideals of commutative semigroups will be related to the two most important structural decompositions of commutative semigroups: condensation and semilattice decompositions.
Algebraic operations on subsets:
Lattice ordered magmas:Let $M$ be a magma with a Moore family of closed sets $F$ formed by a closure operator $cl_F$. Then we can form a lattice ordered magma on $F$ by \[ ST = cl_F(\{st : s \in S, t \in T\}) \] A lattice ordered magma, is a magma that is internal to the category of partial orders and monotone maps. Therefore, it only remains to show that $(F,*)$ is order compatible.
Proposition. (F,*) is a lattice ordered magma
Proof. Let $S_1,T_1,S_2,T_2 \in F$ such that $S_1 \subseteq S_2$ and $T_1 \subseteq T_2$. Then $S_1T_1 = \{st : s \in S_1, t \in T_1 \}$. Then by $s \in S_2$ and $t \in T_2$ so $st \in S_2T_2$. Therefore, $S_1T_1 \subseteq S_2T_2$, now by the fact that closure operators are monotone we have $cl_F(S_1T_1) \subseteq cl_F(S_2T_2)$. $\square$
Properties preserved by subset multiplication:
Let $M$ be a magma then $\wp(M)$ is a lattice ordered magma. In order to show it is a lattice ordered semigroup, all it remains is to preserve associativity. In fact, associativity is just one of the properties preserved by $\wp(M)$.
Proposition. let $M$ be a magma then $\wp(M)$ preserves the associativity and commutativity of $M$.
Proof. (1) let $A,B,C \subseteq S$ then it remains to show that $(AB)C = A(BC)$. Let $x \in (AB)C$ then $x$ can be factored as $(a_1b_1)c_1$. By associativity this equals $a_1(b_1c_1)$ which is in $A(BC)$. The reverse cases follow in the same way.
(2) let $A,B \subseteq S$ then if $ab \in AB$ by commutativity $ab = ba \in BA$ Likewise, if $ba \in BA$ then $ba = ab \in AB$. Therefore, $AB = BA$ so subset multiplication commutes.$\square$
It follows from this that if $S$ is a commutative semigroup, then $\wp(S)$ is a commutative semigroup as well.
Subsemigroup multiplication in the commutative case:
Let $S$ be a semigroup, then $Sub(S)$ always forms a lattice ordered magma. It need not be the case that $Sub(S)$ is a lattice ordered semigroup, which would follow if $Sub(S)$ were a subsemigroup of $\wp(S)$. The product of subsemigroups is a subsemigroup if they permute, so we do have that $Sub(S)$ is a lattice ordered semigroup in the commutative case.
Theorem. let $S$ be a commutative semigroup, then $(Sub(S),*)$ is a subsemigroup of $(\wp(S),*)$.
Proof. let $A,B \in Sub(S)$ then $AB = \{ab : a \in A, b \in B \}$. Let $a_1b_1, a_2b_2 \in AB$ then it remains to show that their product is in $AB$. The product of $a_1b_1$ and $a_2b_2$ is $a_1b_2a_2b_2$. Then $A$ and $B$ commute by the fact that $S$ is a commutative semigroup, so we can rewrite this as $(a_1a_2)(b_1b_2)$. By the fact that $A,B$ are subsemigroups we have $a_1a_2 \in A$ and $b_1b_2 \in B$ so $(a_1a_2)(b_1b_2) \in AB$. It follows that $Sub(S)$ is a subsemigroup of $\wp(S)$.
Subalgebras form more then just lattices:
Let $A$ be an any algebraic structure, then $Sub(A)$ is always more then just a lattice, because the algebraic operations on elements of a set always pass on to their subalgebras. It may be that $Sub(S)$ is merely a magma, and so it lacks desired properties like associativity, but it is always the case that an algebraic structure is there. Therefore, $Sub(S)$ must always be considered an ordered algebraic structure.
Quantales:
Quantale of subsets:Let $S$ be a commutative semigroup, then we saw that $\wp(S)$ is a lattice ordered semigroup. In order to show that it is a quantale, it only remains to show that the product distributes over unions. Then $(\wp(S),\vee,*)$ will form a commutative semiring, and $\wp(S)$ will be a quantale.
Theorem. let $S$ be a commutative semiring and $A,B,C \in \wp(S)$. Then $A(B \cup C) = AB \cup AC$.
Proof. the expression $A(B \cup C)$ can be broken down in the following manner: \[ A(B \cup C) \] \[ = \{ax : a \in A, x \in B \lor x \in C \}\] \[ = \{ax : a \in A, x \in B\} \cup \{ax : a \in A, x \in C \} \] \[ = AB \cup AC \] The first and last expressions combined yield $A(B \cup C) = AB \cup AC$. $\square$
The quantale of subsets is associated with a residual operation $A:B$ which is the largest subset that whose product with a given set $B$ is less then $A$. \[ A:B = \{ c : aB \subseteq A \} \] This can clearly be seen to be a residual so that if $C = A:B$ then $AD \subseteq B$ implies $D \subseteq C$. The residual property of this expression clearly follows from the residual properties of quantales.
Join decompositions of quantales:
The distributivity property of quantales, allows you to express any product of elements of a quantale in terms of products of join components of each element. Let $a,b \in Q$ and suppose we have join decompositions $a = x_1 \vee ... \vee x^n$ and $b = y_1 \vee ... \vee y^m$. Then we can express the product $ab$ as: \[ ab \] \[ = (x_1 \vee ... \vee x_n)(y_1 \vee ... \vee y_m) \] \[ = \bigvee_{1 \leq i \leq n, 1 \leq j \leq m} x_i y_j\] It follows that in a quantale, a product can always be reduced to a combination of the join irreducible components of each element. This generalizes how the product of sets is determined by the elements of each set. Quantales are therefore generalizations of operations like products of sets.
Quantale of ideals:
Let $S$ be a commutative semigroup, then the ideals of $S$ are all two sided. The product of ideals of $S$ is always again an ideal, so $Ideals(S)$ forms a subsemigroup.
Theorem. let $I,J$ be ideals of $S$ then the product of $I$ and $J$ as sets $IJ$ is an ideal.
Proof. let $ij \in IJ$, and let $x \in S$. Then the product $x(ij)$ is equal to $(xi)j$. By the fact that $I$ is an ideal, $xi \in I$. Therefore, $(xi)j \in IJ$. $\square$
It is a basic fact that ideals of a semigroup are closed under unions and intersections. The preceding theorem demonstrates that they are also closed under the operation of taking products. Taken together, this means that $Ideals(S)$ is a sub-quantale of the quantale of subset multiplication.
Corollary. $Ideals(S)$ is a subquantale of $\wp(S)$
A similar sort of construction applies for left and right ideals of a semigroup, but for now we can use this to understand ideals of commutative semigroups. Most constructions including the residual are inherited from the quantale of sets. The residual of ideals is the same as the residual used to define the subobject classifier in the topos of monoid actions.
Rees semigroup congruences:
The ideals of a commutative ring form a quantale, which also has a quotient operation that produces ring objects. In order to make commutative semigroups more analagous to rings, we also need a quotient operation. That is where Rees semigroup congruences come in. By a Rees semigroup congruence, we can associate a semigroup object to any semigroup ideal. \[ q : Ideals(S) \to Ob(Sgrp) \] The addition of this final component makes the ideals of commutative semigroups analogous to those of commutative rings. They are quantales with associated quotient objects.
Ideals theory:
Ideals and condensation:Let $S$ be a semigroup, then we can form a map $\pi : S \to \frac{S}{H}$ that maps the elements of any given semigroup to its corresponding $H$ class. We want to show that this maps both reflects and preserves ideals, which would mean that ideals can be fully determined by the condensation.
Lemma. let $f : S \to T$ be a commutative semigroup epimorphism. Then $f$ preserves ideals.
Proof. let $I$ be an ideal of $S$ and $f(I)$ its image in $T$. Let $x \in f(I)$. This means that there exists $i \in I$ such that $f(i) = x$. Let $t \in T$. By the fact that $f$ is an epimorphism, there exists $s$ such that $t = f(s)$. Then the product $xt$ is equal to $f(i)f(s)$. By the fact that $f$ is a morphism of semigroups, we have $f(i)f(s) = f(is)$. $I$ is an ideal and $i \in I$, so $is \in I$. Finally, $is \in I$ and $xt = f(is)$ implies that $xt \in f(I)$. This holds for all $x \in f(I)$ and $t \in T$ so $f(I)$ is an ideal. $\square$
Lemma. let $f : S \to T$ be a commutative semigroup epimorphism. Then $f$ reflects ideals.
Proof. let $I \subset T$ be an ideal. Then consider $f^{-1}(I) \subseteq S$. Let $x \in f^{-1}(I)$ then $f(x) \in I$. Let $y \in S$. Then by the fact that $f$ is a morphism of semigroups $f(xy) = f(x)f(y)$. We have that $f(x) \in I$ and $I$ is an ideal so $f(x)f(y) \in I$. Since $f(x)f(y) = f(xy)$ this means $f(xy) \in I$. It follows that $xy \in f^{-1}(I)$. Finally, this means that $f^{-1}(I)$ is an ideal. $\square$
Lemma. the induced map $\pi: Ideals(S) \to Ideals(\frac{S}{H})$ is one to one and onto.
Proof. (1) let $I$ be an ideal, then $I$ is clearly $H$ closed. Therefore, any two semigroup ideals must have different sets of $H$ classes, which means the map to their $H$ classes $\pi$ is injective.
(2) the map $\pi$ both preserves and reflects ideals, so for any ideal in $I \in Ideals(\frac{S}{H})$, we have a corresponding ideal $f^{-1}(I)$ with image $I$. $\square$
Lemma. $\pi : S \to \frac{S}{H}$ induces a semigroup homomorphism from $(Ideals(S),*)$ to $(Ideals(\frac{S}{H}),*)$.
Proof. let $I,J$ be ideals in $Ideals(S)$. Then their product is the set of products of elements of both, and $\pi(IJ)$ is the H classes of the products of each element. Then by the fact that $H$ is a congruence, this can be decomposed into a product of the $H$ classes of $i$ and $j$ which makes this a semigroup homomorphism. \[ \pi(IJ) \] \[ = \pi(\{ij: i I, j \in J\}) \] \[ = \{(ij)_H : i \in I, j \in J\} \] \[ = \{i_H j_H : i \in I, j \in J \} \] \[ \pi(I)\pi(J) \] Then by the fact that for all ideals $I,J$ we have $\pi(IJ) = \pi(I)\pi(J)$ we have that $\pi$ is a semigroup homomorphism of ideal multiplication semigroups. $\square$
We can clearly combine these four lemmas to get a quantale isomorphism from $S$ to $\frac{S}{H}$. The first three lemmas produce a lattice isomorphism, and the final one relates the product of the two quantales.
Theorem. $\pi : S \to \frac{S}{H}$ induces a quantale isomorphism: \[Im(\pi) : Ideals(S) \leftrightarrow Ideals(\frac{S}{H}) \] The special case of the ideal quantale of a PID is essentially dealt with by using the condensation, and by noting that the quantale of ideals of a PID can be completely recovered from its multiplication semigroup. This allows us to create a general ideal theory of commutative semigroups based upon the condensation $\frac{S}{H}$.
Radical ideals and semilattice decompositions:
The ideals of a commutative semigroup are determined by its condensation. It would be nice if the radical ideals would be determined by its semilattice decomposition, which is the second most important quotient associated to any commutative semigroup. We will show that this is the case, thereby creating a full theory of both ideals and radical ideals of commutative semigroups.
Lemma. radical ideals are Archidemean closed
Proof. let $S$ be a semigroup with radical ideal $I$. Let $x \in I$ and suppose $x,y$ are in the same archimedean component, then $\exists n \in \mathbb{Z}_+, z \in S: y^n = xz$. By the fact that $x \in I$ and $I$ is an ideal, $xz \in I$. By the fact that $I$ is radical, $y$ is in $I$, so $I$ is Archimedean closed. $\square$
Lemma. Archimedean closed ideals are radical
Proof. let $I$ be an Archimedean closed ideal and suppose there exists $x \not\in I$ and $y \in I$ such that $x^n \in I$. Then by the fact that $I$ is Archimedean closed, $x$ belongs in a separate Archimedean component $C$ from $y$, but then since Archimedean components form a congruence with semilattice quotient, $C^2$ should equal $C$, but we have an element $x \in C$ such that $x^n \not\in C$, which contradicts semilattice decompositions. So, the Archimedean closed ideals must be radical. $\square$
Theorem. $\pi : S \to \frac{S}{\gamma}$ induces a one to one and onto map of radical ideals
Proof. (1) by the fact that radical ideals are Archimedean closed, $\pi$ always produces different image radical ideals from different input ideals. Therefore, $\pi$ is one to one.
(2) By the fact that Archidemean closed ideals are radical, the inverse image of a radical ideal $I$ is a radical ideal $f^{-1}(I)$ which has $I$ as an image. As every radical ideal of $\frac{S}{\gamma}$ is the image of some radical ideal of $S$, we have that $\pi$ is onto. $\square$
The radical ideals of a commutative semigroup are isomorphic to the ideals of its semilattice decomposition. Ideal lattices are always distributive, because they are lattices of subobjects of a topos. So this implies that the lattice of radical ideals of a commutative semigroup is distributive.
Corollary. the lattice of radical ideals of a commutative semigroup is distributive
The induced map of ideals of the condensation was one to one. In the case of semilattice condensation, it is merely a monotone Galois connection, whose closed sets are the radical ideals of the semigroup and whose adjoint is a Galois insertion that inserts a radical ideal into the ideals lattice of the semigroup.
Overview and comparison:
It was known by Dedekind that the lattice of ideals of a commutative ring is modular. The lattice of radical ideals is not only distributive, it is dual to a spatial locale which is why we can construct the spectrum $Spec(R)$. The lattice of ideals of a commutative semigroup is clearly distributive, because it is a subobject lattice of a topos. The lattice of radical ideals of a commutative semigroup is distributive by basically the same reason.
| Commutative ring | Commutative semigroup | |
|---|---|---|
| Ideals: | Modular | Distributive |
| Radical ideals: | Distributive | Distributive |
References:
The Algebraic Theory of Semigroups
By A.H Clifford
Saturday, June 12, 2021
Subtotal semigroups
In this post, we will investigate when it is that every subset of a semigroup is a subalgebra, and when it is that every subsemigroup is a radical subsemigroup. A semigroup is called subtotal if every subset is a subsemigroup. The structure of subtotal semigroups will be described. It will be shown that in a semigroup $S$ if every subset of $S$ is a subsemigroup then every subset is also radical.
Theorem 1. let $A \subseteq B \subseteq C$ be a chain of semigroups. Then the radical of $A$ in $B$ is less then the radical of $A$ in $C$: $\sqrt(A)_B \subseteq \sqrt(A)_C$.
Proof. let $A \in B$ then $\sqrt(A)_B$ is equal to $\{ x \in B : \exists n : x^n \in A \}$. On the other hand, $\sqrt(A)_C$ is equal to $\{ x \in C : \exists n : x^n \in A \}$. Then by $B \subseteq C$ we have: \[ x \in B \implies x \in C \] Therefore, we have the following implication for all $x \in B$: \[ x \in B \wedge (\exists n : x^n \in A) \implies x \in C \wedge (\exists n : x^n \in A) \] It follows that the set formed by comprehesion by the first proposition is included in the set so $\sqrt(A)_B \subseteq \sqrt(A)_C$. $\square$
This easily demonstrates that the property of being a radical subsemigroup is hereditary, that is if a semigroup $A$ is a radical subsemigroup of $C$ then it is radical in every intermediate subsemigroup.
Corollary 1. let $A \subseteq B \subseteq C$ be a chain of semigroups. If $A$ is radical in $C$ then it is radical in $B$.
By this corollary, we know that if $(x)$ is a principal subsemigroup that is radical, then it also must be radical in any monogenic subsemigroup that contains it. Therefore, it is sufficient to investigate the radical subsemigroups of a monogenic semigroup.
Theorem 2. let $S$ be a monogenic semigroup then the only radical subsemigroups of $S$ are $\emptyset$ and $S$.
Proof. (1) let $S$ be finite. Then $S$ contains a unique idempotent $e$, which is contained in every non-empty subsemigroup. As every element generates $e$ we have $\sqrt(e) = S$. Therefore, if $X$ is non-empty we have $e \in X$ which implies $\sqrt(e) \subseteq X$ which implies $S \subseteq X \subseteq S$ which implies $X = S$.
(2) let $S$ be infinite. Then every infinite monogenic semigroup is a well ordered semigroup in a natural way. Let $X$ be a non-empty subsemigroup then by well ordering $X$ has a least element $n$. Additionally, $1$ is a generator for this element by iterating it $n$ times. Therefore, $1 \in X$ but since $\sqrt(\{1\}) = S$ we have that $S \subseteq X \subseteq S$ which implies $X = S$. $\square$
It follows that the lattice ordered family of radical subsemigroups of a monogenic subsemigroup is equal to an indiscrete topology. Furthermore, if every subsemigroup of a monogenic semigroup is radical then it is trivial.
Corollary 2. let $S$ be a monogenic semigroup. If every subsemigroup of $S$ is radical, then $S$ is a trivial monoid on one element.
By the combination of these two collaries we can complete our classification of semigroups for which every subsemigroup is radical.
Theorem 3. let $S$ be a semigroup. Every subsemigroup of $S$ is radical iff $S$ is a band.
Proof. (1) if $S$ is a band then the iteration preorder on $S$ is trivial, therefore every subsemigroup must be radical (2) if every subsemigroup of $S$ is radical, then by corollary one every subsemigroup of a monogenic subsemigroup of $S$ is radical. By corollary two the only monogenic subsemigroups for which every subsemigroup is radical are trivial monoids. Therefore, every monogenic subsemigroup of $S$ must be a trivial monoid, so that every element of $S$ is idempotent which means it is a band. $\square$
A moore family is what is formed by relaxing the union closure condition of a cotopological space. The lattice of Moore families on a set is typically a more broad and useful setting for applications then the lattice of topological spaces. Within this lattice of lattices, we have the following chain of inclusions:
Radical subsemigroups $\subseteq$ Subsemigroups $\subseteq$ Subsets
Subsemigroups and radical subsemigroups are rank two Moore families while the family of all subsets is really rank zero rather then rank two, because it is defined by a nullary closure operation rather then a binary one. The fact that the lattice of subsemigroups is rank two follows from basic universal algebra.
Corollary. let $S$ be a semigroup then $Sub(S)$ is a rank two Moore family
The interesting thing about this is that not all set systems, or even all Moore families, emerge as the families of subsemigroups of a semigroup. In particular, it is enough to get that $S$ is a 1-total and 2-total for it to be completely total.
Lemma. let $S$ be a semigroup and suppose that every subset of order one or two is a subsemigroup of $S$, then every subset of $S$ is a subsemigroup.
Proof. let $X$ be a subset of $S$ then we have that $\forall a,b \in X : ab \in \{a,b\}$. Then the fact that $\{a,b\} \subseteq X$ implies that $ab \in X$. Therefore, $X$ is composition closed. $\square$
This clearly reduces the problem of subalgebraic totality to one of graph theory. In particular, we can define the totality graph for any semigroup.
Definition. let $S$ be a semigroup. Then the totality graph of $S$ has as vertices all elements of $S$, as loops all idempotents, and as edges all size two subbands.
By the preceding theorem, every clique of the totality graph is a subsemigroup. The resulting clique complex is the subclass closed component of the Moore family of subsemigroups of the semigroup $S$. That this set system is a clique complex follows by the rank of the Moore family.
Lemma. let $S$ be a semilattice then $S$ is subtotal iff $S$ is a total order.
Proof. (1) let $S$ be a total order semilattice then $\forall x,y : x \vee y \in \{x,y\}$ so that $S$ is 2-total, it follows that $S$ is subtotal (2) let $S$ be subtotal, then $\forall x,y :x \vee y \in \{x,y\}$. This means $x \vee y = x$ or $x \vee y = y$. By the definition of the ordering on a semilattice, this then implies either $x \subseteq y$ or $y \subseteq x$ which means that $x,y$ are comparable. It follows by the fact that every element of $S$ is comparable that $S$ is a total order. $\square$
Much like the commuting graph of a semigroup can be determined subalgebraically, so to can the comparability graph of a semilattice. By this lemma, when $S$ is a semilattice the comparability graph and the totality graph coincide.
Corollary. let $S$ be a semilattice then the comparability graph of $S$ is equal to its totality graph.
This solves the problem of totality for semilattices, and it relates subtotal semigroups to total order semilattices. However, in order to complete the theory we need to investigate rectangular bands more.
Lemma. let $S$ be a rectangular band then $S$ is subtotal iff $S$ is pure.
Proof. (1) let $S$ be a pure rectangular band, then $S$ is either left zero or right zero. This means that if it is left zero $ab = a$ or if it is right zero then $ab = b$. In either case, $ab \in \{a,b\}$ which means that $S$ is 2-total.
(2) let $S = L_n \times R_m$ then if $S$ is not a pure rectangular band we have $2 \le n,m$. It follows that we can select elements $(1,2) \circ (2,1) = (1,1)$ so that $S$ is not 2-total. $\square$
A band is a 1-total semigroup, so that every singleton is a subsemigroup. A subtotal semigroup is simply a 1-total semigroup that is also 2-total, therefore every subtotal semigroup is a band. Every band is a semilattice of rectangular bands. By this construction, and the previous two lemmas we have a structure theorem for subtotal semigroups.
Theorem. let $S$ be a subtotal semigroup. Then $S$ is a total order semilattice of pure rectangular bands.
Proof. (1) by the fact that $S$ is subtotal it is a band, and then by the classification theorem for bands this means that it is a semilattice of rectangular bands (2) by the fact that only pure rectangular bands are subtotal it follows that each rectangular band must be pure (3) finally the semilattice must be subtotal which must be a total order. $\square$
The class of pure rectangular bands is the union of the atomic varieties of left zero and right zero bands. It follows that each subtotal semigroup can contain either left zero semigroups, right zero semigroups, or both. A subtotal semigroup is called mixed if it contains one of each of the different types.
Proposition. (1) atoms in the lattice of subsemigroups are trivial monoids and (2) atoms in the lattice of subgroups are prime order cyclic groups.
Every atomic subsemigroup is clearly monogenic. In the finite case, we always have an idempotent subsemigroup as an atomic which means $S$ must be a trivial monoid. On the other hand, the infinite monogenic semigroup has no atoms, which means nothing covers the empty set. The empty subsemigroup is an order topological limit point of any maximal chain, because every maximal chain of subsemigroups will terminate at the empty set.
Theorem 1. let $A \subseteq B \subseteq C$ be a chain of semigroups. Then the radical of $A$ in $B$ is less then the radical of $A$ in $C$: $\sqrt(A)_B \subseteq \sqrt(A)_C$.
Proof. let $A \in B$ then $\sqrt(A)_B$ is equal to $\{ x \in B : \exists n : x^n \in A \}$. On the other hand, $\sqrt(A)_C$ is equal to $\{ x \in C : \exists n : x^n \in A \}$. Then by $B \subseteq C$ we have: \[ x \in B \implies x \in C \] Therefore, we have the following implication for all $x \in B$: \[ x \in B \wedge (\exists n : x^n \in A) \implies x \in C \wedge (\exists n : x^n \in A) \] It follows that the set formed by comprehesion by the first proposition is included in the set so $\sqrt(A)_B \subseteq \sqrt(A)_C$. $\square$
This easily demonstrates that the property of being a radical subsemigroup is hereditary, that is if a semigroup $A$ is a radical subsemigroup of $C$ then it is radical in every intermediate subsemigroup.
Corollary 1. let $A \subseteq B \subseteq C$ be a chain of semigroups. If $A$ is radical in $C$ then it is radical in $B$.
By this corollary, we know that if $(x)$ is a principal subsemigroup that is radical, then it also must be radical in any monogenic subsemigroup that contains it. Therefore, it is sufficient to investigate the radical subsemigroups of a monogenic semigroup.
Theorem 2. let $S$ be a monogenic semigroup then the only radical subsemigroups of $S$ are $\emptyset$ and $S$.
Proof. (1) let $S$ be finite. Then $S$ contains a unique idempotent $e$, which is contained in every non-empty subsemigroup. As every element generates $e$ we have $\sqrt(e) = S$. Therefore, if $X$ is non-empty we have $e \in X$ which implies $\sqrt(e) \subseteq X$ which implies $S \subseteq X \subseteq S$ which implies $X = S$.
(2) let $S$ be infinite. Then every infinite monogenic semigroup is a well ordered semigroup in a natural way. Let $X$ be a non-empty subsemigroup then by well ordering $X$ has a least element $n$. Additionally, $1$ is a generator for this element by iterating it $n$ times. Therefore, $1 \in X$ but since $\sqrt(\{1\}) = S$ we have that $S \subseteq X \subseteq S$ which implies $X = S$. $\square$
It follows that the lattice ordered family of radical subsemigroups of a monogenic subsemigroup is equal to an indiscrete topology. Furthermore, if every subsemigroup of a monogenic semigroup is radical then it is trivial.
Corollary 2. let $S$ be a monogenic semigroup. If every subsemigroup of $S$ is radical, then $S$ is a trivial monoid on one element.
By the combination of these two collaries we can complete our classification of semigroups for which every subsemigroup is radical.
Theorem 3. let $S$ be a semigroup. Every subsemigroup of $S$ is radical iff $S$ is a band.
Proof. (1) if $S$ is a band then the iteration preorder on $S$ is trivial, therefore every subsemigroup must be radical (2) if every subsemigroup of $S$ is radical, then by corollary one every subsemigroup of a monogenic subsemigroup of $S$ is radical. By corollary two the only monogenic subsemigroups for which every subsemigroup is radical are trivial monoids. Therefore, every monogenic subsemigroup of $S$ must be a trivial monoid, so that every element of $S$ is idempotent which means it is a band. $\square$
A moore family is what is formed by relaxing the union closure condition of a cotopological space. The lattice of Moore families on a set is typically a more broad and useful setting for applications then the lattice of topological spaces. Within this lattice of lattices, we have the following chain of inclusions:
Radical subsemigroups $\subseteq$ Subsemigroups $\subseteq$ Subsets
Subsemigroups and radical subsemigroups are rank two Moore families while the family of all subsets is really rank zero rather then rank two, because it is defined by a nullary closure operation rather then a binary one. The fact that the lattice of subsemigroups is rank two follows from basic universal algebra.
Corollary. let $S$ be a semigroup then $Sub(S)$ is a rank two Moore family
The interesting thing about this is that not all set systems, or even all Moore families, emerge as the families of subsemigroups of a semigroup. In particular, it is enough to get that $S$ is a 1-total and 2-total for it to be completely total.
Lemma. let $S$ be a semigroup and suppose that every subset of order one or two is a subsemigroup of $S$, then every subset of $S$ is a subsemigroup.
Proof. let $X$ be a subset of $S$ then we have that $\forall a,b \in X : ab \in \{a,b\}$. Then the fact that $\{a,b\} \subseteq X$ implies that $ab \in X$. Therefore, $X$ is composition closed. $\square$
This clearly reduces the problem of subalgebraic totality to one of graph theory. In particular, we can define the totality graph for any semigroup.
Definition. let $S$ be a semigroup. Then the totality graph of $S$ has as vertices all elements of $S$, as loops all idempotents, and as edges all size two subbands.
By the preceding theorem, every clique of the totality graph is a subsemigroup. The resulting clique complex is the subclass closed component of the Moore family of subsemigroups of the semigroup $S$. That this set system is a clique complex follows by the rank of the Moore family.
Lemma. let $S$ be a semilattice then $S$ is subtotal iff $S$ is a total order.
Proof. (1) let $S$ be a total order semilattice then $\forall x,y : x \vee y \in \{x,y\}$ so that $S$ is 2-total, it follows that $S$ is subtotal (2) let $S$ be subtotal, then $\forall x,y :x \vee y \in \{x,y\}$. This means $x \vee y = x$ or $x \vee y = y$. By the definition of the ordering on a semilattice, this then implies either $x \subseteq y$ or $y \subseteq x$ which means that $x,y$ are comparable. It follows by the fact that every element of $S$ is comparable that $S$ is a total order. $\square$
Much like the commuting graph of a semigroup can be determined subalgebraically, so to can the comparability graph of a semilattice. By this lemma, when $S$ is a semilattice the comparability graph and the totality graph coincide.
Corollary. let $S$ be a semilattice then the comparability graph of $S$ is equal to its totality graph.
This solves the problem of totality for semilattices, and it relates subtotal semigroups to total order semilattices. However, in order to complete the theory we need to investigate rectangular bands more.
Lemma. let $S$ be a rectangular band then $S$ is subtotal iff $S$ is pure.
Proof. (1) let $S$ be a pure rectangular band, then $S$ is either left zero or right zero. This means that if it is left zero $ab = a$ or if it is right zero then $ab = b$. In either case, $ab \in \{a,b\}$ which means that $S$ is 2-total.
(2) let $S = L_n \times R_m$ then if $S$ is not a pure rectangular band we have $2 \le n,m$. It follows that we can select elements $(1,2) \circ (2,1) = (1,1)$ so that $S$ is not 2-total. $\square$
A band is a 1-total semigroup, so that every singleton is a subsemigroup. A subtotal semigroup is simply a 1-total semigroup that is also 2-total, therefore every subtotal semigroup is a band. Every band is a semilattice of rectangular bands. By this construction, and the previous two lemmas we have a structure theorem for subtotal semigroups.
Theorem. let $S$ be a subtotal semigroup. Then $S$ is a total order semilattice of pure rectangular bands.
Proof. (1) by the fact that $S$ is subtotal it is a band, and then by the classification theorem for bands this means that it is a semilattice of rectangular bands (2) by the fact that only pure rectangular bands are subtotal it follows that each rectangular band must be pure (3) finally the semilattice must be subtotal which must be a total order. $\square$
The class of pure rectangular bands is the union of the atomic varieties of left zero and right zero bands. It follows that each subtotal semigroup can contain either left zero semigroups, right zero semigroups, or both. A subtotal semigroup is called mixed if it contains one of each of the different types.
- Unmixed subtotal semigroup: all pure rectangular bands are either all left or all right.
- Mixed subtotal semigroup: these contain both left and right zero components
Proposition. (1) atoms in the lattice of subsemigroups are trivial monoids and (2) atoms in the lattice of subgroups are prime order cyclic groups.
Every atomic subsemigroup is clearly monogenic. In the finite case, we always have an idempotent subsemigroup as an atomic which means $S$ must be a trivial monoid. On the other hand, the infinite monogenic semigroup has no atoms, which means nothing covers the empty set. The empty subsemigroup is an order topological limit point of any maximal chain, because every maximal chain of subsemigroups will terminate at the empty set.
Subscribe to:
Comments (Atom)