Complexity ranks of countable models (Q998136): Difference between revisions

The Scott Isomorphism Theorem and its attendant analysis of countable models yields the following invariants. For \(\mathcal L\) a countable relational language, \(M\) a countable \(\mathcal L\)-structure, and \(\vec{a}\in | M| ^n\), \(\text{sr}_{M}(\vec{a})\) is the least \(\alpha<\omega_1\) such that for any \(\vec{b}\in | M| ^n\), \((M, \vec{a})\equiv_{\alpha}(M,\vec{b})\) implies \((M, \vec{a})\cong (M, \vec{b})\). Further, \(\text{sr}(M)=\text{sup}\{\text{sr}_{M}(\vec{a})\mid \vec{a}\in | M| ^n, n>0\}\) is called the Scott rank of \(M\). The author discusses variants of Scott rank. Of particular interest is a notion of rank arising from the Ehrenfreuct-Fraïssé game version of \(\alpha\)-equivalence. For \(\mathcal L\)-structures \(M\) and \(N\), the two-person game that detects \(\alpha\)-equivalence is denoted by \(\text{EF}_\alpha(M,N)\). For \(M\) countable, Scott's analysis produces a countable ordinal \(\alpha<\text{sr}(M)+\omega\) such that whenever \(N\) is a countable \(\mathcal L\)-structure with \(N\equiv_{\alpha}M\), then \(N\cong M\); for this \(\alpha\), player II having a winning strategy in \(\text{EF}_\alpha(M,N)\) means \(M\) and \(N\) are isomorphic. The least such ordinal for which this happens is called the game rank of \(M\) (\(\text{gr}(M)\)). It is known that \(\text{gr}(M)\leq\text{sr}(M)+\omega\). The author presents an argument of Hjorth for the ``folklore'' inequality: \(\text{sr}(M)\leq\text{gr}(M)+\omega\). The bulk of the article is taken up with an investigation of mono-unary algebras. These partially ordered structures arise from the relational version of the language \(\mathcal L=\{f\}\), \(f\) a unary function. For \(\mathbb A\) a mono-unary algebra and \(x\in\mathbb A\), \(\mathbb A(x)=\{y\in\mathbb A\mid x\leq y\}\) is a tree. The author's main result is: for any \(x\in \mathbb A\), \(\text{gr}(\mathbb A(x))\leq \omega+\text{gr}(\mathbb A)\). The author points out that similar questions about linear orderings remain unresolved.