Mathematical Logic and Arithmetic - NLTM010

• Title: Matematická logika a aritmetika
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2011
• Semester: summer
• E-Credits: 3
• Hours per week, examination: summer s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: doc. RNDr. Josef Mlček, CSc.
• Class: Mat. logika a teorie množin
• Classification: Informatics > Theoretical Computer Science
• Is incompatible with: NAIL016
• Is interchangeable with: NAIL016

Annotation

English

Last update: 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.

Czech

Last update: 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.

Literature

Last update: 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

Syllabus

English

Last update: 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.

Czech

Last update: ()

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.