# Discrete Mathematics Lecture 5 — Binary Operations

University course in discrete mathematics for computer science and engineering

Sep 20, 2021
All Files ‐ Post Files

# 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

1. $$(A, +)$$ is a commutative group
2. $$\times$$ is associative
3. 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.

1. Both $$+$$ and $$\times$$ is commutative.
2. $$(A, +)$$ is a group.
3. $$\times$$ is associative, has an identity and every element besides the additive identity has an inverse.
4. 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}$

$\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.

1. 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}$

1. It is associative.
2. 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}$

1. $$\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

1. A relationship $$\mathrel{R}$$ on a set $$A$$ is said to be reflexive if $$\forall a \in A : a R a$$.
2. 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$$.
3. $$\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$$.

4. $$\mathrel{R}$$ is said to be transitive if $$(a\mathrel{R}b)\land(b\mathrel{R}c)\Rightarrow a\mathrel{R}c$$.

5. A relation which is reflexive, symmetric and transitive is said to be a equivalence relation.
6. A relation which is reflexive, antisymmetric and transitive is said to be partial order.