# Order Theory/Series-parallel order

Definition (parallel order):

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

${\displaystyle 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 ${\displaystyle (S_{\alpha },\leq _{\alpha })_{\alpha \in A}}$ be a family of ordered sets, and define ${\displaystyle S:=\bigsqcup _{\alpha \in A}S_{\alpha }}$. Then the pair ${\displaystyle (S,\leq )}$, where ${\displaystyle \leq }$ is the parallel order on ${\displaystyle S}$, is called the parallel composition of the sets ${\displaystyle S_{\alpha }}$.

Definition (series order):

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

${\displaystyle 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 ${\displaystyle (A,\leq _{A})}$ be a preordered set, and let ${\displaystyle (S_{\alpha },\leq _{\alpha })_{\alpha \in A}}$ be a family of ordered sets, and define ${\displaystyle S:=\bigsqcup _{\alpha \in A}S_{\alpha }}$. Then the pair ${\displaystyle (S,\leq )}$, where ${\displaystyle \leq }$ is the series order on ${\displaystyle S}$, is called the series composition of the sets ${\displaystyle S_{\alpha }}$ over ${\displaystyle (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 ${\displaystyle (\{x_{\alpha }\},\leq _{\alpha })_{\alpha \in A}}$ (the ${\displaystyle \leq _{\alpha }}$ order being the order that turns ${\displaystyle (\{x_{\alpha }\},\leq _{\alpha })}$ into a poset) by applying parallel composition and series composition over ${\displaystyle A=(\{1,2\},\{(1,2)\})}$ a finite number of times.