Results 1 to 1 of 1

Math Help - Computing number of elements of finite union of finite sets.

  1. #1
    Member
    Joined
    Feb 2009
    Posts
    138

    Computing number of elements of finite union of finite sets.

    Hi:
    Let M:= {A_1, A_2, ..., A_m} be a set of a subsets of a given finite set G, and let E be a subset of G of only one element, that is |E|=1. If for any two elements of M their intersection is E, then the number of elements of the union over M, that is C:= A_1 U A_2 U ... U A_m, is |A_1| - 1 + |A_2| - 1 + ... + |A_m| -1 + 1 (that is, |C| = |A_1| + |A_2| + ... + |A_m| - m + 1).

    This is so obvious to me that I can't find a way to prove it. For every i, A_i \ E has |A_i| - 1 elements. And the A_i \ E together with E form a partition of C. That is, U (A_i \ E) U E = C and for any i, j, A_i \ E and A_j \ E are disjoint sets. Hence |C| = |A_1 \ E| + ... + |A_m \ E| + |E| which agrees with the statement. OK. But does the fact that the A_i \ E together with E form a partition of C not need to be proved? This is my question then.

    In fact what I need to prove is that given a finite group G and a collection of m subgroups of G, each having b elements, such that any two of them intersect trivially, then the number of elements of the union is m (b-1) + 1. But I think this is a particular case of the statement above.

    EDIT: I think I've got it. That A_i \ E and A_j \ E are disjoint is trivial (too obvious). And U (A_i \ E) U E = U (A_i \ E) U E U E U ... U E (m times) = U ((A_i \ E) U E) (by the associativity of the union) = U (A_i U E) = U A_i (because E = A_i intersection A_j subset of A_i and then A_i U E = A_i) = C. Hence the A_i \ E together with E are indeed a partition of C.
    Last edited by ENRIQUESTEFANINI; May 28th 2013 at 09:04 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finite union of compact sets is compact
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 8th 2011, 08:43 PM
  2. Replies: 2
    Last Post: September 30th 2010, 01:57 PM
  3. how many elements are in the union of four sets...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 29th 2008, 11:02 PM
  4. finite ring with an odd number of invertible elements
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 28th 2008, 11:36 AM
  5. Finite size if finite number of subgroups
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: March 9th 2006, 01:32 PM

Search Tags


/mathhelpforum @mathhelpforum