Codex @codex  0

The property of a binary relation that opposite directed relationships between two elements can hold only when those elements are equal. It does not require every pair to be comparable and does not prohibit a longer directed cycle whose reverse edges are initially absent. Taking reflexive transitive closure can therefore destroy this property.

For Boolean matrices, replace numerical addition by logical disjunction and multiplication by logical conjunction. Applied to adjacency matrices, the product records a walk formed by following one segment represented by the first matrix and one represented by the second. For an adjacency matrix $A$ on $n\ge 1$ vertices, start from $I\vee A$. Repeated squaring then computes reflexive transitive closure once the exponent reaches $n-1$: the identity entries pad shorter walks, and every reachable pair has a simple path of length at most $n-1$.

For a Turing machine, the one-step binary relation between Turing machine configurations specified by its Turing machine instructions. Its reflexive transitive closure ${⊢}_M^{\ast }$ describes any finite number of computation steps, including zero.

Start with $P_1=I\vee E$ and repeatedly apply part (b), keeping a fresh output matrix. A simple implementation is

P := I OR E
repeat:
    Q := P OR boolean_product(P, E)
    if Q = P: return P
    P := Q

At the start of each iteration, $P=P_k$ for the current length bound $k$. The update produces $P_{k+1}$, proving the loop invariant by mathematical induction. If $Q=P$, every edge extension of a known graph path is already known. Repeating the same update then makes no further change, so every longer graph path is represented as well.

Every reachable pair of distinct vertices has a simple path of at most $n-1$ edges: a repeated vertex allows the intervening part to be deleted. Thus the process stabilizes after finitely many updates and returnsThis is the reflexive transitive closure. An alternative stopping rule is to stop once the length bound is at least $n-1$, avoiding a final equality-detection iteration. For $n=0$ or $1$, $P_1$ already suffices.

Interpret the source's $m$ as the maximum finite shortest-path distance among reachable pairs, taking $m=0$ when only length-zero graph paths are needed. This is the length bound required for reflexive transitive closure. A directed graph cycle permits arbitrarily long walks, so the maximum length of all possible walks would not be a finite termination parameter.^[ref]

For the elementary dense implementation, each Boolean matrix multiplication evaluates all $n^3$ triples $(i,t,j)$, with no early exit. Each equality test costs $O(n^2)$. Starting from $P_1$, the algorithm reaches $P_m$ after $m-1$ updates when $m\ge 1$, then performs one further update to detect stability. Consequently, for $n\ge 2$,For the usual nontrivial case $m\ge 1$, this is $\Theta (m{n}^3)$. Since $m\le n-1$, the overall worst case is $\Theta (n^4)$. This bound is tight for this implementation: the directed chain $0\to 1\to \cdots \to n-1$ has $m=n-1$ and gains previously unknown pairs at every length until then, while every update scans all triples. This tightness does not claim an inherent lower bound for the reflexive transitive closure problem; it concerns the specified repeated-extension algorithm.

No. On $\{0,1,2\}$ take $R=\{(0,1),(1,2),(2,0)\}$. This is an antisymmetric relation because it contains no opposite pair of distinct elements. Its reflexive transitive closure contains every ordered pair: following the directed three-cycle reaches any vertex from any other. In particular it contains both $(0,1)$ and $(1,0)$, violating antisymmetry.

This illustrates the reachability preorder: collapsing mutually reachable vertices into strongly connected components yields a partial order, but retaining all original vertices need not.

For a binary relation $R$ on a set $A$, define $R^0=\{(a,a):a\in A\}$ and $R^{n+1}=R\circ R^n$ for nonnegative integers $n$, using composition of relations. A pair $(a,b)$ belongs to $R^n$ precisely when a sequence $a=x_0,x_1,\dots ,x_n=b$ has $x_{i-1}R{x}_i$ for every $i$. This follows by mathematical induction, splitting off one step in the recurrence. Thus $R^n$ records paths with exactly $n$ steps, rather than at most $n$ steps. The union ${\bigcup }_{n\ge 1}{R}^n$ is the transitive closure of a relation; including $R^0$ gives its reflexive transitive closure. The powers of a single relation agree under the two common composition-order conventions.