I am trying to understand transitive relations.
I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive.
But for longer sets I am getting confused in finding out if it is transitive.
So if I had a set: $\{(1,1)(1,3)(1,5)(2,2)(2,4)(3,1)(3,3)(3,5)(4,2)(4,4)(5,1)(5,3)(5,5)\}$
For example: I have $\{(1,3)\}$ and $\{(3,5)\}$ which means I need $\{(1,5)\}$ which I do.
But to prove it is transitive would I need $\{(1,1)\}$ having $\{(1,3)(3,1)\}$?
Also how many transitive relations are within that set?
Best Answer
Heres a nice theorem which helps in determining whether or not a relation is transitive. Let's define a relation $\mathbf{R}$ on a set $A$. We know that this defines a relation $\mathbf{R}:A \longrightarrow A$. Now, we want to prove that $\mathbf{R}$ is a transitive relation.
Theorem: $\mathbf{R}$ is a transitive relation if and only if $\mathbf{R}^{n} \subseteq \mathbf{R}$ for every positive integer $n$.
$\mathbf{Proof} (\longrightarrow)$:(via mathematical induction)
Suppose $\mathbf{R}$ is a transitive relation. Define the propositional function $P(n)$ such that $P(n)$ implies that $\mathbf{R}^{n} \subseteq \mathbf{R}$. Now we check the base case: $n=1$. Since $\mathbf{R}^{1}=\mathbf{R}$, it follows that $\mathbf{R}^{1} \subseteq \mathbf{R}$ and so $P(1)$ is true. We now must show that if $P(n)$ is true, then $P(n+1)$ is true. In other words, if $\mathbf{R}^{n} \subseteq \mathbf{R}$ then $\mathbf{R}^{n+1} \subseteq \mathbf{R}$. Let $\alpha,\beta \in A$ such that $\alpha$ and $\beta$ are related under $\mathbf{R}^{n+1}$. More compactly, we may write this as $(\alpha, \beta) \in \mathbf{R}^{n+1}$. Recall that $\mathbf{R}^{n+1}$ is the composition of $\mathbf{R}^{n}$ and $\mathbf{R}$; in other words: $\mathbf{R}^{n+1} = \mathbf{R}^{n} \circ \mathbf{R}$. Now, since $(\alpha,\beta) \in \mathbf{R}^{n+1}$, it follows from the definition of a transitive relation that there exists $\theta \in A$ such that $(\alpha,\theta) \in \mathbf{R}$ and $(\theta, \beta) \in \mathbf{R}^{n}$. Since $\mathbf{R}^{n} \subseteq \mathbf{R}$, we know that $(\theta, \beta) \in \mathbf{R}$. Since we defined $\mathbf{R}$ as a transitive relation, it follows that $(\alpha ,\beta) \in \mathbf{R}$. Therefore $\mathbf{R}^{n+1} \subseteq \mathbf{R}$.
$\mathbf{Proof} (\longleftarrow)$:
Let $a,b,c \in \mathbf{R}$ such that $(a,b) \in \mathbf{R}$ and $(b,c) \in \mathbf{R}$. Now can compose $\mathbf{R}$ with itself; in other words, take $\mathbf{R} \circ \mathbf{R}$. If we do so, then $(a,c) \in \mathbf{R} \circ \mathbf{R} = \mathbf{R}^{2}$. By hypothesis,$\mathbf{R}^{2} \subseteq \mathbf{R}$, and thus $(a,c) \in \mathbf{R}$. Therefore $\mathbf{R}$ is transitive.
This completes the proof.
Now you have posed a very insightful question regarding the number of transitive relations on a set. Until now, the only way to compute the number of transitive relations is to find them via brute-force methodology: counting transitive relations is an open problem in combinatorics!
Hope this helped.