Introduction to Discrete Structure &Linear Algebra (AL-401) - Unit 3 Short Notes

III. Algebraic Structures

1. Binary Operations and Closure

• Binary Operation: A function \( * : S \times S \to S \). For \( a, b \in S \), \( a * b \) is the result.

• Closure: \( S \) is closed under \( * \) if \( \forall a,b \in S, \; a*b \in S \).

• Examples:

  • Addition on \( \mathbb{Z} \): closed.

  • Subtraction on \( \mathbb{N} \): not closed (e.g., \( 3-5 \notin \mathbb{N} \)).

[!TIP]

Always verify closure first when checking algebraic structures.

2. Semigroups and Monoids

• Associativity: \( (a*b)*c = a*(b*c) \; \forall a,b,c \in S \).

3. Groups

Definition: A group \( (G, *) \) satisfies:

1. Closure: \( \forall a,b \in G, \; a*b \in G \).

2. Associativity: \( (a*b)*c = a*(b*c) \).

3. Identity: \( \exists e \in G \) s.t. \( a*e = e*a = a \).

4. Inverse: \( \forall a \in G, \; \exists a^{-1} \in G \) s.t. \( a*a^{-1} = a^{-1}*a = e \).

• Abelian Group: Additionally, \( a*b = b*a \; \forall a,b \in G \).

Common Examples:

Subgroups

• Definition: \( H \subseteq G \) is a subgroup if \( (H, *) \) is a group under the same operation.

• Subgroup Tests:

  1. One-step: \( H \neq \emptyset \) and \( \forall a,b \in H, \; a*b^{-1} \in H \).

  2. Two-step: \( H \neq \emptyset \), closed under \( * \), and closed under inverses.

Example (from past paper):

Let \( G = \{ e, a, a^2, a^3, b, ab, a^2b, a^3b \} \) (likely dihedral-like). Show \( H = \{ e, a, a^2, a^3 \} \) is a subgroup.

• \( H \neq \emptyset \) (contains \( e \)).

• Closed: Since \( a^4 = e \), products of powers of \( a \) stay in \( H \).

• Inverses: \( a^{-1} = a^3 \), \( (a^2)^{-1} = a^2 \), \( (a^3)^{-1} = a \), \( e^{-1}=e \).

✅ Subgroup.

Normal Subgroups

• Definition: \( H \triangleleft G \) iff \( gH = Hg \; \forall g \in G \) (left/right cosets equal), or equivalently:

  \[ gHg^{-1} = H \quad \forall g \in G. \]

• Theorem (Past paper): \( H \) is normal iff \( xHx^{-1} = H \; \forall x \in G \).

  • Proof:

    • \( \Rightarrow \): If \( H \triangleleft G \), then \( gH = Hg \). So \( \forall h \in H, \; gh \in Hg \Rightarrow gh = h'g \) for some \( h' \in H \Rightarrow ghg^{-1} = h' \in H \). Thus \( gHg^{-1} \subseteq H \). Similarly \( H \subseteq gHg^{-1} \), so equality.

    • \( \Leftarrow \): If \( gHg^{-1} = H \), multiply by \( g \) on right: \( gH = Hg \).

[!CAUTION]

Not all subgroups are normal. In abelian groups, all subgroups are normal.

Cyclic Groups

• Definition: \( G = \langle a \rangle = \{ a^n \mid n \in \mathbb{Z} \} \) for some generator \( a \in G \).

• Order of element \( a \): smallest positive \( n \) with \( a^n = e \), or infinite.

• Theorem: In finite group, order of element divides group order.

• Example: \( (\mathbb{Z}_{12}, +_{12}) \) cyclic generated by \( \overline{1} \). Subgroups correspond to divisors of 12:

  \[ \begin{aligned} &\langle \overline{0} \rangle = \{ \overline{0} \}, \\ &\langle \overline{6} \rangle = \{ \overline{0}, \overline{6} \}, \\ &\langle \overline{4} \rangle = \{ \overline{0}, \overline{4}, \overline{8} \}, \\ &\langle \overline{3} \rangle = \{ \overline{0}, \overline{3}, \overline{6}, \overline{9} \}, \\ &\langle \overline{2} \rangle = \{ \overline{0}, \overline{2}, \overline{4}, \overline{6}, \overline{8}, \overline{10} \}, \\ &\langle \overline{1} \rangle = \mathbb{Z}_{12}. \end{aligned} \]

4. Rings

Definition: A ring \( (R, +, \times) \) satisfies:

1. \( (R, +) \) is an abelian group (identity \( 0 \)).

2. \( (R, \times) \) is a semigroup (associative).

3. Distributive laws:

   \[ a \times (b + c) = a \times b + a \times c, \quad (a + b) \times c = a \times c + b \times c. \]

• Ring with unity: Has multiplicative identity \( 1 \neq 0 \).

• Commutative ring: Multiplication commutative.

• Zero divisor: \( a \neq 0, b \neq 0 \) but \( a \times b = 0 \). Fields have no zero divisors.

Examples:

Ring Homomorphism

• Definition: \( \phi: R \to S \) such that:

  \[ \phi(a+b) = \phi(a) + \phi(b), \quad \phi(a \times b) = \phi(a) \times \phi(b). \]

  If rings with unity, often require \( \phi(1_R) = 1_S \).

• Kernel: \( \ker(\phi) = \phi^{-1}(0_S) \) is an ideal of \( R \).

• Isomorphism: Bijective homomorphism; rings \( R \) and \( S \) are isomorphic (\( R \cong S \)).

5. Fields

Definition: A field \( F \) is a commutative ring with unity where every nonzero element has a multiplicative inverse. Thus:

• \( (F, +) \) is abelian group (identity \( 0 \)).

• \( (F \setminus \{0\}, \times) \) is abelian group (identity \( 1 \)).

• Distributive laws hold.

Examples:

• \( \mathbb{Q}, \mathbb{R}, \mathbb{C} \): infinite fields.

• Finite fields: \( \mathrm{GF}(p) = \mathbb{Z}_p \) for prime \( p \). For \( p=5 \), elements \( \{0,1,2,3,4\} \), inverses: \( 1^{-1}=1, 2^{-1}=3, 3^{-1}=2, 4^{-1}=4 \).

• Not a field: \( \mathbb{Z} \) (no inverses for \( n>1 \)), \( \mathbb{Z}_4 \) (2 has no inverse).

Properties:

• Characteristic: smallest \( n \) s.t. \( n \cdot 1 = 0 \). For fields, characteristic is either 0 or prime.

• Every field is an integral domain (no zero divisors).

6. Past Paper Highlights & Common Pitfalls

• Group Check (Dec 2024): \( G = \{0,1,2,3,4,5\} \) under addition mod 6.

  • ✅ Closure: \( a+b \bmod 6 \in G \).

  • ✅ Associativity: inherited from integers.

  • ✅ Identity: \( 0 \).

  • ✅ Inverses: \( 0\leftrightarrow0, 1\leftrightarrow5, 2\leftrightarrow4, 3\leftrightarrow3 \).

  • ✅ Abelian: commutative.

  → Yes, group.

• Normal Subgroup Proof (Dec 2024):

  \( H \triangleleft G \iff xHx^{-1} = H \; \forall x \in G \).

  Proof given above.

• Subgroups of Cyclic Groups (Jun 2025):

  • \( (\mathbb{Z}_{12}, +_{12}) \): subgroups of orders dividing 12: 1,2,3,4,6,12.

  • \( (\mathbb{Z}_7^*, \times_7) \): order 6 (cyclic). Subgroups:

    \[ \{1\}, \; \{1,6\}, \; \{1,2,4\}, \; \{1,2,3,4,5,6\}. \]

• Semigroup Property (Jun 2024):

  If \( (A, *) \) semigroup, and \( a*c = c*a \), \( b*c = c*b \), then \( (a*b)*c = c*(a*b) \).

  Proof:

  \[ (a*b)*c = a*(b*c) = a*(c*b) = (a*c)*b = (c*a)*b = c*(a*b). \]

• Abelian vs Cyclic (Jun 2025):

  • Cyclic: Generated by one element. All cyclic groups are abelian.

  • Abelian: All elements commute. Not necessarily cyclic (e.g., Klein four-group \( \mathbb{Z}_2 \times \mathbb{Z}_2 \)).

[!TIP]

For subgroup tests, use one-step test for efficiency: check \( a*b^{-1} \in H \) instead of separately checking closure and inverses.

7. Quick Reference: Key Formulas

• Group axioms: Closure, Associativity, Identity, Inverse.

• Normal subgroup condition: \( gHg^{-1} = H \; \forall g \in G \).

• Cyclic group: \( \langle a \rangle = \{ a^n \mid n \in \mathbb{Z} \} \).

• Ring distributive: \( a(b+c) = ab + ac \), \( (a+b)c = ac + bc \).

• Field: Every nonzero element has inverse under multiplication.

\boxed{\text{Algebraic Structures: Groups, Rings, Fields with examples and subgroup tests are core exam topics.}}