# ZK-Book - Chapter 5 - Abstract Algebra

Book Link - ZK Book

Chapter Link - Chapter-5: Abstract Algebra

This post hosts my notes for my studies using the ZK Book by Rareskills.

Why did I start with Chapter 5? Cuz I am an idiot who didn’t look at the Table of Contents. Thats why.

### TLDR

Type | Closed | Associative | Identity | Inverse |
---|---|---|---|---|

Magma | ✔️ | |||

Semigroup | ✔️ | ✔️ | ||

Monoid | ✔️ | ✔️ | ✔️ | |

Group | ✔️ | ✔️ | ✔️ | ✔️ |

**Set** - Well-defined collection of distinct elements $\mathbb{Z}$

**Binary Operator** - An operation that combines two elements from the set e.g addition

**Closed Set** - Set is closed under an operation if applying that operation to elements within the set always results in an element that’s still within the set

**Magma** - Set with closed binary operator

**Semigroup** - Magma but also associative

**Associative** - Grouping of operations doesn’t affect the result e.g $(a∗b)∗c=a∗(b∗c)$

**Exercise:** Work out for yourself that concatenating “foo”, “bar”, “baz” in that order is associative. Remember, associative means $(A \square B) \square C = A \square (B \square C)$, where $\square$ is the Semigroup’s binary operator.

$(foo + bar) + baz = foo + (bar + baz)$

$foobar + baz = foo + barbaz$

$foobarbaz = foobarbaz$

**Exercise:** Give an example of a Magma and a Semigroup. The Magma must not be a Semigroup. This means you must think of a binary operator that is closed but not associative for the Magma, and for the Semigroup, the binary operator must be closed and associative.

*Magma*:

- Set of strings
- Operation
`TrimStart`

such that any instance of the first string from the beginning of the second string is trimmed

e.g

```
a = "fun" , b = "function", c = "functions"
(a TrimStart b) TrimStart c != a TrimStart (b TrimStart c)
("fun" TrimStart "function") TrimStart "functions" != "fun" TrimStart ("function" TrimStart "functions")
"ction" TrimStart "functions" != "fun" TrimStart "s"
"functions" != "s"
```

*Semigroup*:

- All positive integers excluding zero
- Operation
`Addition mod 3`

e.g

```
a = 2, b = 8, c = 12
(a |+|3 b) |+|3 c = a |+|3 (b |+|3 c)
(2 |+|3 8) |+|3 12 = 2 |+|3 (8 |+|3 12)
1 |+|3 12 = 2 |+|3 2
1 = 1
```

**Monoid** - Semigroup with identity element

**Identity** - Binary operation with an element = element e.g addition of positive integers with 0

**Union** - $\set{1,2,3} \cup \set{2,3,4} = \set{1,2,3,4}$

where, identity element is empty set $\set{}$

**Intersection** - $\set{1,2,3} \cap \set{2,3,4} = \set{2,3}$

where, identity element is the domain of the set itself $\mathbb{Z}$

**Exercise:** Let our binary operator be the function `min(a,b)`

over integers. Is this a Magma, Semigroup, or Monoid? What if we restrict the domain to be positive integers (zero or greater)? What about the binary operator `max(a,b)`

over those two domains?

$min(a,b)$ over integers

- closed -> yes
- associative -> yes
- identity -> no

=> Semigroup

$min(a,b)$ over positive integers and 0

- closed -> yes
- associative -> yes
- identity -> no

=> Semigroup

$max(a,b)$ over integers

- closed -> yes
- associative -> yes
- identity -> no

=> Semigroup

$max(a,b)$ over positive integers and 0

- closed -> yes
- associative -> yes
- identity -> yes $0$

=> Monoid

**Exercise:** Let our set be all 3 bit binary numbers (a set of cardinality 8). Let our possible binary operators be bit-wise and, bit-wise or, bit-wise xor, bit-wise nor, bit-wise xnor, and bit-wise nand. Clearly this is closed because the output is a 3 bit binary number. For each binary operator, determine if the set under that binary operator is a Magma, Semigroup, or Monoid.

*Bitwise AND*

A | B | & |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

- closed -> yes
- associative -> yes
- identity -> yes $1$

=> Monoid

*Bitwise OR*

A | B | | |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

- closed -> yes
- associative -> yes
- identity -> yes $0$

=> Monoid

*Bitwise XOR*

A | B | ^ |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

- closed -> yes
- associative -> yes
- identity -> yes $0$

=> Monoid

*Bitwise NOR*

A | B | |~ |
---|---|---|

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

- closed -> yes
- associative -> no
`(1 |~ 1) |~ 0 != 1 |~ (1 |~ 0) 0 |~ 0 != 1 |~ 0 1 != 0`

=> Magma

*Bitwise XNOR*

A | B | |^ |
---|---|---|

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

- closed -> yes
- associative -> yes
- identity -> yes $1$

=> Monoid

*Bitwise NAND*

A | B | &~ |
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

- closed -> yes
- associative -> no
`(1 &~ 1) &~ 0 != 1 &~ (1 &~ 0) 0 &~ 0 != 1 &~ 1 1 != 0`

=> Magma

**Group** - Monoid where each element has an inverse

**Inverse** - For every element $a$ , there is $a’$ such that $a \square a’ = i$ identity

**Exercise:** Why can’t strings under concatenation be a group?

Set - Strings with empty string

Operation - Concatenation

Identity - Empty string

For a given non empty string, there cannot be any other string, concatenating with which will result in an empty string. Therefore, it cannot have an inverse and its not a group.

**Exercise:** Polynomials under addition satisfy the property of a group. Demonstrate this is the case by showing it matches all the properties that define a group.

**Abelien** - Oredering of operations doesnt affect the result e.g $(a∗b)=(b∗a)$