Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Subset of a group

  1. Oct 22, 2008 #1
    Let G be a group and A a subset of G with n elements such that if x is in A then x^(-1) is not in A. Let X={(a,b) a in A, b in A, ab in A}. Prove that X contains at most n(n-1)/2 elements.
  2. jcsd
  3. Oct 22, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hint: X is largest when a,b in A => ab in A.
  4. Oct 23, 2008 #3
    That's how X is defined. What exactly do you mean?
  5. Oct 31, 2008 #4
    Let's see what we are given. We have G as a group and A as a subset of G. Thus, since G is a group, we have the following giveaways:

    1) G is closed under the binary operation
    2) G is associative under the binary operation
    3) G has an identity element
    4) G has an inverse for each element

    A is a subset of G with n elements, such that each element has it's inverse NOT contained in the set.

    Since A is just a subset of G, we cannot assume that it will have an identity (this is only a giveaway if it were a subgroup). Thus, we will have some sort of a max here, meaning, there is a version of A that has the identity, and a version without the identity.

    This matters because the inverse of an identity is itself. Thus if we have A with an identity, we'd have to remove it completely from the set since a = a^-1 and a^-1 is not permitted in A. This gives us (n-1) elements.

    Now, what happens when A does NOT have the identity? This means you have n elements since each a in A is not a self-inverse.

    Thus you have to account for a set that factors in self-inverses, and a set that doesn't. Getting the number of non-inverses just amounts to taking half of the given number of elements of the particular set (since we know through G that each element of A does have an inverse).

    Try applying this to X.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?