# Transitive Relations

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

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

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

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

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

• Oct 8th 2010, 07: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 $\theta^*$ on $A$ as follows: for any $a,b \in A$, where $k \ge 2$ is an integer (which relies on $a$ and $b$), such that $a=a_1, b=a_k$ and $a_i \theta a_{i+1}$ for all $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 $a,b\in A$, define $a\theta^*b$ if there exist a sequence $a_1,\dots,a_k$ of elements of $A$ where $a=a_1, b=a_k$ and $a_i \theta a_{i+1}$ for all $i=1,2,...,k-1$".

Quote:

Originally Posted by lpd
Suppose $$ and $$ are in $\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 $a, b, c\in A$ and assume that $a\theta^* b$ and $b\theta^* c$.

Quote:

Originally Posted by lpd
By definition of $\theta^*$, $$ is in $\theta^m$ for some $m$

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

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

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

By definition of $\theta^*$,
$$ is in $\theta^m$ for some $m$
$$ is in $\theta^n$ for some $n$

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

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

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

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

Quote:

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

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

I was just wondering, wasn't I supposed to prove that a,b is transitive on $\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, 06:15 AM
emakarov
One can say "transitive" only about a relation. A pair of elements a,b cannot be transitive.

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