Reachability Relation

The reachability relation is connected to a given relation and shows whether one element is reachable from another through direct or indirect connections in sequence. This concept is closely related to the transitive closure.

Formal Definition

Let R be a relation on a set A. The reachability relation R* is defined such that (a,b) ∈ R* if and only if there exists a finite chain a = x₀, x₁, …, xₙ = b of elements where each (x_i, x_{i+1}) ∈ R.

This includes the empty chain for reflexivity: every element reaches itself (n=0, R^0 = identity).

Graphical Interpretation

In graph terms, if we represent the relation R as a directed graph (vertices = elements of A, edges = pairs in R), then the reachability relation R* consists of all pairs (a,b) where there is a directed path from a to b in the graph.

Example: Let A = {a,b,c}, R = {(a,b), (b,c)}. Then R* = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c)}, because a reaches b directly, b reaches c directly, and a reaches c via b.

Properties

• The reachability relation is always reflexive.
• The reachability relation is always transitive.
• If the original relation is symmetric, the reachability relation will also be symmetric.
• The reachability relation corresponds to the reflexive transitive closure of the relation.

Summary

The reachability relation shows whether one element is reachable from another through direct or indirect connection chains. This concept is fundamental in graph theory, algorithms, and network analysis.

Practice Exercise