Skip to content

Latest commit

 

History

History
678 lines (530 loc) · 26.7 KB

AbstractAlgebra.MD

File metadata and controls

678 lines (530 loc) · 26.7 KB

Abstract Algebra

Summary of structures with one operation

Summary of structures in abstract algebra consisting of:

  • a Set S
  • binary operation * that are total (so they form a Magma).
Algebraic structure associativity identity invertibility commutativity idempotency
Semigroup associativity
Commutative semigroup associativity commutativity
Inverse semigroup associativity invertibility
Monoid associativity identity
Commutative Monoid associativity identity commutativity
Group associativity identity invertibility
Abelian Group associativity identity invertibility commutativity
Band associativity idempotency
Semilattice associativity commutativity idempotency
Bounded semilattice associativity identity commutativity idempotency

Properties of operation

property definition
closure (totality) x * y belongs to S
associativity x * (y * z) = (x * y) * z
identity x * id = id * x = x
invertibility x * x' = x' * x = id
commutativity x * y = y * x
idempotency x * x = x

Magma

Semigroup

Abstract over associative operation combine on some proper type A.

trait Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
}
  • Semigroup Law - associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))

  • Derived methods:

def combineN(a: A, n: Int): A // multiply1
def combineAllOption(as: TraversableOnce[A]): Option[A]

Commutative Semigroup

Semigroup where operation is commutative

trait CommutativeSemigroup[A] extends Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
}
  • laws:
    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. commutativity: (x |+| y) == (y |+| x)

Monoid

Abstract over associative operation combine that have default value empty.

trait Monoid[A] extends Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
}
  • Monoid Laws

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. right identity: (x |+| empty) == x
    3. left identity: (empty |+| x) == x
  • Derived methods:

def combineAll(as: TraversableOnce[A]): A

Monoid homomorphisms

Function f between two monoids A, B that preserve the structure of monoid:

  1. f(A.empty) == B.empty
  2. f(A.combine(a1,a2)) == B.compine( f(a1), f(a2) )

For example size and Monoid - list with concatenation and integers with addition.

  • Resources:
    • Rúnar Óli Bjarnason - Composing Programs (video)
    • (Haskell) Monoids, theme and variations - Brent Yorgey (video) (paper)

Commutative Monoid

Monoid where operation is commutative

trait CommutativeMonoid[A] extends Monoid[A] with CommutativeSemigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. right identity: (x |+| empty) == x
    3. left identity: (empty |+| x) == x
    4. commutativity: (x |+| y) == (y |+| x)
  • Resources

RegularSemigroup

Semigroup where element with it's inverse don't produce neutral element but produce sth that behaves like one.

trait RegularSemigroup[A] extends Monoid[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
  def inverse(a: A): A
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. pseudoinverse 1: x |+| -x |+| x == x
    3. pseudoinverse 2: -x |+| x |+| -x == -x
  • there could be multiple inverse elements (in group there is only one inverse)

  • x |+| -x is idempotent, because (x |+| -x) |+| (x |+| -x) == (x |+| -x |+| x) |+| -x == x |+| -x

  • Resources:

    • Haskell Live-Coding, Session 4.1, Regular and Inverse Semigroups - Edward Kmett video

InverseSemigroup

Semigroup (or regular semigroup) in which every element has unique inverse. Other definition: Semigroup in which every element has at least one inverse and all indempotent elements commute.

trait InverseSemigroup[A] extends RegularSemigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
  def inverse(a: A): A
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. pseudoinverse 1: x |+| -x |+| x == x
    3. pseudoinverse 2: -x |+| x |+| -x == -x
    4. pseudoinverse is unique
  • Resources:

    • Haskell Live-Coding, Session 4.1, Regular and Inverse Semigroups - Edward Kmett video

Group

Monoid where each element has an inverse

trait Group[A] extends Monoid[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
  def empty: A // mempty
  def inverse(a: A): A
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. right identity: (x |+| empty) == x
    3. left identity: (empty |+| x) == x
    4. inverse: (x |+| -x) == (-x |+| x) == empty
  • derived methods:

def remove(a: A, b: A): A = combine(a, inverse(b))

Abelian Group (Commutative Group)

Group where operation |+| is commutative

trait CommutativeGroup[A] extends Group[A] with CommutativeMonoid[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
  def inverse(a: A): A
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. right identity: (x |+| empty) == x
    3. left identity: (empty |+| x) == x
    4. inverse: (x |+| -x) == (-x |+| x) == empty
    5. commutativity: (x |+| y) == (y |+| x)
  • Resources:

Band (Idempotent semigroup)

Semigroup whose operation is also idempotent

trait Band[A] extends Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. idempotent: (x |+| x) == x
  • Resources:

bands with additional structure:

type of band additional law
left zero band x + y == x
right zero band x + y == y
rectangular band x + y + x == x
normal band z + x + y + z == z + y + x + z
left-regular band x + y + x == x + y
right-regular band x + y + x == y + x
regular bands z + x + z + y + z == z + x + y + z

Semilattice

Semilattice is commutative semigroup whose operation is also idempotent.

trait Semilattice[A] extends Band[A] with CommutativeSemigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
}
  • laws:
    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. commutativity: (x |+| y) == (y |+| x)
    3. idempotent: (x |+| x) == x

MeetSemilattice and JoinSemilattice

Sometimes (in typelevel/algebra) there are two definitions of Semilattice:

A meet-semilattice (or lower semilattice) is a semilattice whose operation is called "meet", and which can be thought of as a greatest lower bound.

trait MeetSemilattice[A] {
 def meet(lhs: A, rhs: A): A
}

and a join-semilattice (or upper semilattice) is a semilattice whose operation is called "join", and which can be thought of as a least upper bound

trait JoinSemilattice[A] {
 def join(lhs: A, rhs: A): A
}

Bounded Semilattice

Semilattice that has identity or Commutative Monoid that idempotent.

trait BoundedSemilattice[A] extends Semilattice[A] with CommutativeMonoid[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
}
  • laws:
    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. right identity: (x |+| empty) == x
    3. left identity: (empty |+| x) == x
    4. commutativity: (x |+| y) == (y |+| x)
    5. idempotent: (x |+| x) == x

Bounded Join Semilattice, Bounded Meet Semilattice

Similar as with Semilattice definition we can define Bounded Join Semilattice and Bounded Meet Semilattice

trait BoundedJoinSemilattice[A] extends JoinSemilattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
}
trait BoundedMeetSemilattice[A] extends MeetSemilattice[A] {
  def meet(lhs: A, rhs: A): A
  def one: A
}

Algebraic structures with two operations

Lattice

Has two associativity, commutativity and idempotent operations: join and meet that obey absorption law:

trait Lattice[A] extends JoinSemilattice[A] with MeetSemilattice[A] {
  def join(lhs: A, rhs: A): A
  def meet(lhs: A, rhs: A): A
}
  • laws:

    1. associativity: (x join y) join z) == (x join (y join z))
    2. commutativity: (x join y) == (y join x)
    3. idempotent: (x join x) == x
    4. associativity: (x meet y) meet z) == (x meet (y meet z))
    5. commutativity: (x meet y) == (y meet x)
    6. idempotent: (x meet x) == x
    7. absorption: a meet (a join b) == a join (a meet b) == a
  • typelevel/algebra Lattice src laws

Distributive Lattice

Lattice that obey distributive law

trait DistributiveLattice[A] extends Lattice[A] {
  def join(lhs: A, rhs: A): A
  def meet(lhs: A, rhs: A): A
}
  • laws:

    1. associativity: (x join y) join z) == (x join (y join z))
    2. commutativity: (x join y) == (y join x)
    3. idempotent: (x join x) == x
    4. associativity: (x meet y) meet z) == (x meet (y meet z))
    5. commutativity: (x meet y) == (y meet x)
    6. idempotent: (x meet x) == x
    7. absorption: a meet (a join b) == a join (a meet b) == a
    8. distributive: a meet (b join c) == (a meet b) join (a meet c)
    9. distributive: a join (b meet c) == (a join b) meet (a join c)
  • typelevel/algebra Distributive Lattice

BoundedLattice

trait BoundedLattice[A] extends Lattice[A] with BoundedMeetSemilattice[A] with BoundedJoinSemilattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
}
  • laws:
    1. associativity: (x join y) join z) == (x join (y join z))
    2. commutativity: (x join y) == (y join x)
    3. idempotent: (x join x) == x
    4. associativity: (x meet y) meet z) == (x meet (y meet z))
    5. commutativity: (x meet y) == (y meet x)
    6. idempotent: (x meet x) == x
    7. absorption: a meet (a join b) == a join (a meet b) == a
    8. identity of zero: a join zero == a
    9. identity of one: a meet one == a

Bounded Distributive Lattice

trait BoundedDistributiveLattice[A] extends BoundedLattice[A] with DistributiveLattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
}
  • laws:

    1. associativity: (x join y) join z) == (x join (y join z))
    2. commutativity: (x join y) == (y join x)
    3. idempotent: (x join x) == x
    4. associativity: (x meet y) meet z) == (x meet (y meet z))
    5. commutativity: (x meet y) == (y meet x)
    6. idempotent: (x meet x) == x
    7. absorption: a meet (a join b) == a join (a meet b) == a
    8. distributive: a meet (b join c) == (a meet b) join (a meet c)
    9. distributive: a join (b meet c) == (a join b) meet (a join c)
    10. identity of zero: a join zero == a
    11. identity of one: a meet one == a
  • typelevel/algebra Bounded Distributive Lattice

Heyting algebras

Heyting algebra is bounded distributive lattices equipped with operation imp (written as ->) and complement operation (written as -a)

trait Heyting[A] extends BoundedDistributiveLattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
  def imp(a: A, b: A): A
  def complement(a: A): A // a imp 0
}
  • laws:

    1. associativity: (x join y) join z) == (x join (y join z))
    2. commutativity: (x join y) == (y join x)
    3. idempotent: (x join x) == x
    4. associativity: (x meet y) meet z) == (x meet (y meet z))
    5. commutativity: (x meet y) == (y meet x)
    6. idempotent: (x meet x) == x
    7. absorption: a meet (a join b) == a join (a meet b) == a
    8. distributive: a meet (b join c) == (a meet b) join (a meet c)
    9. distributive: a join (b meet c) == (a join b) meet (a join c)
    10. identity of zero: a join zero == a
    11. identity of one: a meet one == a
    12. complement law: a meet -a == 0
    13. implication laws: a -> a == 1 a ∧ (a -> b) == a meet b b ∧ (a -> b) == b a -> (b meet c) == (a -> b) meet (a -> c)
  • derived methods:

def or(a: A, b: A): A = join(a, b)
def and(a: A, b: A): A = meet(a, b)
def xor(a: A, b: A): A = or(and(a, complement(b)), and(complement(a), b))
def nand(a: A, b: A): A = complement(and(a, b))
def nor(a: A, b: A): A = complement(or(a, b))
def nxor(a: A, b: A): A = complement(xor(a, b))

Boolean algebras

Boolean algebra is Heyting algebras were law of the excluded middle is true

trait Bool[A] extends Heyting[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
  def imp(a: A, b: A): A
  def complement(a: A): A // a imp 0
}
  • derived methods:
def without(a: A, b: A): A = and(a, complement(b))
  • laws:

    1. associativity: (x join y) join z) == (x join (y join z))
    2. commutativity: (x join y) == (y join x)
    3. idempotent: (x join x) == x
    4. associativity: (x meet y) meet z) == (x meet (y meet z))
    5. commutativity: (x meet y) == (y meet x)
    6. idempotent: (x meet x) == x
    7. absorption: a meet (a join b) == a join (a meet b) == a
    8. distributive: a meet (b join c) == (a meet b) join (a meet c)
    9. distributive: a join (b meet c) == (a join b) meet (a join c)
    10. identity of zero: a join zero == a
    11. identity of one: a meet one == a
    12. complement law: a meet -a == 0
    13. implication laws:
    • a -> a == 1
    • a ∧ (a -> b) == a meet b
    • b ∧ (a -> b) == b
    • a -> (b meet c) == (a -> b) meet (a -> c)
    1. excluded middle law: (a join (a -> 0)) == 1
  • typelevel/algebra Bool

Rig

Ring without (n)egation

trait Ring[T] extends CommutativeGroup[T] {
  def zero: T // empty mempty 
  def plus(l: T, r: T): T // combine mappend <> |+|
  def negate(v: T): T // inverse
  def one: T
  def times(l: T, r: T): T
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. identity: (x |+| zero) == x == (zero |+| x)
    3. inverse: (x |+| -x) == (-x |+| x) == zero
    4. commutativity: (x |+| y) == (y |+| x)
    5. associativity: ((x * y) * z) == (x * (y * z))
    6. right identity: (x * one) == x
    7. left identity: (one * x) == x
    8. distributive: a * (b |+| c) == (a * b) |+| (a * c)
  • Resources

Rng (Semiring)

Ring without an identity

trait Rng[T] extends CommutativeGroup[T] {
  def zero: T // empty mempty 
  def plus(l: T, r: T): T // combine mappend <> |+|
  def negate(v: T): T // inverse
  def times(l: T, r: T): T
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. identity: (x |+| zero) == x == (zero |+| x)
    3. inverse: (x |+| -x) == (-x |+| x) == zero
    4. commutativity: (x |+| y) == (y |+| x)
    5. associativity: ((x * y) * z) == (x * (y * z))
    6. distributive: a * (b |+| c) == (a * b) |+| (a * c)
  • Resources

Semiring

Ring

Abelian group with a second binary operation that is associative, is distributive over the abelian group operation, and has an identity element.

trait Ring[T] extends CommutativeGroup[T] {
  def zero: T // empty mempty 
  def plus(l: T, r: T): T // combine mappend <> |+|
  def negate(v: T): T // inverse
  def one: T
  def times(l: T, r: T): T
}
  • laws:

    1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
    2. identity: (x |+| zero) == x == (zero |+| x)
    3. inverse: (x |+| -x) == (-x |+| x) == zero
    4. commutativity: (x |+| y) == (y |+| x)
    5. associativity: ((x * y) * z) == (x * (y * z))
    6. right identity: (x * one) == x
    7. left identity: (one * x) == x
    8. distributive: a * (b |+| c) == (a * b) |+| (a * c)
  • Resources

United monoid

"Consider two monoids (S, +, 0) and (S, ⋅, 1), which operate on the same set S, such that + is commutative and ⋅ distributes over +.

We call these monoids united if 0 = 1."

Field

Tropical semiring (Min-Plus algebra)

  • twitter/algebird src

Vector Space

  • Resources
    • twitter/algebird src
    • Life After Monoids - Tom Switzer talks about Group, Ring, Vector Space (video)

StarRig

Kleene algebra

  • Resources:
    • Erik Osheim - Regexes, Kleene Algebras, and Real Ultimate Power! (video)
    • (Haskell) A Very General Method of Computing Shortest Paths (article)

Advanced Algebra Resources