Behörighetskrav

60 hp matematik. Algebra II eller Mängdlära genomgången.

Mål

Efter godkänd kurs ska studenten kunna:

• förklara väsentliga begrepp från kursen så som konsistens, fullständighet, kategoricitet, kardinalitet, (primitiv) rekursivitet, rekursiv uppräknelighet, elementär ekvivalens/delstruktur;
• formulera väsentliga resultat från kursen så som sundhetssatsen, modellexistenssatsen, fullständighetssatsen, kompakthetssatsen, villkor som är ekvivalenta med urvalsaxiomet, Löwenheim-Skolem satserna, Vaughts kriterium för fullständighet, karakteriseringar av rekursivt uppräkneliga mängder, Rices sats, Gödels ofullständighetssats;
• använda begrepp, metoder och resultat från kursen för att lösa problem rörande begreppen konsistens, fullständighet, kategoricitet, kardinalitet, rekursivitet, rekursiv uppräknelighet, elementär ekvivalens/delstruktur;
• beskriva huvuddragen i viktigare satsers bevis.

Innehåll

Det formella språket första ordningens logik (FOL) introduceras, liksom dess semantik, dvs. hur påståenden i FOL tolkas som sanna/falska i matematiska strukturer (som t.ex. grafer eller grupper). Ett formellt bevissystem för FOL beskrivs och begreppet konsistens introduceras. Ett starkt samband mellan formell bevisbarhet och logisk konsekvens i strukturer bevisas; den s.k. sundhetssatsen och fullständighetssatsen. Modellexistenssatsen är en viktig ingrediens i beviset. De mest använda axiomen inom mängdläran, betecknade ZF(C), kan uttryckas med FOL. Begreppen ordinaltal, kardinaltal och kardinalitet introduceras, liksom grundläggande räkneregler för kardinaltal. Påståenden som är ekvivalenta med urvalsaxiomet tas upp.

Kursen behandlar grundläggande modellteori, dvs. studiet av de strukturer (modeller) som uppfyller en mängd axiom som kan uttryckas med FOL, samt relationer mellan sådana strukturer så som elementär ekvivalens och (elementär) delstruktur. Kompakthetssatsen och Löwenheim-Skolem satserna bevisas, vilka har som konsekvens att om en uppräknelig mängd axiom i FOL har en oändlig modell, så har den en oändlig modell av varje oändlig kardinalitet. Begreppen 'fullständig' samt 'kategorisk' mängd av axiom behandlas, liksom Vaught-kriteriet för fullständighet. Ett kriterium, Ehrenfeucht-Fraïssé-spel, för att avgöra om två strukturer satisifierar samma påståenden inom första ordningens logik tas upp.

-.

En introduktion ges till rekursionsteorin, dvs. studiet av beräkningsbara (partiella) funktioner och beräkningsbart uppräkneliga mängder, och exempel samt kriterier för algoritmiskt olösbara problem ges. Vidare används FOL för att bevisa Gödels ofullständighetssats, som säger att de grundläggande axiomen för addition och multiplikation på de naturliga talen, tillsammans med alla instanser av induktionsaxiomen som kan formuleras i FOL, inte utgör en fullständig mängd av axiom; dvs. det finns aritmetiska påståenden som inte kan formellt bevisas eller motbevisas från dessa axiom.

Undervisning

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

Examination

Muntligt prov vid kursens slut (4 hp). Inlämningsuppgifter under kursens gång (6 hp).

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en enskild student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare för studenter med funktionsnedsättning.

Övriga föreskrifter

Kursen kan inte ingå i samma examen som Logik II.