Results 1 to 4 of 4

Math Help - Counting AUB

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    36

    Counting AUB

    How to prove lAUBl=lAl+lBl-lAnBl via a counting arguement. A,B finite sets

    Can we simply argue:In counting the elements of AUB, we count the elements in A,nA and the elements in B, nB. But in couting the elements of A and elements of B we have counted x elements twice since the sets intersect. Therefore, we subtract the duplicate, AnB. Then because A,B are finite sets, AnB and AUB are finite sets.

    I feel like this isn't a very strong proof. Is there a more rigorous way of proving the result?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,711
    Thanks
    1640
    Awards
    1
    Quote Originally Posted by qwerty10 View Post
    How to prove lAUBl=lAl+lBl-lAnBl via a counting arguement. A,B finite sets
    Can we simply argue:In counting the elements of AUB, we count the elements in A,nA and the elements in B, nB. But in couting the elements of A and elements of B we have counted x elements twice since the sets intersect. Therefore, we subtract the duplicate, AnB. Then because A,B are finite sets, AnB and AUB are finite sets.
    That is essentially correct.
    Any element in A\cap B is counted once when counting
    A then again when when counting B.
    The subtraction removes the over-count.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    36
    Thanks
    Would this be a sufficient enough reasoning when proving the base case n=2 of the inclusion-exclusion principle?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,711
    Thanks
    1640
    Awards
    1
    Yes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. counting 1
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 8th 2011, 08:01 AM
  2. Counting
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 9th 2010, 04:34 AM
  3. Counting
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 9th 2010, 05:19 PM
  4. help on Counting
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 08:51 AM
  5. Counting
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 10th 2009, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum