<p>If <i>L</i> is a relational language, then an <i>L</i>-structure <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb {X}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">X</mi> </math></EquationSource> </InlineEquation> is reversible iff each bijective homomorphism (condensation) <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(f:{\mathbb {X}}\rightarrow {\mathbb {X}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo>:</mo> <mi mathvariant="double-struck">X</mi> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">X</mi> </mrow> </math></EquationSource> </InlineEquation> is an automorphism of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb {X}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">X</mi> </math></EquationSource> </InlineEquation>. We show that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb {X}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">X</mi> </math></EquationSource> </InlineEquation> is not reversible iff there is a back and forth system <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Pi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Π</mi> </math></EquationSource> </InlineEquation> of partial self-condensations of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb {X}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">X</mi> </math></EquationSource> </InlineEquation> 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, <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\(\langle {\mathbb {N}},\,\mid \,\rangle \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">⟨</mo> <mi mathvariant="double-struck">N</mi> <mo>,</mo> <mspace width="0.166667em" /> <mo>∣</mo> <mspace width="0.166667em" /> <mo stretchy="false">⟩</mo> </mrow> </math></EquationSource> </InlineEquation>, the ideals <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq8.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\([\kappa ]^{&lt;\lambda }\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">[</mo> <mi>κ</mi> <mo stretchy="false">]</mo> </mrow> <mrow> <mo>&lt;</mo> <mi>λ</mi> </mrow> </msup> </math></EquationSource> </InlineEquation>, the meager ideal in the algebra <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\({\textrm{Borel}}(\omega ^\omega )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>Borel</mtext> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mi>ω</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and the direct powers of rationals, <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq10.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb {Q}}^\kappa \)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">Q</mi> </mrow> <mi>κ</mi> </msup> </math></EquationSource> </InlineEquation>, and integers, <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2025_651_Article_IEq11.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb {Z}}^\kappa \)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mi>κ</mi> </msup> </math></EquationSource> </InlineEquation>. Some of the results are obtained under additional set-theoretic assumptions.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Back and forth systems witnessing irreversibility

  • Miloš S. Kurilić

摘要

If L is a relational language, then an L-structure \({\mathbb {X}}\) X is reversible iff each bijective homomorphism (condensation) \(f:{\mathbb {X}}\rightarrow {\mathbb {X}}\) f : X X is an automorphism of \({\mathbb {X}}\) X . We show that \({\mathbb {X}}\) X is not reversible iff there is a back and forth system \(\Pi \) Π of partial self-condensations of \({\mathbb {X}}\) 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, \(\langle {\mathbb {N}},\,\mid \,\rangle \) N , , the ideals \([\kappa ]^{<\lambda }\) [ κ ] < λ , the meager ideal in the algebra \({\textrm{Borel}}(\omega ^\omega )\) Borel ( ω ω ) , and the direct powers of rationals, \({\mathbb {Q}}^\kappa \) Q κ , and integers, \({\mathbb {Z}}^\kappa \) Z κ . Some of the results are obtained under additional set-theoretic assumptions.