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:

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:

    1. \(\oplus\) and \(\odot\) are each commutative and associative, and each distributes over the other.
    2. 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}\]
    1. 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

\[\bigg[ P(M) , \big\{ [ \cup, \varnothing ] , [ \cap, M ] \big\} , \big\{\ '\ \big\} , \big\{ \subset \big\} \bigg]\]

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:

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\)):

  1. \(S-T=S\cap T^{\prime }\).
  2. \(S-S=\varnothing\).
  3. \(S-\varnothing =S\).
  4. \(\varnothing -S=\varnothing\).
  5. \(S-M=\varnothing\).
  6. \(M-S=S^{\prime }\).
  7. \(S\bigtriangleup T=T\bigtriangleup S\). (\(\bigtriangleup\) is commutative.)
  8. \(S\bigtriangleup (T\bigtriangleup U)=(S\bigtriangleup T)\bigtriangleup U\). (\(\bigtriangleup\) is associative.)
  9. \(S\bigtriangleup S=\varnothing\).
  10. \(S\bigtriangleup \varnothing =S\).
  11. \(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:

\[\bigg[\dot{P}(M), [\cup,\varnothing], [+,\varnothing],\cap,\subset \bigg].\]

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:

\[\bigg[ P^{2}(M \times M),[\cup ,\varnothing ],[\mathbb{\cap },P(M \times M)], [\blacktriangledown ,\{\varnothing\}],[\mathbb{\blacktriangle },\{M \times M\}], \vartriangleleft, \vartriangleright, \blacktriangleleft, \blacktriangleright, \subset , \prime \bigg].\]

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

\[\bigg[ \dot{P}(P(M \times M)),[\cup ,\varnothing ],[+,\varnothing],\mathbb{\cap }, [\blacktriangledown ,\{\varnothing\}],[\mathbb{\blacktriangle },\{M \times M\}], \vartriangleleft, \vartriangleright, \blacktriangleleft, \blacktriangleright, \subset \bigg].\]

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.