Homework Help: Proof about finite group

1. Jun 1, 2017

fishturtle1

1. The problem statement, all variables and given/known data
Prove in any finite group G, the number of elements not equal to their own inverse is an even number.

2. Relevant equations
if ab = ba = e, then a = b-1 and b = a-1

3. The attempt at a solution
Let S, A, B, be subsets of G where S = A + B.

Let a ∈ A s.t. there exists a unique b ∈ B so that
ab = ba = e and a =/= b.

Then |A| = |B| = k, k ∈ ℤ.

Then |S| = |A| + |B| = k + k = 2k.

And the definition of even is 2k, so |S| will always be even. []

How can I make this better?

2. Jun 1, 2017

andrewkirk

We can't just assume that there exist elements of A with the property following the 's.t.'. We need to prove it.
This step has not been justified.

The problem is a bit trickier than it first appears.

Are you familiar with the notion of equivalence relations and equivalence classes? Because
an approach that appeals to me is to define a relation $\sim$ on G such that $(a \sim b) \Leftrightarrow (a=b)\vee (a=b^{-1}$ (where $\vee$ means OR). We then show that $\sim$ is an equivalence relation, which is pretty easy, to show that it satisfies the three properties in the link. Hence $\sim$ partitions G into a collection of equivalence classes. The classes of size 1 are the self-inverse elements. If we can prove that no equivalence class can have size larger than two, we will be finished, since the non-self-inverse elements are partitioned in a collection of disjoint equivalence classes of size two.

Say we have three elements $a,b,c$ in an equivalence class so that $a\sim b, b\sim c,c\sim a$. Assume further that $a\neq b$. With that, can you prove that $c$ is equal to either $a$ or $b$? If so then we have proven that no equivalence class can contain three distinct elements, so that the largest equivalence class has size two.

3. Jun 1, 2017

fishturtle1

Ok i've tried but am stuck showing R is an equivalence relation. Maybe the way I defined R is wrong because I don't think this relation can be shown to be reflexive.

Goal: Show that a set R has an even amount of elements.

R = { (a,b) | ab = e Λ ba = e} .. I'm pretty sure this will make it so a = b or b-1

Now to show that R is an equivalence relation, I must show:

1) (a,a) ∈ R (reflexive)
2) (a, b) ∈ R <-> (b,a) ∈ R (symmetry)
3) if (a,b) and (b,c) ∈ R, then (a, c) ∈ R (transitive)

1) I don't think this relation is reflexive. If reflexive means that every element in G maps to itself, then this won't be true if there exists an (a,b) where a = a and b =/= a.

2) case 1: show (a,b) ∈ R -> (b,a) ∈ R.

if (a,b) ∈ R then ab = e and ba = e.
substitute a = b and b = a:
ba = e and ab = e. So case 1 is true.

case 2: show (b,a) ∈ R -> (a,b) ∈ R
if (b,a) ∈ R then ba = e and ab = e.
substitute b = a and a = b.
so ab = e and ba = e. So case 2 is true.

so (a,b) ∈ R <-> (b,a) ∈ R is true.(symmetry)

3) if (a,b) ∈ R and (b,c) ∈ R then (a, c) ∈ R.

so we know ab = e and ba = e and bc = e and cb = e.
We want to show ac = e and ca = e.

ba = bc
b-1ba = b-1bc
a = c

and a = c <=> c = a..and this satisfies (a = b) or ( a = b-1) so the relation R is transitive .

Did I define the relation right or am I just confused about reflexiveness?

4. Jun 1, 2017

andrewkirk

You are not incorrect about reflexivity, but the relation is defined incorrectly. Under your definition, two elements are equivalent iff they are inverses of one another. My suggestion was to define a relation that is true iff the two are inverses of one another OR equal to one another. It is the part after the OR that gives us reflexivity.

5. Jun 2, 2017

fishturtle1

Let G be a finite group.
R = { (a,b) ∈ G x G | (a = b-1) ∨ (a = b)}

Show G is reflexive, symmetric, and transitive.

1) show for all a ∈ G, ∃(a,a) ∈ R.

for (a,a) to be in R, it needs to satisfy the statements: a = b-1 or a = b, ab = e and ba = e

the statement a = b is true because (a,a) implies a = a and b = a. So a = b because by substitution, a = a.

So G is reflexive.

2) show a R b <=> b R a.

case 1:
ab = e
abb-1 = b-1
a = b-1
aa-1 = b-1a-1
e = b-1a-1
a = b-1a-1a
a = b-1
ba = bb-1
ba = e

case 2:

ba = e
baa-1 = a-1
b = a-1
bb-1 = a-1b-1
e = a-1b-1
a = aa-1b-1
a = b-1
ab = b-1b
ab = e

So G is symmetric.

3) show if (a,b) and (b,c) ∈ R then (a,c) ∈ R.

We know ab = e and cb = e,

ab = cb
a = c
therefore (a,c) ∈ R, and (a,c) satisfies (a = b-1) ∨ (a = b), so G is transitive

So G can be split into equivalence classes since R is an equivalence relation.

Let their be an equivalence class of [a, b, c]. Also a =/= b, a ~ b, b ~ c, c ~ a.

Therefore ab = e and ba = e.
and ca = ac.

So b and c are inverses of a. But the inverse is unique. Therefore b = c.

So any equivalence class [a, b, c, d, ...] where a =/= b, there can only be 2 unique elements which are a and b, since all the remaining elements will just equal a or b.
Therefore any equivalence class where a =/= b is of size 2, so the set of all these elements will always be a product of 2 => it will be even.

6. Jun 2, 2017

andrewkirk

That's pretty close. But the cases considered in the Symmetric part (2) should be (i) $a=b^{-1}$ and (ii) $a=b$, rather than the two cases written above.

Similarly, in the transitive part (3), starting with the assumption $a\neq b$, which together with $a\sim b$ implies $a=b^{-1}$, the cases that need to be considered are (i) $b=c^{-1}$ and (ii)$b=c$.

7. Jun 3, 2017

fishturtle1

I think I get it, I was showing symmetry and transitivity as if the relation required ab = e and ba = e but I should be showing a = b-1 and/or a = b because that's how the relation is defined.

so to re do 2) and 3):

2) show if (a,b) ∈ R then (b, a) ∈ R.
Check the cases where (a,b) ∈ R to see if (b,a) ∈ R. (b,a) ∈ R iff (b = a) ∨ (b = a-1)

case1: a = b

a = b
then b = a.

case2: a = b-1
ab = b-1b
ab = e
a-1ab = a-1
b = a-1

For both cases where a R b, b R a. Therefore G is symmetric.

3) show if (a,b) and (b,c) ∈ R where a =/= b, then (a,c) ∈ R.

So we need to check 2 cases: a = c and a = c-1, if either case is true given (a,b) and (b,c) ∈ R, then (a,c) ∈ R.

case1: we know b = c-1

b = c-1
ab = ac-1
we also know a = b-1, so substitute:
b-1b = ac-1
e = ac-1
c = a.

case 2: we know b = c
ab = ac
and we know b = a-1, so substitute:
aa-1 = ac
e = ac
c-1 = a
a = c-1.

case1 and case2 are true, therefore G is transitive.

8. Jun 3, 2017

WWGD

Try using associativity: If ab=e , then aba=a(ba)=a.....

9. Jun 3, 2017

fishturtle1

Thank you for the response. I think you mean for me to try to prove this a different way, using associativity.

Outline:
Goal: Prove in any finite group G, the number of elements not equal to their own inverse is an even number.

Let G be a finite group where a, b ∈ G.

if ab = e then aha = a(ba) = a

a(ba) = a
a-1aba = a-1a
eba = e
ba = e
b-1ba = b-1
ea = b-1
a = b-1, so a and b are inverses of each other.

Consider a = b-1 where a does not equal its own inverse <=> a =/= b (I don't want to consider a = b because that would mean b = b-1)

a = b-1
ab = b-1b
ab = e
a-1ab = a-1
eb = a-1
b = a-1, where b = a-1 =/= b-1, because if a-1 = b-1 then a = b.

So for every ai ∈ G there exists an bk ∈ G where ai = bk-1 and bk = ai-1.
if ai =/= ai-1 then bk =/= bk-1

also ,
for every bk ∈ G there exists an ai ∈ G where bk = ai-1 and ai = bk-1.
if bk =/= bk-1 then ai =/= ai-1

Let A = {a0, a1, ...},
and B ={b0, b1, ...}
From the bold statements, I think we can conclude |A| = |B|, and |A| = k, k ∈ ℤ and k ≥ 0

Let S = A + B.
Then |S| = 2k, and therefore S is even. So in any finite group G, the number of elements not equal to their own inverse is an even number.

10. Jun 4, 2017

WWGD

Yes, in a slightly-different way, we can assign numbers to the k elements of the n-element group that are not their own inverses, indexed so that $i<j$, so we have {$a_1, ...,a_k$} ; k< n ( since, e.g., e*e=e ). Then we pair $a_i, a_j ; i \neq j$ if $a_i * a_j = e ; i<j$ ( re-write the indices so that a_i *a_{i+1} are an inverse pair)

Then we have the inverse pairs { $(a_1, a_2),..,(a_3, a_4),..(a_k, a_{k+1})$} ; k< n+1 . But then we also have the inverse pairs:
{ $(a_2, a_1),..,(a_4, a_3),..(a_{k+1}, a_k)$}

Ultimately, for every inverse pair (a,b) ; $a \neq b$ we also have the inverse pair (b,a) , which shows evenness of the total.

Last edited: Jun 4, 2017
11. Jun 4, 2017

fishturtle1

Ok I get what you are saying, but is the above post a proof or do I need to translate it into a proof?

12. Jun 4, 2017

WWGD

I would say, for something more rigorous, assign numbers to elements in G so that $g_i, g_{i+1} ; g_i*g_{i+1}=e$ , and start listing the inverse pairs, showing the evenness. Sorry, can't give an actual proof, violates this site's rules, but that is pretty much it. If you write it here, I will look at it and critique it.