Metalogik I (7,5 hp)

FIML10

Kursen ges endast på vårterminen.

Kursen förutsätter bekantskap med predikatlogikens språk och med begreppet logisk följd, definierat dels semantiskt i termer av sanning i tolkningar/modeller, dels med hjälp något härledningssystem (tablåsystem, naturlig deduktion, axiomatiskt system, etc.). Fokus ligger på beviset av fullständighetssatsen för predikatlogik, dvs att den semantiska och den syntaktiska karaktäriseringen av logisk följd i predikatlogik sammanfaller. Resultatet visades först av Gödel (1930), men vi går igenom en bevismetod som härstammar från Henkin (1949), och som är intuitivt lätt att förstå och dessutom användbar för att visa fullständighet hos många andra logiska system, t ex i modallogik. Därefter presenteras några modellteoretiska konsekvenser av (beviset för) fullständighetssatsen, såsom kompakthetssatsen och Löwenheim-Skolems sats. Kursen avslutas med en kort presentation av Gödels ofullständighetssats (och relaterade resultat), dvs att varje motsägelsefri axiomatisk teori som innehåller elementär aritmetik är ofullständig, i den meningen att det finns sanna satser som inte kan bevisas i systemet.

Kursplan: Kursplan Metalogik I (238 Kb)

Undervisningsspråk vårterminen 2020: svenska.

Aktuellt schema

Schema för Metalogik 1, våren 2020

Detaljerad kursbeskrivning

Kursen förutsätter kursen Logisk Följd eller motsvarande, vilket betyder att det förutsätts att man är bekant både med den semantiska definitionen av logisk konsekvens i termer av sanning i tolkningar/modeller, och med några vanliga härledningssystem för sats- och predikatlogik (tablåsystem, naturlig deduktion, axiomatiska (Hilbert)system). Vi inleder med en kort repetition av dessa ting (två föreläsningar), och går sedan in på kursens centralmoment, som (liksom förut) är fullständighetsresultaten för sats- och predikatlogik, dvs det faktum att alla logiskt sanna satser kan härledas i (något av) de vanliga härledningssystemen för dessa logiker (mer generellt, att alla logiska konsekvenser av givna premisser kan härledas från dem i dessa system).

Predikatlogikens fullständighet visades först av Gödel (1930), men vi går igenom en bevismetod som härstammar från Henkin (1949), och som är intuitivt lätt att förstå och dessutom användbar för att visa fullständighet hos många andra logiska system, t ex i modallogik. De tekniska verktyg som behövs för att genomföra och förstå beviset i detalj finns beskrivna i ett appendix till kursboken: elementär teori om mängder och funktioner, bevis med matematisk induktion, m m. Vi diskuterar också den filosofiska innebörden av fullständighetsresultat i logiken.

Därefter använder vi de begrepp och metoder som introducerats för att lägga ett modellteoretiskt perspektiv på logiken, dvs relationer mellan logiska satser och de modeller (tolkningar) i vilka de är sanna. På det viset får man en uppfattning om ett logiskt systems uttryckskraft. Beviset för fullständighetssatsen ger oss dessutom gratis några grundläggande resultat i modellteorin, kompakthetssatsen och Löwenheim-Skolems sats, och vi ser på några första tillämpningar av dessa.

Kursen avslutas med en genomgång av Gödels ofullständighetssats, dvs att varje motsägelsefritt axiomatiskt system som innehåller lite elementär aritmetik är ofullständigt i den meningen att det finns sanna satser som inte kan bevisas i systemet. Även Gödels andra ofullständighetssats behandlas, dvs att själva motsägelsefriheten hos ett sådant system inte kan bevisas i systemet självt. Bevisen för dessa resultat bygger på intressanta idéer som kan förklaras informellt, utan att man går igenom alla tekniska detaljer (rekursiva funktioner, härledningar i elementär arirmetik, m m), vilket är vad som görs under detta moment.

Förkunskaper

Kursen Logisk följd (7,5 hp) eller motsvarande kunskaper. Till exempel: den som utan problem läst logikmomentet på grundkursen i teoretisk filosofi kan fortsätta med Metalogik 1. Vad som krävs är att man är bekant med predikatlogikens språk och känner till några härledningssystem för predikatlogik; det finns flera kurser (vid olika institutioner) där man kan tillägna sig detta.

Undervisning

8 föreläsningar och 8 övningar.

Examination

Examinationen består av inlämningsuppgifter som görs under kursens gång. Angående vad som krävs vid examination står det följande i kursplanen:

“Logik är i första hand ett färdighetsämne, och vid examination kontrolleras även studentens förmåga att tillämpa de resultat och tekniker som presenterats. För godkänt betyg (E-D) krävs framför allt kännedom om vad sundhet och fullständighet innebär, och de viktigaste stegen i ett bevis för fullständighetssatsen för predikatlogik. För högre betyg (C-B) krävs större kännedom om detaljerna i beviset, liksom av hur kompakthetssatsen och Löwenheim-Skolems sats följer ur detta bevis, och hur dessa resultat kan tillämpas. Det högsta betyget (A) kräver därutöver att studenten väl behärskar ett modellteoretiskt perspektiv inom logik.”

Till detta kommer i år att man ska känna till (och i viss utsträckning kunna redogöra för) huvuddragen i ofullständighetssatserna och deras bevis.

Lärare

Eric Johannesson

Kurslitteratur

Kurslitteraturen utgörs av föreläsningsanteckningar av Dag Westerståhl:

Predikatlogikens fullständighet; inledning till metalogiken, Filosofiska institutionen, SU, 2014.

samt ytterligare föreläsningar (för kursens avslutande moment). Den som vill kan komplettera med andra standardläroböcker som täcker delvis samma material. Här några möjliga förslag på relativt nya böcker (men det finns många fler!):

Dirk van Dalen, Logic and Structure, Springer, 5th edition, 2013. [Boken täcker allt som gås igenom under Metalogik 1 (och det mesta av Metalogik 2) och mycket mer därtill, men är kompakt skriven och förutsätter vana att läsa matematisk text. Används för en logikkurs på Matematiska institutionen.]
Theodore Sider, Logic for Philosophy, Oxford University Press, 2010. [Denna bok avser täcka det en filosofistudent (vid ett amerikanskt universitet) behöver veta om logik. Kapitel 1–5 överlappar med Metalogik 1; fullständighet för satslogik gås igenom, men inte för predikatlogik. Dessutom finns mycket om andra logiska system, framför allt modallogik.]
G. Boolos, J. Burgess och R. Jeffrey, Computability and Logic, 5th edition (inte tidigare upplagor!), Cambridge University Press, 2007 och senare. [Denna bok, som vi tidigare haft som kurslitteratur, täcker både Metalogik 1 och Metalogik 2. Just avsnittet om predikatlogikens fullständighet (kap. 9–10 och 12–13) är lite onödigt krångligt, vilket är ett av skälen att vi inte längre använder boken. Men det finns mycket som är läsvärt i den.]
Per Lindström, First-order Logic, Thales, 2011. [En underbart kort och (mycket) kompakt framställning, vars två första kapitel täcker predikatlogikens fullständighet. Dessutom mycket mer om modellteori. Svårläst för nybörjaren.