Introduction to abstract algebra

Operation notations

${\odot }_3$ is multiplication under modulo 3 $\oplus$ is addition under modulo 3 $⟨{\mathbb{Z}}_2\times {\mathbb{Z}}_2,{\oplus }_2\times {\oplus }_2⟩\simeq V_4$ (isomorphism of groups) ${\mathbb{Z}}_m$ for $⟨{\mathbb{Z}}_m,{\oplus }_m,{\ominus }_m,0⟩$ ${\mathbb{Z}}_m^{\ast }$ for $⟨\{x\in {\mathbb{Z}}_m|gcd(x,m)=1\},{\odot }_m,mod.Inv.,1⟩$

• ${\mathbb{Z}}_6=⟨\{1,5\},{\odot }_6,mod.Inv.,1⟩$

Uniqueness of the Neutral Element

If $e$ is left neutral element and $e^{\prime }$ is right neutral element, then $e=e^{\prime }$

Proof:

1. Since e′ is a right neutral element, e∗e′=e.
2. Since e is a left neutral element, e∗e′=e′.

Monoid

Definition

A monoid is an algebraic structure consisting of a set M, a binary operation ∗, and a neutral element e, satisfying the following properties:

1. Associativity: For all $x,y,z\in M$, $(x\ast y)\ast z=x\ast (y\ast z)$.
2. Neutral Element: There exists an element $e\in M$ such that for all $x\in M$, $e\ast x=x\ast e=x$.
3. Closed We denote a monoid as $⟨M;\ast ,e⟩$.

Example: Monoid of Bitstrings

Consider the set of all finite bitstrings, denoted by $\{0,1{\}}^{\ast }$, along with the concatenation operation $\Vert$, and the empty bitstring ϵ. This forms a monoid: $⟨0,1\ast ;\Vert ,ϵ⟩$

• Associativity: Concatenation is associative. For example, $(01\Vert 10)\Vert 01=0110\Vert 01=011001$ is the same as $01\Vert (10\Vert 01)=01\Vert 1001=011001$.
• Neutral Element: The empty bitstring ϵ acts as the neutral element for concatenation. For any bitstring $x\in \{0,1{\}}^{\ast }$, $ϵ\Vert x=x\Vert ϵ=x$.

Overview

Algebra Structure

+−⟲

Link to original

Inverse

The algebra we work on must have an neutral element at first

• Left Inverse: An element $b\in S$ is a left inverse of a if $b\ast a=e$, where $e$ is the neutral element.
• Right Inverse: An element $c\in S$ is a right inverse of a if $a\ast c=e$.

Lemma 5.2 If an element $a$ has both a left inverse $b$ and a right inverse $c$, and the operation $\ast$ is associative, then $b$ and $c$ must be the same.

Proof: $b=b\ast e$ (neutral element) $=b\ast (a\ast c)$ (c is the right inverse) $=(b\ast a)\ast c$ (associativity) $=e\ast c$ (b is the left inverse) $=c$ (neutral element)

Groups

Definition

A group is an algebra $⟨G;\ast ,\hat{},e⟩$, if $⟨G;\ast ,e⟩$ is a monoid and every $x\in G$ has an inverse $\hat{a}$

Other definitions

Definition: Group - normal definition

A group $⟨G,\ast ⟩$ is a set $G$, with a operation $\ast$, such that the following axioms are satisfied:

• The set is closed under $\ast$
• associativity of $\ast$
• identity element e for $\ast$
• Every element in $G$ is invertible

Link to original

Formalized

• associativity: $\forall x\forall y\forall z(x\ast y)\ast z=x\ast (y\ast z)$
• identity element: $\forall xx\ast e=e\ast x=x$
  • $\forall xx\ast e=x$ (simplified)
• inverse: $\forall xx\ast \hat{x}=\hat{x}\ast x=e$
  • $\forall xx\ast \hat{x}=e$ (simplified)

Proof: prove that the simplified version is still sufficient $\hat{x}\ast x=(\hat{x}\ast x)\ast e=(\hat{x}\ast x)\ast (\hat{x}\ast \hat{\hat{x}})=\hat{x}\ast ((x\ast \hat{x})\ast \hat{\hat{x}})=\hat{x}\ast (e\ast \hat{\hat{x}})$ $=(\hat{x}\ast e)\ast \hat{\hat{x}}=\hat{x}\ast \hat{\hat{x}}=e$

Examples

$⟨{\mathbb{Z}}_3;{\oplus }_3,{\ominus }_3,0⟩$ $⟨\mathbb{Z};+,-,0⟩$ $⟨{\mathbb{Z}}_m\setminus \{0\},{\odot }_m,\text{ mod Inv. },1⟩$ when $m$ is prime (see Number Theory > Multiplicative Inverses)

Transclude of number-theory#multiplicative-inversesexample

Lemma 5.3

An Important example: Permutation Groups

$S_n$: the set of $n!$ permutations of $n$ elements OR the set of bijections $\{1\dots n\}\to \{1\dots n\}$

Applications

• RSA Public Key Encryption