# 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.