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)$