1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about finite group

  1. Jun 1, 2017 #1
    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. jcsd
  3. Jun 1, 2017 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Jun 1, 2017 #3
    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?
     
  5. Jun 1, 2017 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Jun 2, 2017 #5
    Sorry about the late reply

    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.
     
  7. Jun 2, 2017 #6

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##.
     
  8. Jun 3, 2017 #7
    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.
     
  9. Jun 3, 2017 #8

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Try using associativity: If ab=e , then aba=a(ba)=a.....
     
  10. Jun 3, 2017 #9
    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.
     
  11. Jun 4, 2017 #10

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    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
  12. Jun 4, 2017 #11
    Ok I get what you are saying, but is the above post a proof or do I need to translate it into a proof?
     
  13. Jun 4, 2017 #12

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof about finite group
  1. Finite group proof (Replies: 2)

  2. Proof about a group (Replies: 3)

Loading...