Behörighetskrav

60 hp matematik/datavetenskap inklusive Algebra II, Logik och bevisteknik I

Mål

Efter godkänd kurs ska studenten kunna

• förklara och använda grundläggande begrepp och metoder inom kursens område;
• redogöra för begreppet fullständig formell teori och formulera Gödels ofullständighetssats;
• exemplifiera och tolka viktiga begrepp i konkreta situationer, samt tillämpa resultat från kursen inom problemlösning;
• formulera viktigare resultat och satser inom kursens område, samt beskriva huvuddragen i viktigare satsers bevis;
• presentera matematiska resonemang för andra.

Innehåll

Elementär rekursionsteori: primitivt rekursiva funktioner och partiella rekursiva funktioner, egenskaper hos rekursiva och rekursivt numrerbara mängder, s-m-n-satsen, andra rekursionssatsen, något om den aritmetiska hierarkin och om relativ beräkningsbarhet.

Styrkan hos första ordningens teorier. Modeller för teorier, Tarskisemantik, fullständighetssatsen och kompakthetssatsen. Gödels ofullständighetssatser.

Modellteori: isomorfi, delstruktur, elementär ekvivalens och elementär delstruktur, Löwenheim-Skolemsatserna, Ehrenfeucht-Fraïsséspel, modellfullständighet, fullständiga teorier, algebraiska tillämpningar, icke-standard-modeller.

Undervisning

Föreläsningar och räkneövningar.

Examination

Skriftligt och eventuellt muntligt prov vid kursens slut eventuellt kombinerat med inlämningsuppgifter under kursen enligt anvisningar som lämnas vid kursens start.