Latest Tweets

Binary operation and groupoid

We know various mathematical operations (addition, multiplication…), including set operations (union, intersection…). Furthermore, those operations are defined on some set. In other words, we combine some values from the set to create a new value. We can ask ourselves is that obtained value also an element of the original set. For that purpose, we will define binary operations.

What is a groupoid?

Definition:  Let S be a non – empty set. A mapping

$$\theta: S \times S \rightarrow S$$

is called a binary operation on set S. A binary operation $\theta$ to every ordered pair $(x, y) \in S \times S$ joins an elements $z = \theta(x, y) \in S$. Ordered pair $(S, \theta)$ is called a groupoid.

 

Examples of groupoids

Example 1:  Addition and multiplication on sets $\mathbf{N}, \mathbf{Z}, \mathbf{Q}, \mathbf{R}, \mathbf{C}$ are examples of binary operations.

In other words, $(\mathbf{N}, +), (\mathbf{Z}, +), (\mathbf{Q}, +), (\mathbf{R}, +), (\mathbf{C}, +)$ are groupoids. Furthermore, $(\mathbf{N}, \cdot), (\mathbf{Z}, \cdot), (\mathbf{Q}, \cdot), (\mathbf{R}, \cdot), (\mathbf{C}, \cdot)$ are also groupoids.

Example 2:  Is a subtraction a binary operation on sets $\mathbf{N}$ and $\mathbf{Z}$? Explain or give a counterexample.

Solution:

Subtraction is not a binary operation on set $\mathbf{N}$ because, for example, $5 – 6 = -1 \notin \mathbf{N}$.

But, it is a binary operation on $\mathbf{Z}$ since the difference of every two elements from $\mathbf{Z}$ is again an element of $\mathbf{Z}$.

Example 3:  The cross product (or vector product) $\times$ is a binary operation in three – dimensional space $V^{3}$ because the result is a vector from the same space.

Example 4:  Intersection, union, difference and symmetric difference are binary operations on the power set of S, $\mathcal{P}(S)$.

Example 5:  On a set of all functions $f: S \rightarrow S$ a binary operation is a composition of functions $\circ$.

 

Properties of a binary operations

Definition:  Let $(S, \cdot )$ be a groupoid. A binary operation is commutative if

$$xy = yx, \ x, y \in S$$

is valid. We say that $(S, \cdot)$ is a commutative groupoid.

Example 6: Find some examples of commutative binary operations and some which aren’t commutative.

Solution:

Standard addition and multiplication are commutative operations, while the vector product isn’t. Precisely, vector product is anticommutative, i.e. $a \times b = -b \times a$.

Definition:  Let $(S, \cdot)$ be a groupoid. A binary operation is associative if

$$x(yz) = (xy)z, \  x, y, z \in S$$

is valid. A groupoid with an associative binary operation is called semigroup. Moreover, if a binary operation is commutative also, a groupoid is called a commutative semigroup.

 

Example 7:  Sets $\mathbf{N}, \mathbf{Z}, \mathbf{Q}, \mathbf{R}, \mathbf{C}$ with addition and multiplication  are commutative semigroups.

Example 8:  Is a subtraction associative operation on $\mathbf{Z}$?

Solution:  No. For instance, $7 – (8 – 4) = 7 – 4 = 3$ but $(7 – 8) – 4 = – 1 – 4 = – 5$.

Example 9:  Is a set $(\{f: S \rightarrow S\}, \circ)$ a commutative semigroup?

Solution:  We mentioned that the given set is a groupoid. Furthermore, a composition of functions is associative, but not commutative. In other words, $(\{f: S \rightarrow S\}, \circ)$ is a semigroup, but not commutative.

 

Neutral element of binary operation

Definition:  Let $(S, \cdot)$ be a groupoid. We say that $e \in S$ is a neutral element of binary operation if

$$ex = xe = x$$

is valid for every $x \in S$. Moreover, if a binary operation is associative and has a neutral element, a structure $(S, \cdot)$ is called a monoid. If an operation is commutative also, it is called a commutative monoid.

Note: If there exists a neutral element in a groupoid, it is unique.

Example 10:  Sets $\mathbf{Z}, \mathbf{Q}, \mathbf{R}, \mathbf{C}$ with addition and multiplication are commutative monoids. In addition, the neutral element for multiplication is $1$. Furthermore, neutral element for addition is $0$.

Example 11:  Find more examples of commutative monoids. Also, find neutral elements for the corresponding binary operations.

Solution:  For instance, $(\mathcal{P}(S), \cap)$ and $(\mathcal{P}(S), \cup)$ are commutative monoids. Furthermore, neutral elements are $S$ and $\emptyset$, respectively.