Extension

Definition

Given a set, or algebra \(S\), we say that \(T\) is an extension of \(S\), or extends \(S\), if one or more of the following holds:

  • \(S \subseteq T\) and \(T\) has operations that \(S\) does not.
  • \(S \subset T\) and any operation \(op\) on \(S\) can be obtained from an operation \(OP\) on \(T\) by restricting \(OP\) to elements only in \(S\).

For the purposes of data algebra, we will deal almost exclusively with algebras of sets and their extensions. Mathematically an algebra can be extended in many different ways. Below are some general examples, as well as some specific to data algebra.

Examples of extensions

Basic examples

  • Any set \(S\) with no pre-defined operations on it extends to its set algebra: \(\bigg[P(S), \big \{ [ \cup, \varnothing ] , [ \cap, M ] \big\} , \big\{\ '\ \big\} , \big\{ \subset \big\} \bigg]\).
  • Let \(\mathbb{Z}\) represent the set of integers, and \(\mathbb{Q}\) represent the set of rational numbers. The set \(\mathbb{Z}\) has a natural algebra under addition, and multiplication, and negation with signature: \(\bigg[ \mathbb{Z}, \big \{[+,0],[\cdot ,1]\}, \big \{-\}, \bigg]\). This algebra naturally extends to an algebra on the rational numbers with signature: \(\bigg[ \mathbb{Q}, \big \{[+,0],[\cdot ,1]\}, \big \{-\}, \bigg]\).

Examples from data algebra

  • The algebra of couplets on a set \(M\) with signature \(\bigg[ M \times M , \big\{\ \circ\ \big\} , \big\{ \leftrightarrow \big\} \bigg]\) extends to the algebra of relations \(\bigg[P(M \times M),\big\{[ \circ, D_M ] \big\} , \big\{ \leftrightarrow \big\}\bigg]\), where \(\circ\) is composition, \(\leftrightarrow\) is transposition, and \(D_M\) is the diagonal of \(M\).

  • The power set of a power set has an algebra given by the algebra of sets. Hence, if \(U\) is a set, we have an algebra with signature \(\bigg[ P^{2}(U),[\cup ,\varnothing ],[\mathbb{\cap },P(U)],\subset ,\prime \bigg]\). This algebra extends to the algebra \(\bigg[ P^{2}(U),[\cup ,\varnothing ],[\mathbb{\cap },P(U)], [\blacktriangledown ,\{\varnothing\}],[\mathbb{\blacktriangle },\{U\}],\subset ,\prime \bigg]\), where \(\blacktriangledown\) is the cross-intersection and \(\blacktriangle\) is the cross-union, which are binary extensions of intersection and union resprectively from \(P(U)\) to \(P^{2}(U)\). This is how we extend the algebra of relations to the algebra of clans.

  • An algebra of sets can also be extended to an algebra of multisets. In particular we can simply take binary multi-extensions of all of the binary operations, and replace subset with submultiset. We can also include multiset addition, but we will have to take out complement, as there is not multiset equivalent of that. Therefore, the algebra

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

    extends to

    \[\bigg[\dot{P}(M), [\cup,\varnothing], [+,\varnothing],\cap,\subset \bigg].\]
  • Similar to the previous example an algebra of clans can extend to an algebra of multiclans, by taking binary multi-extensions of all the operations. Hence, an algebra of clans with 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]\]

    can be extended to an algebra of multiclans with signature

    \[\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].\]

An example of adding set operations to an algebra with no given set structure

  • Let us take the algebra of integers with signature \(\bigg[ \mathbb{Z}, \big \{[+,0],[\cdot ,1]\}, \big \{-\}, \bigg]\) as in an earlier example. Since \(\mathbb{Z}\) is a set, it also posesses the set algebra \(\bigg[P(\mathbb{Z}), \big \{ [ \cup, \varnothing ] , [ \cap, M ] \big\} , \big\{\ '\ \big\} , \big\{ \subset \big\} \bigg]\). We can extend \(\bigg[ \mathbb{Z}, \big \{[+,0],[\cdot ,1]\}, \big \{-\}, \bigg]\) to the set algebra by defining addition, multiplication, and negation on subsets of \(\mathbb{Z}\) as follows: Given subsets \(A,B\subset\mathbb{Z}\)

    \[\begin{split}\begin{align*} A + B &:= \{c \in \mathbb{Z} : c = a + b \text{ for some }a \in A \text{ and for some } b \in B\} \\ A \cdot B &:= \{c \in \mathbb{Z} : c = a \cdot b \text{ for some } a \in A \text{ and for some } b \in B\} \\ -A &:= \{c \in \mathbb{Z} : c = -a \text{ for some } a \in A\} \end{align*}\end{split}\]

    In words, the above equations say that over the integers:

    • The sum of sets is the set of sums.
    • The product of sets the set of products.
    • The negative of a set is the set of negatives.

    So for example if \(A=\{3,-5,9\}\) and \(B=\{4,12\}\), then

    \[\begin{split}\begin{eqnarray*} \{3,-5,9\}+\{4,12\} &=&\left\{ \begin{array}{c} 3+4,3+12, \\ -5+4,-5+12, \\ 9+4,9+12% \end{array}% \right\} \\ &=&\left\{ \begin{array}{c} 7,15, \\ -1,7, \\ 13,21% \end{array}% \right\} \\ &=&\{7,15,-1,13,21\}. \end{eqnarray*}\end{split}\]

    and,

    \[\begin{split}\begin{eqnarray*} \{3,-5,9\}\cdot \{4,12\} &=&\left\{ \begin{array}{c} 3\cdot 4,3\cdot 12, \\ -5\cdot 4,-5\cdot 12, \\ 9\cdot 4,9\cdot 12% \end{array}% \right\} \\ &=&\left\{ \begin{array}{c} 12,36, \\ -20,-60, \\ 36,108% \end{array}% \right\} \\ &=&\{12,36,-20,-60,36,108\}. \end{eqnarray*}\end{split}\]

    and

    \[-A=-\{3,-5,9\}=\{-3,5,-9\}\]

    In conclusion, this shows that the algebra \(\bigg[ \mathbb{Z}, \big \{[+,0],[\cdot ,1]\}, \big \{-\}, \bigg]\) extends to the algebra

    \[\begin{equation*} \bigg[ P(\mathbb{Z}),\{[\cup ,\varnothing ],[\mathbb{\cap },% \mathbb{Z}],[+,\{0\}],[\cdot ,\{1\}]\},\{-,^{\prime }\},\{\subset \}\bigg] , \end{equation*}\]