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.
Best Answer
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.