Results 1 to 2 of 2

Math Help - Inclusion/Exclusion

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    66

    Inclusion/Exclusion

    I've been working on this problem for a while. Could someone show me how to connect the last part?

    Let A, B, and C be finite sets. Prove:
    If |A \cup B \cup C| = |A| + |B| + |C|
    then A, B, and C must be pairwise disjoint.


    Here is what I have:

    Suppose A, B, and C are finite sets with |A \cup B \cup C| = |A| + |B| + |C|.

    By inclusion/exclusion, we know that

    |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

    By cancellation, we have:

    |A \cap B \cap C| - |A \cap B| - |A \cap C| - |B \cap C| = 0

    I'm just not sure how to connect that to "Thus A, B, and C must be pairwise disjoint."
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by absvalue View Post
    I've been working on this problem for a while. Could someone show me how to connect the last part?

    Let A, B, and C be finite sets. Prove:
    If |A \cup B \cup C| = |A| + |B| + |C|
    then A, B, and C must be pairwise disjoint.


    Here is what I have:

    Suppose A, B, and C are finite sets with |A \cup B \cup C| = |A| + |B| + |C|.

    By inclusion/exclusion, we know that

    |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

    By cancellation, we have:

    |A \cap B \cap C| - |A \cap B| - |A \cap C| - |B \cap C| = 0

    I'm just not sure how to connect that to "Thus A, B, and C must be pairwise disjoint."

    Well, A \cap B \cap C \subset A\cap B , so rearranging

    <br />
 |A \cap C| + |B \cap C| = |A \cap B \cap C| - |A \cap B| \le 0<br />

    since the LHS must be non negative we have  |A \cap C| + |B \cap C| = 0 so both of those terms must be 0. You can do a similar thing with to get |A \cap B| = 0 proving the result.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2011, 10:38 AM
  2. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 19th 2011, 03:49 AM
  3. inclusion & exclusion help
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 14th 2010, 09:57 AM
  4. Inclusion-exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 28th 2009, 02:45 AM
  5. inclusion/exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 18th 2008, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum