2018/07/01 by Miloš S. Kurilić, Kurilić, Miloš S.
Computer Science · Mathematics · #03C07 #03C50 #03C75 #03E40 #06A06 #Advanced Algebra and Logic #Advanced Topology and Set Theory #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #math.LO #msc:03C07 #msc:03C50 #msc:03C75 #msc:03E40 #msc:06A06
paper · pdf · doi:10.48550/arxiv.1807.00338
22 pages
arxiv created 2018/07/01 · openalex publication_date 2018/07/01 · arxiv updated 2018/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∼ 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∞ ω-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∞ ω∪ \mathcal N∞ ω-theory is countably categorical.