# Groups Lecture 9

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 $G$, the size of any subgroup $H\leq G$ divides the size of $G.$ We saw that the left cosets of $H$ partition $G$, and today we added the fact that all cosets have the same size (as $H$). That put together proves Lagrange’s Theorem: the order of $G$ is the number of cosets of $H$ multiplied by the size of each coset, that is, the size of $H$. Notice that we only need $G$ to be a finite group right at the end: the partitioning and the bijection between $aH$ and $H$ work even for infinite groups. We called the number of cosets $|G:H|$ the index of $H$ in $G$. I left it to you to show one direction of the “same coset check”: $aH=bH$ if and only if $b^{-1}a\in H$.

After this we saw some corollaries of Lagrange: the order of an element divides the order of the group, and for all $a$ in a finite group $G$, we have $a^{|G|}=e$. We called this “the exponent divides the group order” (remember from Sheet 1: the smallest $m$ such that $a^m=e$ for all $a\in G$) . 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 $\sim$ on a set $X$ is an equivalence relation if it is reflexive ($x\sim x$ for all $x\in X$), symmetric ($x\sim y \Rightarrow y\sim x$) and transitive ($x\sim y$ and $y\sim z$ together imply $x\sim z$). As examples we had “is congruent mod $n$ to” and “is isomorphic to” for groups. Such an equivalence relation gives us equivalence classes: $[x]=\{y\in X\mid x\sim y\}$. Equivalence classes form a partition on the set $X$, and we saw that, for a group $G$ with subgroup $H\leq G$, the relation $a\sim b \Leftrightarrow b^{-1}a\in H$ is an equivalence relation on $G$ with the cosets of $H$ 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 $n$ 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 $b^{-1}a\in H$ then $aH=bH$. 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 $X$ 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 $n$. 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 $n$ and an integer $a$ coprime to $n$, we have $a^{\varphi(n)}\equiv 1 \pmod{n}$. Here $\varphi$ is Euler’s totient function $\varphi(n)=$ the number of elements in $\mathbb{Z}_n$ which are coprime to $n$. Perhaps you’ve come across a different, non-groups proof for it, or at least for Little Fermat (the same thing when $n$ is a prime $p$, so $\varphi(p)=p-1$). But in our lecture we will prove it using some nice group theory, it has to do with finding a subset of $\mathbb{Z}_n$ 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 $|G|$. 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 $\leq$ 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 $0$. More formally, a relation $R$ on a set $X$ is a subset $R\subseteq X\times X$ of the cartesian product of $X$ 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 $\leq$). 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.

## 2 thoughts on “Groups Lecture 9”

1. Sebastian Zimmer

In the lecture, you mentioned a set of all finite groups, but I’m pretty sure this can not exist, due to the following argument:

Assume a set of all finite groups. Since every finite set can trivially be turned into a cyclic group by using a bijection with C_n, this implies a set of all finite sets which we will call A. For every set S, {S} is a finite set which must be contained in A. Therefore, the union of A must contain all sets. This union exists by the axiom of union, which is in ZF. This then leads to Russell’s paradox.

This argument certainly does not preclude the existence of a set of all finite groups up to isomorphism, as we can then restrict our groups to only contain natural numbers.

Liked by 1 person

• Now that I’ve had time to process properly what you’ve said, I agree that you are correct. So I guess I’ll have to change that example :-). We can still think of “is isomorphic to” as an equivalence relation if we relax the definition (i.e. if we don’t ask $X$ to be an actual set). As you say, it is a set if we just take “one group in each isomorphism class”, but then that would sort of make the example rather boring. So, sorry about that, I’ll correct it next lecture.

Like