## 3 Minimal Patterns and Pattern Priority
At first, we observe the following. **Fact 1**: _The binary relation of pattern priority is irreflexive and antisymmetric (since properties (1), (2) and (3) of Definition 7 are strictly defined)._  
**Lemma 2**: _Let \(m\) and \(m^{\prime}\) be two patterns with \(\min\{\mathcal{L}_{m}\setminus\mathcal{L}_{m^{\prime}}\}<\min\{\mathcal{L}_ {m^{\prime}}\setminus\mathcal{L}_{m}\}\), such that the two minima both exist, and define \(j\) to be \(\min\{\mathcal{L}_{m}\setminus\mathcal{L}_{m^{\prime}}\}\). Then, the occurrences of \(m\) and \(  
Assume \(\mathcal{L}_{m_{t}}\subset\mathcal{L}_{m_{1}}\). Define \(j\) to be \(\min\{\mathcal{L}_{m_{t}}\setminus\mathcal{L}_{m_{t+1}}\}\), this minimum exists, since \(m_{t-1}\to m_{t}\) (by property (3) of Definition 7). It follows that \(j\in\mathcal{L}_{m_{1}}\) and, from Lemma 2, that the occurrences of \(m_{t}\) and \(m_{t+1}\) that are less than \(j\) are paired. Hence, these occurrences are shared also with \(m_{1}\). Since \(j\
otin\mathcal{L}_{m_{t+1}}\), then either \(m_{1}\to m_{t+1}\) holds (because \(j\) makes the difference between \(\mathcal{L}_{m_{1}}\) and \(\mathcal{L}_{m_{t+1}}\)) or \(m_{1}\) and \(m_{t+1}\) are incomparable. In the latter case, \(\mathcal{L}_{m_{t}}\subset\mathcal{L}_{m_{1}}\) and \(\mathcal{L}_{m_{1}}\subseteq\mathcal{L}_{m_{t+1}}\) imply \(\mathcal{L}_{m_{t}}\subset\mathcal{L}_{mt+1}\), which is impossible, since \(m_{t}\) and \(m_{t+1}\) are comparable by hypothesis. Thus, in this latter case, we have that \(\mathcal{L}_{m_{t+1}}\subset\mathcal{L}_{m_{1}}\). Conversely, assume \(m_{1}\to m_{t}\). Define \(j\) as before and \(j^{\prime}=\min\{\mathcal{L}_{m_{1}}\setminus\mathcal{L}_{m_{t}}\}\). It holds that \(j\
otin\mathcal{L}_{m_{t+1}}\) (as already observed), and that \(j^{\prime}\
eq j\), because of \(j^{\prime}\
otin\mathcal{L}_{m_{t}}\). Then, by Lemma 2, the occurrences of \(m_{t}\) and \(m_{t+1}\) that are less than \(j\) are paired, and the same is true for the occurrences of \(m_{1}\) and \(m_{t}\) that are less than \(j^{\prime}\). It follows that, if \(m_{1}\) and \(m_{t+1}\) are comparable, there exists an occurrence in \(\mathcal{L}_{m_{1}}\) that is more on the left with respect to those of \(\mathcal{L}_{m_{t+1}}\): If \(j^{\prime}<j\), the occurrences of \(m_{1}\), \(m_{t}\) and \(m_{t+1}\) less than \(j^{\prime}\) are paired together, and thus, \(j^{\prime}\) makes the difference; otherwise (\(j^{\prime}>j\)), the occurrences of \(m_{1}\), \(m_{t}\) and \(m_{t+1}\) less than \(j\) are paired together, and hence, \(j\in\mathcal{L}_{1}\) makes the difference. Alternatively, \(\mathcal{L}_{m_{1}}\subseteq\mathcal{L}_{m_{t+1}}\) implies that the occurrences of \(m_{1}\) equal to or less than \(j^{\prime}\) are shared with \(m_{t+1}\), which leads to \(m_{t+1}\to m_{t}\), which is impossible. \(\Box\)  
**Theorem 1**: _Any set of patterns, \(\mathcal{M}\), is sub-ordered with respect to the binary relation of pattern priority._  
ProofWe have to prove that the relation of pattern priority is irreflexive, antisymmetric and acyclic. The first two properties are stated in Fact 1. Now, following the work in Lemma 3, we can prove that the acyclicity holds too. First, observe that length and degeneracy are intrinsic properties of the single pattern. If all patterns in \(\mathcal{M}\) have different lengths and degeneracies, then by definition of pattern priority, it is always true that either \(m\to m^{\prime}\) or \(m^{\prime}\to m\), and a cycle can never exist, because of different lengths or degeneracies. Alternatively, consider a chain of patterns, \(m_{1}\to m_{2},\ldots\), \(m_{t-1}\to m_{t}\), with the same length and degeneracy. In this case, we must use property (3) of Definition 7 to compare the patterns together. From Lemma 3, it follows that a cycle of pattern priority between any chain of patterns is, again, impossible, and hence, the acyclicity holds. \(\Box\)  
Note that the non-decision on some binary comparisons finally discards the relation of totality and, as seen above, of transitivity.