Show simple item record

Condensational order, condensational equivalenceand reversibility of relational structures

dc.contributor.advisorKurilić, Miloš
dc.contributor.otherMadaras-Silađi, Rozalija
dc.contributor.otherKurilić, Miloš
dc.contributor.otherTodorčević, Stevo
dc.contributor.otherTanović, Predrag
dc.contributor.otherŠobot, Boris
dc.creatorMorača, Nenad
dc.date.accessioned2018-10-09T12:24:57Z
dc.date.available2018-10-09T12:24:57Z
dc.date.available2020-07-03T13:40:45Z
dc.date.issued2018-07-09
dc.identifier.urihttps://nardus.mpn.gov.rs/handle/123456789/10006
dc.identifier.urihttps://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija152542360674416.pdf?controlNumber=(BISIS)107294&fileName=152542360674416.pdf&id=11318&source=NaRDuS&language=srsr
dc.identifier.urihttps://www.cris.uns.ac.rs/record.jsf?recordId=107294&source=NaRDuS&language=srsr
dc.identifier.urihttps://www.cris.uns.ac.rs/DownloadFileServlet/IzvestajKomisije152542362206352.pdf?controlNumber=(BISIS)107294&fileName=152542362206352.pdf&id=11319&source=NaRDuS&language=srsr
dc.description.abstractAko je L relacijski jezik, kondenzacioni pretporedak na skupu IntL (X) svih L-interpretacija nad domenom X, dat je sa: ρ≼c σ ako postoji bijektivni homomorfizam (kondenzacija) f:⟨X,ρ⟩→⟨X,σ⟩. Odgovarajući antisimetrični količnik ⟨Int L (X)/~c,≤c⟩ ~naziva se kondenzacioni poredak. Za proizvoljnu L-interpretaciju ρ, klasa [ρ]~c  je konveksno zatvorenje klase [ρ]_≅ u Booleovoj mreži ⟨IntL (X),⊆⟩. Za L-interpretaciju ρ reći ćemo da je jako reverzibilna (redom, reverzibilna, slabo reverzibilna) akko je klasa [ρ]_≅  (ili, ekvivalentno, klasa [ρ]~c )) singlton (redom, antilanac, konveksan skup) u Booleovoj mreži ⟨IntL (X),⊆⟩. U cilju ispitivanja poseta ⟨Int(Lb ) (X)/~c,≤c⟩, za ρ∈IrreflX uveden je skup Dρ:={[ρ∪ΔA ](~c ):A⊆X} i pokazano je kako je poduređenje ⟨Dρ,≤c ⟩ izomorfno određenom količniku partitivnog skupa P(X). Fenomen reverzibilnosti relacijskih struktura igra istaknutu ulogu u istraživanju tog poduređenja. U slučaju prebrojivog jezika  L  i prebrojivog domena X, pokazano je da su ~c i [ρ]~c analitički skupovi u poljskim prostorima, redom, IntL (ω)×IntL (ω) i IntL (ω), i pomoću toga, pokazano ja da su, u slučaju prebrojivog jezika i domena, klase [ρ]≅  i [ρ]~c 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 L-struktura određenih nekim sličnostima njihovih monoida samoutapanja. Naposletku, temeljno je istražen fenomen reverzibilnosti L-struktura. Data je karakterizacija jako reverzibilnih L-intepretacija kao onih čije su komponentne relacije definabilne formulama praznog jezika L∅, 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. Poseban naglasak stavljen je na detektovanje relevantnih klasa reverzibilnih struktura. Pri tome, prvo su proučene strukture koje su ekstremni elementi L∞ω-definabilnih klasa interpretacija, pri određenim sintaktičkim ograničenjima, a zatim su istražene nepovezane Lb-strukture, gde je dato nekoliko karakterizacija njihove reverzibilnosti.sr
dc.description.abstractIf L is a relational language, the condensational preorder on the set IntL (X) of all L-interpretations over the domain X, is given with: ρ≼_c σ iff there exists a bijective homomorphism (condensation) f:⟨X,ρ⟩→⟨X,σ⟩. The corresponding antisymmetric quotient ⟨IntL (X)/~c,≤_c⟩ will be called the condensational order. For any L-interpretation ρ, the class [ρ]~c ) is the convex closure of the class [ρ]≅ in the Boolean lattice ⟨IntL (X),⊆⟩. An L-interpretation ρ is said to be strongly reversible  (respectively, reversible, weakly reversible) iff the class [ρ]≅  (or, equivalently, the class [ρ]~c )) is a singleton (respectively, an antichain, a convex set) in the poset ⟨ IntL (X),⊆⟩. In order to investigate the poset ⟨Int(Lb ) (X)/~c,≤_c⟩, for ρ∈ IrreflX the following set is defined Dρ:={[ρ∪ΔA ]_~c :A⊆X}. It is shown that the suborder ⟨Dρ,≤c ⟩ is isomorphic to a certain quotient of the power set P(X). The phenomenon of reversibility plays prominent role in the investigation of that suborder. In the case of a countable language L and a countable domain  X, it is shown that ~c  and [ρ]_~c  are analytic sets in the Polish spaces, respectively, IntL (ω)× IntL (ω) and IntL (ω), and, using those results, in the case of a countable language and domain it is shown that the classes [ρ]_≅  and [ρ]~c  are of the same size, and that it is a cardinals from {1,ω,c}. Next, the hierarchy between condensational equivalence, elementary equivalence, equimorphism (bi- embedability) and other similarities of L-structures, determined by some similarities of their self-embedding monoids, is investigated. In the last part, the phenomenon of reversibility of L-structures is investigated. Strongly reversible L-intepretations are characterized as those whose component relations are definable by the formulae of the empty language L∅, 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. Particular emphasis is put on detecting relevant classes of reversible structures. First, the structures that are extreme elements of L∞ω-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.en
dc.languagesr (latin script)
dc.publisherУниверзитет у Новом Саду, Природно-математички факултетsr
dc.relationinfo:eu-repo/grantAgreement/MESTD/Basic Research (BR or ON)/174006/RS//
dc.rightsopenAccessen
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/
dc.sourceУниверзитет у Новом Садуsr
dc.subjectmorfizmi L-strukturasr
dc.subjectmorphisms of L-structuresen
dc.subjectelementary quivalenceen
dc.subjectinfnitary logic L1!en
dc.subjectdescriptive complexityen
dc.subjectcondensational orderen
dc.subjectondensationalequivalenceen
dc.subjectreversibility of L-structuresen
dc.subjecttheproperty Cantor-Schroder-Bernstein for condensationsen
dc.subjectextreme structuresen
dc.subjectdisconnected Lb -structuresen
dc.subjectFrasse hypothesisen
dc.subjectelementarna ekvivalencijasr
dc.subjectinfinitarna logika L1!sr
dc.subjectdeskriptivna složenostsr
dc.subjectkondenzacioni poredaksr
dc.subjectkondenzaciona ekvivalencijasr
dc.subjectreverzibilnost L-strukturasr
dc.subjectsvojstvo Cantor-Schroder-Bernstein za kondenzacijesr
dc.subjectekstremne strukturesr
dc.subjectnepovezane Lb- strukturesr
dc.subjectFraisseova hipoteza307sr
dc.titleKondenzacioni poredak, kondenzaciona ekvivalencija i reverzibilnost relacijskih strukturasr
dc.title.alternativeCondensational order, condensational equivalenceand reversibility of relational structuresen
dc.typedoctoralThesisen
dc.rights.licenseBY-NC-ND
dcterms.abstractКурилић, Милош; Тодорчевић, Стево; Мадарас-Силађи, Розалија; Шобот, Борис; Тановић, Предраг; Курилић, Милош; Морача, Ненад; Кондензациони поредак, кондензациона еквиваленција и реверзибилност релацијских структура; Кондензациони поредак, кондензациона еквиваленција и реверзибилност релацијских структура;
dc.identifier.fulltexthttps://nardus.mpn.gov.rs/bitstream/id/37461/IzvestajKomisije.pdf
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/37460/Disertacija.pdf
dc.identifier.fulltexthttps://nardus.mpn.gov.rs/bitstream/id/37460/Disertacija.pdf
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/37461/IzvestajKomisije.pdf
dc.identifier.rcubhttps://hdl.handle.net/21.15107/rcub_nardus_10006


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record