# Finite Sequences in Set Form Acyclic Graph

Jump to navigation
Jump to 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 $\set {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:

- $\card {\Dom p \symdif \Dom q} = 1$, where $\symdif$ is symmetric difference
- $p \restriction D = q \restriction D$, where $D = \Dom p \cap \Dom q$

Then $T = \struct{V, E}$ is an acyclic graph.