[Λ1] Mathematical Logic, μΠλΑ, Εαρινό εξάμηνο 2016

Βιβλιογραφία

Ωρες διαλέξεων: Δευτέρα 11:00-13:00 (Γ33, Μαθηματικό), Τρίτη 14:00-16:00 (Γ43, Μαθηματικό)

Teaching Assistant: Αγγέλα Χαλκή.

Ημερολόγιο Μαθήματος

Ημερομηνια Περιεχόμενο διάλεξης [ΚΔ] [YNM] [HE] [EM]
Δευτέρα, 15/2/2016 Propositional Logic (PL): Syntax of PL, Induction Principle for formulas, Unique Readibility, Definitions by Structural Recursion. Kεφ. 2, σελ. 7-11

§1 (Syntax of PL)

Section 1.1  
Παρασκευή, 19/2/2016 Semantics of PL (Truth assignments, unique extension theorem, tree diagrams, truth tables, logical consequence, laws of PL). Kεφ. 2, σελ. 12-18 §2 (Semantics of PL) (minus 2A.) Section 1.2 & 1.4  
Δευτέρα, 22/2/2016 Boolean functions, Functional Completeness of PL, Complete sets of connectives. Κεφ. 2.3 2.Α Section 1.5  
Τρίτη, 23/2/2016 Proof Theory of PL: Hilbert-style systems and formal deductions

Kεφ. 2.4 (Προτασιακός Λογισμός) σελ. 23-25.

 §3: (Formal Deduction) 3A, 3B    
Δευτέρα, 29/2/2016 Proof Theory of PL: Deduction Theorem and other metatheorems, applications. Kεφ. 2.4: σελ. 25-29 3C-3D.3    
Τρίτη, 1/3/2016 Soundness and Strong Completeness of PL (Maximal Consistent Sets of formulas and Lindenbaum construction)   3B, 3D.5-3E  
Τρίτη, 8/3/2016 Kalmár's proof of Completeness for PL, Gentzen-style deductions for PL, Compactness of PL. Kεφ. 2.5 3D-3D.4, §4    
Τρίτη, 15/3/2016 First-Order Logic: examples of structures, examples of languages   §1 (LPCI)    
Δευτέρα, 21/3/2016 Syntax of FOL: terms, formulae, induction principle for terms and wffs, free and bound variables, notational conventions, examples of FOL languages Kεφ. 3 (37-42) §2 (LPCI) Section 2.1  
Τρίτη, 22/3/2016 Semantics of FOL: structures, variable assignments, satisfaction relation and the Tarski truth conditions, truth and models Kεφ. 3 (42-47) §3 (LPCI) Section 2.2  
Δευτέρα, 28/3/2016 Logical Implication, Defianability within a structure, Definability of a Class of Structures. Kεφ. 3.2   Section 2.2
Τρίτη, 29/3/2016 Elements of Model Theory: Homomorphisms, Isomorphisms, elementary equivalence, elementary extensions. Kεφ. 3.6   Section 2.2  
Τρίτη 5/4/2016

Deduction in FOL: Hilbert-style axiom system, substitution, metatheorems

 Kεφ. 3.4 (49-53)

Section 2.4 (A deductive calculus)  
Πέμπτη 14/4/2016 Metatheorems: Generalization Theorem, Deduction Theorem, Reductio Ad Absurdum.     Section 2.4  
Παρασκευή 15/4/2016 Metatheorems (cont.): Contraposition, using metatheorems for proving (the existence of) formal deductions.     Section 2.4  
Δευτέρα 18/4/2016 Generalization on Constants, Existential Instantiation, Properties of Equality.   Section 2.4  
Τρίτη 19/4/2016 Soundness and Completeness of FOL.   Section 2.5  
Πέμπτη 12/5/2016 Introduction to Gödel's Incompleteness Theorems Κεφ. 4.1      
Παρασκευή 13/5/2016 Roadmap to the proof of Gödel's Incompleteness Theorems (overview of the techniques)        
Δευτέρα 16/5/2016 Basic facts about Peano Arithmetic Κεφ. 4.2   Section 3.1  
Τρίτη 17/5/2016 Representable functions and expressible relations Κεφ. 4.3   Section 3.2  
Δευτέρα 23/5/2016 Primitive recursive & recursive functions Κεφ. 4.3   Section 3.3  
Τρίτη 24/5/2016 Primitive recursive & recursive functions (cont.) Κεφ. 4.3   Section 3.3  
Δευτέρα 30/5/2016 Gödel's β-function. Every recursive function is representable in PA Κεφ. 4.3   Section 3.3  
Τρίτη 31/5/2016 Arithmetization, Gödel numbering. Κεφ. 4.4   Section 3.4  
Δευτερα 13/6/2016 The class of recursive functions coincides with the class of functions representable in PA. Κεφ. 4.4   Section 3.4  
Τρίτη 14/6/2016 The Fixed-Point Theorem. First Incompleteness Theorem. Κεφ. 4.5   Section 3.5  
Τρίτη 21/6/2016 Gödel-Rosser Incompleteness Theorem. Hints on Hilbert-Bernays derivability conditions and the second incompleteness theorem. Κεφ. 4.5   Section 3.5  

Ασκήσεις: οι ασκήσεις του μαθήματος θα αποστέλλονται με email και θα παραδίδονται κατα προτίμηση επίσης ηλεκτρονικά.

Η Πρώτη Σειρά, θα παραδοθεί την Παρασκευή 18 Μαρτίου.

Η Δεύτερη Σειρά, θα παραδοθεί την Παρασκευή 22 Απριλίου.

Η Τρίτη Σειρά, θα παραδοθεί την Παρασκευή 13 Μαίου.