The Role of Counting Quantifiers in Laminar Set Systems

Let $S\subseteq V(T)\setminus L$ be a thin set and let $i\in \{0,1,2,3\}$ be the index such that ${\delta }_T(s)=i$ for every $s\in S$ which exists by (TS1). Let $P$ be the set of all nodes which are parents of a node in $S$. Note that every $p\in P$ satisfies ${\delta }_T(p)\equiv i-1mod4$. We show that for every $s\in S$ we can choose a representative tree $H_s$, which avoids all nodes in $P$ (i.e. does not contain any node in $P$). This statement implies that the representative trees $H_s$ are pairwise disjoint. Clearly, since $H_s$ is a subtree of $T_s$ for every $s\in S$ by (RT1), $H_s$ and $H_{s^{\prime }}$ must be disjoint whenever $s,s^{\prime }\in S$ are not in any ancestor-descendant relationship. If, on the other hand, $s\in S$ is a proper ancestor of $s^{\prime }\in S$ then $H_s$ cannot intersect $T_{s^{\prime }}$ (and hence cannot intersect $H_{s^{\prime }}$) since $H_s$ avoids the parent of $s^{\prime }$.

We now describe how to construct $H_s$ which avoids $P$ for some fixed $s\in S$. We construct the tree $H_s$ recursively, level by level. The $0$-th level of $H_s$ consists of just $s$, which clearly avoids $P$. Assume that we have constructed $j$ levels of $H_s$ that avoid $P$ and aim to construct the $(j+1)$-th level. We distinguish the following cases. First, assume $j\equiv imod4$. In this case, for every node $t$ on level $j$ of $H_s$, which is not a leaf, we choose an arbitrary child $t^{\prime }$ of $t$ and add it to $H_s$. Note that the updated tree $H_s$ clearly still avoids $P$ as ${\delta }_T(t^{\prime })\equiv i+1mod4$ for every newly added node $t^{\prime }$ while nodes $p\in P$ satisfy ${\delta }_T(p)\equiv i-1mod4$. Next, assume that $j\equiv i+1mod4$. In this case, for every $t$ on level $j$ of $H_s$, which is not a leaf of $T$, we add all children of $t$ to $H_s$. Again, each newly added vertex $t^{\prime }$ cannot be contained in $P$ as they satisfy $\delta (t^{\prime })\equiv i+2mod4$. Next, we assume that $j\equiv i+2mod4$. In this case, for every node $t$ on level $j$ of $H_s$, which is not a leaf, we choose a child $t^{\prime }$ of $t$ which is not in $P$ and add it to $H_s$. This choice is always possible, as $S$ is thin and, therefore, every node $p\in P$ must have a sibling that does not have children in $S$ by (TS3) which implies that this child is not contained in $P$. Clearly, the updated tree $H_s$ avoids $P$. Finally, assume $j\equiv i+3mod4$. For every node $t$ on level $j$ of $H_s$, which is not a leaf, we add all its children to $H_s$. The resulting tree $H_s$ still must avoid $P$ as each newly added node $t^{\prime }$ satisfies ${\delta }_T(t^{\prime })=i$ while nodes $p\in P$ satisfy ${\delta }_T(p)\equiv i-1mod4$. Note that the tree $H_s$ is a representative tree of $s$ by construction because $s$ is the root of $H_s$ implying (RT1), for every node $t$ on level $j$ with $j\equiv imod2$ (unless $t$ is a leaf) we added exactly one child of $t$ to $H_s$ implying (RT2) and for every node $t$ on level $j$ with $j\not\equiv imod2$ (unless $t$ is a leaf) we added all children of $t$ to $H_s$ implying (RT3). For an illustration of the construction of representative trees of a thin set $S$ we refer the reader to Figure 2.

We can now set $A_s$ to be the leaves of $H_s$ for every $s\in S$. We argue that $H_{A_s}^{\uparrow }=H_s$. First note that because $s$ is the root of $H_s$ the least common ancestor of the leaves in $A_s$ is some descendant of $s$. By construction, there is exactly one child $t$ of $s$ which is contained in $H_s$ and therefore the least common ancestor of the leaves in $A_s$ is indeed a descendant of $t$. Let $t_1,\mathrm{\dots },t_{\mathrm{\ell }}$ be the children of $t$ and note that $\mathrm{\ell }\ge 2$ by Observation 9. By construction $t_1,\mathrm{\dots },t_{\mathrm{\ell }}$ are contained in $H_s$ (as $\delta (t)\equiv i+1mod4$). Since both the subtree of $H_s$ rooted at $t_1$ and the subtree of $H_s$ rooted at $t_2$ must have a leaf and therefore an element of $A_s$, the least common ancestor of the leaves in $A_s$ is $t$. Therefore the tip of $A_s$ is $s$. Hence, by definition of up-tree, we know that $H_{A_s}^{\uparrow }$ is a subtree of $H_s$ as $H_s$ contains all nodes in $A_s$ and the tip of $A_s$. Furthermore, every node $t$ contained in $H_s$ must be in $H_{A_s}^{\uparrow }$ because the subtree of $H_s$ rooted at $t$ must contain a leaf $t^{\prime }$ which, by construction, is in $A_s$. Then the path from $t^{\prime }$ to $s$ must be contained in $H_{A_s}^{\uparrow }$ implying that $t$ is in $H_{A_s}^{\uparrow }$. Since $H_{A_s}^{\uparrow }=H_s$ is a representative tree, $A_s$ is a representative set. Hence, we have chosen representative sets ${(A_s)}_{s\in S}$ with pairwise disjoint representative trees $H_{A_s}^{\uparrow }$ proving the statement. $◀$

We now aim to prove that given the union $A:={\bigcup }_{s\in S}{A}_s$ of representative sets of a thin set, the representative sets are uniquely defined. We further aim to characterize representative sets in such a way that we can later define them in $\mathrm{MSO}$. For this we use the following terminology. Given a set $B$ of leaves of $T$ we say that an inner-node $s\in V(T)\setminus L$ is fully-branched (by $B$) if for every child $t$ of $s$ the set of leaves in the subtree of $T$ with root $t$ contains a leaf from $B$. Additionally, we say that $s$ is single-branched (by $B$) if there is exactly one child $t$ of $s$ for which the subtree of $T$ rooted at $t$ contains a leaf from $B$. We say that $s$ is missed (by $B$) if the subtree of $T$ rooted at $s$ contains no leaves from $B$.

We start by proving parts of the forwards direction of the statement.

First, note that condition (i) is trivially satisfied. Additionally, (ii) is satisfied by the definition of representative sets. By definition $H_{A_s}^{\uparrow }$ is a representative tree. Observe that for any node $t$ of $H_{A_s}^{\uparrow }$ there is some leaf $v$ of $T_t$ that is contained in $H_{A_s}^{\uparrow }$ by the definition of representative trees. In particular, this implies that every node $t$ in $H_{A_s}^{\uparrow }$ with ${\delta }_T(t)\equiv {\delta }_T(s)mod2$ is either a leaf of $T$ or single-branched by $A_s$ and every node $t$ in $H_{A_s}^{\uparrow }$ with ${\delta }_T(t)\not\equiv {\delta }_T(s)mod2$ is either a leaf of $T$ or fully-branched. Since every inner node $t$ not contained in $H_{A_s}^{\uparrow }$ is missed by $A_s$, we obtain properties (iii)-(iv). $\mathrm{⊲}$ The essential property we use to prove the equivalence in the statement of the lemma is that the up-tree $H_B^{\uparrow }$ of any set $B$ satisfying the properties (i)-(iv) together with the tip of $B$ must be a subtree of $H_{A_s}^{\uparrow }$ for some $s\in S$. We prove this statement in two steps Claim 13 and Claim 14. Let $F^{\uparrow }$ be the forest obtained by taking the union of $H_{A_s}^{\uparrow }$ for all $s\in S$.

Let $i\in \{0,\mathrm{\dots },3\}$ such that $i={\delta }_T(s)$ for every $s\in S$ (note that $i$ is well defined as $S$ is thin). First note that by assumption the subtrees $H_{A_s}^{\uparrow }$ are pairwise disjoint and therefore are the connected components of $F^{\uparrow }$. Towards a contradiction assume the claim is not true and let $u,s\in V(F^{\uparrow })$ be nodes of $T$ such that $s$ is the child of $u$ in $T$, but the edge $us$ is not in $E(F^{\uparrow })$. In this case $s$ is the root of some tree of $F^{\uparrow }$ and in particular $s\in S$. Additionally, $u$ is a node in some tree $H_{\uparrow }^{u^{\prime }}$ with $u^{\prime }\in S$ and $u^{\prime }\ne s$. In particular, ${\delta }_T(s)={\delta }_T(u^{\prime })=i$. Since $u$ is the parent of $s$ this implies that ${\delta }_T(u^{\prime })\not\equiv {\delta }_T(u)mod2$. Since additionally $H_{\uparrow }^{u^{\prime }}$ is a representative tree, all children of $u$ must be contained in $H_{\uparrow }^{u^{\prime }}$. This contradicts the disjointness of representative trees, since $s$ is a child of $u$ and is contained in $H_{\uparrow }^s$. $\mathrm{⊲}$

Our argument essentially amounts to showing that there are not enough leaves from $A$ in any subtree of $T$ with root in $V(H_B^{\uparrow })\setminus V(F^{\uparrow })$ in order for $B$ to satisfy properties (i)-(iv). See Figure 3 for an illustration. To argue this formally, let $t$ be a node which is contained in $H_B^{\uparrow }$ but not in $F^{\uparrow }$ and has maximum depth with this property. Let $(p_0,p_1,\mathrm{\dots },p_{\mathrm{\ell }})$ with $p_0=s$ and $p_{\mathrm{\ell }}=t$ be the path in $H_B^{\uparrow }$ from $s$ to $t$. First observe that no node of $p_0,\mathrm{\dots },p_{\mathrm{\ell }}$ can be missed by $B$ as they are contained in $H_B^{\uparrow }$ which implies that at least one descendant must be contained in $B$ for each of $p_0,\mathrm{\dots },p_{\mathrm{\ell }}$. Property (ii) implies that $p_0=s$ is single-branched by $B$. By property (iv) and since $p_1$ cannot be missed or be a leaf, we conclude that $p_1$ is fully-branched. By property (iii) and because $p_2$ cannot be a leaf, this implies that $p_2$ is single-branched by $B$. Using a recursive argument, we conclude that $p_i$ must be fully-branched by $B$ if $i$ is odd and $p_i$ is single-branched by $B$ if $i$ is even for every $i\in \{0,\mathrm{\dots },\mathrm{\ell }\}$.

We can further argue the following property:

To see this, observe that for any node $t^{\prime }\in S$ and $u\in A_{t^{\prime }}\cap B$ the path between $t^{\prime }$ and $u$ must be fully contained in $F^{\uparrow }$. Since $t$ is not contained in $F^{\uparrow }$, we conclude that $t^{\prime }$ must be a proper descendant of $t$. Now, let $t^{\prime }\in S$ be any node that is contained in the subtree ${(H_B^{\uparrow })}_t$ of $H_B^{\uparrow }$ rooted at $t$. By Claim 13 we have that $H_{A_{t^{\prime }}}^{\uparrow }$ is a connected component of $F^{\uparrow }$. Since $F^{\uparrow }$ is an induced subgraph of $T$ by Claim 13, this implies that the parent $t^{\prime \prime }$ of $t^{\prime }$ cannot be contained in $F^{\uparrow }$. On the other hand, $t^{\prime \prime }$ must be contained in $H_B^{\uparrow }$ as $t$ is in the tree $H_B^{\uparrow }$ and $t$ is an ancestor of $t^{\prime \prime }$. Since we choose $t$ of maximum depth with the property of being in $H_B^{\uparrow }$ but not in $F^{\uparrow }$ this implies that $t^{\prime \prime }=t$. Therefore, every node in ${(H_B^{\uparrow })}_t$ that is contained in $S$ must be a child of $t$ and hence property $(\ast )$ holds. We now distinguish two cases.

First assume that $\mathrm{\ell }$ is odd and therefore $t=p_{\mathrm{\ell }}$ is fully-branched (see right two part of Figure 3). Hence, every child of $t$ must be the ancestor of a node in $B\subseteq A$. By property $(\ast )$, every child of $t$ must be contained in $S$. But this contradicts the fact that $S$ is thin.

On the other hand, assume $\mathrm{\ell }$ is even and, therefore, $t=p_{\mathrm{\ell }}$ is single-branched (see left part of Figure 3). Let $t^{\prime }$ be the child of $t$ that is either a leaf or fully branched, and which exists due to (iv). By statement $(\ast )$, we know that $t^{\prime }\in S$ and therefore cannot be a leaf as $S$ only contains inner nodes of $T$. Because $t^{\prime }\in S$ we know that $H_{A_{t^{\prime }}}^{\uparrow }$ is a representative tree and therefore $t^{\prime }$ has only one child contained in $H_{A_{t^{\prime }}}^{\uparrow }$ by (RT2). By Observation 9 $t^{\prime }$ has at least two children and hence there is a child $t^{\prime \prime }$ of $t^{\prime }$ such that $T_{t^{\prime \prime }}$ contains no leaves from $A_{t^{\prime }}$. On the other hand, by (iv) $t^{\prime }$ is fully-branched by $B$ (as $t$ is single-branched) and therefore there must be a leaf $u\in B\subseteq A$ in the subtree $T_{t^{\prime \prime }}$. In particular, $u\notin A_{t^{\prime }}$. But this contradicts the property $(\ast )$ as $t^{\prime }$ is the child of $t$ that is an ancestor of $u$. $\mathrm{⊲}$ Using the above claims we can now conclude the proof as follows. First assume $B=A_s$ for some $s\in S$. By Claim 12, $B$ and $s$ satisfy (i)-(iv). Presume that $B$ does not satisfy (v) and $B^{\prime }\supset B$ and node $s^{\prime }$ satisfy properties (i)-(iv). Combining Claim 14 and Claim 13, we know that $H_{B^{\prime }}^{\uparrow }$ must be a subtree of a connected component of $F^{\uparrow }$. More specifically, $H_{B^{\prime }}^{\uparrow }$ must be a subtree of $H_B^{\uparrow }=H_{A_s}^{\uparrow }$. This implies that $B^{\prime }\subseteq B$ which contradicts the assumption that $B^{\prime }$ is a proper superset of $B$.

On the other hand, assume $B\subseteq A$ and node $s$ satisfy conditions (i)-(iv). By Claim 14 and Claim 13, $H_B^{\uparrow }$ is a subtree of a connected component of $F^{\uparrow }$ which means that $H_B^{\uparrow }$ is a subtree of $H_{A_{s^{\prime }}}^{\uparrow }$ for some $s^{\prime }\in S$. In particular, this implies that $B\subseteq A_{s^{\prime }}$. Finally, $B$ must in fact be equal to $A_{s^{\prime }}$ because otherwise $A_{s^{\prime }}$ is a proper superset of $B$ which together with $s^{\prime }$ satisfies properties (i)-(iv) by Claim 12. Additionally, $s=s^{\prime }$ because $s$ is the tip of $B$ while $s^{\prime }$ is the tip of $A_{s^{\prime }}=B$ and hence $B=A_s$. $◀$

For every $i\in \{0,1,2,3\}$, let $V^i\subseteq V(T)\setminus L$ be the set of inner nodes with ${\delta }_T(t)=i$. We further denote the root of $T$ by $r$ and the children of $r$ by $s_1,\mathrm{\dots },s_{\mathrm{\ell }}$. We show that for every $i\in \{0,1,2,3\}$ we can partition $V^i$ into $4$ thin sets.

Hence fix $i\in \{0,1,2,3\}$ and let $j_1\equiv i-1mod4$ and $j_2\equiv i-2mod4$. We first partition $V^i$ into two sets $P^{\mathrm{𝖫𝖾𝖿𝗍}},P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ as follows. For every node $t\in V^{j_1}$ (these are the parents of nodes in $V^i$) consider the children $t_1,\mathrm{\dots },t_k$ of $t$ which are contained in $V^i$. Note that every child of $t$ is either a leaf of $T$ or contained in $V^i$. We add $t_1$ to $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ and $t_2,\mathrm{\dots },t_k$ to $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$. In case $t$ has only one child in $V^i$ (all other children are leaves of $T$), no node gets added to $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ and in case $t$ has no children in $V^i$ (all children of $t$ are leaves of $T$), neither $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ nor $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ receive an additional node. We further add $r$ to $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ if $i=0$ ($r$ is the only node in $V^i$ with no parent in $V^{j_1}$). By construction, the partition $(P^{\mathrm{𝖫𝖾𝖿𝗍}},P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}})$ of $V^i$ has the property that every node in $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ has a sibling which is not contained in $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ with the exception of $r$ in case $i=0$ and the same holds for $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$. For this we crucially rely on Observation 9 and additionally observe that the sibling of some node $t\in P^{\mathrm{𝖫𝖾𝖿𝗍}}$, which is not contained in $P^{\mathrm{𝖫𝖾𝖿𝗍}}$, can either be a leaf or contained in $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ and similarly for $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$.

We now refine the partition $(P^{\mathrm{𝖫𝖾𝖿𝗍}},P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}})$ of $V^i$ into a partition $(S^{\mathrm{𝖫𝖫}},S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}},S^{\mathrm{𝖱𝖱}})$ as follows. For every node $t$ in $V^{j_2}$ (these are grandparents of nodes in $V^i$) consider the children $t_1,\mathrm{\dots },t_k$ of $t$ that have at least one child in $V^i$ ($k$ could be $0$ if all children of $t$ are either leaves or only have leaves as children). For $t_1$ we put all children contained in $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ into $S^{\mathrm{𝖫𝖫}}$ and all children contained in $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ into $S^{\mathrm{𝖫𝖱}}$. Similarly, we put all children of $t_2,\mathrm{\dots },t_k$ which are contained in $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ into $S^{\mathrm{𝖱𝖫}}$ and all children of $t_2,\mathrm{\dots },t_k$ that are contained in $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ into $S^{\mathrm{𝖱𝖱}}$. Finally, $r$ gets added to $S^{\mathrm{𝖫𝖫}}$ in case $i=0$ and all children among $s_1,\mathrm{\dots },s_{\mathrm{\ell }}$ of $s$ contained in $P^{\mathrm{𝖫𝖾𝖿𝗍}}$ get added to $S^{\mathrm{𝖫𝖫}}$ while all children of $s$ contained in $P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}}$ get added to $S^{\mathrm{𝖫𝖱}}$ in case $i=1$ ($s,s_1,\mathrm{\dots },s_{\mathrm{\ell }}$ are all the nodes in $V^i$ that cannot have a grandparent in $V^{j_2}$). For an illustration of the construction, see Figure 4. We now argue that each set of the partition is thin.

Clearly $(S^{\mathrm{𝖫𝖫}},S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}},S^{\mathrm{𝖱𝖱}})$ is a refinement of $(P^{\mathrm{𝖫𝖾𝖿𝗍}},P^{\mathrm{𝖱𝗂𝗀𝗁𝗍}})$ and therefore still satisfies the condition that every node in $S^{\mathrm{\ell }}$ has a sibling that is not contained in $S^{\mathrm{\ell }}$, with the exception of $r\in S^{\mathrm{𝖫𝖫}}$ in the case $i=0$. Hence, $S^{\mathrm{𝖫𝖫}},S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}}$ and $S^{\mathrm{𝖱𝖱}}$ each satisfy condition (TS2). Furthermore, by construction, we also satisfy that the parent $p_t$ of every node $t\in S^{\mathrm{𝖫𝖫}}$ has a sibling which is not contained in $S^{\mathrm{𝖫𝖫}}$ with the exception of $r$ and $s_1,\mathrm{\dots },s_{\mathrm{\ell }}$ and the same holds for $S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}}$ and $S^{\mathrm{𝖱𝖱}}$. To see this, consider $t\in S^{\mathrm{𝖫𝖫}}\cup S^{\mathrm{𝖫𝖱}}$, the parent $p_t$ of $t$ and the grandparent $q_t$ of $t$. By Observation 9 $q_t$ must have an additional child $p\ne p_t$. This additional child $p$ is either a leaf (in which case none of $p$’s children are contained in $S^{\mathrm{𝖫𝖫}}$ or $S^{\mathrm{𝖫𝖱}}$) or by construction all non-leaf children of $p$ are contained in $S^{\mathrm{𝖱𝖫}}$ and $S^{\mathrm{𝖱𝖱}}$. Now consider $t\in S^{\mathrm{𝖱𝖫}}\cup S^{\mathrm{𝖱𝖱}}$, the parent $p_t$ of $t$ and the grandparent $q_t$ of $t$. By construction all non-leaf children of $t$ are in $S^{\mathrm{𝖱𝖫}}\cup S^{\mathrm{𝖱𝖱}}$. Therefore, by construction, $q_t$ must have a child $p\ne q_t$ (the “first” child in our construction) for which all non-leaf children are contained in $S^{\mathrm{𝖫𝖫}}\cup S^{\mathrm{𝖫𝖱}}$. Hence, each part $S^{\mathrm{𝖫𝖫}},S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}},S^{\mathrm{𝖱𝖱}}$ also satisfies (TS3). Finally, (TS1) is trivially satisfied for each part $S^{\mathrm{𝖫𝖫}},S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}},S^{\mathrm{𝖱𝖱}}$ and they are therefore thin sets. $◀$

Let $(U,ℱ)$ be a set system and $T$ the laminar tree of $(U,ℱ)$ where we denote the set of leaves of $T$ by $L$. By Lemma 15 we can partition the inner nodes $V(T)\setminus L$ of $T$ into at most $16$ (potentially empty) thin sets $S^1,\mathrm{\dots },S^{16}$ that correspond to the sets $S^{\mathrm{𝖫𝖫}},S^{\mathrm{𝖫𝖱}},S^{\mathrm{𝖱𝖫}},S^{\mathrm{𝖱𝖱}}$ for each of the levels $V^0,V^1,V^2,V^3$. We call such a partition of $V(T)\setminus L$ a thin partition for $(T,ℱ)$. Our colouring of elements of $U$ consists of $32$ colours $A^1,\mathrm{\dots },A^{16},B^1,\mathrm{\dots },B^{16}$. Here $A^i$ is the union of representative sets ${(A_s^i)}_{s\in S^i}$ chosen to satisfy Lemma 10 for every $i\in [16]$ and each $B^i$ contains exactly one (arbitrary) element per representative set $A_s^i$, $s\in S^i$. We call such a $32$-colouring of $U$ an identifying colouring for the thin partition $(S^1,\mathrm{\dots },S^{16})$. An identifying colouring is simply an identifying colouring obtained from any partition $(S^1,\mathrm{\dots },S^{16})$ of $V(T)\setminus L$ into thin sets.

We now show how an identifying colouring can be used to identify in $\mathrm{MSO}$ one representative element of $U$ for each inner node of the laminar tree of a laminar set system $(U,ℱ)$. For this, we use representative sets and then the arbitrarily chosen element from each representative set as the leader which will play the role of the representative element. Before we proceed, let us first provide some auxiliary predicates.

For a set system $(U,ℱ)$, we define $\mathrm{𝖱𝖮𝖮𝖳}(X)$ and $\mathrm{𝖫𝖤𝖠𝖥}(X)$ to be a predicates with one free set variable expressing that $X$ corresponds to the root (or leaf, resp.) of the laminar tree of $(U,ℱ)$ which is easy to implement in $\mathrm{MSO}$. Furthermore, for a unary predicate $A$ we additionally define a predicate with one free set variable ${\mathrm{𝖫𝖤𝖠𝖥}}_A(X)$ that requires $X$ to correspond to a leaf of the laminar tree and the element contained in $X$ additionally needs to satisfy predicate $A$. We further introduce predicates $\mathrm{𝖠𝖭𝖢}(X,Y)$, $\mathrm{𝖣𝖤𝖲𝖢}(X,Y)$, $\mathrm{𝖯𝖠𝖱𝖤𝖭𝖳}(X,Y)$ and $\mathrm{𝖢𝖧𝖨𝖫𝖣}(X,Y)$ each having two free set variables $X,Y$ and which are satisfied if $X,Y\in ℱ$ and the node corresponding to $X$ in the laminar tree of $(U,ℱ)$ is the ancestor, descendant, parent or child, respectively, of the node corresponding to $Y$. It is routine to implement these four predicates in $\mathrm{MSO}$.

The following lemma implements predicates that provide the identification between sets in $ℱ$ and elements in $U$ in such a way that all elements in $A_i$, $i\in \{1,\mathrm{\dots },16\}$ receive distinct representatives which are exactly the leaders of their respective representative sets. We use one leader predicate ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i$ for every $i\in \{1,\mathrm{\dots },16\}$ which provides the leaders for sets corresponding to nodes in $A_i$. We use an additional predicate ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_0$ which gives the identification between singleton sets and elements. While this is trivial, it is convenient later to avoid exceptions for singleton sets.

Our goal is to define the conditions of Lemma 11 in $\mathrm{MSO}$. For this, note that instead of using nodes of the laminar tree, which we do not have access to, in the definition of the sentence ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r,X)$, we rely on the fact that each node corresponds to a unique set in $ℱ$ and use sets of $ℱ$ instead of nodes. We $\mathrm{MSO}$ define the leader in this way for every inner node of the laminar tree. For the leaves which correspond to all singleton sets in $ℱ$ we additionally define the trivial predicate ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_0(r,X):=\mathrm{𝖫𝖤𝖠𝖥}(X)\wedge r\in X$ which assigns every singleton $\{r\}$ the leader $r$.

To implement Lemma 11 in $\mathrm{MSO}$ we first require predicates that define when a set of $ℱ$ is fully branched, single branched or missed by the set defined by any of the predicates $A^i$. Hence, fix any unary predicate $A$ representing a subset of $U$. For any $A\in \{A^1,\mathrm{\dots },A^{16}\}$ we define three predicates with one free set variable $X$ each expressing that $X\in ℱ$ and the node corresponding to $X$ in the laminar tree of $(U,ℱ)$ is fully branched, single branched or missed by $A$ as follows:

Since $A^1,\mathrm{\dots },A^{16},B^1,\mathrm{\dots },B^{16}$ is an identifying colouring for $(S^1,\mathrm{\dots },S^{16})$ each $A^i$ is the union of representative sets ${(A_s^i)}_{s\in S^i}$ with pairwise disjoint up-trees $H_{A_s^i}^{\uparrow }$. Hence, by Lemma 11 any set $R\subseteq U$ and set $X$ corresponding to inner node $s$ of the laminar tree satisfy $R=A_s^i$ if and only if they satisfy predicate ${\mathrm{𝖱𝖤𝖯}}_A^{\ast }(R,X)$ defined below. Note that we first define the following auxiliary predicate ${\mathrm{𝖱𝖤𝖯}}_A(R,X)$ which implements precisely conditions (i)-(iv) of Lemma 11 and then ${\mathrm{𝖱𝖤𝖯}}_A^{\ast }(R,X)$ extends ${\mathrm{𝖱𝖤𝖯}}_A(R,X)$ to also include property (v). This is needed because property (v) states that set $R$ is maximal among all sets for which there is a node and they satisfy (i)-(iv). We define ${\mathrm{𝖱𝖤𝖯}}_A(R,X)$ as follows:
${\mathrm{𝖱𝖤𝖯}}_A(R$ $,X):=\mathrm{𝖲𝖤𝖳}(X)\wedge$ $\forall x(x\in R\to A(x))\wedge$ (i) $\exists Y\left(\mathrm{𝖢𝖧𝖨𝖫𝖣}(Y,X)\wedge R\subseteq Y\wedge \forall Y^{\prime }\left[\left(\mathrm{𝖣𝖤𝖲𝖢}(Y^{\prime },X)\wedge R\subseteq Y^{\prime }\right)\to Y^{\prime }=Y\right]\right)\wedge$ (ii) $\forall Y\left(\left(\mathrm{𝖣𝖤𝖲𝖢}(Y,X)\wedge {\mathrm{𝖿𝗎𝗅𝗅𝗒}}_A(Y)\right)\to \forall Z\left[\mathrm{𝖢𝖧𝖨𝖫𝖣}(Z,Y)\to \left({\mathrm{𝖫𝖤𝖠𝖥}}_A(Z)\vee {\mathrm{𝗌𝗂𝗇𝗀𝗅𝖾}}_A(Z)\right)\right]\right)\wedge$ (iii) $\forall Y((\mathrm{𝖣𝖤𝖲𝖢}(Y,X)\wedge {\mathrm{𝗌𝗂𝗇𝗀𝗅𝖾}}_A(Y))\to \exists Z[\mathrm{𝖢𝖧𝖨𝖫𝖣}(Z,Y)\wedge ({\mathrm{𝖫𝖤𝖠𝖥}}_A(Z)\vee {\mathrm{𝖿𝗎𝗅𝗅𝗒}}_A(Z))\wedge$ $\forall Z^{\prime }((\mathrm{𝖢𝖧𝖨𝖫𝖣}(Z^{\prime },Y)\wedge Z^{\prime }\ne Z)\to {\mathrm{𝗆𝗂𝗌𝗌𝖾𝖽}}_A(Z^{\prime }))]).$ (iv)

Note that each line of the formula above expresses precisely one condition from Lemma 11 (excluding (v)) and we additionally have to ensure that $X$ corresponds to a node and therefore is in $ℱ$. We define ${\mathrm{𝖱𝖤𝖯}}_A^{\ast }(R,X)$ as follow:

For a fixed $i\in [16]$ Lemma 11 implies that for every $X\in ℱ$ corresponding to node $s$ of the laminar tree there is a unique set $R$, namely $R=A_s^i$, for which ${\mathrm{𝖱𝖤𝖯}}_{A^i}^{\ast }(R,X)$ is satisfied. Note that since for every $i\in [16]$ the up-trees $H_{A_s^i}^{\uparrow }$ are pairwise disjoint for all $s\in S^i$ the representative sets ${(A_s^i)}_{s\in S^i}$ must also be pairwise disjoint. Hence, by choosing an arbitrary element in $A_s^i$ as the leader, as the unary predicates $B^1,\mathrm{\dots },B^{16}$ do, we obtain that each set $X\in ℱ$ obtains a unique element as leader (its precisely the element contained in $A_s^i$ which satisfies predicates $B^i$). Hence, for $i\in [16]$ we can define the predicate ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r,X)$ as follows:

Note that since for fixed $i\in [16]$ the $A_s^i$ are pairwise disjoint, it is also guarantied that for any fixed $i\in [16]$ all leaders of nodes in $A^i$ are pairwise different. This concludes the proof of the lemma. $◀$

Let $(U,ℱ)$ be a laminar set system and $𝔽$ be the $\{\mathrm{𝖲𝖤𝖳}\}$-structure representing $(U,ℱ)$. Our $\mathrm{MSO}$-transduction is obtained by composing the following atomic $\mathrm{MSO}$-transductions. To define the transduction, we use the formula constructed in Lemma 16.

1. 1.

   We first apply a $32$-colouring transduction to structure $𝔽$ and obtain unary predicates ${\mathrm{𝖼𝗈𝗅𝗈𝗎𝗋}}_1,\mathrm{\dots },{\mathrm{𝖼𝗈𝗅𝗈𝗎𝗋}}_{32}$.

2. 2.

   We use filtering to ensure that the colouring ${\mathrm{𝖼𝗈𝗅𝗈𝗎𝗋}}_1,\mathrm{\dots },{\mathrm{𝖼𝗈𝗅𝗈𝗎𝗋}}_{32}$ is essentially identifying leaders correctly. To achieve this, we need to check that for every set $X\in ℱ$ there is precisely one $i\in \{0,\mathrm{\dots },16\}$ and one $r\in U$ for which the predicate ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r,X)$ is satisfied. Furthermore, we need to ensure that for every $i\in \{0,\mathrm{\dots },16\}$ and any two distinct sets $X,X^{\prime }\in ℱ$ for which there are elements $r,r^{\prime }$ such that ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r,X)$ and ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r^{\prime },X^{\prime })$ are satisfied, it holds that $r\ne r^{\prime }$. Note that we can express both these properties through an $\mathrm{MSO}$ sentence $\chi$. By Lemma 15 and Lemma 10 there must always exist an identifying colouring while Lemma 16 guarantees that if ${\mathrm{𝖼𝗈𝗅𝗈𝗎𝗋}}_1,\mathrm{\dots },{\mathrm{𝖼𝗈𝗅𝗈𝗎𝗋}}_{32}$ is an identifying colouring then the properties we filter by must be satisfied. Hence, for any laminar set system $𝔽$ we must receive at least one output.

3. 3.

   Copy the resulting structure $16$ times (resulting in $17$ instances of each element of $U$), thus introducing $16$ additional binary relations ${({\mathrm{𝖼𝗈𝗉𝗒}}_i)}_{i\in \{0,\mathrm{\dots },16\}}$ where ${\mathrm{𝖼𝗈𝗉𝗒}}_i(x,y)$ for $i>0$ indicates that $x$ is the $i$-th copy of the original element $y$ and ${\mathrm{𝖼𝗈𝗉𝗒}}_0(x,y)$ indicates that $x$ is the original element $y$. Note that the original elements will represent the leaves of the laminar tree while the $i$-th copy of the leader of a set $X\in ℱ$ will play the role of the node $t$ corresponding to $X$ in case the appropriate thin set $S^i$ contains $t$.

4. 4.

   Finally, we interpret using a pair of formulas $(\varphi ,{\psi }_{\mathrm{𝖣𝖤𝖲𝖢}})$ to obtain a $\{\mathrm{𝖣𝖤𝖲𝖢}\}$ structure $𝕋$. For this we define the realization of a set $X\in ℱ$ to be the $i$-th copy of the element $r\in U$ for which ${\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r,X)$ is satisfied. We define predicate $\mathrm{𝗋𝖾𝖺𝗅}(x,X)$ expressing that $x$ is the relization of $X$ as follows:

   $\mathrm{𝗋𝖾𝖺𝗅}(x,X):=\exists r\left({\displaystyle \underset{i\in \{0,\mathrm{\dots },16\}}{\bigvee }}\left({\mathrm{𝗅𝖾𝖺𝖽𝖾𝗋}}_i(r,X)\wedge {\mathrm{𝖼𝗈𝗉𝗒}}_i(x,r)\right)\right).$

   Now $\varphi$ restrict the universe to elements which are the realization of some set in $ℱ$. We define the descendant relationship of $𝕋$ as follows. For two elements $x,x^{\prime }$ of the restricted universe, ${\psi }_{\mathrm{𝖣𝖤𝖲𝖢}}$ defines that $x$ is a descendant of $x^{\prime }$ if they are the realization of two sets $X,X^{\prime }\in ℱ$ and $X\subseteq X^{\prime }$. Formally, let

   ${\psi }_{\mathrm{𝖽𝖾𝗌𝖼}}(x,x^{\prime }):=\exists X\exists X^{\prime }\left(\mathrm{𝗋𝖾𝖺𝗅}(x,X)\wedge \mathrm{𝗋𝖾𝖺𝗅}(x^{\prime },X^{\prime })\wedge X\subseteq X^{\prime }\right).$