##### LMl5u

# Discrete Mathematics Lecture 5 — Binary Operations

University course in discrete mathematics for computer science and engineering

# Reminder

A binary operation on \(A\) is a function

\[ A \times A \rightarrow A \]

\[ (a_1, a_2) \mapsto a_1 * a_2 \]

## Commutativity

\[ a_1 * a_2 = a_2 * a_1, \forall a_1, s_2 \in A \]

## Associativity

\[ (a_1 * a_2) * a_3 = a_1 * (a_2 * a_3), \forall a_1, a_2, a_3 \in A \]

## Identity

\[ a * e = e * a = a \]

## Inverse

\[ a * b = b * a = e \]

**Ex.1:** \(\mathbb{Z}_+ = \{1, 2, ...\}\)

\(+\) | \(\times\) | |
---|---|---|

Comm | true | true |

Assoc | true | true |

Ident | false | true (1) |

Inver | false | false (just \(1 \dot 1 = 1\)) |

**Ex.1+:** \(\mathbb{Z}\)

Then \(0\) is an additive identity and each integer \(a\) has an additive inverse, that is \(-a\).

\[ \Rightarrow (\mathbb{Z}, +) \]

is a commutative / abelian group. A group is per definition a set with a binary operation which is associative where there is an identity, and where each element in the set has an inverse.

\[ (\mathbb{Z}, +, \times) \]

is a so called commutative ring with unity. The important word here is word.

**Def:** \((A, +, \times)\) is said to be a ring if

- \((A, +)\) is a commutative group
- \(\times\) is associative
- The distributive law is present: \(a\times(b+c)=(a\times b)+(a \times c)\)

**Ex.1++:** \(\mathbb{Q}\)

Now every number besides \(0\) has a multiplicative inverse.

\[ (\mathbb{Q}, +, \times) \]

is a so called field.

This is the same as a ring besides that you have a multiplicative inverse.

**Def:** \((A, +, \times)\) is said to be a field if.

- Both \(+\) and \(\times\) is commutative.
- \((A, +)\) is a group.
- \(\times\) is associative, has an identity and every element besides the additive identity has an inverse.
- The distributative law is present, \(a\times(b+c)=(a \times b) + (a \times c)\).

**Ex2,3:** \(\mathbb{R}\) and \(\mathbb{C}\) are also fields. If \(\mathbb{C}\) is to have a multiplicative inverse, then

\[ \frac{1}{a+bi} \]

must be able to be written in the following form.

\[ a + bi \]

this can be done like

\[ \frac{a - bi}{(a + bi)(a-bi)} = \left(\frac{a}{a^2+b^2}\right) - \left(\frac{b}{a^2+b^2}\right)i \]

which works for all complex numbers where \(a^2+b^2 \neq 0\).

**Note:** \(-\) and \(\div\) are not associative.

\[ (a-b)-c \neq a - (b-c) \]

\[ (a/b)/c \neq a/(b/c) \]

**Note:** \(\mathbb{H}\) is Hamiltons Quaternions.

\[ \mathbb{H} = \left \{a + bi + cj + dk \mid i^2 = j^2 = k^2 = -1, ij = k, ki = j, jk = i \right \} \]

You can show that every $h besides \(h=0\) has a multiplicative inverse. It is not a field because it is not commutative. $ is called a division ring.

\[ \mathbb{C} \subseteq \mathbb{H} \]

# Non Commutative Binary Operations

## Function Composition

Let \(X\) be a set. Let \(A = \{f : X \rightarrow X \}\), that is to say \(A\) is the set of all functions from \(X\) to \(X\).

The binary operation is \(\circ\). \(A \times A \rightarrow A\). Which in our case is \((f, g) \mapsto f \circ g\) which is read as āf after gā.

As we already have seen, \(\circ\) is not a commuatative operation, besides if the set \(X = \emptyset\). Then there is just one function which does nothing, \(f\) and \(g\) would do the same thing. Also besides if \(X\) only has one element because then \(f\) and \(g\) would only be able to output the same value. But what if

\[ X = \{1, 2\} \]

\(1\) can go to \(1\) or \(2\). \(2\) can go to \(1\) or \(2\).

So the function we have are

\[ \begin{align} f_1(1) &= 1 \\ f_1(2) &= 2 \\ \hline f_2(1) &= 1 \\ f_2(2) &= 1 \\ \hline f_3(1) &= 2 \\ f_3(2) &= 1 \\ \hline f_4(1) &= 2 \\ f_4(2) &= 2 \\ \end{align} \]

In this case it is commutative.

Basically while \(|X| \leq 2\), \(\circ\) is commutative.

**Associativity:** Yes, regardless of \(X\). \((f \circ g)\circ h = f \circ (g\circ h)\). This is just fundamentally how this operation works, on the right hand side of the equation you would first do \(h\) then you would do \(g\) and lastly you would do \(f\). The same principle applies for the left hand side of the equation.

**Identity:** Yes, \(\text{id}_x\) is always an identity. \(\text{id}_x(x) = x \forall x \in X\).

\[ f \circ \text{id}_x = \text{id}_x \circ f = f \]

**Inverse:** If \(f : X \rightarrow X\) is injective, then it has a inverse with the domain \(f(X)\). If \(f\) is also surjective, then \(f(X) = X\), so \(f^{-1} : X \rightarrow X\).

\(\Rightarrow\) All bijections from \(X\) to \(X\) have inverses.

**Def:** A bijection from a set \(X\) to itself is called a permutation of \(X\).

**Notation:** \(S_X\) is the set of all permutation of the set \(X\). That is to say that \(S_X\) is a set of function from itself to itself.

\(\Rightarrow\) \((S_X, \circ)\) is a group, and it is also non-commutative as soon as \(|X| \geq 3\).

\(S_X\) is called the symmetric group on \(X\).

Why permutations are also called symmetric is shown below.

\[ |X| = 3 \]

\[ S_n = \text{the set of permutations on } \left\{1, 2, ..., n \right\} \]

\[ |S_n|=n! \]

So if we have

\[ 1, 2, 3 \]

\[ |S_3| = 6 \]

\[ \begin{align} &1, 2, 3 = \text{id}_x \\ &2, 1, 3 \\ &3, 2, 1 \\ &1, 3, 2 \\ &3, 1, 2 \\ &2, 3, 1 \\ \end{align} \]

You can geometrically view what you are doing in the permutations.

(img)

## Matrix Multiplication (linear algebra)

\[ \mathbb{M}_2(\mathbb{R}) = \text{The set of all } 2 \times 2 \text{ matrices with real coefficients} \]

**Addition:**

\[ \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} + \begin{pmatrix} e & f \\ g & h \\ \end{pmatrix} = \begin{pmatrix} a+e & b+f \\ c+g & d+h \\ \end{pmatrix} \]

\((\mathbb{M}_2(\mathbb{R}), +)\) is a abelian group.

**Mulitplication:**

\[ \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \times \begin{pmatrix} e & f \\ g & h \\ \end{pmatrix} = \begin{pmatrix} ae + bg & af + bh \\ ce + dg & cf + dh \\ \end{pmatrix} \]

We note the following.

- It is not commutative.

You can have luck, but in most cases it is not commutative. See below

\[ \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} \begin{pmatrix} 5 & 6 \\ 7 & 8 \\ \end{pmatrix} = \begin{pmatrix} 19 & 22 \\ 43 & 50 \\ \end{pmatrix} \neq \begin{pmatrix} 5 & 6 \\ 7 & 8 \\ \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} = \begin{pmatrix} 23 & 34 \\ 31 & 46 \\ \end{pmatrix} \]

- It is associative.
- There is an identity.

\[ \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \]

Usage seen below.

\[ \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix} \]

- \(\begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}\) has a inverse if and only if \(ad - bc \neq 0\).

\[ \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d & -b \\ -c & c \\ \end{pmatrix} \]

# Relations

**Def:** Let \(A\) be a set, A relation on the set \(A\) is nothing more than a subset to \(A \times A\).

**Notation/Terminology:** Relation is written (default) \(\mathrel{R}\).

\[ \mathrel{R} \subseteq A \times A \]

if \((a_1, a_2) \in \mathrel{R}\), then you usually write \(a_1 \mathrel{R} a_2\). How you would read this is ā\(a_1\) is related to \(a_2\)ā.

**Ex:** \(A = \{1, 2, 3, 4\}\)

\[ \mathrel{R} = \{(1, 2), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)\} \]

We think. \(a_1\mathrel{R}a_2 \Leftrightarrow a_1 \mid a_2\). Which basically means that the relationship is that \(a_1\) can divide \(a_2\).

# 6 Terms

- A relationship \(\mathrel{R}\) on a set \(A\) is said to be
**reflexive**if \(\forall a \in A : a R a\). - A relationship \(\mathrel{R}\) is said to be
**symmetric**if \(\forall a_1, a_2 \in A : a_1 \mathrel{R} a_2 \Leftrightarrow a_2 \mathrel{R} a_1\). \(\mathrel{R}\) is said to be

**antisymmetric**if \((a_1 \mathrel{R} a_2) \land (a_2 \mathrel{R}a_1) \Rightarrow a_1 = a_2\).\(\mathrel{R}\) is said to be

**transitive**if \((a\mathrel{R}b)\land(b\mathrel{R}c)\Rightarrow a\mathrel{R}c\).- A relation which is reflexive, symmetric and transitive is said to be a
**equivalence relation**. A relation which is reflexive, antisymmetric and transitive is said to be

**partial order**.