# Order Theory/Series-parallel order

Definition (parallel order):

Let $(S_{\alpha },\leq _{\alpha })_{\alpha \in A}$ be a family of ordered sets, and define $S:=\bigsqcup _{\alpha \in A}S_{\alpha }$ . Then the parallel order on $S$ is defined to be the order

$s\leq t:\Leftrightarrow \left(\exists \alpha \in A:s\in S_{\alpha }\wedge t\in S_{\alpha }\right)\wedge s\leq _{\alpha }t$ .

Definition (parallel composition):

Let $(S_{\alpha },\leq _{\alpha })_{\alpha \in A}$ be a family of ordered sets, and define $S:=\bigsqcup _{\alpha \in A}S_{\alpha }$ . Then the pair $(S,\leq )$ , where $\leq$ is the parallel order on $S$ , is called the parallel composition of the sets $S_{\alpha }$ .

Definition (series order):

Let $(A,\leq _{A})$ be a preordered set, and let $(S_{\alpha },\leq _{\alpha })_{\alpha \in A}$ be a family of ordered sets over $A$ . The series order on $S:=\bigsqcup _{\alpha \in A}S_{\alpha }$ induced by $A$ is the order $\leq$ on $S$ given by

$s\leq t:\Leftrightarrow \left(\left(\exists \alpha \in A:s\in S_{\alpha }\wedge t\in S_{\alpha }\right)\wedge s\leq _{\alpha }t\right)\vee \exists \alpha ,\beta \in A:\alpha \leq \beta \wedge s\in S_{\alpha }\wedge t\in S_{\beta }$ .

Definition (series composition):

Let $(A,\leq _{A})$ be a preordered set, and let $(S_{\alpha },\leq _{\alpha })_{\alpha \in A}$ be a family of ordered sets, and define $S:=\bigsqcup _{\alpha \in A}S_{\alpha }$ . Then the pair $(S,\leq )$ , where $\leq$ is the series order on $S$ , is called the series composition of the sets $S_{\alpha }$ over $(A,\leq _{A})$ .

Definition (series-parallel order):

A series-parallel order is the order of an ordered set that arises from a family of singleton ordered sets $(\{x_{\alpha }\},\leq _{\alpha })_{\alpha \in A}$ (the $\leq _{\alpha }$ order being the order that turns $(\{x_{\alpha }\},\leq _{\alpha })$ into a poset) by applying parallel composition and series composition over $A=(\{1,2\},\{(1,2)\})$ a finite number of times.