1

A relation $R$ has a "chain" that connects $a$ to $b$ if there exists some sort of

$$(a, x_0),(x_0, x_1),\cdots,(x_{n-1}, x_n),(x_n,b)$$

made out of the elements in $R$. Why doesn't there exist a relation with an infinitely long chain?

My first idea to create a counterexample started with $(0,1)$, and repeatedly replacing $(0,a)$ with $(0,a/2),(a/2,a)$, doing so infinitely many times. Then there exists an infinitely long chain from $0$ to $1$, but then you can no longer tell what $0$ is related to so it breaks down.

The question arose after seeing my book's definition for transitive closure, which appears to imply that such chains are always finite.

For any $2$ binary relations $R$ and $R'$ on a set $S$ we define the composition of $R$ and $R'$ as the binary relation $R\circ R'$ on $S$ such that for any $x,y\in S$ we have

$$(x,y)\in R\circ R'\Leftrightarrow\exists z\in S. (x,z)\in R'\land(z,y)\in R$$

Let $R^1=R$ and define the $m^{th}$ iterate of $R$ as $R^m=R\circ R^{m-1}$ for any integer $m>1$. Furthermore, define the transitive closure of R by

$$Tran(R)=\bigcup_{m\in\mathbb{N}}R^m$$

Community
  • 1
user137794
  • 2,469
  • 1
    In brief, it's a matter of definition - chains are defined as finite entities. If you're wondering why, you might want to revise your question slightly to angle it that way. (And my rough take on it would be that the notion of an 'infinitely long' chain of necessity involves a limiting process that's not the least clear on the abstract entities where one often defines relations.) – Steven Stadnicki Mar 03 '15 at 02:01

1 Answers1

2

The transitive closure of a relation is the minimal transitive relation extending the given relation. Finite chains suffice for defining the transitive closure, that is, if we augment the given relation by pairs related by finite chains, then the result is already transitive. There is no need to consider infinite chains.

A different issue is the one raised by Steven Stadnicki – when would you say that $x$ and $y$ are related by an infinite chain? This is not at all clear. However, in the theory of linear orderings, such definitions are given. Say that $x,y$ are finitely related if there is a (finite) chain connecting them. We can form the condensed linear ordering by taking equivalence classes, and then iterate the construction. If $x,y$ are finitely related after the first condensation, then we can say that they are infinitely related with respect to the original relation.

As a concrete example, we can say that $x,y$ are minimally infinitely related if there are sequences $x_i,y_i$ such that $$ x R x_1 R x_2 R x_3 R \cdots, \\ \cdots R y_3 R y_2 R y_1 R y, $$ $x_i R y_j$ for all $i,j$, and for any $x R z R y$, either $z = x_i$ or $z = y_i$ for some $i$.

Given this, we can say that $x,y$ are infinitely related if there is a finite chain from $x$ to $y$ in which two adjacent elements are minimally infinitely related. We can repeat this construction again to get more notions of relatedness. For the full story, see Rosenstein's Linear orderings.

Yuval Filmus
  • 57,157