All forms of study (i.e. undergraduate, graduate and postgraduate) require the student to pass a comprehensive formal exam. For the undergraduate and graduate programs this exam takes place at the end together with the thesis defense. In the postgraduate programs, students usually take the exam in the second year of their studies.

You will find specifications for Bachelor degree (Bc.), Master degree (Mgr.) and Ph.D. degree examinations below.

Final bachelor degree examination

Every student in the bachelor program is required to pass the Bachelor exam in the last year of his studies. The exam consists of bachelor thesis defense followed by an oral exam. The defense should not exceed 20 minutes and is started by a presentation of the thesis by the student; in case students would like to take advantage of the projector for their presentation, it is advisable to contact the secretary in advance to make necessary preparations. The oral exam only takes place in case of successful defense.

The oral exam consists of three parts, each of which should not exceed 20 minutes. The subject of the first part is Logic, the remaining parts focus on two distinct topics chosen by the student from the list given below.

Students apply to take the bachelor exam after or close to passing all credit and other requirements. The deadlines for applications are set by the faculty and the applications are handled by the SIS. Bachelor theses need to be uploaded electronically to the SIS by the deadline set by the department.  This deadline is typically later than the faculty deadline for exam applications. The exam application is conditional and is binding only after thesis submission. We kindly ask the students to inform the head of the department via e-mail ahead of time of their intention to apply for bachelor exams so that necessary planning can take place and so that a date for the exam can be set (otherwise, in particular for the February terms, the department might not set a date at all).

Bachelor degree examination requirements

Below we list typical requirements sorted according to topics.

Some basic notions are required regardless of the chosen topics, e.g. tautologies, satisfiable formula, logically valid formula, entailment, disjunctive and conjunctive normal form, prenex normal form, the deduction theorem, axiomatical theory, model, recursively enumerable and recursive sets, Post’s theorem, functions, relations and their properties, groups, rings, ordinal and cardinal numbers.

Note that it is always advisable to check with the department the current list of topics.

Typical requirements (in Czech):

Logika

• Syntax a sémantika, logické kalkuly a jejich vlastnosti
• Věta o kompaktnosti a její důsledky, axiomatizovatelné a konečně axiomatizovatelné třídy struktur
• Vlastnosti axiomatických teorií: bezespornost, úplnost, rozhodnutelnost, konečná axiomatizovatelnost, rekurzívní axiomatizovatelnost; vztahy mezi nimi
• Eliminace kvantifikátorů, definovatelné množiny
• Robinsonova a Peanova aritmetika: modely, ekvivalentní axiomatizace, S-úplnost; společné vlastnosti a vlastnosti, kterými se obě teorie liší
• Definovatelné množiny ve struktuře N přirozených čísel; slabá varianta První Gödelovy věty jako důsledek faktu, že Th(N) je nearitmetická množina
• S-korektní teorie, První Gödelova věta a její strukturální důkaz
• Rosserova věta: znění, porovnání s První Gödelovou větou, myšlenka důkazu
• Věta o autoreferenci, klasický důkaz První Gödelovy věty
• Druhá Gödelova věta, význam, Hilbertův program; Löbovy podmínky pro dokazatelnost
• Intuicionistická logika, její kripkovská sémantika a kalkuly, vztah k logice klasické

Teorie množin

• Axiomy teorie množin (ZFC)
• Cantorova věta, Cantor-Bernsteinova věta
• Věta o počtu reálných čísel (R má stejnou velikost jako potence omega)
• Axiom výběru a jeho ekvivalenty (Princip maximality, Princip dobrého uspořádání)
• Základní vlastnosti ordinálních čísel
• Transfinitní indukce, definice fundovaného univerza rekurzí
• Ordinální aritmetika
• Kardinální čísla a kardinální aritmetika, GCH
• Regulární a singulární kardinály, kofinalita

Modální logiky

• Kripkovská sémantika modální logiky, pojem normální modálni logiky;
  operace s rámci a modely (podmodel generovaný vrcholem,
  amalgamace…) a jejich aplikace
• Tradiční modální logiky K, T, K4, S4 a S5 a jejich hilbertovské
  kalkuly; varianty axiomatizace a bezprostřední důsledky axiomů, příklady
  důkazů; charakteristické třídy rámců
• Sekventové kalkuly některých modálních logik, jejich vzájemná
  simulovatelnost s hilbertovskymi kalkuly
• Logika dokazatelnosti GL: kalkuly, varianty axiomatizace,
  charakteristická třída
• Logika H, její charakteristická třída a Cresswellův důkaz, že
  není ekvivalentní s logikou GL
• Vztah modální výrokové logiky ke klasické predikátové logice:
  standardní překlad, vlastnosti, použití (např. věta o kompaktnosti)
• Úplnost některých kalkulů, vlastnost konečných modelů,
  eliminovatelnost řezů
• Bisimulace a p-morfismus, metody pro prokazování, že určitá třída
  rámců není charakteristickou třídou žádné modální logiky (není
  v modální logice definovatelná)

Rekurzivní funkce

• Definice (částečně, primitivně) rekurzívních funkcí, definice rekurzívně spočetných a (primitivně) rekurzívních množin a relací (predikátů) jako základní matematické zpřesnění pojmu algoritmus; odvozené operace s funkcemi a množinami, dvojná (ordinální) rekurze
• Některé výpočtové modely jiné než částečně rekurzívní funkce, například vývojové diagramy, jejich vzájemná ekvivalence; Churchova teze
• Aritmetizace odvození a výpočtů, věta o normální formě, enumerace částečně rekurzívních funkcí a rekurzívně spočetných množin
• Diagonální metoda; rekurzívně spočetné množiny, které nejsou rekurzívní; problém zastavení; pojem univerzální funkce; částečně rekurzívní funkce, která nemá žádné rekurzívní prodloužení
• Věta o projekci; souvislosti mezi rekurzívností funkce a rekurzívností jejího grafu; ekvivalentní definice rekurzívně spočetných množin; Postova věta; uzavřenost tříd PR, OR a RS na operace
• Věta o parametrech, m-převeditelnost, m-kompletnost, m-kompletnost problému zastavení; produktivní a kreativní množiny; kreativnost m-kompletních množin
• Věta o rekurzi, Riceova věta
• Aritmetická hierarchie, P2-kompletní množiny

Analytická filozofie

• Fregovy základní sémantické distinkce
• Russellova teorie deskripcí, Strawsonova kritika
• Deskriptivistické teorie jmen (Frege, Russell, Searle), Kripkovo pojetí vlastních jmen
• Quinův holismus
• Pojetí nutně pravdivých výroků v analytické filosofii (pozdní Wittgenstein, Quine, Kripke)
• Logický atomismus, Tarského sémantická definice pravdy

Struktury a algebry

• Pojem struktury, porovnávání struktur (morfismy, vnoření, isomorfismum, elementární ekvivalence)
• Löwenheim-Skolemovy věty, elementární vnoření, elementární extenze
• Kategoričnost teorií (Morleyho věta, jen znění)
• Ultraprodukt, ultramocnina
• Užití ultraproduktové konstrukce: kompaktnost a elementární třídy struktur
• Pojem grupy, okruhu a tělesa; Lagrangeova věta (řád podgrupy dělí řád konečné grupy)
• Částečná uspořádání a svazy (základní pojmy, algebraická a množinová definice svazu)
• Booleovy algebra, definice, základní vlastnosti
• Příklady konstrukcí Booleových algeber – Clopen algebra topologického prostoru (Cantorův prostor), Lindenbaum-Tarského algebry
• Nekonečné operace na Booleových algebrách
• Pojem regulární podalgebry
• Věty o reprezentaci (Stoneova věta, Stoneova dualita)

Historie a filozofie matematiky a logiky

• Aristotelská sylogistika, logický čtverec
• Středověká nauka de proprietatibus terminorum
• Spor o univerzálie, nominalismus a realismus v současné filosofii logiky a matematiky
• Nutně pravdivé výroky, distinkce apriorní/aposteriorní, analytický/syntetický výrok
• Teorie pravdy (korespondenční, koherenční, pragmatická; redundanční)
• Extenze vs. intenze
• Struktura výroku, singulární a obecné výrazy, „být“, synkategorematické výrazy; problémy s formalizací
• Definice a jejich různé klasifikace; chyby a problémy s definováním
• Paradoxy a jejich možná řešení či blokování
• Fregův logicismus
• Brouwerův intuicionismus
• Hilbertův formalismus

Final master degree examination

The exam consists of two parts, both of which must be passed. The first part is the thesis defense. Provided the student passes this part, he can continue to the next part which is an oral exam.

The oral exam consists of an exam focusing on Classical Logic and two exams focusing on two distinct topics chosen by the student from the list given below.

Technical and organizational details are the same as for the Bachelor Exam.

Typical requirements (in Czech):

Master degree examination requirements

Classical logic

• Vlastnosti logických kalkulů; kvantitativní aspekty, souvislosti s rekurzívně spočetnými množinami a s otevřenými problémy ve výpočtové složitosti
• Věta o kompaktnosti a její důsledky; axiomatizovatelné (tj. elementární) třídy struktur, konečně axiomatizovatelné třídy struktur; existence a struktura nestandardních modelů Peanovy aritmetiky
• Vlastnosti axiomatických teorií: bezespornost, úplnost, rozhodnutelnost, konečná axiomatizovatelnost, rekurzívní axiomatizovatelnost; vztahy mezi nimi
• Eliminace kvantifikátorů, definovatelné množiny
• První Gödelova věta, Rosserova věta a jejich strukturální důkaz; souvislosti s aritmetickou hierarchií a s efektivně nerekurzívními množinami
• Autoreference; vlastnosti Gödelovy, Rosserovy a Henkinovy sentence, formalizovatelnost těchto vlastností v Peanově aritmetice PA
• Důležité axiomatické teorie: PA, Q, ZF a GB (nověji též označovaná NBG), případně MK (Morse‑Kelley); vlastnosti těchto teorií, možnost a nemožnost konečné axiomatizovatelnosti
• Druhá Gödelova věta, význam, Hilbertův program; Löbovy podmínky pro dokazatelnost, jejich platnost a jejich další aplikace, například formalizovaná verze Druhé Gödelovy věty
• Základy logiky dokazatelnosti, její aplikace
• Intuicionistická logika, její kripkovská sémantika a kalkuly, vztah k logice klasické

Set theory

Doporučujeme kontaktovat zkoušejícího (R. Honzík) a ověřit témata ke zkoušce (předmět je pokročilejšího charakteru a v různých ročnících se může trochu lišit). K dispozici jsou sktripta (kontaktujte R. Honzíka).

• Vše jako pro bakalářskou zkoušku plus následující:
• V-hierarchie a H-hierarchie, základní vztahy a vlastnosti
• Fundovaná transfinitní rekurze, Mostowského kolaps
• Princip reflexe a jeho užití (ZF není konečně axiomatizovatelná)
• Tranzitivní třídy jako modely, interpretace (užití: equikonzistence (ZF bez fundovanosti) a ZF)
• Kombinatorika: club filtr, stacionární množiny, stromy

Philosophy of mathematics

• Platotnistics (Goedel, Balaguer) vs. non-platonostic approach to mathemathics (Benaceraff, Resnik, Shapiro; mathematical practice Maddy); historical background and philosophical reflection. 
• Constructive vs. non-constructive mathematics (Brouwer, Weyl). The nature of mathematical knowledge, the notions of proof, and verification.
• Set theory and the phenomenon of independence. The nature of axioms for mathematics (Maddy).
• Foundational frameworks for mathematics: set theory, category theory, logicism (Frege), etc.
• The nature of mathematical truth and epistemological challanges (Balaguer, Maddy, Putnam)
• Hilbert’s programme for foundation of mathematics.
• Goedel’s results and the implications for Hilbert’s programme and epistemology.
• Indispensibility arguments in mathematics. 

Mathematical structures

• Compactness of the first-order logic and applictions to models of first-order theories (eg. chromatic numbers of inifinite graphs, extension of partial orders into linear orders)
• Lowenheim-Skolem arguments; Lowenheim-Skolem paradox 
• Graph theory (finite and/or infinite combinatorics), Ramsey theorems, partition relations
• Lattices and Boolean algebras; Stone representation theorem for finite and infinite Boolean algebras
• Ultrapower and ultraproduct constructions; the proof of compactness via ultraproducts
• Algebraic structures for nonclassical logics (Hayting algebras, etc.)

Foundations of set theory and mathematics

• Axiomatic set theory (ZFC); historical background and its role in mathematics
• Construction of real numbers
• Algebraical notions: groups and rings and their basic properties
• Vector spaces and their properties
• The notion of categoricity in mathematics (the uniqueness of rationals, reals and complex numbers)
• Metric and topological spaces
• The notion of continuity; possible definitions, and connections to metric and topological spaces
• Differentation and Integration: motivations and basic definitions; Fundamental theorem of analysis.
• Alternative foundational concepts (category theory)
• New axioms for mathematics? (the phenomenon of incompleteness and independence in mathematics)

Nonclassical logics

As Modální Logiky (modal logics) pro BZK plus:

• Sémantika intuicionistické výrokové i predikátové logiky, vztah intuicionistické a klasické logiky, výrokové i predikátové (Glivenkova věta, dvojnegační překlad)
• Úplnost intuicionistické výrokové a predikátové logiky a její důsledky (rozhodnutelnost výrokové IL, velikost modelu v případě predikátové IL, vlastnost disjunkce a existence)
• Heytingova aritmetika a její vlastnosti (vlastnost disjunkce a existence, vztah k Peanově aritmetice, de Jonghova věta, rozhodnutelnost některých formulí)
• Algebraická sémantika intuicionistické výrokové logiky, silná úplnost
• Dualita algebraické a kripkovaké sémantiky intuicionistické nebo modální výrokové logiky
• Substrukturální logiky: vymezení třídy logik, algebraická a případně i kripkovská sémantika, teorie důkazů. Vybraná substrukturální logika a její vlastnosti

Proof theory

• Kalkuly přirozené dedukce klasické a intuicionistické predikátové logiky, vztah k hilbertovským a/nebo sekventovým kalkulům (vzájemná simulace)
• Věta o normalizaci, důkaz pro intuicionistickou a klasickou logiku
• Věta o normalizaci, struktura normálních důkazů a aplikace věty o normalizaci
• Sekventové kalkuly klasické a intuicionistické logiky, jejich strukturální varianty, varianta G3 a přípustnost pravidel oslabení a kontrakce
• Věta o eliminovatelnosti řezu, důkaz, vlastnosti bezřezových důkazů a aplikace věty o eliminaci řezu

Recursive functions and sets

• Definice (částečně, primitivně) rekurzívních funkcí, definice rekurzívně spočetných a (primitivně) rekurzívních množin a relací (predikátů) jako základní matematické zpřesnění pojmu algoritmus; odvozené operace s funkcemi a množinami, dvojná (ordinální) rekurze
• Některé výpočtové modely jiné než částečně rekurzívní funkce: Turingovy stroje, vývojové diagramy, jednoduchý vyšší programovací jazyk; jejich vzájemná ekvivalence, věta o normální formě; Churchova teze
• Diagonální metoda; rekurzívní funkce nebo množiny, které nejsou primitivně rekurzívní; rekurzívně spočetné množiny, které nejsou rekurzívní; problém zastavení; pojem univerzální funkce
• Věta o projekci; souvislosti mezi rekurzívností funkce a rekurzívností jejího grafu; ekvivalentní definice rekurzívně spočetných množin; Postova věta; uzavřenost tříd PR, OR a RS na operace
• Věta o parametrech, m-převeditelnost, m-kompletnost, m-kompletnost problému zastavení; produktivní a kreativní množiny; kreativnost m-kompletních množin
• Věta o rekurzi; Riceova věta; m-kompletnost kreativních množin
• Imunní množiny; prosté (simple) případně hyperprosté (hypersimple) množiny jako příklad množin, které nejsou m-kompletní
• Aritmetická hierarchie, P2-kompletní množiny
• 1-převeditelnost, 1-kompletnost, cylindry

Final PhD degree examination

Successfuly passing the state doctoral exam (together with a successful dissertation defense) is a necessary requirement for completing the postgradual program and obtaining a PhD. The faculty has some general requirements applicable to all fields of study.

The state doctoral exam consists of three parts which are chosen by the advisor in coordination with the department board.