Theorem: Order extraction

For every $D\in \mathcal{D}({\mathcal{P}}_{3q})$:

1. ${\sim }_D$ is an equivalence relation;

2. (eq:component-order) is well defined and is a partial order;

3. each experiment contributes between one and three components;

4. $E_D$ is countably infinite, and every chain has at most three distinct elements.

Proof. Reflexivity and transitivity of reachability show reflexivity and transitivity of ${\sim }_D$; symmetry is built into its definition.

Suppose $p{\sim }_D{p}^{\prime }$, $q{\sim }_D{q}^{\prime }$, and $p{⇝}_{D}q$. Concatenating paths gives

Thus the order is independent of representatives. It is reflexive and transitive. If both $[p]{⪯}_D[q]$ and $[q]{⪯}_D[p]$, then $p{\sim }_{D}q$, proving antisymmetry.

A graph on three vertices has between one and three strongly connected components. No component contains vertices from different identifiers, since a nontrivial path cannot change identifier. There are countably many nonempty experiment blocks, so their disjoint union is countably infinite. Every chain lies within one block and hence contains at most three distinct elements.