| From: ROLL::USENET "USENET Newsgroup Distributor" 4-SEP-1984 22:04
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.math
Path: decwrl!decvax!dartvax!chuck
Subject: re: trivial proof about groups
Posted: Mon Sep 3 10:35:38 1984
<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
|
| I'm still working on this one (having deliberately not read reply .1) as I
really love a neat group theory problem. So far the following observations
have occurred...
(1) Clearly the two sets MUST intersect, furthermore this intersection
must contain a non-identity element if the sum is not to cover
G.
(2) Given a group G, and a subset A, the set of elements of G such that
gA = A is in fact a subgroup of G - if G is finite.
proof...
iA = A - hence the identity is 'in'.
(xy)A = x(yA) = xA = A - closure
i/x = x**n for some n, hence
(i/x)A = (x**n)A = A - inverse
/Bevin
|
| Yeah, I found a simple proof....
Given two subsets, A and B, of a finite group G, such that A+B is a true subset
of G show |A| + |B| <= |G|.
Since A+B is a true subset, choose x from G-(A+B).
Now A must have no intersection with {x}-B else (x-b) + b is in A+B, and =x
Hence A is a subset of G-({x}-B)
Hence |A| <= |G| - |{x}-B| = |G| - |B|
Hence |A| + |B| <= |G|
/Bevin
|
|
Ooops - bad notation in previous response, for "G-({x}-B)" read "G intersection
complement {x}-B", I had two different meanings for "-".
I must look up and see which math symbols are in the multinational char set
for my VT200...
I looked at .1, and its the same proof except worded differently and headig
towards a totally unnecessary contradiction.
/Bevin
|