Results 1 to 5 of 5

Thread: Order relation

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    211
    Thanks
    15

    Order relation

    Hey,
    Define the following relation T on P(N),(N is the set of all natural numbers):

    (A,B) is in T if and only if the smallest element of the symmetric difference (A/B)U(B/A) belongs to B.
    prove that T is transitive
    Thank's in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,608
    Thanks
    1714

    Re: Order relation

    Hey hedi.

    Have you expanded out the set differences? You should get something similar to what is an exclusive or [XOR] but for sets.

    The idea is that it contains what is one or the other but not both.

    The natural numbers have a standard ordering which means you can get the XOR by looking at two intervals of numbers.

    Then you will need to apply standard rules regarding transitive relations to do the rest of it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    211
    Thanks
    15

    Re: Order relation

    I tried,but didn't get something helpful
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,168
    Thanks
    3066
    Awards
    1

    Re: Order relation

    Quote Originally Posted by hedi View Post
    Hey,
    Define the following relation T on P(N),(N is the set of all natural numbers):
    (A,B) is in T if and only if the smallest element of the symmetric difference (A/B)U(B/A) belongs to B.
    prove that T is transitive
    Thank's in advance
    Quote Originally Posted by hedi View Post
    I tried,but didn't get something helpful
    Notation: $(A\Delta B)=(A\setminus B)\cup(B\setminus A)$
    $\mathcal{T}$ is truly an interesting relation.
    It is irreflexive. Can you prove that?
    If $(A,B)\in\mathcal{T}$ then for $x=\min\{A\Delta B)$ then we know that:
    $x\in B ~\&~x\notin A$ Can you explain that? So $\mathcal{T}$ is antisymmetric.

    Suppose that $(A,B)\in\mathcal{T}~\&~(B,C)\in\mathcal{T}$ can you show that $(A,C)\in\mathcal{T}~?$
    If $x=\min\{A\Delta B),~y=\min\{B\Delta C)~\&~z=\min\{A\Delta C)$ how are $x,~y,~\&~z$ related to one another given the above?
    If we can show that $z\in C$ then we are done. I have not done that.
    Last edited by Plato; Jan 8th 2018 at 06:19 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Order relation

    Let $A,B,C \in P(\mathbb{N})$ such that $(A,B), (B,C) \in T$.
    We want to show that $(A,C) \in T$.

    Let $n_1 = \text{min}\left( A \setminus B \cup B \setminus A \right)$ and $n_2 = \text{min}\left( B \setminus C \cup C \setminus B\right)$.

    Suppose $n_3 = \text{min}(A \setminus C \cup C \setminus A)$. If $n_3 \notin C$, then $n_3 \in A$. Since $n_3$ is not the minimum of $A\setminus B \cup B\setminus A$ (since $n_1 \notin A$), it must be that $n_3 \in B$. Since $n_3$ is not the minimum of $B \setminus C \cup C \setminus B$ (since $n_2 \notin B$), it must be that $n_3 \in C$. However, this is a contradiction to it being in $A\setminus C \cup C \setminus A$. Therefore, $n_3 \in C$, which shows $(A,C) \in T$.

    This is just a rough sketch of the proof, but it should give you the general idea of it. This only works in certain cases (you may need to split this up into several cases). For instance, I know this works when $n_2 \in A$ and $n_1\in C$.
    Last edited by SlipEternal; Jan 8th 2018 at 06:42 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partial order relation: lub and glb
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 17th 2012, 11:35 PM
  2. Order Relation
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 19th 2012, 06:52 AM
  3. 3rd Order Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 26th 2011, 04:44 AM
  4. last two problems. order relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2006, 02:30 PM
  5. Order/Relation Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2006, 10:51 AM

/mathhelpforum @mathhelpforum