Matematisk logik
Kursplan, Grundnivå, 1MA213
- Kod
- 1MA213
- Utbildningsnivå
- Grundnivå
- Huvudområde(n) med fördjupning
- Datavetenskap G2F, Matematik G2F
- Betygsskala
- Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
- Fastställd av
- Teknisk-naturvetenskapliga fakultetsnämnden, 8 mars 2012
- Ansvarig institution
- Matematiska institutionen
Behörighetskrav
60 hp matematik inklusive Algebra II eller Diskret matematik.
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
Skriftligt prov vid kursens slut (4 hp). Obligatoriska inlämningsuppgifter under kursens gång (6 hp).
Övriga föreskrifter
Kursen kan inte tillgodoräknas i examen tillsammans med Logik II.
Litteraturlista
- Litteraturlista giltig från och med höstterminen 2022, version 2
- Litteraturlista giltig från och med höstterminen 2022, version 1
- Litteraturlista giltig från och med höstterminen 2021
- Litteraturlista giltig från och med höstterminen 2019
- Litteraturlista giltig från och med höstterminen 2013
- Litteraturlista giltig från och med höstterminen 2012, version 2
- Litteraturlista giltig från och med höstterminen 2012, version 1