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.
(1, 1)if you had(1, 3), (3, 1)(you would also need(3, 3), just so you know). In the case of a list of ordered pairs like yours, you actually have to check every single pair of pairs, see if they make a "demand" of transitivity (i.e. one of them ends with the same number the other begins with), and check whether that demanded pair is actually an element of the relation. If your relation is rather given as a general description, that'd take a different strategy. $\endgroup$(3,3)in my example? or the{(1,3)(3,1)}example, or both? $\endgroup$(3, 3)in the{(1, 3),(3, 1)}-example. Because you can read it the "other way", that is{(3, 1), (1, 3)}, so you need(3, 3)as well. In your big example, you just have to check that for every pair of pairs(a, b), (b, c)you also have(a, c). You have(1, 3), (3, 5)therefore you need(1, 5)and so on. $\endgroup$