Wiskundige logica

Mathematical Logic

6 EC

Semester 2, periode 4, 5

5122WILO6Y

Eigenaar Bachelor Wiskunde
Coördinator N. Bezhanishvili
Onderdeel van Bachelor Wiskunde, jaar 2Dubbele bachelor Wis- en Natuurkunde, jaar 2

Studiewijzer 2017/2018

Globale inhoud

Na een korte herhaling van de propositielogica bewijzen we de volledigheid van natuurlijke deductie als formele bewijsmethode. Daarna introduceren we natuurlijke deductie voor de predikaatlogica, en bewijzen we de correctheid en volledigheid hiervan. Enkele andere resultaten uit de modeltheorie van de eerste-orde logica komen aan bod, waaronder de Lowenheim-Skolem stelling.

Studiemateriaal

Literatuur

  • H.-D. Ebbinghaus, J. Flum and Wolfgang Thomas, 'Mathematical Logic, Undergraduate Texts in Mathematics', 2nd edition, Springer.

Syllabus

  • Lecture notes (provided on Blackboard)

Leerdoelen

After the course the students:

  • should have an idea of how to place this course in the general framework of mathematical logic as well as see the way the logic program evolves in the Bachelor of Mathematics and Master of Logic;
  • should be able to point out when a first-order formula is true or false on a given first-order structure;
  • should be able to provide derivations of formulas provable in first-order logic using sequent calculus for FOL;
  • are expected to produce a completeness proof via the Henkin model construction for first-order theories;
  • should be able to show when a given class of structures is or is not first-order definable using the compactness, Loewenheim-Skolem or Los's theorems;
  • should be able to argue when two first-order structures are or are not isomorphic and/or elementary equivalent;
  • should be able to compute ultraproducts of finite structures;
  • are expected to derive facts about Boolean algebras by arguing in terms of their dual topological spaces (Stone duals).

Onderwijsvormen

  • Hoorcollege
  • Werkcollege

Twee uur hoor- en twee uur werkcollege per week. Aanwezigheid bij de hoorcolleges is verplicht.

Verdeling leeractiviteiten

Activiteit

Aantal uur

Tentamen

3

Tussentoets

3

Zelfstudie

162

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

  • Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor hij/zij staat ingeschreven.
  • Als een student door overmacht niet aanwezig kan zijn bij een verplicht onderdeel van het onderdeel, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent. De docent kan dan, eventueel na overleg met de studieadviseur, besluiten om de student een vervangende opdracht op te leggen.
  • Het is niet toegestaan om verplichte onderdelen van een onderdeel te missen als er geen sprake is van overmacht.
  • Bij kwalitatief of kwantitatief onvoldoende deelname, kan de examinator de student uitsluiten van verdere deelname aan het onderdeel of een gedeelte daarvan.
  • Bij alle onderwijseenheden van jaar 1 en 2 is een student verplicht bij minimaal 80% van de werkcolleges en tutoraten aanwezig te zijn. Bovendien moet worden deelgenomen aan eventuele tussentoetsen en verplicht gesteld huiswerk. Als niet aan deze verplichting is voldaan, wordt de student uitgesloten voor de herkansing van de onderwijseenheid.

Aanvullende eisen voor dit vak:

Aanwezigheid bij de werkcolleges is verplicht. Als je niet bij minstens 80% van de werkcolleges aanwezig bent geweest dan vervalt je recht op het hertentamen, zoals vermeldt in het OER-B artikel 4.9 lid 2.

Toetsing

Onderdeel en weging Details

Eindcijfer

3 (30%)

Homework

3 (30%)

Tussentoets

4 (40%)

Tentamen

Moet ≥ 5 zijn

Fraude en plagiaat

Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: www.uva.nl/plagiaat

Weekplanning

Weeknummer Onderwerpen Studiestof
1 Course motivation, basic introduction to the subject, syntax of first-order logic Ebbinghaus et al, Ch 1, Ch 2
2 Semantics of first-order languages. Structures and interpretations, standartization of connectives, the satisfaction relation, the consequence relation, coincidence lemma   Sec 1-4, Ch 3
3 Isomorphisms, Isomorphism Lemma, universal formulas, Substructure Lemma, Dedekind's Theorem  Secs 5, 7.3 - 7.4, Ch. 3 
4 Substitutions, Substitution Lemma, sequent rules, strcuctural rules and connective rules Sec 8, Ch. 3, sequent rules, strcuctural rules and connective rules, Secs 1-2, Ch 4
5 Derivable connective rules, quantifier and equality rules, further derivable rules and sequents, the theorem of correctness  Secs 3 - 6, Ch 4
6 Consistent sets of formulas Sec 7 Ch 4 
7 Henkin's theorem Sec 1 Ch 5
8 Satisfyability of consistent sets of formulas (the countable case). The completeness theorem Secs 2-4, Ch 5
9 Every consistent set can be extended to a negation complete consistent set (uncountable case using Zorn's lemma). The Loewenheim-Skolem and Compactness Theorems Sec 3.5 Ch. 5, Secs 1-2, Ch 6
10 Elementary classes, elementarily equivalent structures, non-standard models of the real numbers and non-standard models of arithmetic Secs 3.1-3.6 and 4, Ch 6
11 Boolean algebras as models of classical propositional logic, filters and ultrafilters Lecturer's notes
12 Stone spaces, the Stone representation theorem for Boolean algebras Lecturer's notes
13 Stone duality Lecturer's notes
14 Applications of Stone duality: infinite chains and anti chains of Boolean algebras Lecturer's notes
15 Conclusions: placing the course in the bigger picture of Mathematical Logic  
16    

 

Rooster

Het rooster van dit vak is in te zien op DataNose.

Honoursinformatie

Op dit vak is geen honoursuitbreiding mogelijk.

Aanvullende informatie

Aanbevolen voorkennis: Inleiding (wiskundige) logica uit het eerste jaar voor studenten van andere opleidingen.

Contactinformatie

Coördinator

  • N. Bezhanishvili