Results 1 to 2 of 2

Math Help - Need help with proving transitivity property

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    38

    Need help with proving transitivity property

    Here is the basic question:

    [n] = {1, 2, 3, ..., n}

    Define the relationship  \mathcal{R} on the powerset  \mathcal{P}([n]) by:  \forall sets  A, B \in  \mathcal{P}([n]), A \mathcal{R}B iff  A-B\subseteq{1,2}. Explain why this is transitive.

    I know transitivity means that  \forall A, B, C \in  \mathcal{P}([n]), if A \mathcal{R}B, B \mathcal{R}C, then A \mathcal{R}C


    This doesn't have to be a direct proof, it just says give reasons why it's transitive. So, I'm thinking of using an element argument, but that doesn't seem to cover everything. And there seems to be cases.

    Here's what I was thinking of saying:

    Suppose A is a set with arbitrary elements. Assuming A-B is a subset of {1, 2} and B-C is a subset of {1, 2}, there are two cases to consider.

    First case, if A has other elements that are not 1, 2, then those elements must be in B since A-B is a subset of {1, 2}. Since B - C is a subset of {1, 2}, those elements must also be in C. Thus, A-C would remove the elements that aren't 1 or 2.

    Second case, if A does not have other elements besides {1, 2}. Thus, no matter what B is, A-B is a subset of {1, 2} (even the empty set is a subset of {1, 2}, and similarly no matter what B-C is, it is also a subset of {1, 2}.


    I know, this sounds like a horrible explanation. Can anyone help me explain it better? Using a single element argument doesn't seem to work logically in my mind...

    Please and thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    First case, if A has other elements that are not 1, 2, then those elements must be in B since A-B is a subset of {1, 2}. Since B - C is a subset of {1, 2}, those elements must also be in C. Thus, A-C would remove the elements that aren't 1 or 2.
    I think this is correct, and this explanation works regardless whether A has other elements besides 1, 2. Any other elements, whether their set is empty or not, must be in B. (Recall that the empty set is a subset of any set.)

    A similar, but more formal, way to write this is the following.

    Lemma. A-B\subseteq\{1,2\}\Leftrightarrow A\subseteq B\cup\{1,2\}.
    Proof. ...

    Proof of transitivity. Suppose A-B\subseteq\{1,2\} and B-C\subseteq\{1,2\}. By Lemma, this means A\subseteq B\cup\{1,2\} and B\subseteq C\cup\{1,2\}. Therefore, A\subseteq B\cup\{1,2\}\subseteq C\cup\{1,2\}\cup\{1,2\}=C\cup\{1,2\}, which, again by Lemma, means that A-C\subseteq\{1,2\}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving linearity property of the integral.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 17th 2010, 05:19 AM
  2. Proving a property of a definition
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: January 7th 2010, 03:26 PM
  3. Proving a Property of Integrals
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 11th 2009, 07:31 AM
  4. Need help proving basic property of tensors
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: October 24th 2009, 10:53 AM
  5. Proving the second property of Density Functions
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: May 24th 2009, 02:30 AM

Search Tags


/mathhelpforum @mathhelpforum