Back and Forth Systems Witnessing Irreversibility

Abstract

If $L$ is a relational language, then an $L$-structure $\mathbb{X}=⟨X,\bar{\rho }⟩$ is reversible iff there is no interpretation $\bar{\sigma }\bar{\rho }$ such that the structures $⟨X,\bar{\sigma }⟩$ and $⟨X,\bar{\rho }⟩$ are isomorphic. We show that $\mathbb{X}$ is not reversible iff there is a back and forth system $\Pi$ of partial self-condensations of $\mathbb{X}$ containing one which is not a partial isomorphism and having certain closure properties. Using that characterization we detect several classes of non-reversible partial orders containing, for example, homogeneous-universal posets (in particular, the random poset), the divisibility lattice, $⟨\mathbb{N},\mid ⟩$, the ideals $[\kappa {]}^{<\lambda }$, the meager ideal in the algebra Borel$({\omega }^{\omega })$, and the direct powers of rationals, ${\mathbb{Q}}^{\kappa }$, and integers, ${\mathbb{Z}}^{\kappa }$. Some of the results are obtained under additional set-theoretic assumptions.

24 pages