Algebras¶
Definition
In mathematics (abstract algebra), an algebra (also referred to as an algebraic structure consists of a set (called the ground set, which is the set that contains the elements to which the algebra applies) with one or more operations (finitary operation) on the set such as:
- A set of binary operations (each with an optional identity element).
- A set of unary operations.
- A set of relations defined on the ground set.
The ground set combined with the set of operations and identity elements together is called the signature of the algebra.
Some types of algebras:
A semigroup is a non-empty set \(X\) together with a binary operation \(\ast\) which is associative.
A monoid is a semigroup \(X\) with an identity element \(e\) under \(\ast\). We call \(e\) and identity element if: \(\begin{equation*} x\ast e=e\ast x\text{ for all }x\in X. \end{equation*}\)
A group is a monoid where every element has an inverse under \(\ast\), namely, for each \(x\in X\) there exists a \(y\in X\) such that \(x\ast y=e=y\ast x\).
A Boolean algebra consists of a non-empty set \(B\) together with two binary operations we will call \(\oplus\) and \(\odot\), a unary operation \(^{*}\), and two distinguished elements \(\mathbf{0}\) and \(\mathbf{1}\) (these are not, in general, the integers 0 and 1) such that:
- \(\oplus\) and \(\odot\) are each commutative and associative, and each distributes over the other.
- For each \(x\in B\)
\[\begin{split}\begin{equation*} \begin{array}{lll} x\oplus \mathbf{0}=x & \text{ } & x\odot \mathbf{0}=\mathbf{0} \\ x\oplus \mathbf{1}=\mathbf{1} & \text{ } & x\odot \mathbf{1}=x \\ x\oplus x\text{*}=\mathbf{1} & \text{ } & x\odot x\text{*}=\mathbf{0}% \end{array}% . \end{equation*}\end{split}\]- For all \(x,y\in B\)
\[\begin{equation*} \begin{array}{lll} x\odot (x\oplus y)=x & \text{ } & x\oplus (x\odot y)=x% \end{array}% . \end{equation*}\]
Algebra of Sets¶
Definition:
The algebra of sets is an algebra with the signature
Its ground set is the power set of set M (\(M\)). The binary operations are union (\(\cup\), with the identity element \(\varnothing\), the empty set) and intersection (\(\cap\), with the identity element \(M\)), the one unary operation is the complement (\('\)) and the one relation is the subset relation.
Other binary operations (that can be derived from the basic operations and relations) include difference, substriction and superstriction; other relations include the superset relation.
Remark and useful fact: The algebra of any non-empty set is always a Boolean algebra. This means that in particular the algebra on set M (\(M\)) is a Boolean algebra. It also true that any Boolean algebra with a finite ground set \(B\) is the algebra of some set.
Other useful operations on sets:
- The difference of two sets.
- The symmetric difference of two sets.
This gives us two alternative algebras of sets where we use difference and symmetric difference:
\[\bigg[ P(M),[-],[\bigtriangleup ],\subset ,^{\prime }\bigg]\]
and an extension
\[\bigg[ P(M), [\cup ,\varnothing ], [\cap ,M],[-], [\bigtriangleup ],\subset ,^{\prime } \bigg].\]
Identities concerning difference and symmetric difference: Given subsets \(S,T\) and \(U\) of set M (\(M\)):
- \(S-T=S\cap T^{\prime }\).
- \(S-S=\varnothing\).
- \(S-\varnothing =S\).
- \(\varnothing -S=\varnothing\).
- \(S-M=\varnothing\).
- \(M-S=S^{\prime }\).
- \(S\bigtriangleup T=T\bigtriangleup S\). (\(\bigtriangleup\) is commutative.)
- \(S\bigtriangleup (T\bigtriangleup U)=(S\bigtriangleup T)\bigtriangleup U\). (\(\bigtriangleup\) is associative.)
- \(S\bigtriangleup S=\varnothing\).
- \(S\bigtriangleup \varnothing =S\).
- \(S\bigtriangleup M=M-S=S^{\prime }\).
Algebra of Multisets¶
Multiset¶
Definition
A multiset is a set that allows multiple instances of any given element. We define it as a function from a given subset of set M (\(M\)) to the positive integers. In particular, we call \(\dot{S}\) a multiset of \(M\) if for certain \(x\in M\) we have \(\dot{S}(x)\) is a positive integer that we call the multiplicity of \(x\).
Example
Let \(M=\{a,b,c\}\) and \(\dot{S}\) represent the multiset \(\{a,a,a,b,b\}\), then we have \(\dot{S}(a)=3\), \(\dot{S}(b)=2\), and \(\dot{S}(c)\) is not defined. In this case \(a\) has multiplicity 3, and \(b\) has multiplicity 2.
Multiset Algebra¶
Definition
Let \(\dot{P}(M)\) represent the set of all multisets of \(M\). Using the definitions of multiset union, multiset addition, multiset intersection, and submultiset as applied to multisets we have an algebra on multisets with the following signature:
Algebra of Couplets¶
The algebra of couplets is an algebra with the signature
\[\bigg[ M \times M , \big\{\ \circ\ \big\} , \big\{ \leftrightarrow \big\} \bigg]\]
Its ground set is the Cartesian product of set M (\(M\)) with itself. The only binary operation is composition (\(\circ\), without identity element) and the only unary operation is the transposition (\(\leftrightarrow\)).
Algebra of Relations¶
Definition
The algebra of relations is the algebra of sets of couplets; its signature is
\[\bigg[ P(M \times M) , \big\{ [ \circ, D_M ] \big\} , \big\{ \leftrightarrow \big\} \bigg]\]
Its ground set is the power set of the Cartesian product of set M (\(M\)) with itself. The only binary operation is composition (\(\circ\), with the identity element \(D_M\), which is the diagonal on set M (\(M\))) and the only unary operation is the transposition (\(\leftrightarrow\)).
The binary operations union and intersection, the unary operation complement and the subset relation are implicitly present, inherited from the algebra of sets (since the algebra of relations is also an algebra of sets).
Other operations and relations (that can be derived from the basic operations and relations) include the binary operations difference, substriction, superstriction, left-functional union and right-functional union and the superset relation.
Algebra of Clans¶
Definition
The algebra of clans is the algebra of sets of relations, which is sets of sets couplets. Its ground set is therefore the second power set of the Cartesian product of set M (\(M\)) with itself. As a result of being a second power set, the operations of cross-union and cross-intersection can be applied, in addition to the operations on an algebra of sets. Moreover, the operations transposition and composition from the algebra of relations extend in a natural way to the algebra of clans. We also include substriction, superstriction, cross-substriction and cross-superstriction. As a result, it has the following signature:
Note that included in the operations of union and cross-union are the special left-functional and right-functional cases of cross-left-functional union and cross-right-functional union.
Algebra of Multiclans¶
Definition
The algebra of multiclans is an algebra that generalizes the algebra of clans. Since we use \(P(M \times M)\) to denote the set of couplets, a multiset of relations is a multiset of sets of couplets, so we will use \(\dot{P}(P(M \times M))\) to denote the multiset of relations. Combining the multiset algebra with the clan algebra we have
Here the binary operations are all binary multi-extensions of the operations from the algebra of clans, with the exception of multiset addition, and subset is replaced with submultiset. For example, cross-substriction is replaced with multi-cross-substriction. Note that there is no extension of the complement operation. As in the case of clans, the multiset versions of the operations of cross-left-functional union and cross-right-functional union are implied.