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 [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• 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
• Je neslučitelnost pro: NAIL016
• Je záměnnost pro: NAIL016

Anotace

čeština

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.

angličtina

Poslední úprava: T_KTI (22.05.2002)

Recursive functions and relations, sequence and expression numbers. Representability. Recursively enumbrable sets. Undecidability and incompleteness. Some undecidable theories and structures. Second Gôdel's theorem on consistency. Partial recursive functions: universal functions, iteration theorem, recursion theorem, indices, fixed point theorem, Rice theorem. Arithmetical hierarchy. About models of arithmetics.

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

čeština

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.

angličtina

Poslední úprava: T_KTI (19.05.2004)

The Peano, Robinson and Presbourger arithmetic. Sigma-completeness. A formalization in an arithmetic.

The recursive functions, relations and recursive enumerable sets. Representability. The undecidability

and incompleteness, the strong undecidability. The partial recursive functions. The arithmetical hierarchy.

Gödel's second incompleteness theorem. Models of arithmetics.