Math 360, Fall 2021, Assignment 4

Mathematicians are like Frenchmen: whatever you say to them they translate into their own language, and forthwith it is something entirely different.

- Goethe

Read:

1. Section 4.

Carefully define the following terms, then give one example and one non-example of each:

1. $(\mathrm{Fun}(S,S))$.
2. $f\circ g$ (the composition of the functions $f$ and $g$).
3. $\iota$ (the identity function from a set $S$ to itself).
4. $\mathbb{Z}_n$.
5. $+_n$ (addition modulo $n$).
6. $\cdot_n$ (multiplication modulo $n$).
7. Semigroup.
8. Monoid.
9. Inverse (of an element of a monoid).
10. Group.
11. Abelian (group).

Carefully state the following theorems (you do not need to prove them):

1. Theorem regarding associativity of composition.
2. Theorem asserting that $+_n$ is well-defined.

Solve the following problems:

1. Section 4, problems 1, 3, 5, 11, 12, 13, 14, 18, and 19.
2. Give an example of (a) a binary structure which is not a semigroup, (b) a semigroup which is not a monoid, (c) a monoid which is not a group, and (d) a group which is not abelian.
3. By making an operation table, determine which elements of the commutative monoid $(\mathbb{Z}_5,\cdot_5)$ have inverses. Then do the same for $(\mathbb{Z}_6,\cdot_6)$ and $(\mathbb{Z}_8,\cdot_8)$.
4. Based on the results of the previous problem, try to make a conjecture regarding which elements of $(\mathbb{Z}_n,\cdot_n)$ have inverses.
5. Carefully show that the operation $\cdot_n$ is well-defined (i.e. state and prove a theorem analogous to the theorem asserting that $+_n$ is well-defined).

--------------------End of assignment--------------------

Definitions:

1. $\mathrm{Fun}(S,S))$: Let $S$ be any set. Then $\mathrm{Fun}(S, S)$ is the set of all functions from S to itself. Non-example: $S = \{1,2,3,4\}, f(x) = x+2 \not\in \mathrm{Fun}(S,S)$.
2. $f\circ g$ (the composition of the functions $f$ and $g$): If $f, g \in \mathrm{Fun}(S,S), define $(f \circ g)$(x) = f(g(x))$.
3. $\iota$ (the identity function from a set $S$ to itself): $\iota (x) = x$.
4. $\mathbb{Z}_n$: the collection of equivalence classes of integers for modulo n.

1. $+_{n}$ (addition modulo $n$): $[a]_{\equiv n} +_{n} [b]_{\equiv n} = [a+b]_{\equiv n}$.
2. $\cdot_{n}$ (multiplication modulo $n$): $[a]_{\equiv n} \cdot_{n} [b]_{\equiv n} = [a \cdot b]_{\equiv n}$.
3. Semigroup: an associative binary structure.

1. Monoid: semigroup with identity.
2. Inverse (of an element of a monoid): operation between an element and it inverse gives identity as result.
3. Group: monoid with inverse.
4. Abelian (group): commutative group.

Theorems:

1. Composition of functions is always associative.
2. $+_n$ is well-defined: if $a=b mod(n)$ and $c = d mod(n)$, then $(a + c) = (b + d) mod(n)$.

Book Problems:

1. 1. No. 0 doesn't have inverse.
2. 3. No. Not associative; No identity.
3. 5. No. Not associative, no identity.
4. 11. Yes.
5. 12 No, null matrix has no inverse.
6. 13. Yes.
7. 14. Yes
8. 18. No. $\{(1,1), (1,1)\}$ has 0 determinant and has no inverse.
9. 19. a. $a + b + ab = (a \cdot (b+1) + b$, if $(a \cdot (b+1) + b = -1, a \cdot (b+1) = - b - 1 = -(b - 1), a = \frac{-(b+1)}{b+1} = -1$, but $a \neq -1$, same thing for b. It gives a binary structure.

Other Problem :

1. A binary structure which is not a semigroup: $(\mathbb Z, \triangle )$ , for $a, b \in \mathbb Z, a \triangle b = a + 2(b + 1)$;a semigroup which is not a monoid: $(S, \triangle), S = \{a,b\}$, for all $a, b \in S, a \triangle b = b$; a monoid which is not a group: $(Z_3, *)$, for $a, b \in Z_3, a * b = (a \cdot b) mod 3$; a group which is not abelian: $(S_5, *), S_5 = \{3*3 \text{ matrices whose determinant } \neq 0 \}$, $*$ is matrix multiplication.
2. Elements: $(\mathbb{Z}_5,\cdot_5): 1,2,3,4; (\mathbb{Z}_6,\cdot_6): 1,5; (\mathbb{Z}_8,\cdot_8): 1,3,5,7$.
3. for $n$, for all $a \in \mathbb Z$, if $a$ is not $1$ and $a$ divides $n$, $a$ and any $a * b \text{ for any } b \in \mathbb Z$ will not have inverse, because $k \cdot a, \forall k \in \mathbb Z$ will never be $n + 1 = 1 (modn)$.
4. For operation $ \cdot_n$, if $a = b mod(n), c = d mod (n)$ for $a, b, c, d \in \mathbb Z$, then $a = b + k_1 \cdot n, c = d + k_2 \cdot n$, for some $k_1, k_2 \in \mathbb Z$. $a \cdot c = (b + k_1 \cdot n) \cdot (d + k_2 \cdot n)$, $(b + k_1 \cdot n) \cdot (d + k_2 \cdot n) = b \cdot d + b \cdot k_2 \cdot n + d \cdot k_1 \cdot n + (k_1 \cdot n) \cdot (k_2 \cdot n)$ $= (b \cdot d + 0 \cdot n) + (0 +(b \cdot k_2 + d \cdot k_1 + k_1 \cdot k_2) \cdot n) = (b \cdot d) mod(n) + 0 mod(n)$. According to theorem of well_defined $+_n$, $(b \cdot d) mod(n) + 0 mod(n) = (bd)mod(n)$. $ a \cdot c = (bd)mod(n)$, $\cdot_n$ is well_defined.