Partial orders of isomorphic substructures of relational structures

Abstract

<p>Cilj ove teze je da se ispitaju&nbsp; lanci u parcijalnim uredjenjima (P(X), &sub;),&nbsp;pri čemu je P(X) skup domena izomorfnih podstruktura relacijske strukture&nbsp;X. Po&scaron;to se svaki lanac u parcijalnom uredjenju može produžiti do maksimalnog lanca, dovoljno je ispitati maksimalne lance u P(X). Dokazano je da, ako je X ultrahomogena relacijska struktura koja ima netrivijalne izomorfne&nbsp;podstrukture, onda je svaki maksimalan lanac u (P(X) &cup; {&empty;}&nbsp; , &sub;) kompletno&nbsp;linearno uredjenje koje se utapa u R i ima neizolovan minimum. Ako &nbsp;je X&nbsp;relacijska struktura, dat je dovoljan uslov da za svako kompletno linearno uredjenje L koje se utapa&nbsp; u R i ima neizolovan minimum, postoji maksimalan lanac u (P(X) &cup; {&empty;}&nbsp; , &sub;) izomorfan L.&nbsp; Dokazano je i da ako je&nbsp;X neka od sledećih relacijskih struktura: Rado graf, Hensonov graf, random poset, ultrahomogeni&nbsp; poset Bn&nbsp; ili&nbsp; ultrahomogeni&nbsp; poset Cn; onda je&nbsp;L izomorfno maksimalnom lancu u (P(X) &cup; {&empty;}&nbsp; , &sub;) ako i samo ako je &nbsp;L&nbsp;kompletno,&nbsp; utapa se u R i ima neizolovan minimum. Ako je X prebrojiv&nbsp;antilanac ili disjunktna unija &micro; kompletnih&nbsp; grafova sa &nu; tačaka za &micro;&nu; = &omega;, onda je L izomorfno maksimalnom lancu u (P(X) &cup; {&empty;}&nbsp; , &sub;) ako i samo ako&nbsp;je bulovsko,&nbsp; utapa se u R i ima neizolovan minimum.</p>

<p>The purpose of this thesis is to investigate chains in partial orders (P(X), &sub;), where P(X) is the set of domains of isomorphic substructures of a relational structure X. Since each chain in a partial&nbsp; order can be extended to a maximal one, it is enough to describe maximal chains in P(X). It is proved that, if X is an ultrahomogeneous relational structure with non-trivial isomorphic substructures, then each maximal&nbsp; chain in (P(X)&cup; {&empty;}&nbsp; , &sub;) is a complete, R-embeddable linear order with minimum&nbsp; non-isolated. If X is a relational structure, a condition is given for X, which is sufficient&nbsp; for (P(X) &cup; {&empty;}&nbsp; , &sub;) to embed each complete,&nbsp; R-embeddable&nbsp; linear order with minimum non-isolated as a maximal&nbsp; chain.&nbsp; It is also proved that if X is one of the follow- ing relational structures: Rado graph, Henson graph, random poset, ultrahomogeneous poset Bn or ultrahomogeneous poset Cn; then L is isomorphic to a maximal&nbsp; chain in (P(X) &cup; {&empty;}&nbsp; , &sub;) if and only if L is complete, R-embeddable with minimum non-isolated. If X is a countable&nbsp; antichain&nbsp; or disjoint union of &micro; complete graphs with &nu; points where &micro;&nu; = &omega;, then L is isomorphic to a maximal&nbsp; chain&nbsp; in (P(X) &cup; {&empty;}&nbsp; , &sub;) if and only if L is Boolean, R-embeddable with minimum non-isolated.</p>