chuck@dartvax.UUCP (Chuck Simmons) (09/03/84)
<Waiting for Fermat> > Given a group G and two subsets A and B with |A| + |B| > |G|, > prove that G = AB > > Obviously the group is finite and | | denotes the cardinality of the > various sets involved. (We use additive notation because it's hard to write multiplicative inverses.) How we do it: Suppose that the theorem is false. That is, suppose there exists some x in G such that x is not in A+B. We can use this hypothesis to construct a subset C of G such that A and C are disjoint and the cardinality of C is the same as the cardinality of B. But this is a contradiction because since A and C are disjoint subsets of G, we have |A|+|C| <= |G|. However, since |C| = |B| by construction, then by the hypothesis of the theorem we have |A|+|C| > |G|. Proof: Suppose the theorem is false. Then let x in G be given such that x is not in A+B. Let C be the set of all y in G such that y = x+(-b) for some b in B. Clearly, |C| = |B|. (If not, then there exist some distinct b1,b2 in B such that x+(-b1) = x+(-b2) implying b1=b2. #) Further, A and C are disjoint. (If they are not disjoint, then there exists some a in A such that a = x+(-b) for some b in B, which means a+b = x for some a in A and some b in B, which means x is in A+B. #) So we have A and C are disjoint subsets of G, thus |G| < |A|+|B| = |A|+|C| <= |G| giving us the desired contradiction. Thanks for posting this problem. Chuck