1. ## 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

2. ## 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.

3. ## Re: Order relation

I tried,but didn't get something helpful

4. ## Re: Order relation

Originally Posted by hedi
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
Originally Posted by hedi
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.

5. ## 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$.