Metalogik I

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.