14 Algebraic Structures and Operations, Monoids, Inverses, Groups, Group Properties, Landscape of Groups

Lecture from: 04.11.2024 | Video: Videos ETHZ

Algebraic Structures and Operations

A generic algebraic structure is represented as $⟨S;\ast ⟩$, where $S$ is a set and $\ast$ is a binary operation defined on the elements of $S$. A binary operation takes two elements from the set $S$ and maps them to another element within the same set. A familiar example is $⟨\mathbb{Z};+⟩$, representing the integers under addition.

Abstract algebra deals with these generic structures and operations, allowing us to derive general properties that apply to various specific sets and operations. To work with these abstract structures, we define axioms, which are properties that the operations must satisfy.

Basic Structures and Properties

Example Structure and Commutativity

Let’s consider an example structure with the set $S=\{a,b,c\}$ and a binary operation $\ast$ defined by the following operation table:

Observing the table, we can identify some properties:

• Commutativity: The table is symmetric across the main diagonal. This means the operation $\ast$ is commutative, i.e., $x\ast y=y\ast x$ for all $x,y\in S$. For example, $a\ast b=b\ast a=c$.

• Neutral Element: The element $c$ acts as a neutral element (also known as an identity element). It satisfies both left and right neutrality:

  • Left Neutral: $c\ast x=x$ for all $x\in S$.
  • Right Neutral: $x\ast c=x$ for all $x\in S$.

Structures with Multiple Operations

Algebraic structures can have more than one operation and can include specific elements with unique roles, like neutral elements. For instance, $⟨\mathbb{Z};+;-;0⟩$ represents the integers with addition ($+$), unary negation ($-$), and the neutral element $0$ for addition.

Associativity

A crucial property for binary operations is associativity. An operation $\ast$ is associative if $(x\ast y)\ast z=x\ast (y\ast z)$ for all $x,y,z\in S$. Let’s examine if our example operation $\ast$ is associative:

In this case, $(b\ast b)\ast a=b\ast a=c$, whereas $b\ast (b\ast a)=b\ast c=b$. Therefore, the operation $\ast$ in our example is not associative.

Associativity is important for several reasons, including computational efficiency. For example, in the Diffie-Hellman key exchange discussed previously, associativity allows for efficient exponentiation using techniques like square-and-multiply.

Ensuring Unique Solutions through Latin Squares

Modifying the operation table can influence the properties of the algebraic structure. Changing the entry for $b\ast b$ from $c$ to $a$ results in a table where each row and each column contains each element of $S$ exactly once (a Latin square):

This modification has implications for solving equations within the structure. Having unique elements in each row and column ensures that equations of the form $u\ast x=v$ and $x\ast u=v$ will always have a unique solution for $x$ within the set $S$, as shown below:

A Second Example

Let’s analyze a different algebraic structure with the set $S=\{e,a,b,c\}$ and a binary operation $\ast$. The operation is defined by the following table:

This operation table exhibits several properties:

• Associativity: While visually verifying associativity from the table can be tedious, this specific operation is associative. A rigorous proof would require checking all possible combinations of $(x\ast y)\ast z$ and $x\ast (y\ast z)$ for $x,y,z\in S$. We’ll soon see a more efficient way to understand this associativity.
• Commutativity: The symmetry of the table indicates that the operation $\ast$ is commutative.
• Neutral Element: The element $e$ serves as the neutral element, as $e\ast x=x\ast e=x$ for all $x\in S$.
• Self-Inverse Elements: Every element is its own inverse, meaning $x\ast x=e$ for all $x\in S$.

(Note from future: This is ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$, see[[#example-the-direct-product-group—mathbbz_2-times-mathbbz_2|Example The Direct Product Group $mathbb{Z}_{2}timesmathbb{Z}_2$]])

Interpreting Operations

We can gain deeper insight into these algebraic structures by interpreting their operations in different contexts.

Interpreting the First Example (Addition Modulo 3 and Rotations)

The first example with $S=\{a,b,c\}$ and the operation table shown can be interpreted as addition modulo 3:

Here, $a$ corresponds to $1$, $b$ to $2$, and $c$ to $0$. The operation $\ast$ becomes ${+}_3$ (addition modulo 3). For example:

• $a\ast b=c$ corresponds to $1+2\equiv 0(\mathrm{mod}3)$
• $b\ast b=a$ corresponds to $2+2\equiv 1(\mathrm{mod}3)$

Alternatively, it can represent rotations by multiples of 120 degrees, with $a=120^{\circ }$, $b=240^{\circ }$, and $c=0^{\circ }$.

Interpreting the Second Example (Bitwise XOR)

For the second table with $S=\{e,a,b,c\}$, considering addition modulo 4 doesn’t work. This is because each element is its own inverse ($x\ast x=e$), whereas in addition modulo 4, $1+1\equiv 2(\mathrm{mod}4)$, and $2$ is not the neutral element.

Instead, this table represents the bitwise XOR (exclusive OR) operation on two-bit strings:

Here, $e$ corresponds to 00, $a$ to 01, $b$ to 10, and $c$ to 11. The operation $\ast$ is the bitwise XOR. For example:

• $a\ast b=c$ corresponds to 01 XOR 10 = 11
• $b\ast b=e$ corresponds to 10 XOR 10 = 00

This interpretation explains both the commutativity and associativity of the operation, as bitwise XOR has these properties. Additionally, it clarifies why each element is its own inverse under XOR.

Uniqueness of the Neutral Element

Within an algebraic structure $⟨S;\ast ⟩$, if a left neutral element ($e$) and a right neutral element ($e^{\prime }$) exist, they must be identical. This holds even without assuming associativity or commutativity of the operation $\ast$.

Proof:

1. Since $e^{\prime }$ is a right neutral element, $e\ast e^{\prime }=e$.
2. Since $e$ is a left neutral element, $e\ast e^{\prime }=e^{\prime }$.

Therefore, $e=e^{\prime }$, demonstrating that the neutral element, if it exists, is unique.

Monoids

A monoid is an algebraic structure consisting of a set $M$, a binary operation $\ast$, 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$.

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

Inverses in Algebraic Structures

Similar to neutral elements, we have the concept of inverse elements. For a given element $a$ in a set $S$ with a binary operation $\ast$, we define left and right inverses as follows:

• 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$.

Uniqueness of Inverse

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:

1. $b=b\ast e$ (Neutral element property)
2. $b=b\ast (a\ast c)$ (Substituting $e$ with $a\ast c$, since $c$ is the right inverse of $a$)
3. $b=(b\ast a)\ast c$ (Associativity of the operation $\ast$)
4. $b=e\ast c$ (Substituting $b\ast a$ with $e$, since $b$ is the left inverse of $a$)
5. $b=c$ (Neutral element property)

This proves that if both a left and right inverse exist for an element in an associative structure, they are identical.

Groups

A group is an algebraic structure $⟨G;\ast ,{}^{-1},e⟩$ consisting of a set $G$, a binary operation $\ast$, an inverse operation denoted by ${}^{-1}$ (or sometimes by ^), and a neutral element $e$, satisfying the following properties:

1. Associativity: For all $x,y,z\in G$, $(x\ast y)\ast z=x\ast (y\ast z)$.
2. Neutral Element: There exists an element $e\in G$ such that for all $x\in G$, $e\ast x=x\ast e=x$.
3. Inverse Element: For every element $x\in G$, there exists an element $x^{-1}\in G$ such that $x\ast x^{-1}=x^{-1}\ast x=e$.

It’s important to note that every element in a group must have an inverse. This distinguishes groups from structures like the integers under multiplication, where not every element (e.g., 2) has a multiplicative inverse within the integers.

Example: Rational Numbers

Consider the set of rational numbers excluding zero, denoted as $\mathbb{Q}\setminus \{0\}$. This set, along with the multiplication operation ($\cdot$) and the multiplicative inverse operation (${}^{-1}$), forms a group with the neutral element 1.

We can represent this group as $⟨\mathbb{Q}\setminus \{0\};\cdot {,}^{-1},1⟩$. Let’s verify the group properties:

1. Associativity: Multiplication of rational numbers is associative. For any $x,y,z\in \mathbb{Q}\setminus \{0\}$, we have $(x\cdot y)\cdot z=x\cdot (y\cdot z)$.
2. Neutral Element: The number 1 serves as the neutral element for multiplication, as $1\cdot x=x\cdot 1=x$ for all $x\in \mathbb{Q}\setminus \{0\}$.
3. Inverse Element: Every non-zero rational number $x$ has a multiplicative inverse $x^{-1}$ within $\mathbb{Q}\setminus \{0\}$. If $x=\frac{p}{q}$, where $p$ and $q$ are integers and $p,q\ne 0$, then $x^{-1}=\frac{q}{p}$. And we have $x\cdot x^{-1}=x^{-1}\cdot x=1$. Therefore, $⟨\mathbb{Q}\setminus \{0\};\cdot {,}^{-1},1⟩$ is a valid example of a group.

Example: Integers under Addition

The integers $\mathbb{Z}$ under addition form a group, represented as $⟨\mathbb{Z};+,-,0⟩$. Here, $+$ is the addition operation, $-$ is the additive inverse (negation) operation, and $0$ is the neutral element.

Example: Integers Modulo m

The set of integers modulo $m$, denoted as ${\mathbb{Z}}_m$, forms a group under addition modulo $m$. This group is represented as $⟨{\mathbb{Z}}_m;{+}_m,{-}_m,0⟩$. Where ${+}_m$ denotes addition modulo $m$, and ${-}_m$ denotes the additive inverse modulo $m$.

However, ${\mathbb{Z}}_m$ under multiplication modulo $m$ does not always form a group. This is because not every element in ${\mathbb{Z}}_m$ has a multiplicative inverse. For example, in ${\mathbb{Z}}_6$, the element 2 does not have a multiplicative inverse.

The Multiplicative Group of Integers Modulo m

While ${\mathbb{Z}}_m$ under multiplication is not always a group, we can construct a group by considering only the elements that have multiplicative inverses. These are the elements that are coprime to $m$. This set is denoted as ${\mathbb{Z}}_m^{\ast }$, where:

${\mathbb{Z}}_m^{\ast }=\{a\in {\mathbb{Z}}_m\mid \text{gcd}(a,m)=1\}$

The structure $⟨{\mathbb{Z}}_m^{\ast };{\cdot }_m{,}_m^{-1},1⟩$ forms a group called the multiplicative group of integers modulo m. Here, ${\cdot }_m$ is multiplication modulo $m$, and ${}_m^{-1}$ is the multiplicative inverse modulo $m$.

For example, ${\mathbb{Z}}_6^{\ast }=\{1,5\}$, and ${\mathbb{Z}}_7^{\ast }=\{1,2,3,4,5,6\}$, since 7 is prime. In ${\mathbb{Z}}_6^{\ast }$, $1$ and $5$ are their own inverses. In ${\mathbb{Z}}_7^{\ast }$, $2$ and $4$ are inverses of each other, and $3$ and $5$ are inverses of each other.

By restricting the set to elements coprime to $m$, we ensure the existence of multiplicative inverses for all elements in the set, fulfilling the requirements for a group.

Example: Integers Modulo a Prime p

For ${\mathbb{Z}}_m$ to form a group under multiplication modulo $m$, $m$ must be a prime number. When $m$ is a prime number, $p$, every non-zero element in ${\mathbb{Z}}_p$ has a multiplicative inverse. This group is denoted as $⟨{\mathbb{Z}}_p\setminus \{0\};{\cdot }_p{,}_p^{-1},1⟩$, where ${\cdot }_p$ is multiplication modulo $p$ and ${}_p^{-1}$ represents the multiplicative inverse modulo $p$.

The requirement for $m$ to be prime is crucial for the existence of multiplicative inverses for all non-zero elements, satisfying the group axioms.

Group Axioms: Defining Properties

Group axioms define the essential properties of a group, an algebraic structure denoted as $⟨G;\ast {,}^{-1},e⟩$. These axioms can be expressed using both typical algebraic notation and predicate logic (quantified form):

1. Associativity

• Typical notation: $(a\ast b)\ast c=a\ast (b\ast c)$ for all $a,b,c\in G$.
• Predicate logic: $\forall x\in G,\forall y\in G,\forall z\in G:(x\ast y)\ast z=x\ast (y\ast z)$

Associativity ensures that the order of operations does not affect the result when combining multiple elements.

2. Identity Element (Neutral Element)

• Typical notation: There exists $e\in G$ such that $a\ast e=e\ast a=a$ for all $a\in G$.
• Predicate logic: $\exists e\in G,\forall a\in G:a\ast e=e\ast a=a$

The identity element $e$ leaves any element unchanged when combined with it under the operation $\ast$.

3. Inverse Element

• Typical notation: For every $a\in G$, there exists $a^{-1}\in G$ such that $a\ast a^{-1}=a^{-1}\ast a=e$.
• Predicate logic: $\forall x\in G,\exists x^{-1}\in G:x\ast x^{-1}=x^{-1}\ast x=e$

Every element in a group has an inverse, which, when combined with the original element using the operation $\ast$, yields the identity element.

Note on Redundancy

In mathematics, it’s generally desirable for axiom sets to be minimal, meaning no axiom can be derived from the others. While the standard group axioms are commonly presented with some redundancy, it’s possible to simplify them.

One simplification involves the identity axiom (G2). Instead of requiring both $a\ast e=a$ and $e\ast a=a$, we can postulate only $a\ast e=a$ (call this G2’). The equation $e\ast a=a$ is then implied by the other axioms. Similarly, the inverse axiom (G3) can be simplified by requiring only $a\ast a^{-1}=e$ (call this G3’). The equation $a^{-1}\ast a=e$ can then be derived.

While the typical presentation of the identity axiom includes both $a\ast e=a$ and $e\ast a=a$, only one of these is strictly necessary. The other can be derived using the other axioms, specifically the existence of inverse elements and associativity. Thus stating both $a\ast e=a$ and $e\ast a=a$ within the group axioms is redundant, though often included for clarity.

Here’s the proof demonstrating that $a^{-1}\ast a=e$ given G1 (associativity), G2’ ($a\ast e=a$), and G3’ ($a\ast a^{-1}=e$):

1. $\hat{a}\ast a=(\hat{a}\ast a)\ast e$ (G2’)
2. $\hat{a}\ast a=(\hat{a}\ast a)\ast (\hat{a}\ast \hat{\hat{a}})$ (G3’, where $\hat{\hat{a}}$ is the inverse of $\hat{a}$)
3. $\hat{a}\ast a=\hat{a}\ast (a\ast (\hat{a}\ast \hat{\hat{a}}))$ (G1)
4. $\hat{a}\ast a=\hat{a}\ast ((a\ast \hat{a})\ast \hat{\hat{a}})$ (G1)
5. $\hat{a}\ast a=\hat{a}\ast (e\ast \hat{\hat{a}})$ (G3’)
6. $\hat{a}\ast a=(\hat{a}\ast e)\ast \hat{\hat{a}}$ (G1)
7. $\hat{a}\ast a=\hat{a}\ast \hat{\hat{a}}$ (G2’)
8. $\hat{a}\ast a=e$ (G3’, i.e., the definition of right inverse of $\hat{a}$)

Therefore, even with the simplified axioms G2’ and G3’, we can derive the full properties of the identity element and inverse elements, demonstrating that the standard presentation contains redundancy.

Abelian Groups

A group $⟨G;\ast ⟩$ (or monoid) is called commutative or abelian if $a\ast b=b\ast a$ for all $a,b\in G$. Abelian groups are named after the Norwegian mathematician Niels Henrik Abel.

Basic Group Properties

The following lemma summarizes some fundamental properties of groups. For a group $⟨G;\ast {,}^{-1},e⟩$, the following properties hold for all $a,b,c\in G$:

(i) Inverse of the Inverse: $(a^{-1}{)}^{-1}=a$

Proof: By definition, $a^{-1}\ast (a^{-1}{)}^{-1}=e$. Multiplying both sides on the left by $a$ yields:

$a\ast (a^{-1}\ast (a^{-1}{)}^{-1})=a\ast e$ $(a\ast a^{-1})\ast (a^{-1}{)}^{-1}=a$ (Associativity) $e\ast (a^{-1}{)}^{-1}=a$ $(a^{-1}{)}^{-1}=a$

(ii) Inverse of a Product: $(a\ast b{)}^{-1}=b^{-1}\ast a^{-1}$

Proof: By definition, $(a\ast b)\ast (a\ast b{)}^{-1}=e$. We want to show that $(a\ast b{)}^{-1}=b^{-1}\ast a^{-1}$. Let’s multiply $a\ast b$ by $b^{-1}\ast a^{-1}$:

$(a\ast b)\ast (b^{-1}\ast a^{-1})=a\ast (b\ast b^{-1})\ast a^{-1}$ (Associativity) $=a\ast e\ast a^{-1}=a\ast a^{-1}=e$

Since $(a\ast b)$ multiplied by $b^{-1}\ast a^{-1}$ gives the identity element, $b^{-1}\ast a^{-1}$ must be the inverse of $(a\ast b)$.

(iii) Left Cancellation Law: $a\ast b=a\ast c⟹b=c$

Proof: Multiply both sides of the equation $a\ast b=a\ast c$ on the left by $a^{-1}$:

$a^{-1}\ast (a\ast b)=a^{-1}\ast (a\ast c)$ $(a^{-1}\ast a)\ast b=(a^{-1}\ast a)\ast c$ (Associativity) $e\ast b=e\ast c$ $b=c$

(iv) Right Cancellation Law: $b\ast a=c\ast a⟹b=c$

Proof: Multiply both sides of the equation $b\ast a=c\ast a$ on the right by $a^{-1}$:

$(b\ast a)\ast a^{-1}=(c\ast a)\ast a^{-1}$ $b\ast (a\ast a^{-1})=c\ast (a\ast a^{-1})$ (Associativity) $b\ast e=c\ast e$ $b=c$

(v) Unique Solutions to Equations

Proof: The equation $a\ast x=b$ has the unique solution $x=a^{-1}\ast b$.
Multiplying both sides of $a\ast x=b$ on the left by $a^{-1}$ gives $(a^{-1}\ast a)\ast x=a^{-1}\ast b$ which simplifies to $x=a^{-1}\ast b$.

Similarly, the equation $x\ast a=b$ has the unique solution $x=b\ast a^{-1}$. Multiplying both sides of $x\ast a=b$ on the right by $a^{-1}$ gives $x\ast (a\ast a^{-1})=b\ast a^{-1}$ which simplifies to $x=b\ast a^{-1}$.

Example: $n\times n$ invertible matrices.

The set of invertible $n\times n$ matrices over the real numbers, together with matrix multiplication, forms a group. This group is known as the general linear group, denoted by GL($n$, $\mathbb{R}$). The identity matrix $I_n$ serves as the neutral element.

Let’s verify the group properties:

1. Set: The set consists of all $n\times n$ invertible matrices with real number entries.
2. Operation: The operation is standard matrix multiplication.
3. Associativity: Matrix multiplication is associative: $(A\cdot B)\cdot C=A\cdot (B\cdot C)$ for all $A,B,C\in \text{GL}(n,\mathbb{R})$.
4. Neutral Element: The $n\times n$ identity matrix $I_n$ is the neutral element, as $A\cdot I_n=I_n\cdot A=A$ for any $A\in \text{GL}(n,\mathbb{R})$.
5. Inverse Element: By definition, every matrix in GL($n$, $\mathbb{R}$) is invertible. This means for every $A\in \text{GL}(n,\mathbb{R})$, there exists a matrix $A^{-1}$ such that $A\cdot A^{-1}=A^{-1}\cdot A=I_n$.

Therefore, GL($n$, $\mathbb{R}$) satisfies all the group axioms.

Non-Commutativity:

It’s important to note that GL($n$, $\mathbb{R}$) is not commutative (abelian) for $n\ge 2$. In other words, matrix multiplication is not commutative in general. There exist matrices $A$ and $B$ such that $A\cdot B\ne B\cdot A$. This can be easily demonstrated with a counterexample for $2\times 2$ matrices.

Exploring the Landscape of Groups

Having established the definition of a group, we now turn our attention to exploring the variety of possible group structures. We’ll start by examining groups with a small number of elements and gradually consider larger groups.

Example: The Group of Integers Modulo 2 under Addition (${\mathbb{Z}}_2$)

The set ${\mathbb{Z}}_2=\{0,1\}$ under addition modulo 2 (${+}_2$, often represented simply as $+$) forms a group. This group can also be interpreted as the bitwise XOR operation.

• $⟨{\mathbb{Z}}_2;{+}_2⟩$ or equivalently $⟨\{0,1\};\text{XOR}⟩$

Let’s verify the group axioms:

1. Set: ${\mathbb{Z}}_2=\{0,1\}$
2. Operation: Addition modulo 2, defined as:
   • $0+0=0$
   • $0+1=1$
   • $1+0=1$
   • $1+1=0$
3. Associativity: Addition modulo 2 is associative.
4. Neutral Element: $0$ is the neutral element.
5. Inverse Element: Each element is its own inverse:
   • $0+0=0$
   • $1+1=0$

Example: The Group of Integers Modulo 3 under Addition (${\mathbb{Z}}_3$)

The set ${\mathbb{Z}}_3=\{0,1,2\}$ under addition modulo 3 (${+}_3$) forms a group: $⟨{\mathbb{Z}}_3;{+}_3⟩$ (our first example).

Here’s the operation table for ${\mathbb{Z}}_3$:

Let’s verify the group axioms:

1. Set: ${\mathbb{Z}}_3=\{0,1,2\}$
2. Operation: Addition modulo 3, as defined in the table above.
3. Associativity: Addition modulo 3 is associative.
4. Neutral Element: $0$ is the neutral element.
5. Inverse Element:
   • The inverse of $0$ is $0$.
   • The inverse of $1$ is $2$.
   • The inverse of $2$ is $1$.

Example: The Direct Product Group ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$

The direct product of two groups, $G$ and $H$, denoted as $G\times H$, is a new group formed by taking the Cartesian product of the sets of $G$ and $H$, and defining the operation component-wise.

Consider the direct product ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$. This group is not the same as ${\mathbb{Z}}_4$.

Example: The Symmetric Group $S_3$

The symmetric group $S_3$ provides a concrete illustration of permutations and their group structure. $S_3$ represents the set of all bijections (one-to-one and onto mappings) from a set of three elements to itself. Let’s visualize this using three points labeled 1, 2, and 3 representing arrows.

$S_3$ consists of all possible ways to rearrange (or map) these three points. Since each point can be mapped to any of the three positions, and once a point is placed, the remaining points have fewer options, we have $3!=3\times 2\times 1=6$ possible rearrangements. These rearrangements are the bijections we’re interested in.

We can describe these bijections through different operations:

1. Rotations: Rotating the points clockwise. For example, a 120-degree rotation maps 1 to 2, 2 to 3, and 3 to 1. A 240-degree rotation is also a distinct bijection.
2. Switches (Transpositions): Swapping two points while leaving the third fixed. Swapping 1 and 2 maps 1 to 2, 2 to 1, and 3 to 3. Similarly, swapping 1 and 3, or 2 and 3, are other bijections.

$S_3$ contains the following six elements (bijections/permutations):

• Identity: The mapping where each element maps to itself (no change).
• Two Rotations: 120° and 240° clockwise rotations.
• Three Switches (Transpositions): Swapping 1 and 2, swapping 1 and 3, and swapping 2 and 3.

Each of these operations represents a different way to bijectively map the set of three points to itself. The composition of any two of these bijections results in another bijection within $S_3$, demonstrating the closure property of the group. This visualization helps to understand how permutations act on elements and how their composition forms the group $S_3$.

Example: The Dihedral Group $D_4$ (Symmetries of a Square)

The dihedral group $D_4$ represents the symmetries of a square. These symmetries are transformations that map the square back onto itself. $D_4$ provides another concrete example of a non-abelian group.

The symmetries of the square are:

1. Rotations:

   • $r_0$: Rotation by 0° (identity)
   • $r_1$: Rotation by 90° clockwise
   • $r_2$: Rotation by 180° clockwise
   • $r_3$: Rotation by 270° clockwise

2. Reflections:

   • $s_1$: Reflection across the vertical axis (through the midpoints of sides 1-4 and 2-3)
   • $s_2$: Reflection across the horizontal axis (through the midpoints of sides 1-2 and 3-4)
   • $d_1$: Reflection across the main diagonal (1-3)
   • $d_2$: Reflection across the other diagonal (2-4)

$D_4$ has 8 elements: $\{r_0,r_1,r_2,r_3,s_1,s_2,d_1,d_2\}$. The group operation is the composition of symmetries. For example, $r_1\circ s_1$ means first reflect across the vertical axis, then rotate 90° clockwise.

$D_4$ is not commutative. For example, $r_1\circ s_1\ne s_1\circ r_1$. This can be visualized by performing the operations in different orders and observing the final positions of the labeled vertices.

Order of an Element in a Group

The order of an element $a$ in a group $⟨G;\ast {,}^{-1},e⟩$ is the smallest positive integer $n$ such that $a^n=e$, where $a^n$ denotes the operation $\ast$ applied to $a$, $n$ times (e.g., $a^3=a\ast a\ast a$). If no such $n$ exists, the element is said to have infinite order.

In other words, the order of an element is the number of times you need to apply the group operation to the element itself to get back to the identity element.

Examples:

• In the additive group of integers modulo 3 (${\mathbb{Z}}_3$), the order of the element 1 is 3, because $1+1+1=0(\mathrm{mod}3)$ (and 3 is the smallest positive integer with this property).
• In the group of rotations of a square, a 90-degree rotation has order 4, since four 90-degree rotations bring the square back to its original position (equivalent to the identity operation).
• In the group of integers under addition ($\mathbb{Z}$), no element other than 0 has finite order. For any non-zero integer $a$, $a+a+...+a$ (n times) will never equal 0.

Continue here: 15 Groups, Homomorphism, Isomorphism, Preservation of Identity and Inverses