# The Pigeon Hole Principle and the Finite Subgroup Test

I am currently reading this document and am stuck on Theorem 3.3 on page 11:

Let $H$ be a nonempty finite subset of a group $G$. Then $H$ is a subgroup of $G$ if $H$ is closed under the operation of $G$.

I have the following questions:

1.

It suffices to show that $H$ contains inverses.

I don't understand why that alone is sufficient.

2.

Choose any $a$ in $G$...then consider the sequence $a,a^2,..$ This sequence is contained in $H$ by the closure property.

I know that if $G$ is a group, then $ab$ is in $G$ for all $a$ and $b$ in $G$.But, I don't understand why the sequence has to be contained in $H$ by the closure property.

3.

By the Pigeonhole Principle, since $H$ is finite, there are distinct $i,j$ such that $a^i=a^j$.

I understand the Pigeonhole Principle (as explained on page 2) and why $H$ is finite, but I don't understand how the Pigeonhole Principle was applied to arrive at $a^i=a^j$.

4. Reading the proof, it appears to me that $H$ = $\left \langle a \right \rangle$ where $a\in G$. Is this true?

-
I think #2 is supposed to read 'Choose any $a$ in $H$...' – REDace0 Oct 24 '11 at 13:00
@REDace0 After reading the answers to this question, I also think that it should read 'Choose any $a$ in $H$'. I guess it is a typo in the lecture then? – Sara Oct 31 '11 at 16:08

Question 1. Suppose $H$ is a nonempty subset of a finite (multiplicative) group $G$, such that whenever $a,b \in H$, the element $a \cdot b$ is also in $H$. We want to show that $H$ is a subgroup of $G$. That is, we want to show that $(H, \cdot)$ is a group. We verify the group axioms for $H$.

1. Closure under the $\cdot$ operation. If $a,b$ are elements of $H$, their product $a \cdot b$ is guaranteed to lie in $H$. So $H$ is indeed closed under $\cdot$. So there's nothing to prove.

2. Associativity. Suppose $a,b,c$ are elements of $H$, and hence of the group $G$. Then since the $\cdot$ is associative (remember that $G$ is a group), we have $a \cdot (b \cdot c) = (a \cdot b) \cdot c$. Thus the subgroup $H$ inherits the associativity of $\cdot$ from $G$. [Still nothing to prove! Don't we wish all proofs are as simple? :-)]

3. Existence of identity element $e$ in $H$. In this case, there is something to prove, but we will come to this after looking at inverses.

4. Existence of inverses. Again, there's something to prove. This was the point that was explicitly shown in great detail in the lecture (through the pigeonhole principle argument).

Coming back to item (3.), note that we still have not established that the identity element $e$ is in $H$. Let $a$ be an arbitrary element of $H$ (here we need the hypothesis that $H$ is nonempty). From item (4.), the inverse $a^{-1}$ is in $H$. Since $H$ is closed w.r.t. $\cdot$, it follows that $e = a \cdot a^{-1} \in H$ as well. $\Box$

Question 2. Suppose $a$ is in $H$. Then $a^2 = a \cdot a$ is also in $H$ by closure property. Then $a^3 = a \cdot a^2$ is also in $H$. Similarly, $a^4 = a \cdot a^3$ is also in $H$, and so on. More generally, we can use mathematical induction to prove the proposition that $a^n$ is in $H$ for each natural number $n$. (For the induction step, we need to show that if $a^{n-1} \in H$, then $a^n \in H$ as well. But this is true because $a^n = a \cdot a^{n-1}$ and $H$ is closed under the $\cdot$ operation.)

Question 3. Consider the sequence $\langle a, a^2, a^3, \ldots, a^n, \ldots \rangle$ of infinite length. Since the group $G$ is finite, there are only a finite number of distinct terms in that sequence. Therefore, some two terms, say the $i^{th}$ and $j^{th}$ terms, are equal. That is, $a^i = a^j$.

Question 4. That conclusion is false. What is true is that if $a$ is in $H$, then $\langle a \rangle \subseteq H$.

-
For question 1, you might note that the place where you implicitly used the hypothesis that $H$ is not empty is where you said "Suppose $a\in H$." – Gerry Myerson Oct 24 '11 at 12:27
@Gerry, Ah, good point. Thanks. – Srivatsan Oct 24 '11 at 12:29
I like this answer the best because it is presented in a neat manner as it clearly identify the question that is being answered and I know where an answer begins and ends.Thank you, Srivatsan for your effort. – Sara Oct 31 '11 at 16:14
You are welcome, @Sara. – Srivatsan Nov 1 '11 at 8:39

To show $H$ is a subgroup you must show it's closed, contains the identity, and contains inverses. But if it's closed, non-empty, and contains inverses, then it's guaranteed to contain the identity, because it's guaranteed to contain something, say, $x$, then $x^{-1}$, then $xx^{-1}$, which is the identity.

$H$ is assumed closed, so if it contains $a$ and $b$, it contains $ab$. But $a$ and $b$ don't have to be different: if it contains $a$, it contains $a$ and $a$, so it contains $aa$, which is $a^2$. But then it contains $a$ and $a^2$ so it contains $aa^2$ which is $a^3$. Etc.

So it contains $a,a^2,a^3,a^4,\dots$. $H$ is finite, so these can't all be different, so some pair is equal, that is, $a^i=a^j$ for some $i\ne j$.

As for your last question, do you know any example of a group with a non-cyclic subgroup?

-

Let's start by 1. To show that $H$ is a subgroup you need three things

1. $e$ (the neutral element) is in $H$.

2. For every $x,y$ in $H$ $xy$ is in $H$ too.

3. For every $a \in H$ $a^{-1}$ (the inverse of $a$) is in $H$ too.

So by the first hypothesis on $H$, (2) is true. It remains to show (1) and (3). But if you have (3) and since $H$ is nonempty, there is at least one $a$ in $H$. By (3) (which we assume) and by (2) which is known already $a^{-1}$ belongs to $H$ and $aa^{-1}$ belongs to $H$. So $e=aa^{-1}$ belongs to $H$ too. Hence (1) is satisfied.

To show the second property, namely that if $a$ is in $H$ then the sequence $a,a^2,\dots$ is in $H$ by the closure property observe that if $a$ is in $H$ then necessarily $a^2=aa$ is in $H$ too by the closure property, hence also $a^3=a a^2$ and so on so the whole sequence lies in $H$.

For the third question, it suffices to consider the sequence $a, a^2,a^3 , \dots$. By the second property, this sequence lies in $H$, but since $H$ is finite and the sequence is infinite the sequence admits arbitrary large finite subsequences so if the cardinality of $H$ is $n$ the sequence contains a finite subsequence $a, a^2 ,\dots, a^{n+1}$. It follows that there must be one bin (as in the pigeonhole principle) where $a^i=a^j$ for $i,j$ distinct.

Finally in the fourth question the statement is wrong. There are many non-cyclic finite groups for instance $\mathbb{Z} / 2\mathbb{Z} \times \mathbb{Z}/ 2\mathbb{Z}$.

-
I like this answer because it helped me understand exactly where the Pigeonhole Principle comes in for Question 3. – Sara Oct 31 '11 at 16:20

I am guessing that by "closed under the operation of $G$" they mean closed under the multiplication on $G$. Then $H$ is a subgroup if it then also contains inverses because it also contains the identity. Since $H$ is finite, then so must be $\{a^k:k\in\mathbb{Z}^+\}$ since it is contained in $H$. Thus, for some $i>j$, we must have $a^i=a^j$. Thus, $a^{i-j}$ must be the identity and $a^{i-j-1}=a^{-1}$.

$H$ is not necessaily cyclic. Here we have shown that $\{a^k:k\in\mathbb{Z}^+\}$ is a cyclic subgroup, but there is no guarantee that this is all of $H$. We may need to perform the above process on any $b\in H\setminus\{a^k:k\in\mathbb{Z}^+\}$, etc.

-
I like this answer because it explains why my conclusion on Question 4 is wrong as opposed to just providing counter examples. – Sara Oct 31 '11 at 16:24

Let $a\in H$ and consider the map $\phi: H \to G$ given by $\phi(x)=ax$. Since $H$ is closed under the operation of $G$, we have that $\phi$ actually goes $H\to H$. Since the cancellation law holds for $G$, the map $\phi$ is injective. Thus, $\phi$ is a bijection because $H$ is finite. In particular, $\phi$ is surjective and there is $u\in H$ such that $a = \phi(u) = au$. This implies that $u=e$ and so $e\in H$. Now there is $b\in H$ such that $e=\phi(b)$. Of course, $b=a^{-1}$ and so $a^{-1}\in H$. We have proved that $H$ contains the identity element and is closed under inverses. Since it is closed under multiplication, $H$ is a subgroup.

-
Interesting answer! – user17090 Oct 24 '11 at 14:04
Unfortunately, I am not able to follow this proof as it makes use of concepts not covered in the lecture. – Sara Oct 31 '11 at 16:25
@Sara, which concepts were not covered in the lecture? The proof relies on two facts: cancellation law for groups, which I assume has been covered in the lectures, and the fact that injective=surjective for functions between finite sets of the same cardinality, which is a basic fact in set theory. – lhf Oct 31 '11 at 16:28
@lhf, I am actually studying linear algebra now and was trying to understand the formula for determinants. Specifically, I wanted to know why n!permutations will have n!/2 odd permutations and n!/2 even permutations. The answer is in Lecture 12, Theorem 5.7 but I started from Lecture 1 since I couldn't understand it. Hence, the reason I am not familiar with the cancellation law for groups. My module did briefly touch on set theory but did not mention injective or surjective functions. But I will definitely revisit your answer once I have sufficient background knowledge to comprehend it. – Sara Oct 31 '11 at 17:30