Discrete Structure (CS-302) Unit 2 Notes

How unit 2 is examined

Groups and their sub-structures dominate this unit: group axioms with Cayley-table proofs, cyclic groups, Lagrange, normal subgroups and homomorphism carry most marks, and rings and fields follow.

Definition, Properties, types: Semigroups, Monoid, Groups, Abelian group

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. An algebraic structure $(S,*)$ is a non-empty set $S$ with a binary operation $*$ on it. <mark>A group is an algebraic structure $(G,*)$ that is closed, associative, has an identity element and gives every element an inverse; it is Abelian if $*$ is also commutative.</mark>

Key points.

A semigroup is a closed, associative structure, for example $(\mathbb{N},+)$.
A monoid is a semigroup with an identity $e$ such that $a*e=e*a=a$, for example $(\mathbb{W},+)$ with $e=0$.
A group is a monoid in which every $a$ has an inverse $a^{-1}$ with $a*a^{-1}=a^{-1}*a=e$, for example $(\mathbb{Z},+)$.
A group is Abelian when $a*b=b*a$ for all $a,b$; invertible $2\times2$ matrices under multiplication form a non-Abelian group.
Every group is a monoid, every monoid a semigroup; the converses fail. The order of a group is its number of elements.
To prove a set is a group, check closure, associativity, identity, inverse in that order, then commutativity for Abelian.

Example (identity). For $a*b=a+b-2$: $a*e=a\Rightarrow a+e-2=a\Rightarrow e=2$. Check: $2*a=2+a-2=a$. Identity $e=2$ (inverse of $a$ is $4-a$).

Example (mod 7). Under $\times_7$, $0$ has no inverse ($0\times x=0\neq1$), so $\{0,\dots,6\}$ fails; the group is $\{1,\dots,6\}$, order 6. Under $+_7$ the full set $\{0,\dots,6\}$ is a group of order 7.

$\times_7$	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

All entries lie in the set (closure); associativity is inherited from integers; identity 1; inverses $1\leftrightarrow1,2\leftrightarrow4,3\leftrightarrow5,6\leftrightarrow6$; the table is symmetric (commutative). For $+_7$ (or $+_4$ on $\{0,1,2,3\}$) the identity is 0 and the inverse of $a$ is $n-a$.

Example (numbers and matrices). $\{a+b\sqrt2:a,b\in\mathbb{Z}\}$ under $+$: sum is $(a+c)+(b+d)\sqrt2$ (closed), associativity comes from $\mathbb{R}$, identity $0+0\sqrt2$, inverse $-a-b\sqrt2$, commutative. The four matrices $\mathrm{diag}(\pm1,\pm1)$ are closed under multiplication, have identity $I$, satisfy $A^2=I$ (own inverse) and commute.

Answer frame. Open with the group definition; for a proof question write the axioms as a numbered list; build the Cayley table first, then tick closure, associativity, identity, inverse, commutativity; close with "hence $(G,*)$ is an Abelian group". For "explain algebraic structures" add the semigroup, monoid, group chain with one example each.

Pitfall: Writing $\{0,\dots,6\}$ under multiplication mod 7 as a group without pointing out that $0$ has no inverse.

Asked: [7 marks] (Nov 2018) What do you mean by algebraic structures? Explain its different properties. Asked: [7 marks] (Nov 2018) Show that $(\{a+b\sqrt2:a,b\in I\},+)$ forms a group. Asked: [7 marks] (Nov 2019) Prove the four diagonal $\pm1$ matrices form an Abelian group under matrix multiplication. Asked: [7 marks] (Nov 2022, Jun 2024, Jun 2025) Prove $G=\{0,\dots,6\}$ is an abelian group of order 7 under multiplication modulo 7 (variants: addition modulo 7; $\{0,1,2,3\}$ under addition modulo 4 with identity and inverses). Asked: [7 marks] (Jun 2023) Define group. Explain the properties of groups. Asked: [7 marks] (Jun 2024, Dec 2024) For $a*b=a+b-2$ on $\mathbb{Z}$, find the identity of $\langle\mathbb{Z},*\rangle$.

Properties of groups

Definition. Standard results follow from the axioms alone and hold in every group.

Key points.

The identity is unique: if $e,e'$ are identities then $e=e*e'=e'$.
Each inverse is unique: if $b,c$ invert $a$ then $b=b*(a*c)=(b*a)*c=c$.
Cancellation holds: $a*b=a*c\Rightarrow b=c$; also $(a*b)^{-1}=b^{-1}*a^{-1}$ and $(a^{-1})^{-1}=a$.
Pigeonhole principle: if $n+1$ objects are put in $n$ boxes, some box holds at least two objects.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 424 406.8" width="424" height="406.8" role="img" aria-label="Complete graph K5, 5 vertices, 10 edges"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M227.6,50.9 L368.4,149.5"/><path class="e" d="M218.2,58 L317.6,348.8"/><path class="e" d="M205.8,58 L106.4,348.8"/><path class="e" d="M196.4,50.9 L55.6,149.5"/><path class="e" d="M378.7,178.6 L329.1,348.6"/><path class="e" d="M368.6,171.6 L115.6,355.6"/><path class="e" d="M365,160.4 L59,160.4"/><path class="e" d="M304.8,366.8 L119.2,366.8"/><path class="e" d="M308.4,355.6 L55.4,171.6"/><path class="e" d="M94.9,348.6 L45.3,178.6"/><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="384" cy="160.4" r="18"/><text class="t" x="384" y="160.4" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="323.8" cy="366.8" r="18"/><text class="t" x="323.8" y="366.8" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="100.2" cy="366.8" r="18"/><text class="t" x="100.2" y="366.8" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="40" cy="160.4" r="18"/><text class="t" x="40" y="160.4" dy=".35em" text-anchor="middle">E</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Complete graph K5, 5 vertices, 10 edges</figcaption></figure>

Asked: [7 marks] (Dec 2025) Define group and Abelian group. Prove that the identity element of a group is unique. Asked: [7 marks] (Dec 2020) State the pigeonhole principle; draw $K_5$; prove the identity of a group is unique.

Subgroup

Definition. <mark>A non-empty subset $H$ of a group $(G,*)$ is a subgroup if $H$ is itself a group under the same operation $*$.</mark>

Key points.

Test: $H\ne\emptyset$ and $a,b\in H\Rightarrow a*b^{-1}\in H$ is enough.
Every group has the trivial subgroups $\{e\}$ and $G$.
The identity of $H$ is the identity of $G$, and inverses in $H$ are those of $G$.
By Lagrange, the order of a subgroup divides the order of $G$.
The intersection of subgroups is a subgroup; a union need not be.

Proof (intersection). Let $H_1,H_2\le G$. Then $e\in H_1\cap H_2$, so it is non-empty. Take $x,y\in H_1\cap H_2$. As each is a subgroup, $xy^{-1}\in H_1$ and $xy^{-1}\in H_2$, so $xy^{-1}\in H_1\cap H_2$. Hence closure, identity and inverses hold and $H_1\cap H_2$ is a subgroup.

Example ($\mathbb{Z}_8$). Orders divide 8, and $\mathbb{Z}_8$ is cyclic, so one subgroup per divisor: $\{0\}$, $\{0,4\}$, $\{0,2,4,6\}$, $\mathbb{Z}_8$. Four subgroups.

Answer frame. Open with the subgroup definition; prove via the $xy^{-1}$ test (identity, then closure with inverses); for $\mathbb{Z}_8$ list divisors 1, 2, 4, 8 and generate each with $\langle4\rangle,\langle2\rangle$; close with the count.

Asked: [7 marks] (Dec 2020) Prove that the intersection of two subgroups of a group $G$ is again a subgroup of $G$. Asked: [7 marks] (Dec 2025) Find all subgroups of the group $\mathbb{Z}_8$.

Cyclic groups

Definition. ==A group $G$ is cyclic if some element $a$ generates it, that is $G=\langle a\rangle=\{a^n:n\in\mathbb{Z}\}$; in additive notation $G=\{na\}$.== The element $a$ is a generator.

Key points.

$(\mathbb{Z},+)$ is cyclic with generators $1$ and $-1$; $(\mathbb{Z}_n,+_n)$ is cyclic with generator 1.
Verification of the example: $a^m a^n=a^{m+n}$ (closure), $a^0=e$, and $(a^n)^{-1}=a^{-n}$ lie in $G$.
If $a$ generates $G$ so does $a^{-1}$; $\mathbb{Z}_6$ has generators 1 and 5 only.
Every cyclic group is Abelian (proof below).
Every subgroup of a cyclic group is cyclic (proof below).
The converse of 4 fails: the Klein four-group is Abelian but not cyclic.

Proof (cyclic $\Rightarrow$ Abelian). Let $G=\langle a\rangle$, $x=a^m$, $y=a^n$. Then $xy=a^{m+n}=a^{n+m}=yx$.

Proof (subgroup). Let $H\le G=\langle a\rangle$. If $H=\{e\}$ it is $\langle e\rangle$. Otherwise $H$ has a positive power of $a$ (as $a^{-k}\in H$ gives $a^k\in H$). Let $m$ be the least positive integer with $a^m\in H$ (well-ordering). Take $a^k\in H$ and write $k=qm+r$, $0\le r<m$. Then $a^r=a^k(a^m)^{-q}\in H$, so $r=0$ by minimality of $m$. Hence $a^k=(a^m)^q$ and $H=\langle a^m\rangle$ is cyclic.

Lattice part. A finite Boolean algebra has $2^n$ elements; $5\ne2^n$, so no 5-element lattice is Boolean.

Answer frame. Open with the definition and $(\mathbb{Z},+)$; give the two proofs as separate numbered steps; for the double question write the lattice fact in one closing sentence.

Asked: [7 marks] (Nov 2019) Define cyclic group with suitable example. Asked: [7 marks] (Jun 2020, Dec 2020) Define semigroup. Prove that every subgroup of a cyclic group is cyclic. Asked: [7 marks] (Jun 2024, Dec 2024) Show that every cyclic group is Abelian. Prove that a lattice with 5 elements is not a Boolean algebra.

Cosets

Definition. For a subgroup $H\le G$ and $a\in G$, the left coset is $aH=\{ah:h\in H\}$. The index $[G:H]$ is the number of distinct cosets.

Key points.

Every coset has exactly $|H|$ elements, because $h\mapsto ah$ is a bijection $H\to aH$.
Any two left cosets are equal or disjoint, since $c\in aH\cap bH$ gives $aH=cH=bH$.
The cosets cover $G$ ($a\in aH$), so they partition $G$.
$aH=H$ exactly when $a\in H$.

Lagrange's theorem. ==If $H$ is a subgroup of a finite group $G$, then $|H|$ divides $|G|$, and $|G|=[G:H]\,|H|$.== Proof: by points 1 to 3, $G$ splits into $[G:H]$ disjoint cosets, each with $|H|$ elements; counting gives the formula.

Example. $G=\mathbb{Z}_6$, $H=\{0,2,4\}$: cosets $H$ and $1+H=\{1,3,5\}$, so $6=2\times3$. Corollary: the order of every element divides $|G|$.

Answer frame. State the theorem, define coset, prove in the order equal size, disjoint, partition, count; add the $\mathbb{Z}_6$ example. For the Nov 2022 question add the definitions from Permutation groups.

Pitfall: The converse of Lagrange is false: $A_4$ has order 12 but no subgroup of order 6.

Asked: [7 marks] (Nov 2019) State and prove Lagrange's theorem on groups. Asked: [7 marks] (Nov 2022) State Lagrange's theorem with example. Also explain permutation and symmetric group.

Factor group

Definition. For a normal subgroup $N\trianglelefteq G$, the factor (quotient) group is $G/N=\{aN:a\in G\}$ with $(aN)(bN)=abN$.

Key points.

The operation is well defined only because $N$ is normal.
The identity is $N$ and the inverse of $aN$ is $a^{-1}N$.
$|G/N|=|G|/|N|$, and $G/N$ is Abelian if $G$ is.
Example: $\mathbb{Z}/n\mathbb{Z}\cong\mathbb{Z}_n$.

Permutation groups

Definition. A permutation of a set is a bijection of it onto itself. <mark>The symmetric group $S_n$ is the group of all permutations of $n$ objects under composition.</mark>

Key points.

$|S_n|=n!$, for example $|S_3|=6$.
The identity is the identity map; the inverse is the inverse map.
$S_n$ is non-Abelian for $n\ge3$.
A permutation group is any subgroup of $S_n$; every finite group is isomorphic to one (Cayley).

Normal subgroup

Definition. ==A subgroup $N$ of $G$ is normal, written $N\trianglelefteq G$, if $gNg^{-1}=N$ for every $g\in G$, that is $gng^{-1}\in N$ for all $g\in G$, $n\in N$.==

Key points.

Equivalently, every left coset equals the right coset: $gN=Ng$.
Every subgroup of an Abelian group is normal; $\{e\}$ and $G$ are always normal.
$\{e,(12)\}$ is a subgroup of $S_3$ that is not normal.
The kernel of a homomorphism is normal.
Quotient group $G/N$ exists exactly for normal $N$ (see Factor group); example $\mathbb{Z}/2\mathbb{Z}$.
Subgroup example: $2\mathbb{Z}\le\mathbb{Z}$.

Proof (intersection is normal). The statement is true. Let $H,K\trianglelefteq G$. Both are subgroups, so $H\cap K$ is a subgroup. Take $x\in H\cap K$, $g\in G$. As $H$ is normal, $gxg^{-1}\in H$; as $K$ is normal, $gxg^{-1}\in K$. So $gxg^{-1}\in H\cap K$, hence $H\cap K\trianglelefteq G$.

Answer frame. Write "True" first; prove subgroup, then normality; close with the conclusion. For the definitions question give subgroup, normal subgroup, quotient group each with one example (Symmetric group: see Permutation groups).

Asked: [7 marks] (Dec 2024) Prove or disprove that the intersection of two normal subgroups of a group $G$ is a normal subgroup of $G$. Asked: [7 marks] (Jun 2024) Same proof; also define subgroup, normal subgroup, quotient group, with an example for each. Asked: [7 marks] (Dec 2023) Define symmetric group, normal subgroup, homomorphism.

Homomorphism and isomorphism of groups

Definition. ==A map $f:(G,*)\to(H,\circ)$ is a homomorphism if $f(a*b)=f(a)\circ f(b)$ for all $a,b\in G$; an isomorphism is a bijective homomorphism, written $G\cong H$.==

Key points.

A homomorphism preserves the identity: $f(e)=e'$.
It preserves inverses: $f(a^{-1})=f(a)^{-1}$.
The image $f(G)$ is a subgroup of $H$.
The kernel $\ker f=\{x:f(x)=e'\}$ is a normal subgroup of $G$.
$f$ is one-one exactly when $\ker f=\{e\}$.
First isomorphism theorem: $G/\ker f\cong f(G)$.
Isomorphic groups have the same order, and are both Abelian or both not.

Proof (identity). $f(e)=f(e*e)=f(e)\circ f(e)$. Multiply by $f(e)^{-1}$: $e'=f(e)$.

Point	Homomorphism	Isomorphism
Rule	$f(ab)=f(a)f(b)$	same rule
One-one	not needed	required
Onto	not needed	required
Inverse map	may not exist	exists, also a homomorphism
Structure	preserved, may collapse	identical in form
Example	$\mathbb{Z}\to\mathbb{Z}_n$, $x\mapsto x\bmod n$	$\exp:(\mathbb{R},+)\to(\mathbb{R}^+,\times)$

Example ($f(x)=2x$). $f(x+y)=2x+2y=f(x)+f(y)$, so $f$ is a homomorphism on $(\mathbb{R},+)$ (and bijective, so an isomorphism).

Example (Jun 2023). $(a,b)*(a',b')=(aa',bb')$, $f(a,b)=a/b$. (i) $f\big((a,b)*(a',b')\big)=\frac{aa'}{bb'}=\frac ab\times\frac{a'}{b'}=f(a,b)\times f(a',b')$, so $f$ is a homomorphism. (ii) $(a,b)\sim(c,d)\iff\frac ab=\frac cd$, so $(a,b)\sim(c,d)\iff ad=bc$.

Answer frame. Define homomorphism then isomorphism; for proofs use the substitution $f(e)=f(ee)$; for the comparison give the table and an example; for numericals compute both sides and state "equal, hence homomorphism".

Asked: [7 marks] (Nov 2019) Prove that a group homomorphism preserves the identity element. Asked: [7 marks] (May 2019, Nov 2018) Differentiate between homomorphism and isomorphism of groups with an example (Nov 2018 adds rings and fields; see Rings and fields). Asked: [14 marks] (Jun 2023) With $S=\mathbb{N}\times\mathbb{N}$, $(a,b)*(a',b')=(aa',bb')$: show $f(a,b)=a/b$ is a homomorphism to $(\mathbb{Q},\times)$ and find the congruence $\sim$ it determines. Asked: [7 marks] (Jun 2025) Define a homomorphism. Verify whether $f(x)=2x$ on $\mathbb{R}$ is a homomorphism under addition.

Rings and fields

Definition. <mark>A ring $(R,+,\cdot)$ has $(R,+)$ an Abelian group, $(R,\cdot)$ a semigroup, and $\cdot$ distributing over $+$ on both sides. A field is a commutative ring with unity $1\ne0$ in which every non-zero element has a multiplicative inverse.</mark>

Key points.

Examples of rings: $(\mathbb{Z},+,\cdot)$, $(\mathbb{R},+,\cdot)$, $\mathbb{Z}_n$; $\mathbb{Q},\mathbb{R},\mathbb{C}$ are fields.
Elementary properties: $a\cdot0=0\cdot a=0$.
Also $a(-b)=(-a)b=-(ab)$ and $(-a)(-b)=ab$.
Also $a(b-c)=ab-ac$.
$\mathbb{Z}$ is a ring but not a field, since $2$ has no inverse in $\mathbb{Z}$.

Point	Ring	Field
Multiplication	associative only	commutative group on non-zero elements
Unity	not needed	required, $1\ne0$
Inverses	none needed	every non-zero element
Example	$\mathbb{Z}$	$\mathbb{Q}$

Proof ($F=\{a+b\sqrt2:a,b\in\mathbb{Q}\}$ is a field). Sum $(a+c)+(b+d)\sqrt2$ and product $(ac+2bd)+(ad+bc)\sqrt2$ have rational coefficients (closure). Associativity, commutativity and distributivity are inherited from $\mathbb{R}$. Additive identity $0$, inverse $-a-b\sqrt2$; multiplicative identity $1$. For $a+b\sqrt2\ne0$: $\frac1{a+b\sqrt2}=\frac{a-b\sqrt2}{a^2-2b^2}$, where $a^2-2b^2\ne0$ as $\sqrt2$ is irrational, and coefficients stay rational. So $F$ is a field (a subfield of $\mathbb{R}$).

Answer frame. Write the ring axioms as a list, then the properties with one line each; for the field proof follow closure, additive group, multiplicative inverse by rationalising, conclusion.

Asked: [7 marks] (Dec 2024) What is a ring? Define elementary properties of a ring with example. Asked: [7 marks] (Dec 2023) Prove that $F=\{a+b\sqrt2:a,b\text{ rational}\}$ is a field. Asked: [7 marks] (Nov 2018) Differentiate between (i) homomorphism and isomorphism, (ii) rings and fields.

Last-minute revision

Group: closure, associativity, identity, inverse; Abelian adds commutativity.
Semigroup is closed and associative; monoid adds identity; group adds inverses.
For $a*b=a+b-2$ the identity is 2 and the inverse of $a$ is $4-a$.
$\{1,\dots,6\}$ under $\times_7$ is a group of order 6 (0 has no inverse); $\mathbb{Z}_7$ under $+_7$ has order 7.
Subgroup test: $ab^{-1}\in H$; intersection of subgroups (and of normal subgroups) is again one.
Subgroups of $\mathbb{Z}_8$: $\{0\}$, $\{0,4\}$, $\{0,2,4,6\}$, $\mathbb{Z}_8$.
Every cyclic group is Abelian; every subgroup of a cyclic group is cyclic.
Lagrange: $|G|=[G:H]\,|H|$; the converse is false.
Homomorphism: $f(ab)=f(a)f(b)$, $f(e)=e'$; isomorphism is bijective.
Kernel is normal; $G/\ker f\cong f(G)$; $|S_n|=n!$.
Field is a commutative ring with unity where non-zero elements are invertible.
Congruence for $f(a,b)=a/b$: $ad=bc$.

Memory hooks

CAII: Closure, Associativity, Identity, Inverse (group), plus C again for Commutative (Abelian).
Semigroup, Monoid, Group: add one thing each time, identity then inverse.
Cyclic means one generator, so everything is a power of it, so it commutes.
Lagrange: cosets are equal-sized boxes that tile the group.
Homomorphism is a translator of operations; isomorphism is a perfect translator (bijective).

Coverage checklist

Definition, Properties, types: Semi Groups, Monoid, Groups, Abelian group: Nov 2018 (2), Nov 2019 matrix group, Nov 2022/Jun 2024/Jun 2025 mod 7, Jun 2023 define group, Jun 2024/Dec 2024 identity $a+b-2$.
properties of groups: Dec 2020 pigeonhole/K5/identity unique, Dec 2025 identity unique.
Subgroup: Dec 2020 intersection, Dec 2025 subgroups of $\mathbb{Z}_8$.
cyclic groups: Nov 2019 define, Jun/Dec 2020 subgroup of cyclic, Jun/Dec 2024 cyclic is Abelian and 5-element lattice.
Cosets: Nov 2019 Lagrange proof, Nov 2022 Lagrange with example.
factor group: definition and points, none asked.
Permutation groups: definition and points, none asked (Nov 2022 symmetric group covered here).
Normal subgroup: Dec 2024, Jun 2024, Dec 2023 definitions.
Homomorphism and isomorphism of Groups, example and standard results: Nov 2019, May 2019, Nov 2018, Jun 2023, Jun 2025.
Rings and Fields: definition and standard results: Dec 2024, Dec 2023, Nov 2018.

Account

Discrete Structure (CS-302) - Unit 2 Short Notes

How unit 2 is examined

Definition, Properties, types: Semigroups, Monoid, Groups, Abelian group

Properties of groups

Subgroup

Cyclic groups

Cosets

Factor group

Permutation groups

Normal subgroup

Homomorphism and isomorphism of groups

Rings and fields

Last-minute revision

Memory hooks

Coverage checklist