On Scott's thesis for domains of information and well-quasi-orderings (Q1813971)

Let \((E,\leq)\) be an ordered set of events \((\leq\) represents causal dependencies). Let \([e]_ E=\{e'\in E\mid e'\leq e\}\) (the set of necessary conditions for \(e\)). Given a subset \(D\) of \(E\), its underlying domain of information \({\mathcal L}(D)\) is the set of all left-closed subsets of \(D\). If \(E_ 0\) and \(E_ 1\) are two subsets of \(E\) (interpreted as input and output of a computation), we can define two functions: \(f_{E_ 0E_ 1}: {\mathcal L}(E_ 0)\to{\mathcal L}(E_ 1)\) and \(f^*_{E_ 0E_ 1}: {\mathcal L}(E_ 0)\to{\mathcal L}(E_ 1)\) such that \[ f_{E_ 0E_ 1}(X)=\{e\in E_ 1\mid [e]_ E\cap E_ 0\subseteq X\} \] and \[ F*_{E_ 0E_ 1}(X)=\{e\in E_ 1\mid [e]_{E_ 1}\cap E_ 0\subseteq X\}. \] A poset \((E,\leq)\) obeys Scott's thesis iff \(f_{E_ 0E_ 1}\) is continuous for all \(E_ 0,E_ 1\subseteq E\) with the induced orders. The main result of the paper characterizes such posets: Theorem. Let \((E,\leq)\) be a poset. The following are equivalent: (i) \((E,\leq)\) obeys Scott's thesis. (ii) \(f^*_{E_ 0E_ 1}\) is continuous for all \(E_ 0,E_ 1\subseteq E\). (iii) For all \(e\in E\), \([e]_ E\) does not contain an infinite antichain or an infinite increasing chain. (iv) For all \(e\in E\), \(([e]_ E,\leq^*)\) is a well-quasi-ordering (here \(\leq^*\) is the inverse order with respect to \(\leq\)).