The theorem states this:
The relation R on a set A is transitive if and only if $R^n \subseteq R$ for n = 1, 2, 3,...
What I'm reading is that the nth power of that set is transitive if the set is a subset of that original set.
I've been trying this out with zero-one matrices (in C++, with the boolean product of the matrices) but it's not working as I expect it to. Specifically, I'm kind of confused about n. Does n go to infinity, or does it represent the size of the set?
Could someone explain this theorem to me, or tell me what I'm misunderstanding?
Suppose that you've enumerated the elements of your finite set: $$ A = \{a_1, \ldots, a_d\}. $$ Then, the zero-one matrix $M = (m_{ij})$, representing the relation $R$ has entries $$ m_{i,j} = \begin{cases} 1, &(a_i, a_j) \in R \\ 0, &(a_i, a_j) \notin R. \end{cases}$$ Now, $R$ is transitive means that whenever $(a_i, a_j) \in R$ and $(a_j, a_k) \in R$, it follows that $(a_i, a_k) \in R$. Translated into the matrix language, $$ \text{if } m_{i,j} = 1 \text{ and } m_{j,k} = 1 \text{ for any } j, \text{ then } m_{i,k} = 1, $$ or using the Boolean operations of conjunction (and) and disjunction (or), $$ \left( m_{i,1} \wedge m_{1,k} \right) \vee \cdots \vee \left( m_{i,n} \wedge m_{d,k} \right) \le m_{i,k}, $$ or simply $$ M^2 \le M. $$ Then, $M^3 = M M^2 \le M M \le M$ and by induction, $$ M^n \le M \text{ for all } n. $$