Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site dartvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!decvax!dartvax!chuck
From: chuck@dartvax.UUCP (Chuck Simmons)
Newsgroups: net.math
Subject: re:  trivial proof about groups
Message-ID: <2364@dartvax.UUCP>
Date: Mon, 3-Sep-84 13:35:38 EDT
Article-I.D.: dartvax.2364
Posted: Mon Sep  3 13:35:38 1984
Date-Received: Thu, 6-Sep-84 03:43:44 EDT
Organization: Dartmouth College
Lines: 35

<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