Studentsky logicky seminar - drivejsi program
(Student logic seminar - past program)

The outline of the program in past semesters is given in English from year 2013/14 onwards, before then only themes are in English.


  • Letni semestr 06/07: Teorie konecnych modelu (Finite model theory)

    Pro ilustraci, prehledovy clanek R.Fagina, skripta J.Vaananena a M.Otta). Toto bylo doplneno prednaskami hostu: Neil Thapen (prednaska Resolution and pebbling games) a Pavel Pudlak (prednaska Resolution proofs and games).

  • Zimni semestr 07/08: Studium clanku
    Dana Scott, A proof of the independence of the continuum hypothesis, Mathematical Systems Theory, 1, (1967), str.89-111.

    Toto je jeden z nejkrasnejsich prehledovych clanku v matematicke logice vsech dob. Byl napsan pro matematiky bez prupravy v matematicke logice a je dostupny i matematickym zacatecnikum. Predklada dukaz, ze tzv. Hypoteza Kontinua (tez jeden ze slavnych Hilbertovych problemu) neni dokazatelna v teorii mnozin.

  • Letni semestr 07/08: Omezena aritmetika (Bounded arithmetic)

    Omezena aritmetika je souborny nazev pro skupinu teorii (formalne podteoriich Peanovy aritmetiky). Tyto teorie matematicky podchycuji neformalni pojem "feasible reasoning", podobne jako pojmy (pravdepodobnostni) polynomialni algoritmus ci log-space algoritmus (a rada dalsich) formalizuji pojem "feasible computation". Literatura.

    Paralelne s timto tematem oragizoval student p.Jan Pich dalsi studium literatury o konecne teorii modelu, zejmena skripta M.Otta - viz informace o letni semestru 06/07 vyse (ucast na tomto drivejsim seminari neni podminkou).

  • Zimni semestr 08/09: Booleovska slozitost (Boolean complexity)

    Radu otevrenych problemu v teorii vypocteni slozitosti (vcetne tzv. P vs. NP problemu) lze redukovat na ukol dokazat vhodny spodni odhad na velikost obvodu pocitajici konkretni funkci. Potrebne odhady neumime zatim dokazat pro obecne obvody, ale pouze pro obvody splnujici dodatecna omezeni (konstatni hloubky, monotonni a pod.). Toto tema je jednou z fundamentalnich souvislosti mezi logikou a teorii vypocetni slozitosti. Literatura.

  • Letni semestr 08/09: Slozitost resoluce (Complexity of resolution)

    Resoluce (vyrokova) R je jednoduchy a elegantni dukazovy system pro dokazovani nesplnitelnosti CNF formuli. Jeji verse jsou v zaklade (primo ci neprimo) mnoha systemu pro automaticke dokazovani.

    V seminari se budeme zabyvat tzv. "dukazovou slozitosti" resoluce. Obecnym cilem dukazove slozitosti je porozumet slozitosti dukazu (merene zejmena jejich delkou) v ruznych dukazovych systemech. Delky dukazu odpovidaji casu nedeterministickych algoritmu. Dukazova slozitost je tak dalsim z temat spojujicich matematickou logiku a teorii vypocetni slozitosti.

    Resoluce je jednim z nejlepe prozkoumanych systemu a lze se na ni naucit radu metod vhodnych i ke studiu silnejsich systemu.
    Podivame se zejmena na nektera temata z nasledujiciho seznamu (dle casu): obecne cile dukazove slozitosti, delka, sire a prostor dukazu v R a jejich vztah, spodni a horni odhady na delky dukazu v R, tzv. feasible interpolation pro R, souvislost prostoru s oblazkovou hrou z t.konecnych modelu, kriteria pro spodni odhady v jazyce teorie modelu, ne-automatizovatelnost hledani kratkych dukazu, zesileni R: systemy R(k) a tzv. "rozsirena resoluce" ER, souvislosti s omezenou aritmetikou.
    Literatura.

  • Zimni semestr 09/10: Teorie modelu usporadaneho telesa realnych cisel a o-minimalita (The theory of the ordered real closed field and o-minimality)

    Eliminace kvatifikatoru pro RCF a jeji dusledky pro definovatelne mnoziny. O-minimalita a jeji obecne dusledky.
    Literatura.
    ( Nektere vety jsou obtizne a museji je prednaset dva studenti soucasne.)

    Host: 12. a 19.10.2009 Lou van den Dries (U. of Illinois, Urbana)

  • Letni semestr 09/10: Teorie modelu telesa komplexnich cisel aneb uvod do geometricke teorie modelu (The theory of the field of complex numbers and the introduction to geometric model theory)

    Toto je zaklad moderni teorie modelu. Eliminace kvatifikatoru pro ACF a jeji dusledky pro definovatelne mnoziny. Minimalita a jeji obecne dusledky. Pregeometrie a geometrie minimalnich struktur. Literatura.

  • Zimni semestr 10/11: NP vyhledavaci problemy (NP search problems)

    NP vyhledavaci problem je dan polynomialne rozhodnutelnou relaci R(x,y), ktera ma tu vlastnost, ze pro kazde x existuje y (delky polynomialne omezene v delce x) t.z. plati R(x, y), tzv. reseni pro x. Ukolem je ze vstupu x nejake reseni y spocitat. Rada prirozenych uloh v diskretni matematice ma tuto formu.

    Slozitost NP vyhledavacich problemu je mozne porovnat s pouzitim pojmu polynomialni simulace. Rada problemu a vzajemnem vztahu ruznych prirozenych NP vyhledavacich problemu je otevrena a napr. neni znamo, jestli existuje uplny problem.

    NP vyhledavaci problemy hraji i vyznamnou roli v logice (omezena aritmetika a dukazova slozitost).

    Hoste:
    Neil Thapen: Game induction search problems (25.11.2010)
    Pavel Pudlak: Feasible incompleteness thesis (sekce 3), ( 9.12.2010)

    Literatura.

  • Letni semestr 10/11: Gödelovy vety a slozitost (Godel's theorems and complexity)

    Gödelovy vety o neuplnosti jsou fundamentalnim poznatkem o zakladech matematiky a mely a maji radu konkretnich dusledku v matematicke logice a v informatice. Existuji i jejich kvantitativni verse, ktere misto o existenci ci neexistenci dukazu hovori o existenci ci neexistenci dukazu nejak omezene velikosti.

    Formalni dukazy jsou uzce svazany s vypocty a tak neni prekvapenim, ze tyto kvantitativni verse jsou relevantni pro teorii vypocetni slozitosti. Jedna plausibilni (ale dosud nedokazana) kvantitativni verse druhe Gödelovy vety o neuplnosti implikuje, ze tridy vypocetni slozitosti P a NP jsou ruzne (to je fundamentalni otevreny problem).

    Literatura.

  • Zimni semestr 11/12: Open problems in logic & complexity

    This semester the seminar was a part of the programme of the Special semester in Logic & Complexity that run from 19.September until 18.December. It was open to all students even if they did not took part in other special semester activities. Program.

  • Letni semester 11/12: -

    Seminar se tento semestr nekonal - byl jsem v Cambridge.

  • Zimni semester 12/13: Nestandardni modely aritmetiky (Nonstandard models of arithmetic)

    Jednou ze zakladnich vlastnosti logiky prvniho radu (predikatove logiky) je kompaktnost, jejimz dusledkem je existence tzv. nestandardnich modelu. Obecne se takovym modelem mysli kazdy model nejake teorie, ktery se lisi od jejich "zamyslenych" standardnich modelu. Napr. teorie konecnych teles ma i nekonecny model - nekonecne teleso, teorie usporadaneho telesa realnych cisel ma i model s infinitesimalne malymi cisly (to je zaklad tzv. nestandardni analyzy) a teorie usporadaneho okruhu celych cisel (tzv. aritmetika) ma i model s nekonecne velkymi cisly.

    Prave na priklade aritmetiky lze demonstrovat radu vlastnosti techto nestandardnich modelu, zpusoby jejich konstrukci a jejich vyuziti v matematicke logice. I jen zakladni poneti o strukture techto modelu umoznuje lepe chapat radu pokrocilejsich temat ze vsech oblasti matematicke logiky.

    Literatura.

  • Letni semestr 12/13: pokracovani tematu ze zimniho semestru (a continuation from the Winter semester)

  • Winter semester 13/14: Second order arithmetic

    First order arithmetic studies the structure of natural numbers with the usual arithmetic operations in the context of first-order logic. One can talk about sets of numbers only as long as they are definable. A prominent theory used in this context is Peano arithmetic PA. It is mutually interpretable with the theory of finite sets.

    Second order arithmetic approaches the structure of natural numbers together with the class of sets of natural numbers. One can talk directly about sets and, for example, quantify them in formulas. A prominent theory used in this context is Z_2 going back to Hilbert - Bernays. It lies somewhere between the theory of finite sets and set theory ZFC and a lot of mathematics can be formalized in it.

    It has also several natural subtheories and H.Friedman showed that many basic theorems of various fields of mathematics are logically equivalent to one of just five such subsystems (this is called reverse mathematics).

    The aim of the seminar was to learn some of the topics involved. We used S.Simpson's book "Subsystems of second order arithmetic".

  • Summer semester 13/14: Limits of finite structures

    Model theory knows several constructions of infinite structures that can be interpreted as limits of classes of finite structures (e.g. ultraproducts, compactness arguments, non-standard analysis, amalgamation constructions, versions of forcing, asymptotic classes, pseudofinite structures, robust classes, etc.). These constructions are relevant to core parts of model theory as well as to its applications (e.g. the currently popular notion of "limits of graphs").

    Obviously, we were not able to get to all topics listed on the literature page. We first read Vaananen's notes on pseudofinite structures and then parts of Goldbring's lecture notes on nonstandard analysis, including Chpts.15 and 16 on measure theory (Loeb's measure in particular) and a proof Szemeredi's regularity lemma using it. Finally we went through a nonstandard approach to the construction of Lovasz-Szegedy's limits of graph sequences, following Elek-Szegedy's paper (with some simplifications using facts well-known in nonstandard analysis).

  • Winter semester 14/15: Geometric model theory

    At the heart of Geometric model theory lies the fact that the relation of definability (or some related notion) in certain first-order structures has formal properties analogous to various dependence relations (linear, algebraic,...) in geometry. Geometric approach can be then used to study, construct and classify first-order structures or, on the other hand, to make various geometric situations amenable to model-theoretic methods. This is the basis of some of the most remarkable applications of model theory during the last twenty years.

    Our aim was to learn the basics on which one can base a later study of more advanced topics. During the winter semester we worked through the first four chapters of Zilber's notes "Elements of geometric stability theory" (see the literature page).

  • Summer semester 14/15: Geometric model theory

    Continuation from the winter semester: we read some more from Zilber's notes and then most of Scanlon's survey article "Diophantine geometry from model theory" 5(available via the literature page).

  • Winter semester 2015/16:

    The seminar had a form of a reading group run by Igor Carboni Oliveira, a postdoctoral visitor from Columbia University. Information about papers covered is at Igor's seminar web page.

  • Summer semester 2015/16: Feasible complexity theory

    Run by Igor C. Oliveira as a reading group (texts studied are listed there).

  • Winter semester 2016/17: Infinitary methods in complexity theory

    Run by Michal Garlik and Igor C. Oliveira: topics and relevant literature studied.

  • Summer semester 2016/17: Models of bounded arithmetic

    This was a follow-up on the previous semester: topics.