A binary relation $\mathcal R$ over a set $A$ is transitive if and only if $\mathcal R$ is equal to its transitive closure $\mathcal R^{+}$.

Question

Given a binary relation $\mathcal R$ over a set $A$,then the $\mathsf {Transitive \;Closure}$ of $\mathcal R$ over $A$ is the smallest transitive relation on $A$ containing $\mathcal R$, it's indeed the intersection of all transitive relations over $A$ that are a superset of $\mathcal R$.

The transitive closure of $\mathcal R$ is denoted by $\mathcal R^{+}$ and has the following explicit formula: $$\mathcal R^{+}=\bigcup_{n=1}^{\infty} \mathcal R^n$$

Where $\mathcal R^1=\mathcal R$, and

$\mathcal R^{n+1}=\mathcal R^n ∘ \mathcal R^1\tag{$n \in \mathbb N^+$}$

---

Theorem: A binary relation $\mathcal R$ over a set $A$ is transitive if and only if $\mathcal R$ is equal to its transitive closure $\mathcal R^{+}$.

$\Longrightarrow$

Assume $\mathcal R$ is transitive,then by the definition of transitive closure $\mathcal R \subseteq \mathcal R^{+}$,it's left to show that $\mathcal R^+ \subseteq \mathcal R$.For the sake of contradiction assume exists $a,b$ in $A$ such that $(a,b) \in \mathcal R^+ \setminus \mathcal R$,then there are two cases two consider:

• $\exists \;c \in A:(b,c) \in \mathcal R$
• Such $c$ for which $(b,c) \in \mathcal R$ does not exist.

If the first case happens then since $\mathcal R \subseteq \mathcal R^{+}$ and $\mathcal R^{+}$ is transitive follows $(a,c) \in \mathcal R^{+}$,if such ordered pair does exist,then $\mathcal R^+=\mathcal R \cup \mathcal F$,where $\mathcal F$ is a set containing $(a,b),(a,c)$.Define a transitive relation $\mathcal R^{'}:=\mathcal R$ (the transitivity of $\mathcal R^{'}$ follows from the transitivity of $\mathcal R$),clearly $\mathcal R^+ \not \subseteq \mathcal R^{'}$.Contradicts the definition of transitive closure as the smallest.

If the ordered pair $(a,c)$ does not exist in $\mathcal R^+$,then it contradicts the transitivity of the transitive closure.

If the second case happens then $\mathcal R^+=\mathcal R \cup \mathcal F'$,where $\mathcal F'$ is a set containing $(a,b)$.Define a transitive relation $\mathcal R^{'}:=\mathcal R$ (the transitivity of $\mathcal R^{'}$ follows from the transitivity of $\mathcal R$),clearly $R^+ \not \subseteq \mathcal R^{'}$.Contradicts the definition of transitive closure as the smallest.

Implies $\mathcal R^+ \subseteq \mathcal R$, also since $\mathcal R \subseteq \mathcal R^+$ follows $$\mathcal R^+=\mathcal R$$

$\Longleftarrow$

If $\mathcal R=\mathcal R^+$,then the definition of transitive closure implies $\mathcal R^+$ is transitive and from the equality we conclude that $\mathcal R$ is also transitive. $\;\blacksquare$

---

The theorem is indeed based on my conjecture and I could not find any kind of proof about the theorem.It would be appreciated if someone check the proof.

Answer 1

Your proof can be streamlined. You suppose $\mathcal{R}^{+} \setminus \mathcal{R} \neq \emptyset$. Then you use that $\mathcal{R}^{+}$ is the smallest transitive relation containing $\mathcal{R}$, but this is not the case because $\mathcal{R}$ is transitive and $\mathcal{R}^{+} \not\subseteq \mathcal{R}$. So the whole case distinction is not needed and the construction using $\mathcal{F}$ is not needed.

---

If you use the fact that the transitive closure of $\mathcal{R}$ is equal to the intersection of all transitive relations containing $\mathcal{R}$, then there is an alternative proof.

Define the set $Tr=\{\text{transitive relation }\mathcal{S}\text{ over }A \mid \mathcal{R} \subseteq \mathcal{S}\}$.

Our above fact above becomes $\mathcal{R}^{+}=\bigcap_{\mathcal{S} \in Tr} \mathcal{S}$.

$\Rightarrow$

Since $\mathcal{R}$ is transitive and it contains $\mathcal{R}$, we know that $\mathcal{R} \in Tr$, hence $\mathcal{R}^{+} \subseteq \mathcal{R}$. Because $\mathcal{R} \subseteq \mathcal{S}$ for all $\mathcal{S} \in Tr$, we have that $\mathcal{R} \subseteq \mathcal{R}^{+}$.

$\Leftarrow$

Since $\mathcal{R}=\mathcal{R}^{+}$ and $\mathcal{R}^{+}$ is transitive, so is $\mathcal{R}$. $\quad\blacksquare$

---

For completeness, a proof of the above fact (using the definition of transitive closure as the smallest transitive relation containing the original)

Let $\mathcal{R}^{+}$ the smallest transitive relation, and let $\mathcal{R}^{\cap}$ be the intersection of all transitive relations containing $\mathcal{R}$. By definition of smallest, $\mathcal{R}^{+} \subseteq \mathcal{R}^{\cap}$. Now, since $\mathcal{R} \subseteq \mathcal{R}^{+}$ and $\mathcal{R}^{+}$ is transitive, $\mathcal{R}^{+}$ is one of the sets in the intersection of $\mathcal{R}^{\cap}$; hence $\mathcal{R}^{\cap} \subseteq \mathcal{R}^{+}$. $\quad \blacksquare$

This proof uses that the smallest transitive relation exists. If there is not a smallest transitive relation, then there are multiple minimal transitive relations (because the power set lattice is complete). You can take the intersection of these minimal elements to get a smaller transitive relation, thus getting a contradiction.

Answer 2

As requested, I will post shortened version of your proof. But first I want to reiterate the main points in my comments. Your proof breaks into two directions: $\Rightarrow$ and $\Leftarrow$. The $\Rightarrow$ direction breaks into two cases. Here are the key assumptions that distinguish the two cases:

Case 1: There is $c\in A$ such that $(b,c)\in \mathcal{R}$.

Case 2: There is no $c\in A$ such that $(b,c)\in\mathcal{R}$.

Then, in both cases, you obtain a contradiction to the initial assumption that $(a,b)\in\mathcal{R}^+\setminus\mathcal{R}$. So the important question to ask yourself is: When obtaining a contradiction, where exactly do you use the fact that you have distinguished these two cases? In other words, where do you use the existence or non-existences of $c$?

The answer is "nowhere". The separation of cases has no bearing on the rest of the proof, and in fact, your arguments for a contradiction in the two cases are mathematically identical (despite insignificant differences like between $\mathcal{F}$ vs $\mathcal{F}'$).

So below I will rewrite your proof to demonstrate this in detail, but it should be obvious at this point. I am going to keep some of the same wording and notation that you use so that it resembles what you wrote, but there are further simplifications you can make as detailed in the footnotes. The point is as given in the accepted answer: $\mathcal{R}^+$ is defined to be the intersection of all transitive relations containing $\mathcal{R}$. So it contains $\mathcal{R}$ by definition. Moreover, if $\mathcal{R}$ is transitive then $\mathcal{R}$ is one of the relations in the collection whose intersection is $\mathcal{R}^+$. So if $\mathcal{R}$ is transitive then $\mathcal{R}^+\subseteq\mathcal{R}$.

On the other hand, I have removed the notation involved with naming the set $\mathcal{R}^+\setminus\mathcal{R}$ with $\mathcal{F}$ and/or $\mathcal{F}'$. This is completely superfluous.

So here is a shortened version of the $\Rightarrow$ direction of your proof. I modify case 2.

Assume $\mathcal{R}$ is transitive.$^1$ First, by the definition of transitive closure, $\mathcal{R}\subseteq\mathcal{R}^+$. It is left to show that $\mathcal{R}^+\subseteq\mathcal{R}$. For the sake of contradiction, assume there exists $a,b\in A$ such that $(a,b)\in\mathcal{R}^+\setminus\mathcal{R}$. Define a transitive relation $\mathcal{R}':=\mathcal{R}$ (the transitivity of $\mathcal{R}'$ follows from the transitivity of $\mathcal{R}$).$^2$ By choice of $a,b$,$^3$ $\mathcal{R}^+\not\subseteq\mathcal{R}$. This contradicts the definition of transitive closure as the smallest transitive relation containing $\mathcal{R}$.

This implies $\mathcal{R}^+\subseteq\mathcal{R}$. Also, since $\mathcal{R}\subseteq\mathcal{R}^+$, it follows that $\mathcal{R}^+=\mathcal{R}$.$^4$

---

$^1$ Notice that I put a sentence break here. In your proof, you say "assume $\mathcal{R}$ is transitive, then by the definition of transitive closure $\mathcal{R}\subseteq\mathcal{R}^+$..." This makes it sound like the conclusion that $\mathcal{R}\subseteq\mathcal{R}^+$ also requires the assumption that $\mathcal{R}$ is transitive, rather than just the definition of transitive closure.

$^2$ I use this phrasing to keep it similar to your proof. But notice that there is really no need to redefine $\mathcal{R}'$. You can just say "$\mathcal{R}$ is a transitive relation that contains $\mathcal{R}$ (trivially) but doesn't contain $\mathcal{}R^+$, contradiction."

$^3$ At this point in your proof, you say "clearly". But you might as well be specific. Especially since, the way your proof is currently written, you fix $a$ and $b$ and then never reference them directly again. On the other hand, this also demonstrates why there is no need to specifically name $a$ and $b$. You only need to know that $\mathcal{R}^+\setminus\mathcal{R}$ is nonempty (as in the accepted answer).

$^4$ I have made this last part a bit more grammatically correct.