Go back to UGC NET COMUPTER SCIENCE

UNIT-1 — Group Theory (UGC NET: Computer Science & Applications)

(Groups • Subgroups • Semigroups • Product & Quotients • Isomorphism • Homomorphism • Automorphism • Rings • Integral Domains • Fields • Applications)

---

1. SEMIGROUPS

Definition: Semigroup

A semigroup is a set $S$ with a binary operation $\ast$ such that:

1. Closure:
   For all $a,b\in S$,

   $$a\ast b\in S\mathrm{.}$$

2. Associativity:
   For all $a,b,c\in S$,

   $$(a\ast b)\ast c=a\ast (b\ast c)\mathrm{.}$$

No requirement of identity or inverse.

Example:

$(\mathbb{N},+)$ is a semigroup.

---

2. MONOID

Definition: Monoid

A monoid is a semigroup with an identity element $e$ such that:

$$e\ast a=a\ast e=a\mathrm{\forall }a\in S\mathrm{.}$$

Example:

$({\mathbb{N}}_0,+)$ with identity 0.

---

3. GROUPS

Definition: Group

A group is a set $G$ with a binary operation $\ast$ satisfying:

1. Closure: $a\ast b\in G$.

2. Associativity: $(a\ast b)\ast c=a\ast (b\ast c)$.

3. Identity: There exists $e\in G$ such that $e\ast a=a\ast e=a$
   

4. Inverse: For each $a\in G$, there exists $a^{-1}\in G$ such that

   $$a\ast a^{-1}=a^{-1}\ast a=e\mathrm{.}$$

---

Definition: Abelian Group

A group is Abelian (or commutative) if:

$$a\ast b=b\ast a\mathrm{\forall }a,b\in G\mathrm{.}$$

---

4. SUBGROUPS

Definition: Subgroup

A non-empty subset $H$ of a group $G$ is a subgroup if:

1. $a,b\in H\Rightarrow a\ast b^{-1}\in H$
   (one-step subgroup test)

– OR –

Equivalent conditions:

• Closed under operation

• Closed under inverse

• Contains identity

---

Cyclic Subgroup

Generated by an element $g\in G$:

$$⟨g⟩=\{g^n:n\in \mathbb{Z}\}\mathrm{.}$$

---

5. PRODUCT OF ALGEBRAIC STRUCTURES

Definition: Direct Product of Groups

For groups $G$ and $H$,

$$G\times H=\{(g,h):g\in G,h\in H\}$$

with operation

$$(g_1,h_1)\ast (g_2,h_2)=(g_1\ast g_2,h_1\ast h_2)\mathrm{.}$$

This forms a group.

---

6. QUOTIENT GROUPS (FACTOR GROUPS)

Normal Subgroup (Important)

A subgroup $N$ of group $G$ is normal if:

$$gN=Ng\mathrm{\forall }g\in G$$

or equivalently

$$gn{g}^{-1}\in N\mathrm{\forall }g\in G,n\in N\mathrm{.}$$

---

Definition: Quotient Group

If $N$ is a normal subgroup of $G$:

$$G\mathrm{/}N=\{gN:g\in G\}$$

with operation

$$(gN)(hN)=(gh)N\mathrm{.}$$

---

7. HOMOMORPHISM, ISOMORPHISM, AUTOMORPHISM

---

Definition: Homomorphism

A function $f:G\to H$ between groups is a homomorphism if:

$$f(a\ast b)=f(a)\ast f(b)\mathrm{\forall }a,b\in G\mathrm{.}$$

Kernel:

$$\ker (f)=\{x\in G:f(x)=e_H\}$$

Image:

$$\text{Im}(f)=\{f(x):x\in G\}$$

---

Definition: Isomorphism

A homomorphism that is bijective.
Isomorphic groups have:

• same structure

• same properties

• different elements but identical algebraic behavior

Notation:

$$G\cong H$$

---

Definition: Automorphism

An isomorphism from a group to itself:

$$f:G\to G\mathrm{.}$$

The set of all automorphisms forms a group under composition.

---

8. RINGS

Definition: Ring

A ring $(R,+,\cdot )$ is a set with two operations satisfying:

Under Addition:

• Associative

• Commutative

• Identity (0)

• Inverses exist (each element has an additive inverse)

Under Multiplication:

• Associative

• Closed

Distributive Laws:

$$a(b+c)=ab+ac,(a+b)c=ac+bc\mathrm{.}$$

---

Definition: Commutative Ring

If multiplication is commutative:

$$ab=ba\mathrm{.}$$

---

Definition: Ring with Unity

A ring with multiplicative identity $1$ such that

$$1\cdot a=a\cdot 1=a\mathrm{.}$$

---

9. INTEGRAL DOMAINS

Definition: Integral Domain

A commutative ring with unity and no zero divisors.

Zero divisor definition:

Non-zero $a,b\in R$ such that

$$ab=0.$$

Thus, in an integral domain:

$$ab=0\Rightarrow a=0\text{ or }b=0.$$

Examples:

• $\mathbb{Z}$

• Polynomial rings over fields

---

10. FIELDS

Definition: Field

A set $F$ with two operations (+,·) such that:

Under addition:

Forms an Abelian group.

Under multiplication:

Non-zero elements $F-\{0\}$ form an Abelian group.

Distributivity holds.

Examples:

• Rational numbers $\mathbb{Q}$

• Real numbers $\mathbb{R}$

• Complex numbers $\mathbb{C}$

• Finite field $GF(p)$ where p is prime

---

11. APPLICATIONS OF GROUP THEORY (in Computer Science)

✔ Cryptography
– Uses groups, rings, finite fields
– Example: RSA, ECC use modular arithmetic groups

✔ Coding Theory
– Error-correcting codes use group and field structures
– Linear codes over finite fields

✔ Automata Theory
– Symmetry groups help in minimizing finite automata

✔ Graph Theory
– Automorphism groups classify graphs by symmetry

✔ Computer Graphics
– Rotations & transformations form groups

✔ Network Theory
– Cayley graphs build interconnection networks

✔ Algorithms
– Group operations used in hashing, randomization