Global ETD Search

1	Kondenzacioni poredak, kondenzaciona ekvivalencija i reverzibilnost relacijskih struktura / Condensational order, condensational equivalenceand reversibility of relational structures Morača Nenad 09 July 2018 (has links) <p>Ako je<em> L </em>relacijski jezik, kondenzacioni pretporedak na skupu<em> Int</em><sub>L</sub> <em>(X)</em> svih <em>L-</em>interpretacija nad domenom <em>X,</em> dat je sa: ρ≼<sub>c</sub> <em>σ</em> ako postoji bijektivni homomorfizam (kondenzacija)<em> f:〈X,ρ</em>〉→<em>〈X,σ〉.</em> Odgovarajući antisimetrični količnik <em>〈Int<sub> L</sub></em> (X)/~<sub>c</sub>,≤<sub>c</sub>〉 ~naziva se kondenzacioni poredak. Za proizvoljnu<em> L-</em>interpretaciju ρ, klasa [ρ]~<sub>c</sub>  je konveksno zatvorenje klase [ρ]_&cong; u Booleovoj mreži 〈<em>IntL (X</em>),&sube;〉. Za <em>L</em>-interpretaciju ρ reći ćemo da je jako reverzibilna (redom, reverzibilna, slabo reverzibilna) akko je klasa [ρ]_&cong;  (ili, ekvivalentno, klasa [ρ]~<sub>c </sub>)) singlton (redom, antilanac, konveksan skup) u Booleovoj mreži 〈<em>IntL (X)</em>,&sube;〉. U cilju ispitivanja poseta 〈<em>Int(<sub>Lb</sub></em><sub> </sub>) (X)/~c,≤c〉, za ρ∈<em>Irrefl<sub>X</sub></em> uveden je skup D<sub>ρ</sub>:={[ρ∪Δ<sub>A</sub> ](~<sub>c</sub> ):<em>A&sube;X</em>} i pokazano je kako je poduređenje 〈D<sub>ρ</sub>,≤<sub>c</sub> 〉 izomorfno određenom količniku partitivnog skupa<em> P(X)</em>. Fenomen reverzibilnosti relacijskih struktura igra istaknutu ulogu u istraživanju tog poduređenja.</p><p>U slučaju prebrojivog jezika <span id="cke_bm_1038S" style="display: none;"> </span><em>L</em><span id="cke_bm_1038E" style="display: none;"> </span> i prebrojivog domena <em>X</em>, pokazano je da su ~<sub>c</sub> i [ρ]~<sub>c </sub>analitički skupovi u poljskim prostorima, redom, <em>Int<sub>L </sub>(ω)×Int<sub>L </sub>(ω) i Int<sub>L</sub> (ω)</em>, i pomoću toga, pokazano ja da su, u slučaju prebrojivog jezika i domena, klase [ρ]&cong;  i [ρ]~<sub>c</sub> iste veličine, i da je to neki kardinal iz {1,ω,c}. Dalje je istražena hijerarhija između kondenzacione ekvivalencije, elementarne ekvivalencije, ekvimorfizma (bi-utopivosti) i drugih sličnosti <em>L-</em>struktura određenih nekim sličnostima njihovih monoida samoutapanja.</p><p>Naposletku, temeljno je istražen fenomen reverzibilnosti <em>L</em>-struktura. Data je karakterizacija jako reverzibilnih<em> L</em>-intepretacija kao onih čije su komponentne relacije definabilne formulama praznog jezika<em> L</em><sub>∅</sub>, bez kvantifikatora i parametara. Pokazano je kako su slabo reverzibilne interpretacije upravo one koje imaju svojstvo Cantor-Schrӧder-Bernstein (kraće, svojstvo CSB) za kondenzacije.</p><p>Poseban naglasak stavljen je na detektovanje relevantnih klasa reverzibilnih struktura. Pri tome, prvo su proučene strukture koje su ekstremni elementi L<sub>∞ω</sub>-definabilnih klasa interpretacija, pri određenim sintaktičkim ograničenjima, a zatim su istražene nepovezane<em> L</em><sub>b</sub>-strukture, gde je dato nekoliko karakterizacija njihove reverzibilnosti.</p> / <p>If <em>L</em> is a relational language, the condensational preorder on the set <em>Int<sub>L</sub> (X)</em> of all <em>L-</em>interpretations over the domain<em> X</em>, is given with: ρ≼_c σ iff there exists a bijective homomorphism (condensation) <em>f:〈X,ρ〉→〈X,σ〉. </em>The corresponding antisymmetric quotient 〈<em>Int<sub>L</sub> (X)/</em>~<sub><em>c</em></sub>,≤_<sub>c</sub>〉 will be called the condensational order. For any <em>L</em>-interpretation ρ, the class<em> [ρ]~<sub>c</sub> )</em> is the convex closure of the class [<em>ρ</em>]&cong; in the Boolean lattice 〈<em>IntL (X</em>),&sube;〉. An <em>L</em>-interpretation ρ is said to be strongly reversible  (respectively, reversible, weakly reversible) iff the class <em>[ρ]</em>&cong;  (or, equivalently, the class<em> [ρ]~c )</em>) is a singleton (respectively, an antichain, a convex set) in the poset 〈 <em>IntL</em> <em>(X)</em>,&sube;〉. In order to investigate the poset 〈<em>Int<sub>(Lb</sub> ) (X)/~c,≤_c</em>〉, for ρ∈<em> IrreflX</em> the following set is defined <em>D<sub>ρ</sub></em>:={[ρ∪Δ<sub>A</sub> ]_~c :A&sube;X}. It is shown that the suborder 〈<em>D<sub>ρ</sub>,</em>≤<sub>c</sub> 〉 is isomorphic to a certain quotient of the power set <em>P(X)</em>. The phenomenon of reversibility plays prominent role in the investigation of that suborder.<br />In the case of a countable language<em> L</em> and a countable domain  <em>X</em>, it is shown that ~c  and [<em>ρ]_<sub>~c  </sub></em>are analytic sets in the Polish spaces, respectively,<em> IntL (ω)× IntL (ω)</em> and <em>Int<sub>L</sub> (ω)</em>, and, using those results, in the case of a countable language and domain it is shown that the classes <em>[ρ]_</em>&cong;  and <em>[ρ]~<sub>c  </sub></em>are of the same size, and that it is a cardinals from <sub>{1,ω,c}. N</sub>ext, the hierarchy between condensational equivalence, elementary equivalence, equimorphism (bi- embedability) and other similarities of <em>L</em>-structures, determined by some similarities of their self-embedding monoids, is investigated.<br />In the last part, the phenomenon of reversibility of<em> L</em>-structures is investigated. Strongly reversible <em>L</em>-intepretations are characterized as those whose component relations are definable by the formulae of the empty language<em> L<sub>∅</sub>, </em>without quantifiers and parameters. It is shown that weakly reversible interpretations are exactly those having the property Cantor-Schrӧder-Bernstein (shorter, the property CSB) for condensations.<br />Particular emphasis is put on detecting relevant classes of reversible structures. First, the structures that are extreme elements of<em> L</em><sub>∞ω</sub>-definable classes of interpretations, under certain syntactical restrictions, are investigated. Following that, disconnected Lb-structures are investigated, where several equivalents of their reversibility are proven.</p>

Search results

Kondenzacioni poredak, kondenzaciona ekvivalencija i reverzibilnost relacijskih struktura / Condensational order, condensational equivalenceand reversibility of relational structures