PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Matematická logika a aritmetika - NLTM010
Anglický název: Mathematical Logic and Arithmetic
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2011
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: zrušen
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Josef Mlček, CSc.
Třída: Mat. logika a teorie množin
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: T_KTI (22.05.2002)
Přednáška se zabývá otázkami formalizace matematiky, zejména pokud jde o problémem rozhodnutelnosti, úplnosti, dokazatelnosti bezespornosti a konečné axiomatizovatelnosti a zmiňuje se i o konstrukci modelů aritmetiky. Formalizace se opírá o rekurzivní funkce a množiny, podstatně pak o větu o reprezentovatelnosti, což umožní vyložit ještě navíc základní nauku o částečně rekurzivních funkcích a aritmetické hierarchii.
Literatura
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)
  • J.R.Shoenfield: Mathematical Logic, Addison-Wesley, 1967
  • J.D.Monk: Mathematical Logic, Springer-Verlag, 1976
  • R.M.Smullyan: Gödel's Incopmleteness Theorems, Oxford Univ. Press, Inc., New York, Oxford, 1992

Sylabus -
Poslední úprava: ()

Formální aritmetiky 1. rádu: Robinsonova, Presbourgerova a Peanova aritmetika. Problém modelu. (Modely s prvočíselnými dvojčaty.) Věta o sigma-úplnosti. Rekurzivní relace a funkce, rekurzivně spočetné množiny. Aritmetická reprezentace syntaxe. Reprezentovatelnost rekurzivních relací a funkcí, kódování rekurzivních množin. Veta o nerozhodnutelnosti. Veta o neúplnosti. Diagonální lemma. Gödelova a Rosserova formule. Reprezentace a slabá reprezentace v numerické teorii. Rekurzivní neoddělitelnost. Silná nerozhodnutelnost. Kriteria nerozhodnutelnosti. Rozhodnutelnost konkrétních teorií. Podstatně, silně a dedičně nerozhodnutelné teorie. Kritéria úplnosti. (Úplnost Presbourgerovy aritmetiky a jiných teorií.) Částečně rekurzivní funkce. Věta o indexu, iteraci, pevném bodu, halting problem, Riceova věta. Kreativní množiny. Aritmetická hierarchie. Formalizace dokazatelnosti. Löbova věta. Formalizace syntaxe v Peanove aritmetice. Věty o nedokazatelnosti bezespornosti. (2. Gödelova věta.) Problém konečné axiomatizovatelnosti. Algebra definovatelných množin modelu aritmetiky.

 
Univerzita Karlova | Informační systém UK