The Pigeon Hole Principle and the Finite Subgroup Test

Question

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?

Answer 1

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$.

Answer 2

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?

Answer 3

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.

Answer 4

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}$.

Answer 5

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.