Finite Sequences in Set Form Acyclic Graph

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set.

Let $V$ be the set of finite sequences in $S$.

Let $E$ be the set of unordered pairs $\{p, q\}$ of elements of $V$ such that either:

$q$ is formed by extending $p$ by one element or
$p$ is formed by extending $q$ by one element.

That is:

$| \operatorname{Dom}(p) * \operatorname{Dom}(q) | = 1$, where $*$ is symmetric difference and
$p \restriction D = q \restriction D$, where $D = \operatorname{Dom}(p) \cap \operatorname{Dom}(q)$


Then $T = (V, E)$ is an acyclic graph.


Proof