Back and Forth Systems of Condensations

Abstract

If $L$ is a relational language, an $L$-structure $\mathbb{X}$ is condensable to an $L$-structure $\mathbb{Y}$, we write $\mathbb{X}{\preccurlyeq }_c\mathbb{Y}$, iff there is a bijective homomorphism (condensation) from $\mathbb{X}$ onto $\mathbb{Y}$. We characterize the preorder ${\preccurlyeq }_c$, the corresponding equivalence relation of bi-condensability, $\mathbb{X}{\sim }_c\mathbb{Y}$, and the reversibility of $L$-structures in terms of back and forth systems and the corresponding games. In a similar way we characterize the ${\mathcal{P}}_{\infty \omega }$-equivalence (which is equivalent to the generic bi-condensability) and the $\mathcal{P}$-elementary equivalence of $L$-structures, obtaining analogues of Karp's theorem and the theorems of Ehrenfeucht and Fraïssé. In addition, we establish a hierarchy between the similarities of structures considered in the paper. Applying these results we show that homogeneous universal posets are not reversible and that a countable $L$-structure $\mathbb{X}$ is weakly reversible (that is, satisfies the Cantor-Schröder-Bernstein property for condensations) iff its ${\mathcal{P}}_{\infty \omega }\cup {\mathcal{N}}_{\infty \omega }$-theory is countably categorical.

arXiv comment22 pages