CS2050 L16 Group Theory
Overview
Abrahim Ladha introduces groups as sets with an operation satisfying identity, associativity, inverses, and closure, then uses integer addition, modular arithmetic, complex numbers, and symmetries to show how the same axioms apply to very different structures. He develops the gcd criterion for multiplicative inverses modulo n and defines group isomorphism as a bijective structure-preserving map, illustrating it with the reals under addition and positive reals under multiplication, permutation groups, and triangle symmetries.
Key takeaways
- In any group, AB = AC implies B = C by multiplying on the left by A⁻¹; the proof does not require commutativity or a general notion of division.
- A residue a has a multiplicative inverse modulo n exactly when gcd(a, n) = 1, and the extended Euclidean algorithm finds that inverse through Bézout coefficients.
- The nonzero residues modulo n form a multiplicative group precisely when n is prime; for composite n, the group of units consists only of residues relatively prime to n.
- Isomorphic groups can use different operations and elements yet have identical structure: x ↦ 2ˣ identifies real addition with positive-real multiplication.
- Permutations of three objects and the six rotations and reflections of an equilateral triangle describe isomorphic groups, both with six elements.
Chapters
- A group consists of a set and one binary operation that maps two elements of the set to another element in the set.
- The operation must satisfy identity, associativity, inverses, and closure; inverse notation means an inverse under the operation, not necessarily a reciprocal.
- The integers under addition form a group: 0 is the identity, each integer a has inverse −a, and integer addition is closed and associative.
- The positive reals under multiplication form a group with identity 1 and inverse 1/x for each positive real x.
- Excluding 0 matters because 0 has no multiplicative inverse; products of positive reals remain positive.
- Cancellation follows from the group axioms: if AB = AC, multiply on the left by A⁻¹ and use associativity and the identity to conclude B = C.
- Groups are not assumed to be commutative; a group with AB = BA for all elements is called abelian.
- The identity is unique: if e and e′ both act as identities, cancellation applied to ae = ae′ gives e = e′.
- Inverses are unique, and the inverse of an inverse is the original element.
- The inverse of a product reverses order: (AB)⁻¹ = B⁻¹A⁻¹, the shoes-and-socks rule.
- The set {1, −1, i, −i} is a four-element group under complex multiplication, using i² = −1.
- Its identity is 1; 1 and −1 are their own inverses, while i and −i are inverses of each other.
- A finite group's multiplication table can directly verify closure and identify inverses; associativity is inherited from complex multiplication.
- Natural numbers under subtraction fail multiple group axioms: subtraction is not associative, and 2 − 3 is not a natural number.
- There is no two-sided identity for subtraction on the naturals, and subtraction does not provide inverses for every element.
- A single counterexample, such as (2 − 3) − 4 differing from 2 − (3 − 4), is enough to disprove associativity.
- The residue classes Zₙ = {0, 1, …, n − 1} form a group under addition modulo n.
- The identity is 0, addition is associative because it is inherited from integer addition on equivalence classes, and results reduce to a residue in Zₙ.
- The additive inverse of a representative a can be written n − a, interpreted modulo n; for example, modulo 12 the inverse of 1 is 11.
- Group theory here uses one operation at a time: additive inverses are allowed, but division by an element is not automatically defined.
- Modulo 5, the nonzero residues {1, 2, 3, 4} form a multiplicative group with identity 1.
- In this group, 2⁻¹ = 3 because 2 · 3 ≡ 1 (mod 5); 1 and 4 are their own inverses.
- Removing 0 is not enough for modulo 6: 2 · 3 ≡ 0 (mod 6), so the nonzero residues are not closed under multiplication.
- Modulo 6, 2 has no multiplicative inverse, illustrating that modular inverses depend on the modulus.
- Repeated addition modulo 12 shows that residues sharing a factor with 12 cycle through only part of the residue classes.
- For example, repeatedly adding 3 modulo 12 visits 3, 6, 9, 0 and never reaches 1, so 3 has no inverse modulo 12.
- A residue relatively prime to the modulus cycles through all residues when repeatedly added, including 1; this motivates the gcd criterion for inverses.
- An inverse of a modulo n exists exactly when gcd(a, n) = 1.
- If ab ≡ 1 (mod n), then ab − nc = 1 for some integer c, expressing 1 as a linear combination of a and n and forcing their gcd to be 1.
- Conversely, Bézout's identity gives integers s and t with as + nt = 1 when gcd(a, n) = 1; reducing modulo n shows as ≡ 1.
- The extended Euclidean algorithm computes the coefficient s, which gives a modular inverse of a.
- All nonzero residues modulo n form a multiplicative group exactly when n is prime, since every nonzero residue is then relatively prime to n.
- For composite n, the multiplicative group modulo n keeps only residues a with 1 ≤ a < n and gcd(a, n) = 1.
- Modulo 6, the group of units is {1, 5}; modulo 10 it is {1, 3, 7, 9}, with 4 elements.
- Modulo 23 there are 22 units because 23 is prime, while modulo 24 there are only 8.
- A group isomorphism is a bijection that preserves the group operation, making two groups structurally identical even when their elements or operations have different names.
- For groups G and H, a map φ is a homomorphism when φ(a ⋅G b) = φ(a) ⋅H φ(b).
- A homomorphism need not be bijective and can collapse structure, such as mapping every element to the identity of a one-element group.
- An isomorphism must be both a homomorphism and a bijection.
- The integers under addition are isomorphic to the even integers under addition via φ(a) = 2a.
- The map preserves addition because φ(a + b) = 2(a + b) = 2a + 2b = φ(a) + φ(b), and it is a bijection onto the even integers.
- The reals under addition are isomorphic to the positive reals under multiplication using φ(x) = 2ˣ.
- The exponential map preserves operations because 2ˣ⁺ʸ = 2ˣ · 2ʸ; its inverse is log₂, so the map is a bijection.
- Sₙ is the set of all bijections from an n-element set to itself, with function composition as the group operation.
- The identity element is the identity function; every bijection has an inverse bijection, and composing bijections gives another bijection.
- Function composition is associative but generally not commutative, so Sₙ is not generally an abelian group.
- There are n! elements in Sₙ because there are n! bijections of an n-element set to itself.
- An equilateral triangle has six symmetries: rotations by 0°, 120°, and 240°, plus three reflections.
- Composing two symmetries produces another of the six, and the identity is the 0° rotation.
- Each reflection is its own inverse; the 120° and 240° rotations are inverses of each other.
- The triangle's symmetry group is isomorphic to S₃, the group of permutations of three elements.
Transcript excerpt
0:01 All right, let's get started. This is uh CS 2050. The topic of today is something called group theory. In general, um uh most of the lectures are about kind of like basics, like going back and revisit concepts you kind of already know. We had a whole lecture on the equal sign and and we formalize that in terms of equivalence relations. Group theory in one perspective, not all perspectives, is the study of symmetry. So, it's really just understanding what it means for objects to act upon each other in a in a really way in a way that only depends on their like relationship to other ones. It's a part of a branch of this larger field of mathematics known as abstract algebra, where you're not really doing
0:47 algebra on numbers necessarily, but on things that are nothing but elements of some kind of structure that are you're working under. Formally, a group is two things. It's a set of objects and a function uh where we call the multiplication, where it takes as input two elements of G and returns a third element of G. Um this is understood kind of as a multiplication or an addition or an operation as you're used to, but it's more generalized uh than that and it's kind of arbitrary as we'll see. It can be instantiated as many different actual operations. So, there are are In order for this such such a structure to be a group, a set with a function, it needs to have four properties. One, the identity.
1:36 There exists some element E in G for all A in G AE = EA = A. By the way, implicitly there is an equivalence relation also on whatever the objects of G are. Uh second is associativity.
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.