Prove: X Contains at Most n(n-1)/2 Elements in Subset of a Group

[the_fox]

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.

 

[morphism]

Hint: X is largest when a,b in A => ab in A.

 

[the_fox]

That's how X is defined. What exactly do you mean?

 

[BryanP]

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.