Games played on partial isomorphisms (Q1879001): Difference between revisions

For \(L\) a countable relational language and \(\mathcal A\) and \(\mathcal B\) structures for \(L\), \(\mathcal I_\kappa\) is the set of partial isomorphisms \(p\colon \mathcal A\rightarrow \mathcal B,\) where \(| p| <\kappa.\) The set \(\mathcal I_\kappa\) partially ordered by \(\subseteq\) is a measure of the similarity of \(\mathcal A\) and \(\mathcal B\). The set \(\mathcal I^{*}_\kappa\) denotes the largest subset of \(\mathcal I_\kappa\) that has the \(\kappa\)-\textit{back-and-forth} property. If \(\mathcal I^{*}_ 2\not=\emptyset\), then \(\mathcal A\) and \(\mathcal B\) are said to be partially isomorphic (\(\mathcal A\simeq_ p\mathcal B\)). The statement \((\sigma)_\kappa\) asserts the existence of a subset of \(\mathcal I^{*}_\kappa\) that is closed under unions of countable ascending chains. Structures \(\mathcal A\) and \(\mathcal B\) satisfying \((\sigma)_{\aleph_ 1}\) are said to be strongly partially isomorphic (\(\mathcal A\simeq^ s_ p\mathcal B\)). The authors state that the main open question for \((\sigma)_{\aleph_ 1}\) is whether or not it is transitive, i.e., do \(\mathcal A\simeq^ s_ p\mathcal B\) and \(\mathcal B\simeq^ s_ p\mathcal C\) imply \(\mathcal A\simeq^ s_ p\mathcal C?\) In this regard they obtain some partial results. They show that for the class of structures of size \(\leq 2^{\aleph_0}\) strong partial isomorphism is a transitive relation. They get similar results for certain classes of size \(\leq\aleph_ 2\), and they show that \((\sigma)_{\kappa^{+}}\) is transitive in the class of structures of size \(\leq \kappa^ +\). The authors characterize the relation \(\mathcal A\simeq^ s_ p\mathcal B\) in terms of an Ehrenfeucht-Fraïssé game \(EF^{\aleph_ 1}_{\omega_ 1}\) on \(\mathcal A\) and \(\mathcal B\) in which two players \(\forall\) and \(\exists\) alternately choose sequences of length \(<\aleph_ 1\) for \(\omega_ 1\) rounds. The statement \((\exists)^{\aleph_ 1}_{\omega_ 1}\) asserts that \(\exists\) has a winning strategy in this game. Though \((\sigma)_{\aleph_ 1}\) implies \((\exists)^{\aleph_ 1}_{\omega_ 1}\), the equivalence of these two statements remains open. However, they are equivalent for the class of structures of size \(\leq 2^{\aleph_0}\) and certain classes of structures of size \(\leq\aleph_ 2.\) The authors also explore a connection between the Banach-Mazur game and \((\sigma)_{\aleph_ 1}.\)