A Note on Chain Definability¶
Setting¶
\(A\) and \(B\) are fixed finite and disjoint sets.
For \(K \subseteq A \times B\), define the pair of partial preorders \(\tuple{\ale^K, \ble^K}\) on \(A\) and \(B\) respectively by
\(K\) has the chain property if \(\tuple{\ale^K, \ble^K}\) are total preorders.
Proposition 1
\(\ale^K\) is a total preorder iff \(\ble^K\) is.
Proof.
For the sake of contradiction, suppose \(\ale^K\) is a total preorder but \(\ble^K\) is not. Then \(\ble^K\) must fail totality (since it is always transitive), i.e. there are \(b, b' \in B\) such that neither \(K^{-1}(b) \subseteq K^{-1}(b')\) nor \(K^{-1}(b') \subseteq K^{-1}(b)\). This means there are \(a, a' \in A\) with \(a \in K^{-1}(b) \setminus K^{-1}(b')\) and \(a' \in K^{-1}(b') \setminus K^{-1}(b)\). Consequently \(b \in K(a) \setminus K(a')\) and \(b' \in K(a') \setminus K(a)\); but this means neither \(K(a) \subseteq K(a')\) nor \(K(a') \subseteq K(a)\), i.e. \(a\) and \(a'\) are not comparable under \(\ale^K\). This contradicts \(\ale^K\) being a total preorder.
An identical argument shows that \(\ale^K\) is a total preorder whenever \(\ble^K\) is.
Chain Definability¶
A pair \(\tuple{\le_A, \le_B}\) of total preorders on \(A\) and \(B\) respectively is chain-definable if there exists \(K \subseteq A \times B\) with the chain property such that \({\le_*} = {\preceq_*^K}\) for \(* \in \{A, B\}\).
Notation. For a tpo \(\le\) on a set \(Z\) and \(z \in Z\), write \([z]_\le\) for the equivalence class of \(z\) wrt the symmetric closure of \(\le\), i.e.
The subscript in \([z]_\le\) can be omitted when the tpo is clear from context. Note that \(\le\) induces a total order on the set of equivelence classes, by \([z] \le [z']\) iff \(z \le z'\).
Also write
for the number of ‘ranks’ in \(\le\).
Proposition 2 (due to Richard)
\(\tuple{\le_A, \le_B}\) is chain-definable if and only if \(|r(\le_A) - r(\le_B)| \le 1\).
Proof.
(⇒) Suppose \(\tuple{\le_A, \le_B}\) is chain-definable, i.e. there is \(K \subseteq A \times B\) with the chain property such that \(a \le_A a'\) iff \(K(a) \subseteq K(a')\), and \(b \le_B b'\) iff \(K^{-1}(b) \supseteq K^{-1}(b')\).
Write
for the set of equivalence classes corresponding to each order, excluding those whose elements have empty neighbourhoods in \(K\). Note that \([a] = [a']\) iff \(K(a) = K(a')\) (and similarly for \(B\)).
We will show that \(|\X| = | \Y|\). Enumerate \(\X = \{X_1,\ldots,X_n\}\) and \(\Y = \{Y_1,\ldots,Y_m\}\), ordered such that \(X_1 <_A \cdots <_A X_n\) 1 and similarly for \(\Y\). First we show \(n \le m\).
For each \(1 \le i \le n\), let \(a_i\) be an arbitrary element of \(X_i\). Then \(\emptyset \subset K(a_1) \subset \cdots \subset K(a_n)\). We can therefore choose \(b_1,\ldots,b_n \in B\) such that \(b_1 \in K(a_1)\) and \(b_{i+1} \in K(a_{i+1}) \setminus K(a_i)\), for \(1 \le i < n\). It follows that \(a_i \in K^{-1}(b_i) \setminus K^{-1}(b_{i+1})\).
This means that \(K^{-1}(b_i) \not\subseteq K^{-1}(b_{i+1})\); since \(K\) has the chain property this means \(K^{-1}(b_{i+1}) \subset K^{-1}(b_i)\), i.e. \(b_i \le_B b_{i+1}\).
We now have a chain \(b_1 <_B \cdots <_B b_n\) of \(n\) strict inequalities in \(B\), and the corresponding chain \([b_1] <_B \cdots <_B [b_n]\) in \(\Y\). Clearly each \([b_i]\) is distinct, so we have \(n \le | \Y| = m\).
Repeating the above argument with the roles of \(A\) and \(B\) interchanged, we find that \(m \le n\) also, and so \(n = m\).
To conclude, note that \(r({\le_A}) \in \{n, 1 + n\}\) and \(r({\le_B}) \in \{m, 1 + m\}\); the two cases corresponding to whether there exists an equivalence class of elements with empty neighbourhoods in \(K\). 2 Since \(n = m\), it is clear that \(r({\le_A})\) and \(r({\le_B})\) differ by at most one as required.
(⇐) Suppose \(|r(\le_A) - r(\le_B)| \le 1\). Let \(X_1 <_A \cdots <_A X_n\) and \(Y_1 <_B \cdots <_B Y_m\) be the equivalence classes corresponding to \(\le_A\) and \(\le_B\) respectively. By hypothesis \(|n - m| \le 1\). We will construct \(K\) with the chain property such that the \(X_i\) and \(Y_j\) correspond to elements of \(A\) and \(B\) respectively with the same neighbourhood in \(K\).
Define \(g: \{1,\ldots,n\} \to \{0, \ldots, m\}\) by
Let \(K \subseteq A \times B\) be the unique relation such that any \(a \in X_i\) has neighbourhood
where \(Y_0 := \emptyset\). Note that since \(g(i+1) = g(i) + 1\) we have \(K(X_{i+1}) = K(X_i) \cup Y_{g(i+1)}\) and consequently
It follows that \(K\) has the chain property and \(a \le_A a'\) iff \(K(a) \subseteq K(a')\), as required.
Now we show \(b \le_B b'\) iff \(K^{-1}(b) \supseteq K^{-1}(b')\). Note that if \(a \in X_i\) and \(b \in Y_j\), we have \(a \in K^{-1}(b)\) iff \(b \in K(a) = K(X_i) = \bigcup_{k \le g(i)}{Y_k}\) iff \(j \le g(i)\), since \(Y_1,\ldots,Y_m\) are disjoint. Hence \(K^{-1}(b)\) depends only on \(j\), and is given by
Consequently, for \(1 \le j < m\),
Now, since \(j < m\) we have
In particular \(g^{-1}(j) \ne \emptyset\), so \(K^{-1}(Y_{j+1}) \subset K^{-1}(Y_j)\) and thus
From this it follows that \(b \le_B b'\) iff \(K^{-1}(b) \supseteq K^{-1}(b')\). Hence \(\tuple{\le_A, \le_B}\) is chain-definable.
Remark. It is also possible to prove the bulk of the ‘only if’ statement of Proposition 2 by constructing a bijection \(f\) from \(\X\) to \(\Y\) directly: set \(f([a]) = \max(K(a), \le_B)\).