Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

🔗

Section 11.3 Some General Properties of Groups

🔗
In this section, we will present some of the most basic theorems of group theory. Keep in mind that each of these theorems tells us something about every group. We will illustrate this point with concrete examples at the close of the section.
🔗

Subsection 11.3.1 First Theorems

🔗
One difficulty that students often encounter is how to get started in proving a theorem like this. The difficulty is certainly not in the theorem’s complexity. It’s too terse! Before actually starting the proof, we rephrase the theorem so that the implication it states is clear.
(Indirect): Suppose that f∈G, f≠e, and f is an identity of G. We will show that f=e, which is a contradiction, completing the proof.
f=f∗e Since e is an identity=e Since f is an identity
🔗
Next we justify the phrase “... the inverse of an element of a group.”
🔗
The same problem is encountered here as in the previous theorem. We will leave it to the reader to rephrase this theorem. The proof is also left to the reader to write out in detail. Here is a hint: If b and c are both inverses of a, then you can prove that b=c. If you have difficulty with this proof, note that we have already proven it in a concrete setting in Chapter 5.
🔗
As mentioned above, the significance of Theorem 11.3.3 is that we can refer to the inverse of an element without ambiguity. The notation for the inverse of a is usually a−1 (note the exception below).
  1. In any group, e−1 is the inverse of the identity e, which always is e.
  2. (a−1)−1 is the inverse of a−1 , which is always equal to a (see Theorem 11.3.5 below).
  3. (x∗y∗z)−1 is the inverse of x∗y∗z.
  4. In a concrete group with an operation that is based on addition, the inverse of a is usually written −a. For example, the inverse of k−3 in the group [Z;+] is written −(k−3)=3−k. In the group of 2×2 matrices over the real numbers under matrix addition, the inverse of (411−3) is written −(411−3), which equals (−4−1−13).
🔗
Again, we rephrase the theorem to make it clear how to proceed.
a=a∗ee is the identity of G=a∗(b∗c) because c is the inverse of b=(a∗b)∗c why?=e∗c why?=c by the identity property
🔗
The next theorem gives us a formula for the inverse of a∗b. This formula should be familiar. In Chapter 5 we saw that if A and B are invertible matrices, then (AB)−1=B−1A−1.
Let x=b−1∗a−1. We will prove that x inverts a∗b. Since we know that the inverse is unique, we will have proved the theorem.
(a∗b)∗x=(a∗b)∗(b−1∗a−1)=a∗(b∗(b−1∗a−1))=a∗((b∗b−1)∗a−1)=a∗(e∗a−1)=a∗a−1=e
Similarly, x∗(a∗b)=e; therefore, (a∗b)−1=x=b−1∗a−1
We will prove the left cancellation law. The right law can be proved in exactly the same way. Starting with a∗b=a∗c, we can operate on both a∗b and a∗c on the left with a−1:
a−1∗(a∗b)=a−1∗(a∗c)
Applying the associative property to both sides we get
(a−1∗a)∗b=(a−1∗a)∗c⇒e∗b=e∗c⇒b=c
We prove the theorem only for a∗x=b, since the second statement is proven identically.
a∗x=b=e∗b=(a∗a−1)∗b=a∗(a−1∗b)
By the cancellation law, we can conclude that x=a−1∗b.
If c and d are two solutions of the equation a∗x=b, then a∗c=b=a∗d and, by the cancellation law, c=d. This verifies that a−1∗b is the only solution of a∗x=b.
🔗

Note 11.3.10.

🔗
🔗
Our proof of Theorem 11.3.9 was analogous to solving the concrete equation 4x=9 in the following way:
4x=9=(4⋅14)9=4(149)
🔗
Therefore, by cancelling 4,
x=14⋅9=94
🔗

Subsection 11.3.2 Exponents

🔗
🔗
If a is an element of a group G, then we establish the notation that
a∗a=a2a∗a∗a=a3etc.
🔗
In addition, we allow negative exponents and define, for example,
a−2=(a2)−1
🔗
Although this should be clear, proving exponentiation properties requires a more precise recursive definition.
🔗

Definition 11.3.11. Exponentiation in Groups.

🔗
For n≥0, define an recursively by a0=e and if n>0,an=an−1∗a. Also, if n>1, a−n=(an)−1.
  1. In the group of positive real numbers with multiplication,
    53=52⋅5=(51⋅5)⋅5=((50⋅5)⋅5)⋅5=((1⋅5)⋅5)⋅5=5⋅5⋅5=125
    and
    5−3=(125)−1=1125
  2. In a group with addition, we use a different form of notation, reflecting the fact that in addition repeated terms are multiples, not powers. For example, in [Z;+], a+a is written as 2a, a+a+a is written as 3a, etc. The inverse of a multiple of a such as −(a+a+a+a+a)=−(5a) is written as (−5)a.
🔗
Although we define, for example, a5=a4∗a, we need to be able to extract the single factor on the left. The following lemma justifies doing precisely that.
(By induction): If n=0,
b1=b0∗b by the definition of exponentiation=e∗b by the basis for exponentiation=b∗e by the identity property=b∗b0 by the basis for exponentiation
Now assume the formula of the lemma is true for some n≥0.
b(n+1)+1=b(n+1)∗b by the definition of exponentiation=(b∗bn)∗b by the induction hypothesis=b∗(bn∗b) associativity=b∗(bn+1) definition of exponentiation
🔗
Based on the definitions for exponentiation above, there are several properties that can be proven. They are all identical to the exponentiation properties from elementary algebra.
We will leave the proofs of these properties to the reader. All three parts can be done by induction. For example the proof of the second part would start by defining the proposition p(m) , m≥0, to be an+m=an∗am for all n. The basis is p(0):an+0=an∗a0.
🔗
Our final theorem is the only one that contains a hypothesis about the group in question. The theorem only applies to finite groups.
Consider the list a,a2,…,an+1 . Since there are n+1 elements of G in this list, there must be some duplication. Suppose that ap=aq, with p<q. Let m=q−p. Then
am=aq−p=aq∗a−p=aq∗(ap)−1=aq∗(aq)−1=e
Furthermore, since 1≤p<q≤n+1, m=q−p≤n.
🔗
🔗
Consider the concrete group [Z;+]. All of the theorems that we have stated in this section except for the last one say something about Z. Among the facts that we conclude from the theorems about Z are:
  • 🔗
    Since the inverse of 5 is −5, the inverse of −5 is 5.
  • 🔗
    The inverse of −6+71 is −(71)+−(−6)=−71+6.
  • 🔗
    The solution of 12+x=22 is x=−12+22.
  • 🔗
    −4(6)+2(6)=(−4+2)(6)=−2(6)=−(2)(6).
  • 🔗
    7(4(3))=(7⋅4)(3)=28(3) (twenty-eight 3s).
🔗

Exercises 11.3.3 Exercises

🔗

1.

🔗
🔗
Let [G;∗] be a group and a be an element of G. Define f:G→G by f(x)=a∗x.
  1. 🔗
    Prove that f is a bijection.
  2. 🔗
    On the basis of part a, describe a set of bijections on the set of integers.
Answer.
  1. f is injective:
    f(x)=f(y)⇒a∗x=a∗y⇒x=y by left cancellation.
    f is surjective: For all b∈G, f(x)=b has the solution a−1∗b.
  2. Functions of the form f(x)=a+x, where a is any integer, are bijections
🔗

3.

🔗
Prove by induction on n that if a1, a2,…,an are elements of a group G, n≥2, then (a1∗a2∗⋯∗an)−1=an−1∗⋯∗a2−1∗a1−1. Interpret this result in terms of [Z;+] and [R∗;⋅].
Answer.
Basis: (n=2) (a1∗a2)−1=a2−1∗a1−1 by Theorem 11.3.7.
Induction: Assume that for some n≥2,
(a1∗a2∗⋯∗an)−1=an−1∗⋯∗a2−1∗a1−1
We must show that
(a1∗a2∗⋯∗an∗an+1)−1=an+1−1∗an−1∗⋯∗a2−1∗a1−1
This can be accomplished as follows:
(a1∗a2∗⋯∗an∗an+1)−1=((a1∗a2∗⋯∗an)∗an+1)−1 by the associative law=an+1−1∗(a1∗a2∗⋯∗an)−1 by the basis=an+1−1∗(an−1∗⋯∗a2−1∗a1−1) by the induction hypothesis=an+1−1∗an−1∗⋯∗a2−1∗a1−1 by the associative law
🔗

4.

🔗
True or false? If a, b, c are elements of a group G, and a∗b=c∗a, then b=c. Explain your answer.
🔗

5.

Answer.
In this answer, we will refer to Lemma 11.3.13 simply as “the lemma.”
  1. Let p(n) be a−n=(a−1)n, where a is any element of group [G;∗]. First we will prove that p(n) is true for all n≥0.
    Basis: If n=0, Using the definition of the zero exponent, (a0)−1=e−1=e, while (a−1)0=e. Therefore, p(0) is true.
    Induction: Assume that for some n≥0, p(n) is true.
    (an+1)−1=(an∗a)−1 by the definition of exponentiation=a−1∗(an)−1 by the lemma=a−1∗(a−1)n by the induction hypothesis=(a−1)n+1 by the lemma
    If n is negative, then −n is positive and
    a−n=(((a−1)−1)−n)=(a−1)−(−n) since the property is true for positive numbers=(a−1)n
  2. For m>1, let p(m) be an+m=an∗am for all n≥1. The basis for this proof follows directly from the basis for the definition of exponentiation.
    Induction: Assume that for some m>1, p(m) is true. Then
    an+(m+1)=a(n+m)+1 by the associativity of integer addition=an+m∗a1 by the definition of exponentiation=(an∗am)∗a1 by the induction hypothesis=an∗(am∗a1) by associativity=an∗am+1 by the definition of exponentiation
    To complete the proof, you need to consider the cases where m and/or n are negative.
  3. Let p(m)be (an)m=anm for all integers n.
    Basis: (am)0=e and am⋅0=a0=e therefore, p(0) is true.
    Induction; Assume that p(m) is true for some m>0,
    (an)m+1=(an)m∗an by the definition of exponentiation=anm∗an by the induction hypothesis=anm+n by part (b) of this proof=an(m+1)
    Finally, if m is negative, we can verify that (an)m=anm using many of the same steps as the positive case.
🔗

6.

🔗
🔗
Each of the following facts can be derived by identifying a certain group and then applying one of the theorems of this section to it. For each fact, list the group and the theorem that are used.
  1. 🔗
    (13)5 is the only solution of 3x=5.
  2. 🔗
    −(−(−18))=−18.
  3. 🔗
    If A,B,C are 3×3 matrices over the real numbers, with A+B=A+C, then B=C.
  4. 🔗
    There is only one subset K of the natural numbers for which K⊕A=A for every subset A of the natural numbers.
<Prev^TopNext>