This course is 2 credits, but contents deserve at least 3 credits!! 
					Mathematical Logic
					Prof. C. Nehaniv
				        First Semester 1997-98
					University of Aizu

Syllabus

(approximately 14 meetings of 90 minutes each) 
I. Introduction
    - Logic, Proofs, Formalizablity, Examples, Preview,
       Historical and Philosophical Remarks, Formal Languages
    - Formalizations of Mathematical Deduction

II. Syntax (of First-Order Languages)
       Logical Connectives, Quantifiers, Terms,
       Well-Formed Formulas, Induction on Terms
       and Formulas, Sentences & Free Variables. 
      
       
III. Semantics  
        - Structures and Interpretations
        - Satisfaction Relation, Consequence Relation
        - Isomorphisms
        - Examples of Formalizations
        - Peano's Axioms, Limits of Formalization
        - Substitution 

IV. Sequent Calculus  
        - Rules & Formal Provability
        - Correctness Theorem
        - Consistency

V.  Completeness   
      - Henkin's Theorem
      - Adequacy of First-Order Logic

VI. Compactness

VII.  Limits of Formal Methods
       - Decidability, Enumerability, Computable Functions
       - Register Machines - Halting Problem -Church-Turing Thesis
       - Undecidabilty of First-Order Logic and Undecidability of Arithmetic
       - Gödel's First Incompleteness Theorem


Required Text: Mathematical Logic, 2nd Edition
               by H.-D. Ebbinghaus, J. Flum, W. Thomas
               Publisher: Springer Verlag

Addition Reference (optional):

               Notes on Logic and Set Theory
               by P.T. Johnstone
               Publisher: Cambridge                  

Description: What is a mathematical proof? How can proofs
             be justified? Are their limitations to provability?
             To what extent can machines carry out mathematical
             proofs?  In this century, mathematicians have
             obtained deep and surprising answers to these
             questions.  We will consider the relation between the
             concepts of form, meaning, truth and their
             formalizations.  Mathematical logic uses the language 
             that problems are expressed in as weapons for their
             solution. The consequences for computer science 
             are profound.

Reading Covered in this Course

We cover Chapters I, II, III, & IV,
In Chapter V, The Completeness Theorem: sections 1,2, & 4
In Chapter VI, read from the begining of section 2 to the end of theorem 2.2 (pp. 88-89) on the Compactness Theorem.
Chapter X: Limitations of the Formal Method (except section 5).
(Especially Register Machines, Halting Problem, and Gödel's 1st Incompleteness Theorem)

(Optional Reading) Chapter VII: The Scope of First-Order Logic

Grading

There is NO final exam. Grading is based on the problems you turn in from the Exercise Sheets (download below), plus any additonal problems from the book that you solve. For Chapter X, the following problems are suggested : 1.2, 1.9, 2.*, 3.5. The deadline for turning in problems and worksheets is in class on July 10.

Exercise Sheets:

Please note: if you do not turn in any problems, you will not receive a grade for this course.