Kursplan för Matematisk logik

Mathematical Logic

  • 10 högskolepoäng
  • Kurskod: 1MA213
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Matematik G2F, Datavetenskap G2F

    Förklaring av koder

    Koden visar kursens utbildningsnivå och fördjupning i förhållande till andra kurser inom huvudområdet och examensfordringarna för generella examina:

    Grundnivå
    G1N: har endast gymnasiala förkunskapskrav
    G1F: har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav
    G1E: innehåller särskilt utformat examensarbete för högskoleexamen
    G2F: har minst 60 hp kurs/er på grundnivå som förkunskapskrav
    G2E: har minst 60 hp kurs/er på grundnivå som förkunskapskrav, innehåller examensarbete för kandidatexamen
    GXX: kursens fördjupning kan inte klassificeras.

    Avancerad nivå
    A1N: har endast kurs/er på grundnivå som förkunskapskrav
    A1F: har kurs/er på avancerad nivå som förkunskapskrav
    A1E: innehåller examensarbete för magisterexamen
    A2E: innehåller examensarbete för masterexamen
    AXX: kursens fördjupning kan inte klassificeras.

  • Betygsskala: Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
  • Inrättad: 2012-03-08
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Reviderad: 2020-10-15
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 26, 2021
  • Behörighet: 60 hp matematik inklusive Algebra II eller Mängdlära.
  • Ansvarig institution: Matematiska institutionen

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). 
 
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 tillgodoräknas i examen tillsammans med Logik II.

Litteratur

Uppgift om kurslitteratur saknas. Ta kontakt med ansvarig institution för mer information.