Spoorthi Satheesha

Sporadic writer
Serial anthropomorphizer

Share: 

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:

  1. Set of strings
  2. 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:

  1. All positive integers excluding zero
  2. 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

  1. closed -> yes
  2. associative -> yes
  3. identity -> no

=> Semigroup

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

  1. closed -> yes
  2. associative -> yes
  3. identity -> no

=> Semigroup

$max(a,b)$ over integers

  1. closed -> yes
  2. associative -> yes
  3. identity -> no

=> Semigroup

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

  1. closed -> yes
  2. associative -> yes
  3. 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
  1. closed -> yes
  2. associative -> yes
  3. identity -> yes $1$

=> Monoid

Bitwise OR

A B |
0 0 0
0 1 1
1 0 1
1 1 1
  1. closed -> yes
  2. associative -> yes
  3. identity -> yes $0$

=> Monoid

Bitwise XOR

A B ^
0 0 0
0 1 1
1 0 1
1 1 0
  1. closed -> yes
  2. associative -> yes
  3. identity -> yes $0$

=> Monoid

Bitwise NOR

A B |~
0 0 1
0 1 0
1 0 0
1 1 0
  1. closed -> yes
  2. 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
  1. closed -> yes
  2. associative -> yes
  3. identity -> yes $1$

=> Monoid

Bitwise NAND

A B &~
0 0 1
0 1 1
1 0 1
1 1 0
  1. closed -> yes
  2. 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)$

,