Core-like properties of infinite graphs and structures (Q1842150): Difference between revisions

A structure \(G\) is a set together with (possibly infinitely many) relations on it. (If there is just one relation then the structure is a digraph.) The fact that there is a homomorphism from a structure \(G\) to a structure \(H\) (of the same type) is denoted by \(G\to H\). If \(G\to H\) and \(H\to G\) then \(G\) and \(H\) are homomorphically equivalent. The following core-like properties of a structure \(G\) are studied: \({\mathbf I}(G)\) holds if any endomorphism \(f\) of \(G\) is an injection. \({\mathbf S}(G)\) holds if any endomorphism \(f\) of \(G\) is a surjection. \({\mathbf N}(G)\) holds if any endomorphism \(f\) of \(G\) preserves non-relations (i.e. \(\neg R(v_ 1,\dots, v_ n)\) implies \(\neg R(f(v_ 1),\dots, f(v_ n))\) for every relation \(R\)). \({\mathbf R}(G)\) holds if \(G\) has no proper retractions (i.e. there is no non-surjective endomorphism \(f: G\to G\) such that \(f\bigl|_{f(G)}\) is an identity). \({\mathbf x}(G)\) holds if \(G\) contains a subgraph \(H\) such that \(G\to H\), and \({\mathbf X}(G)\) holds if \({\mathbf X}\) is either \({\mathbf I}\), or \({\mathbf S}\), or \({\mathbf N}\). \({\mathbf r}(G)\) holds if \(G\) has a retract \(H\) for which \({\mathbf R}(H)\) holds. All implications are shown between properties \({\mathbf I}\), \({\mathbf S}\), \({\mathbf N}\), \({\mathbf R}\) and their combinations, and between \({\mathbf i}\), \({\mathbf s}\), \({\mathbf n}\), \({\mathbf r}\) and their combinations. (E.g., the combination \({\mathbf S}{\mathbf N}(G)\) means that \({\mathbf S}(G)\) and \({\mathbf N}(G)\) hold, and combination \({\mathbf s}{\mathbf n}(G)\) means that there is a subgraph \(H\) for which \({\mathbf s}(H)\) and \({\mathbf n}(H)\) hold.) It is proved (1) that the properties \({\mathbf i}\), \({\mathbf n}\), \({\mathbf i}{\mathbf s}\), \({\mathbf i}{\mathbf n}\), \({\mathbf s}{\mathbf n}\) and \({\mathbf i}{\mathbf s}{\mathbf n}\) are invariant under homomorphic equivalence of structures and properties \({\mathbf s}\) and \({\mathbf r}\) are not, and (2) the properties \({\mathbf I}{\mathbf S}{\mathbf N}\) and \({\mathbf S}{\mathbf N}\) are strongly invariant, and the properties \({\mathbf I}\), \({\mathbf S}\), \({\mathbf N}\), \({\mathbf I}{\mathbf S}\), \({\mathbf I}{\mathbf N}\) and \({\mathbf R}\) are not (a property \({\mathbf X}\) is strongly invariant if whenever \(G\) and \(H\) are homomorphically equivalent and \({\mathbf X}(G)\) and \({\mathbf X}(H)\) hold then \(G\) and \(H\) are isomorphic).