Algebra Reference¶

absolute

Applied to couplets, sets, constructs derived from them (like relations) and algebras. Such a construct is called absolute if its ground set is based on set A (\(A\)).

See for example absolute set.

A relation that has only members that are elements of the Cartesian product \(A \times A\) is an ‘absolute relation’. Example: \(\{a{\mapsto}1, b{\mapsto}2\}\). (However, an absolute relation is not an absolute set; the members of the relation are couplets, not atoms.)
The relation \(\{a{\mapsto}1, b{\mapsto}\{2\}\}\) is not an absolute relation, as one of the right elements of the member couplets is not an atom (it is a set \(\{2\}\)).

absolute clan

An absolute clan is a clan that is an element of the second power set of the Cartesian product of set A (\(A\)) (\(P^2(A \times A)\)). Such a clan has only atoms as members of the couplets in the relations. Example: \(\{ \{2{\mapsto}1, 3{\mapsto}2\}, \{5{\mapsto}4, 9{\mapsto}7\} \}\).

absolute couplet

An absolute couplet is a couplet that is an element of the Cartesian product of set A (\(A\)) (\(A \times A\)). Such a couplet has only atoms as members. Example: \(2{\mapsto}1\).

absolute ground set

Our algebras normally have a ground set and an absolute ground set. The absolute ground set is the ground set with the elements of the algebra being expressed in terms of set A (\(A\)).

For example, the ground set of the algebra of relations is \(P(M \times M)\); this allows sets and couplets as elements of the couplets that form the relations. The absolute ground set of the algebra of relations is \(P(A \times A)\); this requires atoms to form the couplets that form the relations.

absolute relation

An absolute relation is a set that is an element of the power set of the Cartesian product of set A (\(A\)) (\(P(A \times A)\). Such a set has only couplets as elements that consist only of atoms. Example: \(\{2{\mapsto}1, 5{\mapsto}2\}\).

absolute set

An absolute set is a set that is an element of the power set of set A (\(A\)) (\(P(A)\). Sukch a set has only atoms as elements. Example: \(\{1, 2\}\).

addition

An operation defined only on multisets. Given multisets \(\dot{A}\) and \(\dot{B}\) we define \(\dot{A}+\dot{B}\) as follows:

\[\big(\dot{A} + \dot{B}\big)(x) = \dot{A}(x) + \dot{B}(x)\]

for any \(x\in M\).

algebra

An algebra is a set together with one or more operations defined on it. For a more detailed definition see Algebras.

algebra of clans

The algebra of clans is the algebra on sets of relations. As a result its ground set is the second power set of couplets, which allows us to use more operations in addition to those on an algebra of sets. See Algebra of Clans for a more detailed explanation.

algebra of couplets

Given a collection of couplets define an algebra on it by including the operations of composition and transposition. See Algebra of Couplets for a more detailed definition.

algebra of multiclans

An algebra defined on multisets of relations. This algebra is similar to the algebra of clans, but takes into account multiplicities of relations. See Algebra of Multiclans for more information.

algebra of multisets

An algebra on the set of all multisets of set M (\(M\)) with the operations of multiset union, intersections, addition, difference, and subset. See Multiset Algebra for more detailed information.

algebra of relations

The algebra of relations is an algebra on a set of couplets under the operations of composition and transposition. See Algebra of Relations for a more detailed definition.

algebra of sets

Also called set algebra, is the algebra formed by taking the power set of a set and applying the operations of union and intersection. See Algebra of Sets for a more detailed definition.

arbitrary intersection

An arbitrary intersection is the intersection of two or more sets. See intersection for a complete definition.

atom

An atom is a datum that is not a set or a couplet. The set of all atoms is set A (\(A\)).

binary extension

A binary extension is an extension of a binary operation from a given algebra to a extension of the algebra.

\[binaryExtn(op, S1, S2) := \{op(s1, s2)\ :\ s1 \in S1 \text{ and } s2 \in S2 \text{ where } op(s1, s2) \text{ is defined}\}\]

binary intersection

A binary intersection is an intersection of two sets. See intersection for a complete definition.

binary multi-extension

A binary multi-extension is an extension of a binary operation on multisets. In particular, in addition to the requirements on a standard binary extension the multi-extension must extend the operation on multiplicities in a way that is well-defined.

binary operation

An operation with two arguments, typically with a result that belongs to the same ground set as the arguments (when the operation is a member of an algebra).

binary relation

We represent a binary relation as a set where every member is a couplet.

binary union

A binary union is a union of two sets. See union for more information.

Cartesian product

The Cartesian product of two sets \(A \times B\) is the set of all couplets where the first member of the couplet is a member of \(A\) and the second member of the couplet is a member of \(B\).

clan

A set of relations.

complement

The complement of a given set is the collection of elements not in the given set. This definition depends on a choice of a larger set in which context every other set is a subset of. In particular, given an algebra of sets whose ground set is the power set \(P(M)\) and \(A\in P(M)\), the the complement of \(A\), denoted \(A'\) is

\[\{x \in M: x \not\in A\}.\]

Using set difference, it is true that \(A'=M-A\).

composition

The composition of the couplets \(a{\mapsto}b\) and \(c{\mapsto}d\) is defined as

\[\begin{split}c{\mapsto}d \circ a{\mapsto}b := \begin{cases} a^d & \text{if } b = c \\ \text{undefined} & \text{if } b \ne c \end{cases}\end{split}\]

The operation may be extended to extended algebras using the binary extension and – if there is no danger of ambiguities – is then also called simply ‘composition’.

Specific extensions:

Algebra of relations: \(R_2 \circ R_1 := \{c_2 \circ c_1\ :\ c_1 \in R_1,\ c_2 \in R_2\}\)

(\(R_1\) and \(R_2\) are relations; \(c_1\) and \(c_2\) are couplets.)
Algebra of clans: \(C_2 \circ C_1 := \{R_2 \circ R_1\ :\ R_1 \in C_1,\ R_2 \in C_2\}\)

(\(C_1\) and \(C_2\) are clans; \(R_1\) and \(R_2\) are relations.)

For multiclans the operation is the same, but with the multiplicity of the resulting relations being the product of the multiplicities of the individual relations.

couplet

A couplet is an ordered pair, following the Kuratowski definition of an ordered pair defined as \(\{\{l\}, \{l, r\}\}\). It is the mathematical object used to represent a datum or data point. We denote it by \(l{\mapsto}r\), with \(l\) called the left component, and \(r\) the right component.

cross-intersection

The cross-intersection is a binary extension of intersection from an algebra of sets to an algebra of sets of sets (for example, from the algebra of relations to the algebra of clans). The cross-intersection of the sets (of sets) \(\mathbb{S}\) and \(\mathbb{T}\) is defined as

\[\mathbb{S} \blacktriangle \mathbb{T} = \{X \cap Y\ : X \in \mathbb{S} \text{ and } Y \in \mathbb{T}\}\]

For multisets and multiclans the multiplicity of any set or relation in the result is the product of the multiplicities of the individual sets or relations.

cross-superstriction

The cross-superstriction is a binary extension of superstriction from an algebra of sets to an algebra of sets of sets (for example, from the algebra of relations to the algebra of clans). The cross-superstriction of the sets (of sets) \(\mathbb{S}\) and \(\mathbb{T}\) is defined as

\[\mathbb{S} \blacktriangleright \mathbb{T} = \{X \triangleright Y\ : X \in \mathbb{S} \text{ and } Y \in \mathbb{T}\}\]

cross-union

The cross-union is a binary extension of union from an algebra of sets to an algebra of sets of sets (for example, from the algebra of relations to the algebra of clans). The cross-union of the sets (of sets) \(\mathbb{S}\) and \(\mathbb{T}\) is defined as

\[\mathbb{S} \blacktriangledown \mathbb{T} = \{X \cup Y\ : X \in \mathbb{S} \text{ and } Y \in \mathbb{T}\}\]

For multisets and multiclans the multiplicity of any set or relation in the result is the product of the multiplicities of the individual sets or relations.

diagonal

The diagonal is an equality relation. The diagonal of a set \(S\) is defined as

\[D_S = \{x{\mapsto}x \in S \times S\ : x \in S\}\]

difference

The difference of two sets \(S\) and \(T\) is the set of elements in \(S\) but not in \(T\) (see also Wikipedia: Relative complement). The definition is

\[\begin{split}S \setminus T = \{x: x \in S\ \&\ x \notin T\}\end{split}\]

For multisets there is a separate multiset difference defined as follows: Given two multisets \(\dot{A}\) and \(\dot{B}\) we define

\[\big(\dot{A} \setminus \dot{B}\big)(x) = \max \big(\dot{A}(x) - \dot{B}(x), 0\big)\]

where \(x\) is any element of \(M\).

equivalence relation

A relation \(R\) is said to be an equivalence relation if it is reflexive, symmetric and transitive.

extension

An extension of a given set or algebra, is an extension of the set or algebra either by expanding the ground set, the set of operations on the set or both. For a more detailed definition, see Extension.

finite union

A finite union is the union of a finite collection of sets. See union for a more detailed explanation.

function

A function is a left-functional relation.

ground set

The set that contains all the elements of an algebra.

identity element

The element of the ground set of an algebra that, when used as one of the arguments of a binary operation produces the other argument of the operation as result of the operation.

intersection

An operation on sets that creates a set by collecting the elements in common to two or more individual sets into a new set. In mathematical terms, if \(\mathbb{S}\) is a collection of sets, then the intersection of all of the sets in \(\mathbb{S}\) is denoted

\[\bigcap \mathbb{S} = \bigcap_{T\in\mathbb{S}}T,\]

and is the set \(\{x\ : \forall T \in \mathbb{S},\ x \in T\}\). If \(\mathbb{S}\) consists of only two sets, the intersection is called a binary intersection. If \(\mathbb{S}\) consists of a finite collection of sets, the intersection is called a finite intersection. Otherwise, the intersection is referred to as an arbitrary intersection. See also Wikipedia: Intersection.

For multisets, say \(\dot{A}\) and \(\dot{B}\), we define the multiset intersection to be

\[\big(\dot{A}\cap\dot{B}\big)(x)=min\big(\dot{A}(x),\dot{B}(x)\big)\]

for \(x\in M\).

This term is used to name two related operations: the binary intersection of two sets, and the arbitrary intersection of one or more sets.

left component

Given a couplet represented by \(l{\mapsto}r\), the element \(l\) is called the left component.

left set

The left set of a relation \(R\) is the set of all left components of its members:

\[left(R) = \{ l\ : l{\mapsto}r \in R \}\]

The left set of a clan \(\mathbb{C}\) is the union of all left sets of its member relations:

\[left(\mathbb{C}) = \underset{R\ \in\ \mathbb{C}}{\bigcup} left(R)\]

left-functional

A relation \(R\) is said to be left-functional, or simply functional, if

\[\begin{split}x{\mapsto}y \in R\ \& \ x{\mapsto}z \in R \implies y = z\end{split}\]

left-functional cross-union

The left-functional cross-union of two clans \(\mathbb{C}\) and \(\mathbb{D}\) is a binary extension of the left-functional union from the algebra of relations to the algebra of clans:

\[\mathbb{C} \underset{f}{\blacktriangledown} \mathbb{D} = \{R \underset{f}{\cup} Q\ : R \in \mathbb{C} \text{ and } Q \in \mathbb{D}\}\]

left-functional union

The left-functional union of two relations \(R\) and \(Q\) is the union of the two relations if the result is left-functional, otherwise the result is not defined:

\[\begin{split}R \underset{f}{\cup} Q = \begin{cases} R \cup Q & \text{if }R \cup Q \text{ is left-functional} \\ \text{undefined} & \text{if it is not left-functional} \end{cases}\end{split}\]

left-regular

A clan \(\mathbb{C}\) is said to be left-regular if the left sets of all its relations are the same:

\[\forall R, Q \in \mathbb{C}: left(R) = left(Q)\]

lhs-functional cross-union

Given two clans the lhs-functional cross-union takes the left-functional cross-union, then any relations in the clan on the left side of the operation that resulted in the empty set are collected by taking their union and combined with the result of the left-functional cross-union. Mathematically, if \(\mathbb{C}\) and \(\mathbb{D}\) are the two clans in question, then their lhs-functional cross-union is

\[\begin{split}\mathbb{C} \underset{f}{\blacktriangledown} \mathbb{D} \bigcup\{T : T\in\mathbb{C}\ \& \ T \underset{f}{\blacktriangledown} \mathbb{D} = \varnothing \}\end{split}\]

multiclan

A multiclan is a multiset of relations.

multiplicity

Given an element of a multiset, the multiplicity of that element is the number of times the element appears in the multiset. See Multiset for more information.

multiset

A multiset, also sometimes called a bag, is a generalization of the idea of a set where multiple instances of the same element are allowed. See Multiset for more information.

partition

A partition of a set is the splitting of a set into a collection of smaller subsets. Mathematically, given a set \(S\), we create a set of subsets of \(S\) such that the union of those sets is \(S\), and whose pairwise intersection is the empty set (another term for this is that any two sets are disjoint).

power set

The power set of any set \(S\), written \(P(S)\), is the set of all subsets of \(S\), including the empty set and \(S\) itself. We also use the expressions ‘second power set’, ‘third power set’ and so on to mean successive application of the power set operation for the indicated number of times: ‘power set of the power set of the ... of \(S\). (Adapted from Wikipedia: Power set.)

project

Given a clan, call it \(C\), and a collection of elements, call it \(lefts\), the projection of \(C\) onto \(lefts\) is a new clan where all of the left components of all of the couplets of the relations of \(C\) are in the set \(lefts\).

To obtain the projection of \(C\) onto \(lefts\) mathematically we can do this as follows:

\[\begin{split}D_{lefts} := \{l{\mapsto}l\ : l\in lefts \} \\ project(C,lefts) = \{ R \circ D_{lefts}\ : R\in C\}\end{split}\]

reflexive

A relation \(R\) is said to be reflexive if

\[\forall x \in left(R) \cup right(R): x{\mapsto}x \in R\]

Algebra Reference¶

Previous topic

Next topic

This Page