Perhaps the most basic object of mathematical discourse is that of a set system. This picture is complicated somewhat when we consider topos theory, and we start to consider copresheaf topoi which are about as fundamental as set systems. But we always can find ourselves looking back at concepts of set systems and hypergraphs. As we introduce and develop more forms of mathematical structure we can see set systems from different lights. We will see today how a semiring structure can be established on set systems.
Let $F(S)$ be a free commutative monoid on a set $S$. Then $\mathbb{N}F(S)$ is the semigroup semiring of all multiset systems whose terms are in $S$. We can now define an injective function that maps set systems into this semiring.
\[ f: \wp(\wp(S)) \to \mathbb{N}F(S) \]
With this we can treat set systems like any other arithmetic structure such as $\mathbb{N}$. In fact it is similar to $\mathbb{N}$ in a remarkable way: it is both additively and multiplicative J-trivial.
Proposition. let $\mathbb{N}F(S)$ be a semigroup semiring of multiset systems. Then both its additive and multiplicative parts are J-trivial commutative semigroups.
A semigroup semiring is additively J-trivial if its base semiring is. On the other hand, $\mathbb{N}F(S)$ is multiplicatively J-trivial because both the argument semigroup $F(S)$ and the multiplicative semigroup of the semiring are J-trivial. On the other hand, $\mathbb{Z}F(S)$ is clearly neither additively or multiplicatively J-trivial. We can always recover a J-trivial semigroup from a commutative semiring by quotienting out by the H classes.
Multiplication of set systems:
The definition of the multiplication of set systems follows easily from the definition of semigroup semirings. Algorithms can easily be provided for dealing with the multiplication of set systems by using for example either Clojure's list comprehensions or Java's for loops.
Definition. let $S$ and $T$ be indexed families of multiset systems. Let addition constitute the composition of multisets in a free commutative monoid. Then $ST$ can be defined by the sum:
\[ \sum_{i \in I, j \in J} \{(S_i + T_j)\} \]
This can be used to define our first examples of set system multiplication. Recall from the most basic of mathematics that an ordered pair is a set system of the form $\{\{a\},\{a, b \}\}$. I will first demonstrate the properties of set system multiplication by getting the powers of an ordered pair.
\[ \{\{a\},\{a,b\}\}^2 = \{\{a,a\},\{a,a,b\},\{a,a,b\},\{a,a,b,b\}\} \]
This process can naturally be continued to get yet higher powers of the ordered pair. The resulting multiset systems get quite large as the multiplication process continues.
\begin{equation}
\{\{a\},\{a,b\}\}^3 = \{\{a,a,a\},\{a,a,a,b\},\{a,a,a,b\},\{a,a,a,b,b\}, \\
\{a,a,a,b\},\{a,a,a,b,b\},\{a,a,a,b,b\},\{a,a,a,b,b,b\}\}
\end{equation}
In fact, the exact asymptotics of the growth of the cardinality of products of multiset systems is determined by a homomorphism of semigroups from the multiplication of set systems to the free commutative monoid.
Proposition. let $\mathbb{N}F(S)$ be the semigroup semiring of multiset systems. Let $|X|$ denote the cardinality of a multiset $X$. Then if $A$,$B$ are multiset systems we have that $|AB| = |A||B|$.
It follows that there is a homomorphism $f: (\mathbb{N}F(S),*) \to (\mathbb{N},*)$. Furthermore, it is not hard to see that this can be extended to a homomorphism of semirings $f: \mathbb{N}F(S) \to \mathbb{N}$.
Multiplicative factorisation of set systems:
We can now use the semigroup semiring $\mathbb{N}F(S)$ to interpret the properties of set systems.
Theorem. let $G$ be a complete bipartite graph between the sets $S$ and $T$. Then the binary family of edges of $G$ is the product of disjoint unary families formed from $S$ and $T$.
Proof. the complete bipartite graph has one edge ${s,t}$ for each $s \in S$ and each $t \in T$. On the other hand, the unary family of $S$ has one singleton $\{s\}$ for each $s \in S$ and likewise for $T$ there is one $\{t\}$ in the unary family of $T$ for each $t \in T$. Now given any $s \in S$ and $t \in T$ we get $\{s\} + \{t\} = \{s,t\}$ which is a set because $S$ and $T$ are disjoint. So the product of the unary families of $S$ and $T$ is the family of $G$. $\square$
This general process produces a multiplicative factorisation from complete bipartite binary families. We can now demonstrate this as an example of
Example. $\{\{a,x\},\{a,y\},\{b,x\},\{b,y\}\} = \{\{a\},\{b\}\}*\{\{x\},\{y\}\} $
With this approach, we can form a whole new algebraic theory of multiset systems. All the different set systems that emerge from graphs, partial orders, designs, matroids, etc can now be considered in a new light.
Foundations of combinatorial commutative algebra:
We have seen that commutative algebraic, and in particular the commutative semigroup semiring $\mathbb{N}F(S)$, can be used to better understand set systems and multiset systems. The dual concept is to use set systems as a tool of commutative algebra, which leads to combinatorial commutative algebra.
We have seen that multiset systems are elements of $\mathbb{N}F(S)$. There is an obvious correspondence from $\mathbb{N}F(S)$ to $\mathbb{Z}F(S)$, which extends the homomorphism $f: \mathbb{N} \to \mathbb{Z}$.
\[ i : \mathbb{N}F^(S) \to \mathbb{Z}F(S) \]
Where $\mathbb{Z}F(S)$ is in fact a ring of polynomials, because polynomial rings are nothing more then semigroup rings over free commutative monoids. Let $R$ be a commutative ring with identity $1$ then $R$ has a characteristic $C$ which means that extends over $GF(C)$. There is an obvious morphism $f: \mathbb{Z} \to GF(C)$ so that any non-zero characteristic prime ring is a quotient of $\mathbb{Z}$.
This naturally means that any integral polynomial in the semigroup ring $\mathbb{Z}F(S)$ can be embedded into a commutative ring with identity. This then produces a series of maps $\mathbb{N}F^(S) \to \mathbb{Z}F^{S} \to R F^(S)$ so that multiset systems are embeddable into arbitrary polynomial rings.
The Stanley-Reisner ring is nothing more then an application of this general construction in the case where $F$ is a field and the multiset system in question is the subclass closed set system of an abstract simplicial complex. The Stanley-Reisner ring is the simple the quotient ring determined by the monomial ideals of the set of this set system, but this could just as well be applied to get a quotient ring of a ring from arbitrary multiset systems.
See also:
[1] https://en.wikipedia.org/wiki/Stanley%E2%80%93Reisner_ring
Showing posts with label multiset systems. Show all posts
Showing posts with label multiset systems. Show all posts
Tuesday, February 22, 2022
Tuesday, September 14, 2021
Multiset addition semigroups
The class of all multisets on a set forms a semigroup $F(S)$ with multiset addition as its operation. The additive property of $F(S)$ is formalied by a semigroup homomorphism $f : F(S) \to \mathbb{N}$ which maps each multiset to its cardinality. Given a free commutative semigroup $F(S)$ then there are two ways to form semigroups from it by taking a quotient to get a commutative semigroup presentation or taking a subalgebra to get a multiset addition semigroup.
Theorem. the free $\mathbb{N}$ semimodule $F(S)$ is:
(2) the semiring $\mathbb{N}$ is additively cancellative so that $a + b = a + c$ implies that $b = c$. It follows from additive cancellativity that we have $a + b = a + c$ for addition in the free $\mathbb{N}$ semimodule.
(3) the semiring $\mathbb{N}$ is multiplicatively cancellative for $n \not= 0$. It follows that $na = nb$ implies that $a = b$ for $n \not= 0$. Therefore, $F(S)$ is torsion-free.
(4) every semimodule is an additive commutative monoid, therefore so too is $F(S)$. $\square$
Although $F(S)$ is a distributive lattice ordered torsion-free commutative cancellative semigroup, not all of these propreties are inherited by its subsemigroups. In particular, the distributive lattice ordering is not preserved.
Definition. a commutative semigroup is subfinite provided that each element is contained in a finite number of principal ideals.
Corollary. every subsemigroup of $F(S)$ is a subfinite J-trivial commutative cancellative torsion-free semigroup
Proof. let $A \subseteq B$ be semigroups, then the algebraic preorder on $A$ is a suborder of that of $B$. Therefore, given $C \subseteq F(S)$ then the algebraic preorder on $C$ is a subpreorder of a subfinite partial order, so it is a subfinite partial order making $C$ subfinite J-trivial. It is also commutative, cancellative, and torsion-free as these properties are hereditary. $\square$
This demonstrates that not all J-trivial commutative cancellative torsion-free semigroups can be embedded in a free commutative semigroup $F(S)$. The Puiseux monoid $(\mathbb{Q}_{\ge 0}, +)$ is a J-trivial commutative cancellative semigroup but it is not subfinite so there is no way of achieving an embedding.
A notable property of the Puiseux monoid $(\mathbb{Q}_{\ge 0},+)$ is that is infinitely generated. This suggests perhaps we can produce an embedding in the finitely generated case. This is an easy corollary of Grillet's theorem.
Grillet's theorem. a monoid is finitely generated commutative cancellative reduced monoid iff it is embeddable in $\mathbb{N}^n$.
Corollary. a finitely generated commutative cancellative J-trivial monoid is embeddable in $\mathbb{N}^n$ iff it is torsion-free
This demonstrates that the only properties necessary to demonstrate that a finitely generated commutative J-trivial semigroup is embeddable in $\mathbb{N}^n$ is that it is cancellative and torsion-free. These semigroups can therefore be expressed as multiset addition semigroups.
Example 1. consider the subsemigroup $xy,x^2,y^2$. Then every factorisation of $x^n,y^m$ is a solution of the following system of linear equations: \[ \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Each solution to the system of linear equations produces a different factorisation of the multiset. For example, $x^4y^4$ has three factorisations: $(x^2)^2(y^2)^2$,$(xy)^2x^2y^2$,$(xy)^4$.
Example 2. consider the subsemigroup $x^3,x^2y,xy^2,y^3$. Then a factorisation of $x^n,y^m$ is a solution to the following system of linear equations: \[ \begin{bmatrix} 3 & 2 & 1 & 0 \\ 0 & 1 & 2 & 3 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Now $x^6 y^6$ has five factorisations: $(x^3)^2(y^3)^2$, $(xy^2)^2 (x^2y)^2$, $x^3 y^3 x^2y xy^2$, $x^3 (xy^2)^3$, $y^3 (yx^2)^3$.
This demonstrates by linear factorisation, that not all commutative J-trivial cancellative torsion-free finitely generated semigroups have unique factorisations. Although $F(S)$ does have unique factorisations, so that each element is uniquely expressed as a multiset.
Definition. a commutative J-trivial semigroup is called factorial provided that every element has a unique factorisation.
Example. the condensation $\frac{*}{H}$ of the multiplicative semigroup $*$ of a UFD is a factorial commutative cancellative J-trivial semigroup.
Notice that $x^2,y^2,xy$ determines a commutative subsemigroup but $x^2,x^2,xy,x^2y^2$ determines the same semigroup. We therefore need one more concept in order to enable computations on multiset systems related to the subsemigroups they generate:
Definition. a multiset system $S$ is sum minimal provided that $\forall x : x \not\in (S-x)$ so that no element $x$ is generated by the other elements in the multiset system.
For example, we can describe a numerical semigroup by a minimal set of generators, which is a simple combinatorial data structure we can work with. With this definition, it is a fairly simple procedure to create an algorithm to check if a given multiset system is sum minimal by solving a system of linear equations to check for factorisations of each element.
Proposition. the category of free commutative monoids is equivalent to the category of $\mathbb{N}$ semimodules with natural matrices between them.
The linear algebraic approach to free $\mathbb{N}$ semimodules allows us to describe any homomorphism of $\mathbb{N}$ semimodules by natural matrices. In particular, the endomorphism semiring $End(F(S))$ of a free commutative semimodule is equivalent to a matrix ring $Mat_S(\mathbb{N})$ over the semiring of natural numbers.
The factorisation of multisets can be determined by solving systems of linear equations over the natural numbers, or by determining the inverse image of a natural-valued matrix. This leads to the linear algebraic approach to $\mathbb{N}$ semimodules.
Properties of free $\mathbb{N}$-semimodules
The free $\mathbb{N}$ semimodule $F(S)$ on a set $S$ has a number of properties that are inherited by its subalgebras. Although every commutative semigroup is a quotient of some $F(S)$, only a small number of commutative semigroups can be embedded in the free commutative semigroup $F(S)$.Theorem. the free $\mathbb{N}$ semimodule $F(S)$ is:
- $\mathbb{N}^S$ distributive lattice ordered
- Cancellative
- Torsion-free
- Commutative and a monoid
(2) the semiring $\mathbb{N}$ is additively cancellative so that $a + b = a + c$ implies that $b = c$. It follows from additive cancellativity that we have $a + b = a + c$ for addition in the free $\mathbb{N}$ semimodule.
(3) the semiring $\mathbb{N}$ is multiplicatively cancellative for $n \not= 0$. It follows that $na = nb$ implies that $a = b$ for $n \not= 0$. Therefore, $F(S)$ is torsion-free.
(4) every semimodule is an additive commutative monoid, therefore so too is $F(S)$. $\square$
Although $F(S)$ is a distributive lattice ordered torsion-free commutative cancellative semigroup, not all of these propreties are inherited by its subsemigroups. In particular, the distributive lattice ordering is not preserved.
Definition. a commutative semigroup is subfinite provided that each element is contained in a finite number of principal ideals.
Corollary. every subsemigroup of $F(S)$ is a subfinite J-trivial commutative cancellative torsion-free semigroup
Proof. let $A \subseteq B$ be semigroups, then the algebraic preorder on $A$ is a suborder of that of $B$. Therefore, given $C \subseteq F(S)$ then the algebraic preorder on $C$ is a subpreorder of a subfinite partial order, so it is a subfinite partial order making $C$ subfinite J-trivial. It is also commutative, cancellative, and torsion-free as these properties are hereditary. $\square$
This demonstrates that not all J-trivial commutative cancellative torsion-free semigroups can be embedded in a free commutative semigroup $F(S)$. The Puiseux monoid $(\mathbb{Q}_{\ge 0}, +)$ is a J-trivial commutative cancellative semigroup but it is not subfinite so there is no way of achieving an embedding.
A notable property of the Puiseux monoid $(\mathbb{Q}_{\ge 0},+)$ is that is infinitely generated. This suggests perhaps we can produce an embedding in the finitely generated case. This is an easy corollary of Grillet's theorem.
Grillet's theorem. a monoid is finitely generated commutative cancellative reduced monoid iff it is embeddable in $\mathbb{N}^n$.
Corollary. a finitely generated commutative cancellative J-trivial monoid is embeddable in $\mathbb{N}^n$ iff it is torsion-free
This demonstrates that the only properties necessary to demonstrate that a finitely generated commutative J-trivial semigroup is embeddable in $\mathbb{N}^n$ is that it is cancellative and torsion-free. These semigroups can therefore be expressed as multiset addition semigroups.
Factorisation in $F(S)$ subsemimodules
The free commutative semigroup $F(S)$ is a $\mathbb{N}$ semimodule, and so most important operations over it can be solved by linear algebra over the natural numbers. A finitely generated subsemirgoup of $F(S)$ can be described by the span of a multiset system $\{M_1,M_2,...\}$ which is the set of all linear combinations of the system of multisets. Each solution is a different factorisation.Example 1. consider the subsemigroup $xy,x^2,y^2$. Then every factorisation of $x^n,y^m$ is a solution of the following system of linear equations: \[ \begin{bmatrix} 1 & 2 & 0 \\ 1 & 0 & 2 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Each solution to the system of linear equations produces a different factorisation of the multiset. For example, $x^4y^4$ has three factorisations: $(x^2)^2(y^2)^2$,$(xy)^2x^2y^2$,$(xy)^4$.
Example 2. consider the subsemigroup $x^3,x^2y,xy^2,y^3$. Then a factorisation of $x^n,y^m$ is a solution to the following system of linear equations: \[ \begin{bmatrix} 3 & 2 & 1 & 0 \\ 0 & 1 & 2 & 3 \end{bmatrix} * v = \begin{bmatrix} n \\ m \end{bmatrix} \] Now $x^6 y^6$ has five factorisations: $(x^3)^2(y^3)^2$, $(xy^2)^2 (x^2y)^2$, $x^3 y^3 x^2y xy^2$, $x^3 (xy^2)^3$, $y^3 (yx^2)^3$.
This demonstrates by linear factorisation, that not all commutative J-trivial cancellative torsion-free finitely generated semigroups have unique factorisations. Although $F(S)$ does have unique factorisations, so that each element is uniquely expressed as a multiset.
Definition. a commutative J-trivial semigroup is called factorial provided that every element has a unique factorisation.
Example. the condensation $\frac{*}{H}$ of the multiplicative semigroup $*$ of a UFD is a factorial commutative cancellative J-trivial semigroup.
Notice that $x^2,y^2,xy$ determines a commutative subsemigroup but $x^2,x^2,xy,x^2y^2$ determines the same semigroup. We therefore need one more concept in order to enable computations on multiset systems related to the subsemigroups they generate:
Definition. a multiset system $S$ is sum minimal provided that $\forall x : x \not\in (S-x)$ so that no element $x$ is generated by the other elements in the multiset system.
For example, we can describe a numerical semigroup by a minimal set of generators, which is a simple combinatorial data structure we can work with. With this definition, it is a fairly simple procedure to create an algorithm to check if a given multiset system is sum minimal by solving a system of linear equations to check for factorisations of each element.
Proposition. the category of free commutative monoids is equivalent to the category of $\mathbb{N}$ semimodules with natural matrices between them.
The linear algebraic approach to free $\mathbb{N}$ semimodules allows us to describe any homomorphism of $\mathbb{N}$ semimodules by natural matrices. In particular, the endomorphism semiring $End(F(S))$ of a free commutative semimodule is equivalent to a matrix ring $Mat_S(\mathbb{N})$ over the semiring of natural numbers.
The factorisation of multisets can be determined by solving systems of linear equations over the natural numbers, or by determining the inverse image of a natural-valued matrix. This leads to the linear algebraic approach to $\mathbb{N}$ semimodules.
Sunday, August 29, 2021
Multiset representations of partial orders
Every partial order can be embedded in a boolean algebra, by representing each element of the poset as sets. A natural generalisation of this is to represent each element of the poset as a multiset. In order to do this, we need to determine when an element is a multiple of another. This occurs when it has at most one irreducible predecessor. This is implemented below.
(defn irreducible-representation
[family elem]
(let [predecessors (direct-subdimembers family elem)]
(if (= (count predecessors) 1)
(let [predecessor (first predecessors)]
(let [dipredecessors (direct-subdimembers
family
predecessor)]
(if (= (count dipredecessors) 1)
(let [next-coll (frequencies
(irreducible-representation
family
predecessor))]
(Multiset. {(first (keys next-coll))
(inc (first (vals next-coll)))}))
(Multiset. {elem 1}))))
(Multiset. {}))))
(defn clan-representations
[family]
(set
(map
(fn [i]
(let [coll (subdimembers family i)]
(apply
join
(map
(fn [i]
(irreducible-representation family i))
coll))))
(apply union family))))Monday, August 16, 2021
Commutative J-trivial semigroup presentations
Commutative semigroups have presentations in the lattice of multisets, by their description as quotients of the free semimodule $F(S)$. In the case of commutative groups, there is no uniqueness of presentation even for the cyclic group $C_3$ on three elements. However, for the other fundamental type of commutative semigroups it is often possible to find a unique minimal generating set.
Theorem. let $S$ be a finite commutative J-trivial semigroup, then $S$ has a unique minimal generating set.
Proof. the semigroup $S$ is finite, so it satisfies the ACC on principal ideals. By the maximal condition, let $M$ be the set of all maximal principal ideals of $S$. Then by J-triviality each of these maximal principal ideals is associated with a unique irreducible element $x$. Let $X$ be the set of irreducible elements that generate $M$.
Let $I$ be the current set of irreducibles and $C$ the set of remaining elements of $S$. Then union $X$ to $I$ and remove $(X)$ from $C$. Then we have a new set $C$, which again satisfies the ACC so take its maximal elements and add them to the irreducibles and remove the elements they generate from $C$. Repeat this process a finite number of times to produce the unique minimal generating set $I$. $\square$
The basis of this is the ACC on principal ideals of the commutative J-trivial semigroup. This clearly holds when $S$ is finite. Suppose that $S$ is instead a finitely generated commutative J-trivial semigroup. Then $S$ satisfies the ACC on principal ideals as well.
Theorem. finitely generated commutative semigroups satisfy the ACC on principal ideals
Proof. define $X$ to be any finite set of elements and consider the map \[ f : F(X) \to S \] Mapping any word expressed in $X$ to $S$. Then $f$ is monotone (from the multiset ordering on $F(X)$ words to the increasing action preorder on $S$). Let $T$ be the ascending chain of principal ideals. Then form the ideal closure of $T$ to get an ideal $I$ in $S$ that contains every element of the ascending chain of principal ideals.
Then by the monotonicity of $F$ the ideal $I$ in $S$ reflects back to an ideal in $F(X)$ of the form $f^{-1}(I)$. By Dickson's lemma, this ideal $f^{-1}(X)$ is finitely generated. Consider the finite generators of $f^{-1}(X)$ then they reflect to a set of maximal principal ideals in $T$, these in turn in have a maximal represpentative (their join), so they do not generate the entire ascending chain. $\square$
We can now use this theorem with a generalization of the first theorem, to get a unique minimal generating set for any finitely generated commutative semigroup. More generally, this works for any commutative semigroup satisfying the ACC on principal ideals: for example $(\mathbb{Z}_+,*)$ satisfies the ACC on principal ideals and has a minimal generating set the set of prime numbers.
Theorem. let $S$ be a commutative J-trivial semigroup satisfying the ACC on principal ideals then it has a unique minimal generating set
Proof. (1) the base case: by the maximum condition $S$ has a set of maximum proper principal ideals, which by maximality are not generated by any element so they must be in any minimal generating set (2) we can remove from $S$ the generators of its maximum proper principal ideals and the elements generated by them to get another suborder satisfying the ACC. By transfinite induction this terminates after some ordinal number of steps to produce a minimal generating set. $\square$
One could speculate that the existence of unique generators is applicable to any commutative J-trivial semigroups, but this is not the case. A counter example is $(\mathbb{Q}_+,+)$. This doesn't satisfy the ACC on principal ideals (or any chain condition of any kind because it is dense), so it need not have a unique minimal generating set. A generating set for $(\mathbb{Q},+)$ is any lower interval, but by density there is no minimal lower interval so it doesn't have a unique minimal generating set.
Numerical semigroups are an example of a class of commutative finitely generated J-trivial semigroups. Naturally, it is known that any such numerical semigroup has a unique minimal generating set, which is finite because numerical semigroups are finitely generated. The size of the minimum generating set of a numerical semigroup is its embedding dimension.
Proposition. let $S$ be a commutative finitely generated semigroup, then $\frac{S}{H}$ is finitely generated.
Proof. let $X$ be a finite generating set for $S$ and $\pi : S \to \frac{S}{H}$. Then get the image $\pi(X)$, then this forms a finite generating set for $\frac{S}{H}$. Let $x \in \frac{S}{H}$ then choose a representative in $S$ for it and form its factorisation $t$ in terms of $X$ then $\pi(t)$ is a factorisation of $x$ in $\frac{S}{H}$ expressed in terms of $\pi(X)$, so every term in $\frac{S}{H}$ has a unique factorisation by $\pi(X)$. $\square$
In general, there is not a unique minimal generating set for a finite semigroup. The first counter example is the cyclic group $C_3$ on three elements: it has two different unique generators. In general, the number of generators for a cyclic group is the totient $\phi(n)$. We have a general idea of what finitely generated commutative groups are and what they look like, but no inherent notion of what their generating sets need to be.
The preceding theorem for finitely generated commutative semigroups, demonstrates that every finitely generated commutative semigroup is associated with a condensation $\frac{S}{H}$ which has a unique minimal generating set. This tells you the minimal set of J classes necessary to generate $S$, but still doesn't tell you how to generate each of the classes, or even if other J classes are necessary.
We can now speak about presentations. Suppose that we have a commutative semigroup $S$ with generating set $X$ then we have a map from the free commutative semigroup $F(X)$ to $S$. The free commutative semigroup $F(X)$ is a lattice ordered family of multisets, and the commutative J-trivial semigroup $S$ is naturally partially ordered. As a first step, I would like to relate the order on $F(X)$ to $S$.
Theorem. let $S$ be a commutative semigroup and $C$ a congruence of $S$ then the algebraic preorder on $\frac{S}{C}$ is the ordinary precedence preorder on $C$ with respect to the ordering of $S$.
Proof. suppose $A \subseteq B$ in $\frac{S}{C}$ then $\exists C : AC = B$. By an appropriate choice of representatives, this means that $ac = b$ for some $a \in A, c \in C, b \in B$ so that $a \subseteq b$ which implies that $a \frac{\subseteq}{C} b$. Thus, algebraic precedence in $\frac{S}{C}$ implies ordinary precedence.
Conversely, suppose that $a \frac{\subseteq}{C} b$. This means that there exists some $x$ such that $ax = b$. Consider the projection $pi : S \to \frac{S}{C}$. Then we can get the projection $\pi(x)$ so that $\pi(A)\pi(x) = \pi(B)$ so that $\pi(A) \subseteq \pi(B)$ in $\frac{S}{C}$. Thusly, ordinary precedence applies algebraic precedence in the quotient. $\square$
This implies that in order for the congruence of a commutative J-trivial semigroup to again be J-trivial, all of its equivalence classes must be convex. This generalizes the case for semilattice congruences, lattice congruences, etc. In those cases the congruence classes also need other conditions (like being a subsemilattice or a sublattice). In the finite case, this implies upper or lower bounds, or in the case of congruences of finite lattice that each congruence class is an interval.
Corollary. let $S$ be a commutative J-trivial semigroup and $C$ a congruence with J-trivial quotient. Then the congruence classes of $C$ are convex.
In the case of a semilattice congruence, we have that each congruence class is a subsemilattice. In a finite join semilattice, this implies the existence of upper bounds. This has a further implication: each congruence class has a unique representative. In the case of a finite semilattice congruence, these are the principal filters of irreducibles. It would be nice if this process could pass over to commutative J-trivial semigroups.
We see though, that it does not. The exceptional commutative J-trivial semigroup has neither upper or lower bounds for the congruence class of its intermediate element in its presentation determined by its unique minimal generating set. Thusly, it won't be as easy to characterize the representatives of congruence classes of commutative J-trivial semigroups as it is for semilattices.
The presentations of commutative J-trivial semigroups are interestingly linked to the combinatorics of multiset lattices. This is a major motivation for the study of commutative J-trivial semigroups. The following construction describes how to finite commutative J-trivial semigroups in terms of finite multiset lattices.
Definition. let $S$ be a finite commutative J-trivial semigroup with finite generating set $X$. Then define a map $m : X \to \mathbb{N}$ that assigns each $X$ element to the cardinality of its monogenic semigroup. Then this map $m: X \to \mathbb{N}$ defines a multiset, by considering its outputs to be multiplicities.
Then consider the power multiset $\wp(m)$ consisting of all submultisets of $m$. Then $\wp(m)$ forms a finite multiset lattice. The words of $S^1$ can now be presented by congruence classes in the finite multiset lattice $\wp(m)$. Define the power multiset partition of $S^1$ to be the family of all congruences of terms in $\wp(m)$ by the unique minimal generating set of $S$.
This associates to any element in a finite commutative J-trivial semigroup a finite convex family of multisets. As an application, we can consider any element that is maximally presentable to be any element whose generating set equivalence class has an upper bound. The maximally presentable elements form a subset of $S$.
That subset of commutative J-trivial monoids that have maximal representatives for each element, can be associated to closure operations on finite multiset lattices. This generalisations the representation of semilattices with identity by closures on finite boolean algebras.
Theorem. let $S$ be a finite commutative J-trivial semigroup, then $S$ has a unique minimal generating set.
Proof. the semigroup $S$ is finite, so it satisfies the ACC on principal ideals. By the maximal condition, let $M$ be the set of all maximal principal ideals of $S$. Then by J-triviality each of these maximal principal ideals is associated with a unique irreducible element $x$. Let $X$ be the set of irreducible elements that generate $M$.
Let $I$ be the current set of irreducibles and $C$ the set of remaining elements of $S$. Then union $X$ to $I$ and remove $(X)$ from $C$. Then we have a new set $C$, which again satisfies the ACC so take its maximal elements and add them to the irreducibles and remove the elements they generate from $C$. Repeat this process a finite number of times to produce the unique minimal generating set $I$. $\square$
The basis of this is the ACC on principal ideals of the commutative J-trivial semigroup. This clearly holds when $S$ is finite. Suppose that $S$ is instead a finitely generated commutative J-trivial semigroup. Then $S$ satisfies the ACC on principal ideals as well.
Theorem. finitely generated commutative semigroups satisfy the ACC on principal ideals
Proof. define $X$ to be any finite set of elements and consider the map \[ f : F(X) \to S \] Mapping any word expressed in $X$ to $S$. Then $f$ is monotone (from the multiset ordering on $F(X)$ words to the increasing action preorder on $S$). Let $T$ be the ascending chain of principal ideals. Then form the ideal closure of $T$ to get an ideal $I$ in $S$ that contains every element of the ascending chain of principal ideals.
Then by the monotonicity of $F$ the ideal $I$ in $S$ reflects back to an ideal in $F(X)$ of the form $f^{-1}(I)$. By Dickson's lemma, this ideal $f^{-1}(X)$ is finitely generated. Consider the finite generators of $f^{-1}(X)$ then they reflect to a set of maximal principal ideals in $T$, these in turn in have a maximal represpentative (their join), so they do not generate the entire ascending chain. $\square$
We can now use this theorem with a generalization of the first theorem, to get a unique minimal generating set for any finitely generated commutative semigroup. More generally, this works for any commutative semigroup satisfying the ACC on principal ideals: for example $(\mathbb{Z}_+,*)$ satisfies the ACC on principal ideals and has a minimal generating set the set of prime numbers.
Theorem. let $S$ be a commutative J-trivial semigroup satisfying the ACC on principal ideals then it has a unique minimal generating set
Proof. (1) the base case: by the maximum condition $S$ has a set of maximum proper principal ideals, which by maximality are not generated by any element so they must be in any minimal generating set (2) we can remove from $S$ the generators of its maximum proper principal ideals and the elements generated by them to get another suborder satisfying the ACC. By transfinite induction this terminates after some ordinal number of steps to produce a minimal generating set. $\square$
One could speculate that the existence of unique generators is applicable to any commutative J-trivial semigroups, but this is not the case. A counter example is $(\mathbb{Q}_+,+)$. This doesn't satisfy the ACC on principal ideals (or any chain condition of any kind because it is dense), so it need not have a unique minimal generating set. A generating set for $(\mathbb{Q},+)$ is any lower interval, but by density there is no minimal lower interval so it doesn't have a unique minimal generating set.
Numerical semigroups are an example of a class of commutative finitely generated J-trivial semigroups. Naturally, it is known that any such numerical semigroup has a unique minimal generating set, which is finite because numerical semigroups are finitely generated. The size of the minimum generating set of a numerical semigroup is its embedding dimension.
Proposition. let $S$ be a commutative finitely generated semigroup, then $\frac{S}{H}$ is finitely generated.
Proof. let $X$ be a finite generating set for $S$ and $\pi : S \to \frac{S}{H}$. Then get the image $\pi(X)$, then this forms a finite generating set for $\frac{S}{H}$. Let $x \in \frac{S}{H}$ then choose a representative in $S$ for it and form its factorisation $t$ in terms of $X$ then $\pi(t)$ is a factorisation of $x$ in $\frac{S}{H}$ expressed in terms of $\pi(X)$, so every term in $\frac{S}{H}$ has a unique factorisation by $\pi(X)$. $\square$
In general, there is not a unique minimal generating set for a finite semigroup. The first counter example is the cyclic group $C_3$ on three elements: it has two different unique generators. In general, the number of generators for a cyclic group is the totient $\phi(n)$. We have a general idea of what finitely generated commutative groups are and what they look like, but no inherent notion of what their generating sets need to be.
The preceding theorem for finitely generated commutative semigroups, demonstrates that every finitely generated commutative semigroup is associated with a condensation $\frac{S}{H}$ which has a unique minimal generating set. This tells you the minimal set of J classes necessary to generate $S$, but still doesn't tell you how to generate each of the classes, or even if other J classes are necessary.
We can now speak about presentations. Suppose that we have a commutative semigroup $S$ with generating set $X$ then we have a map from the free commutative semigroup $F(X)$ to $S$. The free commutative semigroup $F(X)$ is a lattice ordered family of multisets, and the commutative J-trivial semigroup $S$ is naturally partially ordered. As a first step, I would like to relate the order on $F(X)$ to $S$.
Theorem. let $S$ be a commutative semigroup and $C$ a congruence of $S$ then the algebraic preorder on $\frac{S}{C}$ is the ordinary precedence preorder on $C$ with respect to the ordering of $S$.
Proof. suppose $A \subseteq B$ in $\frac{S}{C}$ then $\exists C : AC = B$. By an appropriate choice of representatives, this means that $ac = b$ for some $a \in A, c \in C, b \in B$ so that $a \subseteq b$ which implies that $a \frac{\subseteq}{C} b$. Thus, algebraic precedence in $\frac{S}{C}$ implies ordinary precedence.
Conversely, suppose that $a \frac{\subseteq}{C} b$. This means that there exists some $x$ such that $ax = b$. Consider the projection $pi : S \to \frac{S}{C}$. Then we can get the projection $\pi(x)$ so that $\pi(A)\pi(x) = \pi(B)$ so that $\pi(A) \subseteq \pi(B)$ in $\frac{S}{C}$. Thusly, ordinary precedence applies algebraic precedence in the quotient. $\square$
This implies that in order for the congruence of a commutative J-trivial semigroup to again be J-trivial, all of its equivalence classes must be convex. This generalizes the case for semilattice congruences, lattice congruences, etc. In those cases the congruence classes also need other conditions (like being a subsemilattice or a sublattice). In the finite case, this implies upper or lower bounds, or in the case of congruences of finite lattice that each congruence class is an interval.
Corollary. let $S$ be a commutative J-trivial semigroup and $C$ a congruence with J-trivial quotient. Then the congruence classes of $C$ are convex.
In the case of a semilattice congruence, we have that each congruence class is a subsemilattice. In a finite join semilattice, this implies the existence of upper bounds. This has a further implication: each congruence class has a unique representative. In the case of a finite semilattice congruence, these are the principal filters of irreducibles. It would be nice if this process could pass over to commutative J-trivial semigroups.
We see though, that it does not. The exceptional commutative J-trivial semigroup has neither upper or lower bounds for the congruence class of its intermediate element in its presentation determined by its unique minimal generating set. Thusly, it won't be as easy to characterize the representatives of congruence classes of commutative J-trivial semigroups as it is for semilattices.
The presentations of commutative J-trivial semigroups are interestingly linked to the combinatorics of multiset lattices. This is a major motivation for the study of commutative J-trivial semigroups. The following construction describes how to finite commutative J-trivial semigroups in terms of finite multiset lattices.
Definition. let $S$ be a finite commutative J-trivial semigroup with finite generating set $X$. Then define a map $m : X \to \mathbb{N}$ that assigns each $X$ element to the cardinality of its monogenic semigroup. Then this map $m: X \to \mathbb{N}$ defines a multiset, by considering its outputs to be multiplicities.
Then consider the power multiset $\wp(m)$ consisting of all submultisets of $m$. Then $\wp(m)$ forms a finite multiset lattice. The words of $S^1$ can now be presented by congruence classes in the finite multiset lattice $\wp(m)$. Define the power multiset partition of $S^1$ to be the family of all congruences of terms in $\wp(m)$ by the unique minimal generating set of $S$.
This associates to any element in a finite commutative J-trivial semigroup a finite convex family of multisets. As an application, we can consider any element that is maximally presentable to be any element whose generating set equivalence class has an upper bound. The maximally presentable elements form a subset of $S$.
That subset of commutative J-trivial monoids that have maximal representatives for each element, can be associated to closure operations on finite multiset lattices. This generalisations the representation of semilattices with identity by closures on finite boolean algebras.
Monday, September 16, 2019
Max order one multiset systems
In a previous post I described how the ordering of distinct max order one multiset systems is a disjoint union of total orders. This describes the order type of the support of a max order one multiset system but it does not completely describe the multiset system type of the max order one multiset system.
Therefore, we need to further consider max order one multiset systems, and the multisets of prime powers, which often emerge from commutative groups. Consider as an example {2,2,4,4,3,3,27} then in this case we can partition this by the support of each of these multisets and therefore we will get {2,2,4,4} and {3,3,27}. Then each of these has their own signature defined by the multiset of exponents of each of these multisets of prime factorizations in this case, though the multiplicative concept of a positive integer and a finitary multiset are equivalent. The multiset system type of these is then the multiset of exponent signatures of these components.
So for the example of {2,2,4,4} we will have {1,1,2,2} and for {3,3,27} we will have {1,1,3}. The overall type is then {{1,1,2,2},{1,1,3}. This perhaps demonstrates that multisets of signatures will play a key role in understanding multiset systems. The only other detail is the multiplicity of the empty set, in the not necessarily nullfree case, which is simply a non-negative integer. These multisets of signatures can also be acquired from the membership signatures of each dimember of a multiset system, which generalizes signatures of set systems themselves.
A larger example is {2,2,4,3,3,9,5,125,125,3125,3125,3125,7,343} which produces the multiset system type {{1,1,2},{1,1,2},{1,3,5},{1,3}}. This demonstrates that this multiset of signatures can have repetition as we can see that {2,2,4} is isomorphic to {3,3,9} as a multiset system of prime factorizations. Together this fully defines these multiset systems that emerge from commutative groups. The height of each element of each total order is the support size of each of these multisets, so we can get the order type as well from this full description.
Therefore, we need to further consider max order one multiset systems, and the multisets of prime powers, which often emerge from commutative groups. Consider as an example {2,2,4,4,3,3,27} then in this case we can partition this by the support of each of these multisets and therefore we will get {2,2,4,4} and {3,3,27}. Then each of these has their own signature defined by the multiset of exponents of each of these multisets of prime factorizations in this case, though the multiplicative concept of a positive integer and a finitary multiset are equivalent. The multiset system type of these is then the multiset of exponent signatures of these components.
So for the example of {2,2,4,4} we will have {1,1,2,2} and for {3,3,27} we will have {1,1,3}. The overall type is then {{1,1,2,2},{1,1,3}. This perhaps demonstrates that multisets of signatures will play a key role in understanding multiset systems. The only other detail is the multiplicity of the empty set, in the not necessarily nullfree case, which is simply a non-negative integer. These multisets of signatures can also be acquired from the membership signatures of each dimember of a multiset system, which generalizes signatures of set systems themselves.
A larger example is {2,2,4,3,3,9,5,125,125,3125,3125,3125,7,343} which produces the multiset system type {{1,1,2},{1,1,2},{1,3,5},{1,3}}. This demonstrates that this multiset of signatures can have repetition as we can see that {2,2,4} is isomorphic to {3,3,9} as a multiset system of prime factorizations. Together this fully defines these multiset systems that emerge from commutative groups. The height of each element of each total order is the support size of each of these multisets, so we can get the order type as well from this full description.
Monday, September 9, 2019
Commutative aperiodic semigroups as multiset systems
The classification of finite commutative groups is relatively straightforward and has essentially already been achieved in terms of certain prime factorizations (which are of course multisets themselves). The harder problem then is to consider commutative aperiodic semigroups, so most of the work has went into examining them in detail. A brief description of some of these commutative aperiodic semigroups is therefore described below. All commutative associative operations are operations on multisets. Semilattices on the other hand are like operations on sets, and their characteristic operation is the closure of certain sets in a set system.
In order to generalize that to commutative aperiodic semigroups we need to define semigroups that can be described by their closure operations. To do this first we determine the idempotents by the non-repeating elements in the multisets of the set system, for these the product is equal to themselves. Otherwise the closure operation is the typical closure operation in the distributive lattice of multisets corresponding to the smallest parent. In this way, we can generalize the notion of a semilattice. There is one exceptional case size four, and then there are eighteen more of size five, and the exceptions increase within the class of aperiodic semigroups.
Semilattices:
total order
weak order [1 2 1]
weak order [2 1 1]
weak order [3 1]
tree semilattice
Near semilattices
Monogenic monoid + zero
Monogenic semigroup + 0 + 0
2-monogenic and 1-monogenic semigroups linked by a new zero element
Monogenic monoid + identity
Bi-idempotent near-zero semigroup + identity
Exceptional tri-idempotent semigroup
Blockwise near-zero semigroup with total order
Tri-idempotent near-zero semigroup
Max index two semigroups:
Zero semigroup + new zero (4 4 4 4)
Zero semigroup + identity (1 2 3 4)
Zero-semigroup plus a new idempotent element (1 2 2 4)
Zero-semigroup plus a new idempotent element (1 1 3 4)
Bi-idempotent near-zero semigroup (1 1 1 4)
Non-unique iteration
One element nilpotent the other is notand otherwise the elements go to zero
Semigroups of max index three
Monogenic semigroup of index 3 with identity element
Monogenic semigroup of index 3 with a new zero element
Monogenic semigroup of index 3 with lesser idempotent
Monogenic with semigroup with element that is index two but for which 3,4 is not directly nilpotent
Monogenic semigroup plus a zero
Monogenic semigroup with lesser element that is nilpotent but for which the generator and the new element do not directly go to zero Reducibles: 1,2
The aperiodic monogenic semigroup:
Aperiodic monogenic semigroup:
In order to generalize that to commutative aperiodic semigroups we need to define semigroups that can be described by their closure operations. To do this first we determine the idempotents by the non-repeating elements in the multisets of the set system, for these the product is equal to themselves. Otherwise the closure operation is the typical closure operation in the distributive lattice of multisets corresponding to the smallest parent. In this way, we can generalize the notion of a semilattice. There is one exceptional case size four, and then there are eighteen more of size five, and the exceptions increase within the class of aperiodic semigroups.
Size zero:
The only semigroup on zero elements corresponds to the empty set system {}.Size one:
The only semigroup on one element is the trivial semigroup {{}}.Size two:
There are two size two commutative aperiodic semigroups which are associated with the two types of multiset system: a set system and a multiset system. The monogenic aperiodic semigroup is clearly the multiset system because it is not idempotent and therefore it is not a semilattice.- The semilattice: {{} {0}}
- The monogenic aperiodic semigroup : {{0} {0 0}}
Size three:
There are seven commutative aperiodic semigroups that have three elements. Since there is so few of these, it is still possible for us to give each of them different names. Since the tree semilattice is not unital, it does not include the identity element. The order of the multiset system is essentially the number of generators used to represent it.- The total order semilattice: {{} {0} {0 1}}
- The tree semilattice: {{0} {1} {0 1}}
- The monogenic monoid: {{} {0} {0 0}}
- The monogenic semigroup plus zero: {{0} {0 0} {0 0 1}}
- The pseudozero semigroup : {{0} {1} {0 0 1}}
- The zero semigroup: {{0} {1} {0 1}}
- The monogenic semigroup: {{0} {0 0} {0 0 0}}
Size four:
Semilattices:
total order
[ [ 1, 1, 1, 1 ],
[ 1, 2, 2, 2 ],
[ 1, 2, 3, 3 ],
[ 1, 2, 3, 4 ] ]
{{} {0} {0 1} {0 1 2}}
weak order [1 2 1]
[ [ 1, 1, 1, 1 ],
[ 1, 2, 1, 2 ],
[ 1, 1, 3, 3 ],
[ 1, 2, 3, 4 ] ]
{{} {0} {1} {0 1}}
weak order [2 1 1]
[ [ 1, 1, 1, 1 ],
[ 1, 2, 2, 2 ],
[ 1, 2, 3, 2 ],
[ 1, 2, 2, 4 ] ]
{{0} {1} {0 1} {0 1 2}}
weak order [3 1]
[ [ 1, 1, 1, 1 ],
[ 1, 2, 1, 1 ],
[ 1, 1, 3, 1 ],
[ 1, 1, 1, 4 ] ]
{{0} {1} {2} {0 1 2}}
tree semilattice
[ [ 1, 1, 1, 1 ],
[ 1, 2, 1, 1 ],
[ 1, 1, 3, 3 ],
[ 1, 1, 3, 4 ] ]
{{0} {1} {1 2} {0 1 2}}
Near semilattices
Monogenic monoid + zero
[ [ 1, 1, 1, 4 ],
[ 1, 1, 2, 4 ],
[ 1, 2, 3, 4 ],
[ 4, 4, 4, 4 ] ]
{{} {2} {2 2} {2 2 4}}
Bi-idempotent near-zero semigroup + zero
[ [ 1, 1, 1, 4 ],
[ 1, 1, 1, 4 ],
[ 1, 1, 3, 4 ],
[ 4, 4, 4, 4 ] ]
{{2} {2 2} {2 2 3} {2 2 3 4}}
Monogenic semigroup + 0 + 0
[ [ 1, 1, 3, 4 ],
[ 1, 1, 3, 4 ],
[ 3, 3, 3, 3 ],
[ 4, 4, 3, 4 ] ]
{{2} {2 2} {2 2 4} {2 2 3 4}}
2-monogenic and 1-monogenic semigroups linked by a new zero element
[ [ 1, 1, 3, 3 ],
[ 1, 1, 3, 3 ],
[ 3, 3, 3, 3 ],
[ 3, 3, 3, 4 ] ]
{{4} {2} {2 2} {2 2 4 3}}
Monogenic monoid + identity
[ [ 1, 1, 1, 1 ],
[ 1, 1, 2, 2 ],
[ 1, 2, 3, 3 ],
[ 1, 2, 3, 4 ] ]
{{} {3} {2 3} {2 2 3}}
Bi-idempotent near-zero semigroup + identity
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 3, 3 ],
[ 1, 2, 3, 4 ] ]
{{} {3} {2} {2 2 3}}
Exceptional tri-idempotent semigroup
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 3, 1 ],
[ 1, 2, 1, 4 ] ]
{{3} {4} {2 4} {2 2 3 4}}
Blockwise near-zero semigroup with total order
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 3, 3 ],
[ 1, 1, 3, 4 ] ]
{{4} {3 4} {2} {2 2 3 4}}
Tri-idempotent near-zero semigroup
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 3, 1 ],
[ 1, 1, 1, 4 ] ]
{{2} {3} {4} {2 2 3 4}}
Max index two semigroups:
Zero semigroup + new zero (4 4 4 4)
[ [ 1, 1, 1, 4 ],
[ 1, 1, 1, 4 ],
[ 1, 1, 1, 4 ],
[ 4, 4, 4, 4 ] ]
{{2} {3} {2 2 3 3} {2 2 3 3 4}
Zero semigroup + identity (1 2 3 4)
[ [ 1, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 1, 1, 1, 3 ], [ 1, 2, 3, 4 ] ]{{} {2} {3} {2 2 3 3}}
Zero-semigroup plus a new idempotent element (1 2 2 4)
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 1, 2 ],
[ 1, 2, 2, 4 ] ]
{{3} {4} {3 4} {3 3 4}}
Zero-semigroup plus a new idempotent element (1 1 3 4)
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 3 ],
[ 1, 1, 3, 4 ] ]
{{3} {3 4} {2} {2 2 3 3 4}}
Bi-idempotent near-zero semigroup (1 1 1 4)
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 4 ] ]
{{4} {2} {3} {2 2 3 3 4}}
Non-unique iteration
[ [ 1, 1, 1, 1 ],
[ 1, 1, 2, 2 ],
[ 1, 2, 3, 3 ],
[ 1, 2, 3, 3 ] ]
{{4} {4 4} {2 4 4} {2 2 4 4}}
One element nilpotent the other is notand otherwise the elements go to zero
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 3, 3 ],
[ 1, 1, 3, 3 ] ]
{{4} {4 4} {2} {2 2 4 4}}
Semigroups of max index three
Monogenic semigroup of index 3 with identity element
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 2, 3 ],
[ 1, 2, 3, 4 ] ]
{{} {0} {0 0} {0 0 0}}
Monogenic semigroup of index 3 with a new zero element
[ [ 1, 1, 1, 4 ],
[ 1, 1, 1, 4 ],
[ 1, 1, 2, 4 ],
[ 4, 4, 4, 4 ] ]
{{3} {3 3} {3 3 3} {3 3 3 4}}
Monogenic semigroup of index 3 with lesser idempotent
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 2, 1 ],
[ 1, 1, 1, 4 ] ]
{{4} {3} {3 3} {3 3 3 4}}
Monogenic with semigroup with element that is index two but for which 3,4 is not directly nilpotent
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ],
[ 1, 1, 2, 2 ] ]
{{4} {3} {3 4 4} {3 3 4 4 4}}
Monogenic semigroup plus a zero
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 2 ] ]
{{4} {3} {4 4} {3 3 4 4 4}}
Monogenic semigroup with lesser element that is nilpotent but for which the generator and the new element do not directly go to zero Reducibles: 1,2
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 2, 2 ],
[ 1, 1, 2, 2 ] ]
{{3} {4} {3 3 4 4} {3 3 3 4 4 4}}
The aperiodic monogenic semigroup:
Aperiodic monogenic semigroup:
[ [ 1, 1, 1, 1 ],
[ 1, 1, 1, 3 ],
[ 1, 1, 1, 1 ],
[ 1, 3, 1, 2 ] ]
{{0} {0 0} {0 0 0} {0 0 0}}
Thursday, August 22, 2019
Types of multiset systems
A set of sets is often called a family. Therefore, a multiset of sets can be called a multifamily. The idea of a set of multisets has rarely been considered, owing to the rarity of studies of multisets. There are a couple of publications that call them "macrosets" but that is a bit verbose and then adding multi to that wouldn't be right. I developed the idea of calling them clans instead, so we could have a better understanding of the theory.
References:
Toward a Formal Macroset Theory:
https://dl.acm.org/citation.cfm?id=721844
- Family: a set of sets
- Multifamily: a multisets of sets
- Clan: a set of multisets
- Multiclan: a multiset of multisets
- Families: sets of squarefree numbers
- Multifamily: multisets of squarefree numbers
- Clan: any set of numbers
- Multifamily: any multiset of numbers
References:
Toward a Formal Macroset Theory:
https://dl.acm.org/citation.cfm?id=721844
Tuesday, December 16, 2014
Multiset systems
One of the critical problems of set theory is how to represent sequences as sets. Well Kuratowski solved the problem for sequences of size two through the set theoretic definition of the ordered pair there is no obvious solution to the problem of representing sequences of arbitrary size as set systems because sequences may contain repeated elements. I have thought about this problem so much in terms of set systems that I did not consider the possibility of using a multiset system instead.
In order to represent any sequence all we need to do is use a multiset system containing the multiset of elements up to a point in the sequence for each point in the sequence. This solution is so simple I am surprised I did not hear about this before. It is probably because multisets are far too often pushed aside for sets but no more. From now on I am going to make full use of multisets when I think about mathematics.
In order to represent any sequence all we need to do is use a multiset system containing the multiset of elements up to a point in the sequence for each point in the sequence. This solution is so simple I am surprised I did not hear about this before. It is probably because multisets are far too often pushed aside for sets but no more. From now on I am going to make full use of multisets when I think about mathematics.
Sunday, January 13, 2013
Multiset partitions
Every multiset can be partitioned into a multiset of parts . The mathematical structure of a multisets partition system is determined by the collection of its multiplicities:
Additive partitions:
Additive partitions are partitions of the multiset {1 n}.
Set partitions:
Multisets whose multiplicities are all one can be described as sets:
Multiplicative partitions:
Every positive integer can be factored into a multiset of prime numbers. The multiplicities multiset of the prime factorization is known as the numbers prime signature.
{:x 2, :y 2, :z 3}
{2 2, 3 1}
Multiplicity sets of {1 n} describe sets and multiplicity multisets of {n 1} describe additive partitions.Additive partitions:
Additive partitions are partitions of the multiset {1 n}.
{1 4}, {1 2, 2 1}, {1 3}, {2 2}, {4 1}
Every multiset that contains only a single element has partitions isomorphic to the additive partitions. Set partitions:
Multisets whose multiplicities are all one can be described as sets:
{:x 1, :y 1, :z 1}
#{#{:x} #{:y :z}}
In Clojure, sets can be described using the pound sign # leaving out the multiplicity values of one.
Multiplicative partitions:
Every positive integer can be factored into a multiset of prime numbers. The multiplicities multiset of the prime factorization is known as the numbers prime signature.
(= (factors 24) {2 3, 3 1})
Multiplicative partitions can be used to describe association structures in terms of the size of each place in the structure.
Subscribe to:
Posts (Atom)