in which we finish the proof of Lagrange’s Theorem, see what consequences it has on orders of elements, and meet equivalence relations.
Last time we started proving Lagrange’s Theorem: For a finite group , the size of any subgroup divides the size of We saw that the left cosets of partition , and today we added the fact that all cosets have the same size (as ). That put together proves Lagrange’s Theorem: the order of is the number of cosets of multiplied by the size of each coset, that is, the size of . Notice that we only need to be a finite group right at the end: the partitioning and the bijection between and work even for infinite groups. We called the number of cosets the index of in . I left it to you to show one direction of the “same coset check”: if and only if .
After this we saw some corollaries of Lagrange: the order of an element divides the order of the group, and for all in a finite group , we have . We called this “the exponent divides the group order” (remember from Sheet 1: the smallest such that for all ) . We also proved that groups of prime order are cyclic, and are generated by any of their non-identity elements.
To prepare for some further applications of Lagrange, we defined an equivalence relation: A relation on a set is an equivalence relation if it is reflexive ( for all ), symmetric () and transitive ( and together imply ). As examples we had “is congruent mod to” and “is isomorphic to” for groups. Such an equivalence relation gives us equivalence classes: . Equivalence classes form a partition on the set , and we saw that, for a group with subgroup , the relation is an equivalence relation on with the cosets of as equivalence classes.
As next application of Lagrange, we are working towards the Fermat-Euler Theorem, which is really a number theory theorem, but has a nice short groups proof. To get there, we looked at why adding and multiplying “numbers mod ” works, i.e. is well-defined. It all rests on them being cosets. We’ll take it from there next time.
Understanding today’s lecture
Make sure you are happy with the proof of Lagrange, it is an important result. Don’t forget to do the exercises given in lectures, for example showing that if then . Are you surprised by the Lagrange corollaries? I think they are very comforting :-). Someone asked about the exponent: I did prove the statement of the lemma, but I didn’t quite prove the name (or slogan) of the lemma. You can do that yourselves, I’m sure.
For equivalence relations, there are actually quite a lot of nice instructive “non-mathematical” examples that might help you to get a feel for it: for example, if is the set of all undergraduates in Cambridge, we could have “has their birthday in the same month as”, or “is in the same College as”. Show that these are indeed equivalence relations; can you say what their equivalence classes are? Others would be “having the same height as”, “having the same haircolour as”, and so on; I’m sure you can come up with some more. Undergrads who go to the same college are definitely not the same people, but they have a particular property in common.
Think about what we showed about the well-definedness of addition and multiplication mod . Is this trivial? It may well be something you “knew all along” but now see the proper reason for (that happens a lot in maths…).
Preparing for Lecture 10
Next time we will prove Fermat-Euler: for a natural number and an integer coprime to , we have . Here is Euler’s totient function the number of elements in which are coprime to . Perhaps you’ve come across a different, non-groups proof for it, or at least for Little Fermat (the same thing when is a prime , so ). But in our lecture we will prove it using some nice group theory, it has to do with finding a subset of which actually forms a group under multiplication. Can you find such a subset yourself?
We will also use Lagrange to help us find subgroups of certain groups. You could have a go at some dihedral groups yourself.
Going a little deeper
We said that the exponent divides the group order. In fact, the exponent has all prime factors of the group order . We can only prove this later when we have Cauchy’s theorem.
I didn’t really tell you what a relation is, only when a relation (whatever it might be) is an equivalence relation. Naively, a relation is something that “relates two elements of a set”. They either are related or not. For example on the integers, on the reals, or “have the same quotient” on the set of ordered pairs of integers, where we don’t allow the second one to be . More formally, a relation on a set is a subset of the cartesian product of with itself. So it just tells you which pairs of elements are related and which aren’t. The order does usually matter (as you can see with ). If it doesn’t, then it is a symmetric relation. I can’t actually remember whether this is defined in that formality in Numbers and Sets, but I think you’ll see it in third year in Logic and Set Theory.
In some sense, is the “prototype” of an equivalence relation. We said above that being in the same equivalence class doesn’t mean being exactly the same element, but if we are concentrating on just that particular property, it might be “the same enough” for our purposes. That is what I meant when I said “isomorphic groups are the same enough for us”. We will see in the next chapter how we can “make” all the elements in one equivalence class the same by forming a quotient.