Seminar for Mathematical Logic
PROGRAM
Plan rada Seminara za logiku za decembar 2009.
Seminar za matematicku logiku Matematickog instituta SANU nastavlja rad u zimskom semestru 2009/2010.g. na novoj adresi: Kneza Mihaila 36/III sprat, soba 301f - sala za seminare. Cetvrtkom posle podne, ali od 15:00 sati, odrzavace se predavanja na Seminaru iz verovatnosnih logika pod rukovodstvom Profesora Miodraga Raskovica koji je u decembru 2007. dobio akreditaciju Naucnog veca Instituta. Na taj nacin, ponovo, kao pre vise decenija, postoje dva logicka seminara.
PETAK, 04.12.2009. U 16:15 SATI
Petar Markovic (Departman za matematiku i informatiku Prirodno-matematickog fakulteta Univerziteta u Novom Sadu)
Klonovi konacnog karaktera na konacnom skupu
(Clones of finite character on a finite set)
Klon operacija na nekom skupu je konavcnog karaktera ako je to skup svih operacija kompatibilnih sa nekim konacnim skupom relacija konacne arnosti. U istrazivanju racunske slozenosti Constraint Satisfaction Problema svi klonovi koji se pojavljuju su konacnog karaktera, ali taj uslov do skora nije bio iskoriscen. Ove godine je dokazano nekoliko rezultata koji uspevaju da primene konacnost karaktera klonova. Najistaknutiji od njih je rezultat L. Barto-a koji dokazuje da svaki klon konacnog karaktera koji sadrzi Jonsonove operacije mora da sadrzi i near-unanimity operaciju (cime je dokazana hipoteza L.Zadorija). Time je algoritam za resavanje Constraint Satisfaction Problema u kongruencijski distributivnom slucaju znatno pojednostavljen. Zatim, A. Kazda je pre par nedelja pokazao da svaki klon na konacnom skupu koji je klon svih operacija kompatibilnih sa jednom binarnom relacijom (drugim recima, klon svih polimorfizama konacnog digrafa) i koji sadrzi Maljcevljevu operaciju mora da sadrzi i majority operaciju (cime je poboljsao rezultate L. Egrija i predavaca). Predavanje cu zavrsiti jednim otvorenim problemom, hipotezom M. Valeriote-a.
(The clone of operations on a set is said to be of finite character if it is the set of all operations on that set which are compatible with some finite set of relations of finite arities. In the research on the computational complexity of the Constraint Satisfaction Problem, all clones which are considered are of finite character, but that fact was not applied until recently. This year a few results using the finite character of clones finally appeared. The most prominent of these is L. Barto's proof of L. Zadori's conjecture stating that any clone of finite character on a finite set which contains Jonsson operations must contain a near-unanimity operation as well. This drastically simplifies the algorithm for solving the Constraint Satisfaction Problem for templates invariant under a package of Jonsson operations. Also, a few weeks ago A. Kazda proved that if a clone C on a finite set is the clone of all operations compatible with one binary relation (i. e. the clone of all polymorphisms of a finite digraph) and C contains a Mal'cev operation, then C contains a majority operation, as well (this improves a result proved independently by L. Egri and the lecturer). I will finish the lecture with an open problem on this topic, due to M. Valeriote.)
Petak, 11.12.2009. U 16:15 SATI
Predrag Tanovic (Matematicki institut SANU, Beograd)
Teorije s tacno tri prebrojiva modela (Theories with exactly three countable models)}
Predavanje ce sadrzati pregled do sada poznatih cinjenica o teorijama s tacno tri prebrojiva modela (do na izomorfizam). The talk will contain a survey of known facts about theories with exactly three countable models (up to an isomorphism).
Petak, 18.12.2009. u 16:15 sati
Dragan Doder (Masinski fakultet Univerziteta u Beogradu)
Verovatnosna semantika za nemonotone relacije izvodjenja
(Probability semantics for non-monotone inference relations)
Predavanje sadrzi pregled relacija izvodjenja koje se koriste u vestackoj inteligenciji. Za neke od tih relacija moguce je definisati modele bazirane na nestandardnim verovatnosnim konacno aditivnim merama, sto predstavlja produzenje rezultata Lehmann-a i Magidor-a.
Petak, 25.12.2009. U 16:15 sati
Zoran Petric (Matematicki institut SANU, Beograd)
Vek Saundersa Maklejna (The hundredth anniversary of Saunders Mac Lane (1909 - 2005)- After the meeting a cocktail party)
Americki matematicar Saunders Maklejn (Saunders Mac Lane, 1909 - 2005) poznat je pre svega po tome sto je, zajedno sa Samjuelom Ejlenbergom (Samuel Eilenberg), osnovao teoriju kategorija. Karijeru je zapoceo kao logicar, a kasnije se bavio algebrom, algebarskom topologijom i, naravno, teorijom kategorija. Ovo predavanje posveceno je stogodisnjici njegovog rodjenja. Posle predavanja je koktel.
OBAVESTENJE:
Profesor Kosta Dosen je u sredu 14. oktobra 2009.g. poceo jednosemestralni kurs iz Teorije dedukcije na doktorskim studijama na Filozofskom fakultetu Univerziteta u Beogradu. Kurs se odrzava sredom u 18:00 sati u sali 301f, Kneza Mihaila 36, III sprat (sala za seminare Matematickog instituta SANU).
Plan kursa po nedeljama:
1. Prirodna dedukcija i sistemi sekvenata
2. Teoreme o normalnoj formi dokaza
3. Teorema o eliminaciji secenja
4. Posledice teoreme o eliminaciji secenja
5. Lambda racun s tipovima
6. Korespondencija Karija i Hauarda
7. Pojam kategorije, funktora i prirodne transformacije
8. Adjunkcija
9. Kartezijanske kategorije
10. Kartezijanske zatvorene kategorije
11. Koherencija u teoriji kategorija
12. Jednakost dokaza
13. Teorija dokaza i filozofija
Ovim pocinje rad Seminara u zimskom semestru.
Ukoliko zelite mesecne programe ovog Seminara u elektronskom obliku, obratite se: vdjordje@mi.sanu.ac.rs. Programi svih seminara Matematickog instituta SANU nalaze se na sajtu: www.mi.sanu.ac.rs
Beograd, 30. novembar 2009.g.
Rukovodioci Seminara: Kosta Dosen i Djordje Vukomanovic