The missing element is the free commutative monoid, because then there are no identities in the presentation which can be used to eliminate elements except for the identity element. The identity element is always a redundant element that doesn't effect an operation so there is nothing we can do about that. Thats why small set systems of a certain size avoid considerations about the inclusion of the identity element. So for {{0 1} {0 2} {1 2}} the sum in the free commutative monoid is {0 0 1 1 2 2} and the elimination of any element strictly reduces the result of the operation. So the most interesting element is free commutative monoids which of course produce multisets.
Sets are directly linked to semilattices because they forbid repetition, and semilattices make any repetition redundant to the result of the operation. This is why there is an underlying set (the support) of any multiset produced by the idempotent-reduction of the multiset in the free commutative monoid. A natural question is how to generalize semilattices. The first that comes to mind in generalizing semilattices is that the commutative semigroup generalization should be aperiodic, because that preserves the antisymmetry of the algebraic preordering. The closest thing to a semilattice is an aperidoic commutative max index two unique non-idempotent semigroup, because semilattices require every element to be idempotent and these structures only have one element that is not. The max index of the aperidoic commutative semigroup is the max multiplicity of irredundant representations.
Many more aperiodic commutative semigroups share properties with semilattices though, without being the most similar to them. In particular, they can tend to preserve the monotonicity of presentations which is true until the weak ordered [2 1 1] commutative aperiodic semigroup of order four which doesn't preserve joins of its minimal elements. Commutative semigroups are clearly the closest to commutative semigroups, which is why we can compare the combination of elements to their joins to see similarity to semilattices and the semilattice decompositions feature in their decomposition theory. Its also worth mentioning max order two abelian groups like the xor operation which generalize the symmetric difference and therefore operate on sets, but they are not aperiodic and as groups their preorder is actually symmetric rather then antisymmetric which is what we wanted.
Commutative semigroups can naturally be described by lattice theory by considering presentations in terms of the distributive lattice of multisets. The questions of commutative semigroups then are related to their presentation in this lattice, and its operations like interiors and closures. In the other direction considerations of sets of multisets (as subsets of the multiset inclusion lattice) can be used to better understand commutative semigroups. In this sense, commutative semigroups relate the most to lattices and semilattices.
We considered commutative semigroups and their relation to lattices. However, there are two main objects of study in basic abstract algebra: structures with a single binary operation and structures with two binary operations related to one another. We can generalize from semilattices to abandon idempotence which gets us commutative semigroups, but something different happens when we abandon idempotence in lattices. A commutative semigroup pair (S,+,*) contains two commutative semigroups related by distributivity.
- The operations + and * are semigroups
- Commutativity : the operations are both commutative
- Distributivity : the operations distribute over one another
By this definition all distributive lattices and commutative hemirings are special cases and of course this means that commutative rings are as well as they are a special case of commutative hemirings. Commutative rings are of course a common common area of study then commutative hemirings because the relation between congruence and ideals in them. Importance is lended to commutative hemirings because of the fact that the natural numbers (N,+,*) are one of them which means all arithmetic can be described by hemiring theory. On the other hand, logical operations like boolean algebra and set theory can be described by distributive lattices. It is fascinating to notice this relation between fundamental arithmetic and logic.
The combined conditions of commutativity and distributivity mean that any multivariate polynomial can be described as a multiset of multisets, or a multiset system in some normal form. This relates the theory of multiset systems we are familiar with to the theories of commutative algebra and algebraic geometry. In boolean algebra, this is the relationship between set systems and boolean operations which plays a key role in the set theoretic ontology. This property noticeably only works for distributive lattices though, so for other lattices polynomials can take different forms. Lattice theory can be divided into two halves (1) the theory of distributive lattices and (2) the theory of non-distributive lattices. So a great many important lattices don't have the distributive property.
The commutative hemiring (N,+,*) is actually described by the free commutative monoid on one generator and by the fundamental theorem of arithmetic the free commutative monoid on an infinite generating set adjoined with a zero element. Which means multiplication is free except when dealing with the zero element, which absorbs or annihilates everything else as redundant when it appears in an expression. This means that fundamentally arithmetic is just the combination of multisets keeping repetition. Which demonstrates why free commutative monoids are the most fundamental concept we introduced when studying commutative semigroup theory.
I want the initial guiding principle of commutative hemiring theory to be the actually be the study of iteration, which can then be used in any semigroup because all monogenic semigroups are commutative (as seen in the ontology of commutative semigroups above). Addition is the composition of iterations, and multiplication is repeated iteration. In this way, modular arithmetic forms a commutative ring which describes the iteration properties of automorphisms. Eventually modular arithmetic could be used to describe the iteration of any monogenic semigroup element. Natural numbers describe iteration of functions without congruences, integers exactly describe iteration of functions and elements with inverses, and the rational and real numbers describe fractional iterations. Selecting structures with a specific purpose limits the selection of arbitrary structures.
Besides the theory of arithmetic and monogenic semigroups, it is noted that the subsemigroups of a semigroup form a lattice which means lattice theory can also be used in understanding general semigroups. Monogenic semigroups include the smallest possible semigroups because if a semigroup is not monogenic, a smaller monogenic semigroup can always be produced by determining the subsemigroup generated by a single element. Monogenic semigroups are also commutative, which means that certain commutative semigroups build up all semigroups. In this sense, commutative semigroups can be used to understand all semigroups. In finite group theory, the join irreducibles are actually precisely the cyclic groups of prime power order.
Commutative operations are strictly simpler then general binary operations, because they use less information then them. The output of a commutative operation is entirely determined by the underlying multiset. This property is also shared by left and right invariant binary operations, which only use the first or second argument to determine their output. These types of binary operations aren't that interesting though, because they are entirely determined by ordinary functions. This leaves us with the key of commutative operations.
No comments:
Post a Comment