If $R$ is transitive, then $R^+$ exists. In fact, $R^+ = R$.

75 Views Asked by At

If $R$ is transitive, then $R^+$ exists. In fact, $R^+ = R$.

So for this question. I was wondering If I had the correct approach. My thinking went like this: Suppose $R$ is transitive.

$R^+$ means it is the smallest transitive x that contains $R$ as a subset. By definition, $R^+$ is the smallest transitive of $R$. It contains itself as a subset. So therefore, $R^+ = R$.

1

There are 1 best solutions below

0
On

The idea you present is in spirit correct, but you need to write more precisely. For instance you write

$R^{+}$ means it is the smallest transitive x that contains R as a subset

but probably mean "$R^{+}$ is the smallest transitive relation on the set $X$ that contains $R$ as a subset".

By definition, $R^{+}$ is the smallest transitive of $R$

means exactly the same thing as that which you wrote in the previous sentence. And by continuing with

It contains itself as a subset.

You are only saying that "$R^{+}$ contains itself as a subset" which is probably not what you wanted to say but this in turn does not justify the punchline $R^{+}=R$.

As such it is difficult to judge the correctness of what you have written.


If I were to write up the idea which I think you are trying to convey it would be:

Suppose that $R$ is a transitive relation on a set $X$. By definition, $R^{+}$ is the smallest transitive relation on $X$ that contains $R$ as a subset. Since $R$ is a transitive relation on $X$ that contains $R$, $R^{+}\subseteq R$. Then we get $R\subseteq R^{+}\subseteq R$ so $R^{+} = R$.