Приказ основних података о дисертацији
Kondenzacioni poredak, kondenzaciona ekvivalencija i reverzibilnost relacijskih struktura
Condensational order, condensational equivalenceand reversibility of relational structures
dc.contributor.advisor | Kurilić, Miloš | |
dc.contributor.other | Madaras-Silađi, Rozalija | |
dc.contributor.other | Kurilić, Miloš | |
dc.contributor.other | Todorčević, Stevo | |
dc.contributor.other | Tanović, Predrag | |
dc.contributor.other | Šobot, Boris | |
dc.creator | Morača, Nenad | |
dc.date.accessioned | 2018-10-09T12:24:57Z | |
dc.date.available | 2018-10-09T12:24:57Z | |
dc.date.available | 2020-07-03T13:40:45Z | |
dc.date.issued | 2018-07-09 | |
dc.identifier.uri | https://nardus.mpn.gov.rs/handle/123456789/10006 | |
dc.identifier.uri | https://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija152542360674416.pdf?controlNumber=(BISIS)107294&fileName=152542360674416.pdf&id=11318&source=NaRDuS&language=sr | sr |
dc.identifier.uri | https://www.cris.uns.ac.rs/record.jsf?recordId=107294&source=NaRDuS&language=sr | sr |
dc.identifier.uri | https://www.cris.uns.ac.rs/DownloadFileServlet/IzvestajKomisije152542362206352.pdf?controlNumber=(BISIS)107294&fileName=152542362206352.pdf&id=11319&source=NaRDuS&language=sr | sr |
dc.description.abstract | Ako 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.abstract | If 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.language | sr (latin script) | |
dc.publisher | Универзитет у Новом Саду, Природно-математички факултет | sr |
dc.relation | info:eu-repo/grantAgreement/MESTD/Basic Research (BR or ON)/174006/RS// | |
dc.rights | openAccess | en |
dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
dc.source | Универзитет у Новом Саду | sr |
dc.subject | morfizmi L-struktura | sr |
dc.subject | morphisms of L-structures | en |
dc.subject | elementary quivalence | en |
dc.subject | infnitary logic L1! | en |
dc.subject | descriptive complexity | en |
dc.subject | condensational order | en |
dc.subject | ondensationalequivalence | en |
dc.subject | reversibility of L-structures | en |
dc.subject | theproperty Cantor-Schroder-Bernstein for condensations | en |
dc.subject | extreme structures | en |
dc.subject | disconnected Lb -structures | en |
dc.subject | Frasse hypothesis | en |
dc.subject | elementarna ekvivalencija | sr |
dc.subject | infinitarna logika L1! | sr |
dc.subject | deskriptivna složenost | sr |
dc.subject | kondenzacioni poredak | sr |
dc.subject | kondenzaciona ekvivalencija | sr |
dc.subject | reverzibilnost L-struktura | sr |
dc.subject | svojstvo Cantor-Schroder-Bernstein za kondenzacije | sr |
dc.subject | ekstremne strukture | sr |
dc.subject | nepovezane Lb- strukture | sr |
dc.subject | Fraisseova hipoteza307 | sr |
dc.title | Kondenzacioni poredak, kondenzaciona ekvivalencija i reverzibilnost relacijskih struktura | sr |
dc.title.alternative | Condensational order, condensational equivalenceand reversibility of relational structures | en |
dc.type | doctoralThesis | en |
dc.rights.license | BY-NC-ND | |
dcterms.abstract | Курилић, Милош; Тодорчевић, Стево; Мадарас-Силађи, Розалија; Шобот, Борис; Тановић, Предраг; Курилић, Милош; Морача, Ненад; Кондензациони поредак, кондензациона еквиваленција и реверзибилност релацијских структура; Кондензациони поредак, кондензациона еквиваленција и реверзибилност релацијских структура; | |
dc.identifier.fulltext | https://nardus.mpn.gov.rs/bitstream/id/37461/IzvestajKomisije.pdf | |
dc.identifier.fulltext | http://nardus.mpn.gov.rs/bitstream/id/37460/Disertacija.pdf | |
dc.identifier.fulltext | https://nardus.mpn.gov.rs/bitstream/id/37460/Disertacija.pdf | |
dc.identifier.fulltext | http://nardus.mpn.gov.rs/bitstream/id/37461/IzvestajKomisije.pdf | |
dc.identifier.rcub | https://hdl.handle.net/21.15107/rcub_nardus_10006 |