Friday, May 10, 2019

An infinite chain can't have two ends

Say that a chain C is a collection of nodes with the following properties:

  1. Each node is directly connected to at most two other nodes.

  2. If x is directly connected to y then y is directly connected to x (symmetry).

  3. C is globally connected in the sense that for any non-empty proper subset S of C, there is a node in S and a node outside of S that are directly connected to each other.

(This is a different sense of “chain” from the one in Zorn’s Lemma.)

Fun fact: Every infinite chain has at most one endpoint, where an endpoint is a node that is directly connected to only one other node.

I.e., one cannot join two nodes with an infinite chain.

Corollary: We cannot join two events by an infinite chain of instances of immediate causation.

I've occasionally wondered if there is a useful generalization of transitive closure to allow for infinite chains, and to my intuition the fact above suggests that there isn't.

No comments: