# Transitive Relations

• Oct 8th 2010, 03:13 AM
lpd
Transitive Relations
Hi. I have this problem.

Let $\displaystyle \theta$ be a binary relation on a set $\displaystyle A$, which is not necessarily transitive.
Define a binary relation $\displaystyle \theta^*$ on $\displaystyle A$ as follows: for any $\displaystyle a,b \in A$, where $\displaystyle k \ge 2$ is an integer (which relies on $\displaystyle a$ and $\displaystyle b$), such that $\displaystyle a=a_1, b=a_k$ and $\displaystyle a_i \theta a_{i+1}$ for all $\displaystyle i=1,2,...,k-1$. $\displaystyle \theta*$ is called the transitive closure of $\displaystyle \theta$.
Prove that $\displaystyle \theta^*$ is a transitive relation on $\displaystyle A$.

This is what I did... but not sure if it really make sense though.

Suppose $\displaystyle <a_1, a_2>$ and $\displaystyle <a_2,a_k>$ are in $\displaystyle \theta^*$.
Show that $\displaystyle <a_1,a_k>$ is in $\displaystyle \theta^*$.
By definition of $\displaystyle \theta^*$,
$\displaystyle <a_1, a_2>$ is in $\displaystyle \theta^m$ for some $\displaystyle m$
$\displaystyle <a_2,a_k>$ is in $\displaystyle \theta^n$ for some $\displaystyle n$
Then $\displaystyle <a_1, a_k>$ is in $\displaystyle \theta^m\theta^n=\theta^{m+n}$ which is contained in $\displaystyle \theta^*$. Hence $\displaystyle \theta^*$ must be transitive. i.e. $\displaystyle \theta^*$ is a transitive relation on $\displaystyle A$.

What I'm not sure what I have done is choosing an artribrary number in the sequence between $\displaystyle a$ and $\displaystyle b$ is correct, it is where I chose $\displaystyle a_2$. Also shall I use $\displaystyle a_1$ and $\displaystyle a_k$ instead of $\displaystyle a$ and $\displaystyle b$ in my proof? Or should i just stick with $\displaystyle a$ and $\displaystyle b$?

• Oct 8th 2010, 06:57 AM
emakarov
OK, some critique. One of the main rules is that every variable must be introduced either by "for all", "any", etc. or "there exists", "some", etc.

Quote:

Originally Posted by lpd
Define a binary relation $\displaystyle \theta^*$ on $\displaystyle A$ as follows: for any $\displaystyle a,b \in A$, where $\displaystyle k \ge 2$ is an integer (which relies on $\displaystyle a$ and $\displaystyle b$), such that $\displaystyle a=a_1, b=a_k$ and $\displaystyle a_i \theta a_{i+1}$ for all $\displaystyle i=1,2,...,k-1$.

The structure of you sentence is as follows: For any a and b ..., where ..., such that ... and ... . What happens for any such a and b? Next, "where k is an integer (which relies on a and b)" is not good because it is not clear how precisely k relies on a and b. Finally, you did not introduce a_2, a_3, etc.

I would say: "for any $\displaystyle a,b\in A$, define $\displaystyle a\theta^*b$ if there exist a sequence $\displaystyle a_1,\dots,a_k$ of elements of $\displaystyle A$ where $\displaystyle a=a_1, b=a_k$ and $\displaystyle a_i \theta a_{i+1}$ for all $\displaystyle i=1,2,...,k-1$".

Quote:

Originally Posted by lpd
Suppose $\displaystyle <a_1, a_2>$ and $\displaystyle <a_2,a_k>$ are in $\displaystyle \theta^*$.

Now that the definition has ended, the scope of a, b, k, a_1, ..., a_k is closed and they are just names with no assigned meanings. The proof opens a new scope. So, to answer your question, it does not make sense to choose a_2 as an arbitrary element of the sequence between a and b. So far, a and b are undefined. You should say, e.g.: Consider arbitrary $\displaystyle a, b, c\in A$ and assume that $\displaystyle a\theta^* b$ and $\displaystyle b\theta^* c$.

Quote:

Originally Posted by lpd
By definition of $\displaystyle \theta^*$, $\displaystyle <a_1, a_2>$ is in $\displaystyle \theta^m$ for some $\displaystyle m$

I think a remark about the relationship between $\displaystyle \theta^*$ and $\displaystyle \theta^m$ for various $\displaystyle m$ would be merited since the actual definition does not mention powers of $\displaystyle \theta$. This relationship may seem obvious to a sophisticated reader, but our discussion is not at that level.
• Oct 8th 2010, 05:36 PM
lpd
Cool. This is just what I needed! Need help with constructing a proof! Okay, let me try again.

For any $\displaystyle a,b\in A$, define $\displaystyle a\theta^*b$ if there exist a sequence $\displaystyle a_1,\dots,a_k$ of elements of $\displaystyle A$ where $\displaystyle a=a_1, b=a_k$ and $\displaystyle a_i \theta a_{i+1}$ for all $\displaystyle i=1,2,...,k-1$.

Consider arbitrary $\displaystyle a, b, c\in A$ and assume that $\displaystyle a\theta^* b$ and $\displaystyle b\theta^* c$

By definition of $\displaystyle \theta^*$,
$\displaystyle <a, c>$ is in $\displaystyle \theta^m$ for some $\displaystyle m$
$\displaystyle <c,b>$ is in $\displaystyle \theta^n$ for some $\displaystyle n$

Then $\displaystyle <a, b>$ is in $\displaystyle \theta^m\theta^n=\theta^{m+n}$ which is contained in $\displaystyle \theta^*$. Hence $\displaystyle \theta^*$ must be transitive. i.e. $\displaystyle \theta^*$ is a transitive relation on $\displaystyle A$.

(What should I write for the explaination of $\displaystyle \theta^m$? Should I say something along the lines of... as $\displaystyle \theta^m$ for some $\displaystyle m$ is defined by the artibrary values of $\displaystyle <a, c>$.)
• Oct 9th 2010, 04:27 AM
emakarov
Quote:

Should I say something along the lines of... as $\displaystyle \theta^m$ for some $\displaystyle m$ is defined by the artibrary values of $\displaystyle <a, c>$.
I did not understand this phrase, namely, what it means to be "defined by".

After the definition of $\displaystyle \theta^*$, I would say: "Note that by definition of $\displaystyle \theta^m$, $\displaystyle a\theta^*b$ iff there exists an $\displaystyle m$ such that $\displaystyle a\theta^mb$. In particular, $\displaystyle \theta^m\subseteq\theta^*$ for all $\displaystyle m$." Otherwise, I repeat that saying "By definition of $\displaystyle \theta^*$, $\displaystyle <a, c>$
is in $\displaystyle \theta^m$ for some $\displaystyle m$" looks strange since the definition of $\displaystyle \theta^*$ does not mention powers of $\displaystyle \theta$.

Quote:

Consider arbitrary $\displaystyle a, b, c\in A$ and assume that $\displaystyle a\theta^* b$ and $\displaystyle b\theta^* c$

By definition of $\displaystyle \theta^*$,
$\displaystyle <a, c>$ is in $\displaystyle \theta^m$ for some $\displaystyle m$
$\displaystyle <c,b>$ is in $\displaystyle \theta^n$ for some $\displaystyle n$
It should say that $\displaystyle \langle a,b\rangle\in\theta^m$ and $\displaystyle \langle b,c\rangle\in\theta^n$, not $\displaystyle \langle a,c\rangle$ and $\displaystyle \langle c,b\rangle$.
• Oct 9th 2010, 04:43 AM
lpd
Thanks for that.

I was just wondering, wasn't I supposed to prove that a,b is transitive on $\displaystyle \theta^*$, because a is at the start of the sequence, and b is the end?

Edit: is it because if we show that if a,c is transitive, then the sequence, a, b will also?
• Oct 9th 2010, 05:15 AM
emakarov
One can say "transitive" only about a relation. A pair of elements a,b cannot be transitive.

When proving that $\displaystyle \theta^*$ is transitive, you assume that $\displaystyle \langle a,b\rangle \in\theta^*$ and $\displaystyle \langle b,c\rangle \in\theta^*$ for some a,b,c. This means that $\displaystyle \langle a,b\rangle \in\theta^m$ and $\displaystyle \langle b,c\rangle \in\theta^n$ for some m,n. It does not imply that $\displaystyle \langle a,c\rangle \in\theta^m$ and $\displaystyle \langle c,b\rangle \in\theta^n$ for some m,n.