LMl5u

Discrete Mathematics Lecture 5 — Binary Operations

University course in discrete mathematics for computer science and engineering

Sep 20, 2021
Downloads ‐ HTML, Markdown, PDF
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} \]

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.

  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.

Reference