Apstrakt: Jedan od razloga zbog kojeg su modeli ZFC teorije posebno značajni je to što svaki takav model služi kao univerzum, "okruženje" u okviru kojeg se posmatraju modeli drugih teorija prvog reda. Međutim, ZFC nije kompletna teorija: u nekim njenim modelima mogu biti tačne formule koje u drugima nisu. Forsing je metoda kojom se od jednog modela ZFC konstruiše novi, koji može imati drugačije osobine. Na taj način se izvode dokazi nezavisnosti raznih tvrđenja sa ZFC: konstrukcijom dva modela ZFC, jednog u kojem je tačna i aksioma A i drugog u kojem nije. Na ovom predavanju ćemo, pored uvoda o modelima ZFC, razmotriti i koje su to osobine koje se ne mogu menjati prelaskom iz jednog modela u drugi (tzv. apsolutne osobine). Takođe će biti objašnjeno, na intuitivnom nivou, kako se osobine koje nisu apsolutne mogu menjati.
Apstrakt: In this talk, we present a paper, in which we try to minimize the scope of possible unique metric spectra up to equivalence. While it is well known that every real spectra is equivalent to a spectra with $T$ with integral entries, it has remained open if $T$ could also maintain a desirable combinatorial form. Conant questioned if $T= \{t_1,...,t_n \}_{<}$ could be taken such that $2^i-1 \leq t_i \leq 2^n -1$. In this paper, we come to two partial answers. The first is that the largest element $t_n$ can be chosen such that $t_n\leq 2^n $. Approximating a full solution, we also observe $T$ with the combinatorial form $2^i \leq t_i \leq 2^{n+1}$. Our methods are rather unique in the field as we utilize linear optimization and convex polyhedra to achieve our results. We use these results to computationally check the conjecture for $n=7$. Our work aims to approach a full characterization of metric spectra, and simplify future computational endeavors in the field.
Apstrakt: Topologies can be expanded with the help of ideals, using the local function, an operator resembling the closure of a set. The aim of this talk is to define the ideals which enable us to create this topology simultaneously making a specific set A open. We study certain properties of this extended topology, especially under the assumption that A is a preopen set. Further, we reflect on the ideal topological space in which the ideal is generated by a chosen family of dense sets. Here we prove that the generated topology by this ideal is submaximal, but not always maximal connected. This is joint work with Anika Njamcul.
Apstrakt: Пол Коен је 1964. конструисао модел у коме важе ZF аксиоме, али не и аксиома избора (па чак ни аксиома зависног избора). Халперн и Леви су 1971. доказали да у том моделу важи BPI (тврђење да свака Булова алгебра има прост идеал). У сврху тог доказа, Халперн и Лојхли су 1966. доказали дубоко ремзијевско комбинаторно тврђење које зовемо Халперн-Лојхлијевом теоремом. Касније је Харингтон доказао Халперн-Лојхкијеву теорему на елегантнији начин форсингом. Овде се дају алтернативе Халперн-Лојхлијевој теореми у три облика - тврђења о Коеновом симетричном моделу, тврђења о пољским просторима у ZFC моделима са много додатих Коенових реалних бројева (као и пратећим теоремама апсолутности) и у виду класичних ZFC теорема.
Apstrakt: Na predavanju će biti predstavljen Todorčevićev rezultat da je svaka Frešeova grupa koja ima bazičku tačku metrizabilna.
Apstrakt: Topological Ramsey spaces have been introduced by Carlson in 1988 and have been applied successfully to various fields of mathematics ranging from set theory to Banach spaces. In contrast to that, not much is known about topological Ramsey spaces that can be associated to Fraïssé limits. In this talk we present a simple construction of a topological Ramsey space of copies of an arbitrary Fraïssé limit whose age is strongly amalgamable. We conclude the talk with a proposal of a research project involving small cardinals of dense copies of such Fraïssé limits. This is joint work with Natasha Dobrinen.
Apstrakt: U ovom preglednom predavanju biće reči o nekoliko tipova nestandardnih proširenja skupa N prirodnih brojeva, a to su: (1) nestandardni modeli Peanove aritmetike, (2) nestandardni modeli kompletne aritmetike i (3) nestandardni modeli s Principom transfera i eventualnim dodatnim svojstvima. Ova proširenja pominjana su na nekim ranijim predavanjima na seminaru, a biće korišćena i ubuduće. Definisaćemo sve ove vrste proširenja, pričati o nekim njihovim osobinama i posledicama tih osobina, kao i načinima da se dokaže njihova egzistencija. Kao bonus, pomenućemo i nestandardne modele ZFC teorije.
Apstrakt: Topološki prostor X je reverzibilan akko je svaka neprekidna bijekcija X u X otvoreno preslikavanje (tj. homeomorfizam).
Relacijska struktura X je reverzibilna akko je svaki bijektivni homomorfizam (kondenzacija) X u X izomorfizam.
Klasa reverzibilnih struktura uključuje mnoge relevantne (npr. euklidske prostore konačne dimenzije (R^n), kompaktne Hausdorfove prostore, linearna uredjenja, Bulove algebre) a isto važi za klasu nereverzibilnih struktura (tu su npr. Banahovi prostori beskonačne dimenzije, Rado graf...).
Veliki deo predavanja biće razumljiv širokom auditorijumu (motivacija, istorija, poznati rezultati). Na kraju će biti navedeni neki novi rezultati.
Teorema 1: Relacijska struktura X kardinalnosti k nije reverzibilna akko postoji back-and-forth sistem parcijalnih kondenzacija (b.f.s.p.k.) P koji sadrži konačnu "lošu kondenzaciju" i ima Berov broj veći od k. Poslednji uslov se može zameniti sa:
(a) "P je k-zatvoren", u svim modelima ZFC;
(b) "P je ccc", ako je k manje od c (kontinuuma), u modelima MA;
(c) "P je proper", ako je k manje od c, u modelima PFA.
Reverzibilna struktura je destruktibilna akko prestaje da bude reverzibilna u nekom (forsing) povećanju univerzuma.
Teorema 2: Reverzibilna relacijska struktura X je destruktibilna akko postoji b.f.s.p.k. P koji sadrzi konačnu "lošu kondenzaciju", akko postoji b.f.s. konačnih parcijalnih kondenzacija P koji sadrži "lošu kondenzaciju" i generički dodaje novu kondenzaciju - svedoka nereverzibilnosti u proširenju univerzuma.
Teorema 3: Neka je X reverzibilna relacijska struktura kardinalnosti k manje od c. Tada
(a) Ako je X prebrojiva struktura, onda nije destruktibilna;
(b) (MA) X nije ccc-destruktibilna;
(c) (PFA) X nije proper-destruktibilna.
Apstrakt: Svaki pretporedak je mala kategorija. Obrat, naravno, ne važi. Cilj današnjeg izlaganja je da pokažemo da pretporedak koga pre-adjunkcije zavode među malim kategorijama sa Remzijevim svojstvom predstavlja uopštenje Tukeyjevog poretka, i da izolujemo najmanji element -- klasu kategorija koje su Remzi-najslabije.
Apstrakt: Na predavanju ćemo uvesti Tukeyev poredak parcijalnih uredjenja i skup pcf(A) za skup regularnih kardinala A, kao i jedan problem koji ih povezuje. Plan je da sve definicije i tvrdjenja budu vrlo elementarni.
Apstrakt: Na predavanju cu predstaviti deo zajednickog rada sa K. Krupinjskim i Dz. Lijem. Definisacu (i pokusacu da opravdam njihovo uvodjenje) nekoliko Remzijevih svojstava u kontekstu teorija prvog reda, i dati odgovarajuce dinamicke karakterizacije.
Apstrakt: A. Bulatov je poslednjih 20-tak godina razvijao svoju varijantu ispitivanja lokalnog ponašanja algebre koja se nastavlja i nadgrađuje teoriju pitomih kongruencija D. Hobija i R. Mekenzija. On se restrikuje na pogodno izabrane term redukte algebre i onda definiše grafove sa tri boje ivica (A, S i M). Koristeći svoju teoriju, razrešio je dugo istraživano pitanje složenosti. Problema zadovoljenja uslova (najavljen 2017., rad godine ACM).
U ovom radu, mi dajemo drugi pristup koji pojednostavljuje definiciju Bulatovljevih grafova i skraćuje mnoge od dokaza. Koristimo dve vrste ivica (AS i SM), a redukt na koji restrikujemo su minimalno-Tejlorove algebre, definisane prvi put u radu L. Bartoa, Z. Brejdija, A. Bulatova, M. Kožika i D. Žuka. Neke od rezultata smo i pojačali. Istraživanje je u toku, pa nismo još sve rezultate prepričali na našim grafovima, ali smo uvereni da je samo pitanje vremena dok to ne obavimo. Prepričavamo samo opštu teoriju Bulatova, najnoviju verziju (zahvata tri rada i deo četvrtog), a ne njegov dokaz dihotomije Problema zadovoljenja uslova (ostatak tog četvrtog rada i peti rad). Nadamo se da će naši razultati omogućiti primenu teorije obojenih grafova algebre i na druge otvorene probleme.
U ovom predavanju, daćemo naše definicije grafova, prikazaćemo koje smo rezultate dokazali, a koji još nisu ispisani. Nećemo dokazivati ništa ili skoro ništa, da bismo pokrili što više materijala. Ovo je zajednički rezultat sa Z. Brejdijem i M. Kožikom.
Apstrakt: Konačna utopivost (finite embeddability) je relacija između skupova prirodnih brojeva koja se na prirodan način prenosi na ultrafiltere. Njena (originalna) aditivna verzija proučavana je u radovima Di Nassa, Blassa i Luperi Baglinija. Ispostavlja se da se multiplikativna verzija ove relacije uklapa na prirodan način u sliku relacija deljivosti na ultrafilterima, preciznije nalazi se (po jačini) između dve takve relacije. To omogućuje da se neke njene osobine izvode iz osobina relacija deljivosti, što će biti prikazano na ovom predavanju.
Apstrakt: Sudoku je veoma popularna kombinatorna igra za jednog igrača u kojoj je potrebno popuniti tablu 9x9 brojevima 1, 2, ..., 9 prema veoma jednostavnim pravilima. Iako ovu igru mnogi doživljavaju kao „matematičke ukrštene reči" savremena Sudoku zajednica je došla do niza netrivijalnih strategija koje se primenjuju na intuitivnom nivou. Cilj ovog izlaganja je da postavi matematičke osnove Sudoku logike i da prikaže strog dokaz dve netrivijalne strategije rešavanja Sudoku problema: Strategije jedinstvenog deducibilnog rešenja, i Gurtove teoreme o simetričnoj postavci.
Apstrakt: Skiciraćemo dokaz da MA(k) implicira da svaka kolekcija P_c-tačaka kardinalnosti najviše k, koja ima P_c-tačku kao RK gornje ograničenje, mora imati P_c-tačku i kao donje RK ograničenje. Ovo je zajednički rad sa Dilipom Raghavanom i Jonathanom Vernerom.
Apstrakt: In this talk we provide purely categorical proofs of two important results of structural Ramsey theory: the result of M. Sokić that the free product of Ramsey classes is a Ramsey class, and the result of M. Bodirsky that adding constants to the language of a Ramsey class preserves the Ramsey property. The proofs that we present here ignore the model-theoretic background of these statements. Instead, they focus on categorical constructions by which the classes can be constructed generalizing the original statements along the way. It turns out that the restriction to classes of relational structures, although fundamental for the original proof strategies, is not relevant for the statements themselves. The categorical proofs we present here remove all restrictions on the signature of first-order structures and provide the information not only about the Ramsey property but also about the Ramsey degrees.
Apstrakt: Inside the field of complex systems, one relevant scenario is the following: given the data-generating system, discover the causal-effect relationships among the variables. Here, our goal is to investigate emergent/synergic relationships, i.e., given a target a cause depend on another to produce an influence. By combining techniques from artificial intelligence and information theory we analyzed the contributions of the mutual information (MI) and conditional mutual information (CMI) from the sets of variables that reveal causal influences showing how synergic information is contained necessarily on CMIs. Also, by exploring the mathematical structure of the synergic sets and using classical results from Ramsey's theory we argue that MIs with large datasets contain arbitrary correlations. These correlations appear only because of the size and, not the nature, of the data. We finalize discussing how these results propose a review of some of the assumptions of well-known causal discovery algorithms.
Apstrakt: U ovom predavanju, drugom u seriji o SMB algebrama, dokazacemo da je klasa S svih SMB algebri jedan varijetet sa konacnom bazom identiteta, definisacemo njegov podvarijetet "pravilnih" SMB algebri i bavicemo se pitanjima generisanja kongruencija u SMB algebrama. Predavanje zavrsavamo primenama u pravcu Parkove hipoteze.
Apstrakt: The starting point of this talk is the recent categorical understanding of structural Ramsey degrees, which then leads to a way to compute entropy of an object in a small category not as a measure of statistical, but as a measure of its combinatorial complexity. The new entropy function we propose, the Ramsey entropy, is a real-valued invariant of an object in an arbitrary small category. Motivated by combinatorial phenomena (structural Ramsey degrees) we build the necessary infrastructure and prove the fundamental properties using only special partitions imposed on homsets.
Apstrakt: The aim of this talk is to report on the most recent results from an ongoing research concerning the classification of oriented graphs with respect to polymorphism-homogeneity. From the onset, a clear distinction will be made between the observed structures on the basis of whether or not they possess any loops. Two subclasses will thus naturally arise, one of which will yield satisfactory results and the other feistier one which will leave behind a few subclasses that will have been tackled in the meantime. This is joint work with Christian and Maja Pech.
Apstrakt: U ovom predavanju definisacemo jedan varijetet algebri sa jednom binarnom i jednom ternarnom operacijom. Pokazacemo da se pojavljuju dosta cesto kao faktori podalgebri od Tejlorovih algebri i da su u nekom smislu "najgori slucaj" za odredjenu vrstu problema na Tejlorovim algebrama. Ovo predavanje ce ukljuciti rezultate R. Mekenzija, P. Djapica, A. Prokica i predavaca. Ovo je prvo od najvise tri predavanja o SMB algebrama. Ostala predavanja, ako bude interesa, ce se posvetiti poredjenju dva dokaza CSP dihotomije (tu ce biti i rezultata A. Bulatova, M. Marotija i D. Zuka) i nasim istrazivanjima u pravcu Parkove hipoteze.
Apstrakt: Neka je betaN skup ultrafiltera na skupu N prirodnih brojeva, i elementi skupa N su izjednačeni sa glavnim ultrafilterima. Kvaziuređenje | na betaN, ekstenzija relacije deljivosti na N, proučavano je u nekoliko prethodnih radova predavača. Kongruencija po modulu m (m prirodan broj) može se proširiti na prirodan način na betaN. Ispitaćemo, za početak, u kojoj meri se ovo proširenje slaže sa |. Potom ćemo razmotriti dva načina da se definiše i kongruencija po modulu U, gde je U neglavni ultrafilter. Drugi od ta dva načina vodi nas do prirodnog pojačanja relacije deljivosti ultrafiltera |. Razmotrićemo i koliko su ove nove relacije kongruentnosti saglasne sa relacijama deljivosti.
Apstrakt: The modern theory of homogeneous structures begins with the work of Roland Fraïssé. His fundamental results traced a road for classification of homogeneous structures, which can be witnessed by results of Gardiner, Woodrow, Lachlan, Schmerl, Cherlin, Cameron, and others. The theory developed in last 70 years is placed in the border area between combinatorics, model theory, algebra, and analysis. We turn our attention to the combinatorial pillar of this theory, namely, the work on the classification of structures for given homogeneity types. Of the special interest are homomorphism-homogeneous ones, introduced 2006 by Cameron and Nešetřil, as well as polymorphism-homogeneous structures, introduced in 2015 by Pech and Pech. In this talk, I will discuss several approaches for classifying homomorphism- and polymorphism- homogeneous structures. Special emphasis will be given to two different methods that are used for the classification of homomorphism- and polymorphism-homogeneous oriented graphs. This is joint work with Bojana Pantić and Christian Pech.
Abstract: A partially ordered set is said to be directed if every finite subset has an upper bound. In the talk we will introduce the notion of Tukey reducibility between directed sets, and present some basic facts about it.
Abstract: In this talk we show that nontrivial varieties of algebras enjoy various dual Ramsey properties. The search for dual Ramsey statements has been an important research direction in the past 50 years not only because dual Ramsey results are relatively rare in comparison to the vast number of ``direct'' Ramsey results, but also because they require intricate proof strategies and are usually more powerful than their ``direct'' analogues. It turns out that classes of algebras are a gold mine of dual Ramsey results. In order to prove various dual Ramsey statements for classes of algebras we develop a completely new set of strategies that rely on the fact that right adjoints preserve the Ramsey property while left adjoints preserve the dual Ramsey property. We then consider varieties (that is, equationally defined classes) of algebras as Eilenberg-Moore categories for a monad and show that for every nontrivial variety of algebras all the finite algebras have small dual Ramsey degrees, and that every finite algebra has a finite dual big Ramsey degree with respect to Borel
Abstract: Generalizing the classical results of F. P. Ramsey from the late 1920's, the structural Ramsey theory originated at the beginning of 1970's. In this talk we give a brief overview of fundamental results of structural Ramsey theory, explain the problems that the theory has encountered in its 50 year long history, and introduce the modern apparatus of Ramsey degrees (small and big). In the talk we focus on the categorical reinterpretation of basic notions of Ramsey theory.
Abstract: Following a short introduction to nonstandard arithmetic, we will explain its connection to the Stone-Čech compactification, as well as the place of the divisibility relation. Several results will be obtained using nonstandard methods. The main result we will prove is: the divisibility hierarchy contains a copy of the standard order on the reals.
Apstrakt: Nakon kratkog uvoda u nestandardnu aritmetiku, objasnićemo njenu vezu sa Stone-Čechovom kompaktifikacijom, kao i to kako se deljivost ultrafiltera uklapa u tu vezu. Izvešćemo nekoliko rezultata koristeći nestandardne metode. Glavni rezultat koji dokazujemo je: hijererhija deljivosti ultrafiltera sadrži kopiju standardnog uređenja realnih brojeva.
Abstract: We introduce divisibility relation on the Stone-Cech space of ultrafilters on the set of natural numbers \(\mathbb N\), which is an extension of the ordinary divisibility on \(\mathbb N\). The ordering obtained in this way can be split into two different parts: "the upper one" and "the lower one". In the talk we will discuss the lower part of this hierarchy, where ultrafilters are arranged into levels, similar to the arrangement of natural numbers according to the number of their prime divisors. For example, the first level (without considering number one) consists of prime ultrafilters, the ones divisible only by themselves and unity. However, we will prove that, under CH, for each prime ultrafilter \(U\), at every level there are \(2^{\mathfrak c}\) ultrafilters whose only prime divisor is \(U\).
Apstrakt: Na Stone-Čechovom prostoru ultrafiltera na skupu prirodnih brojeva \(\mathbb N\) uvodimo relaciju deljivosti, ekstenziju relacije deljivosti na \(\mathbb N\). Uređenje dobijeno na taj način može se podeliti na dva sasvim različita dela: "donji" i "gornji". Na ovom predavanju razmotrićemo donji deo te hijerarhije, na kojem su ultrafilteri podeljeni na nivoe, slično podeli prirodnih brojeva prema broju prostih delilaca. Na primer, prvi nivo (ne računajući jedinicu) čine prosti ultrafilteri: deljivi samo sobom i jedinicom. Dokazaćemo međutim da, uz pretpostavku CH, za svaki prost ultrafilter \(U\) na svakom nivou postoji \(2^{\mathfrak c}\) ultrafiltera čiji je jedini prost delilac \(U\).