Phil 403 : Mathematical Logic 1 (Spring 2012)

Class Times: Tuesdays and Thursdays, 2.30pm-4pm
Location: Wilson Hall, 104
Course Website: http://www.artsci.wustl.edu/~grussell/Phil403.html

Instructor: Professor Gillian Russell
Office hours: Tuesdays 4.15-5.15pm or by appointment
Office Location: 209 Wilson Hall
Email: grussell – at – wustl – dot – edu

This is a course in mathematical logic for those who are already familiar with first-order symbolic logic. The main results are Goedel’s incompleteness theorems. The course assumes some basic set theory and faciliity with informal proof methods, such as proof by induction. Students are strongly advised to take Phil 100 Introduction to Logic and Phil 301: Symbolic Logic before attempting this more advanced course.

Books

The textbook for this course is the 5th edition of Boolos, Burgess and Jeffrey’s Logic and Computability, published by Cambridge. It is the only text you need to buy. Second hand copies are fine.

Readings, Topics and Homework Assignments

Tuesday 17th January

Enumerability
Reading: Chapter 1 of the textbook.

Thursday 19th January

Diagonalisation
Reading: Chapter 2
Exercises (1): 1.3, 1.5, 2.2

Tuesday 24th January

Turing Computability
Reading: Chapter 3

Thursday 26th January

The Halting Problem
Reading: section 4.1
Exercises (2): 3.3, 3.5, 4.1, 4.2

Tuesday 31st January

Abacus Computability
Reading: chapter 5

Thursday 2nd February

Recursive Functions
Reading: chapter 6
Exercises (3): 5.1, 5.6, 6.1, 6.4

Tuesday 7th February

Recursive Sets and Relations
Reading: chapter 7

Thursday 9th February

Equivalent Definitions of Computability (I)
Reading: sections 8.1 and 8.2

Exercises (4): 7.1, 7.3, 7.12, 8.1

Tuesday 14th February

Equivalent Definitions of Computability (II)
Reading: section 8.3

Thursday 16th February

Midterm Exam 1 (on chapters 1-8)

Tuesday 21st February

A Precis of First Order Logic: Syntax
Reading: chapter 9.

Thursday 23rd February

A Precis of First Order Logic: Semantics
Reading: chapter 10.
Exercises (5): 9.1, 9.4, 10.1, 10.6, 10.8.

Tuesday 28th February

The Undecidability of First-Order Logic
Chapter 11

Thursday 1st March

Models
Chapter 12
Exercises (6): 11.1, 11.7, 12.3, 12.8, 12.9

Tuesday 6th March

The Existence of Models (I)
Reading: section 13.1

Thursday 8th March

The Existence of Models (II)
Section 13.2
~~Exercises (7): 13.8, 13.9, 13.10, 13.11~~

Tuesday 13th March

SPRING BREAK

Thursday 15th March

SPRING BREAK
Exercises (7): 13.8, 13.9, 13.10, 13.11

Tuesday 20th March

Proofs and Completeness
Reading: chapter 14

Thursday 22nd March

NO CLASS
Exercises (8): 14.1, 14.3, 14.5, 14.7, 14.9

Tuesday 27th March

Arithmetization
Reading: Chapter 15

Thursday 29th March

Representability of Recursive Functions (I)
Reading: sections 16.1 and 16.2
~~Exercises (9): 15.1, 15.4, 16.1, 16.2~~

Tuesday 3rd April

NO CLASS

Thursday 5th April

MIDTERM EXAM II (on chapters 9-15)
Exercises (9): 15.1, 15.4, 16.1, 16.2

Tuesday 10th April

NO CLASS

Thursday 12th April

Representability of Recursive Functions (II)
Reading: sections 16.3 and 16.4

Exercises (10): 16.3, 16.5, 16.9, 16.10

Tuesday 17th April

Representability of Recursive Functions (III)
Reading: No additional Reading.

Thursday 19th April

Indefinability, Undecidability and Completeness (I)
Reading: section 17.1

Tuesday 24th April

Indefinability, Undecidability, Incompleteness (II)
Reading: sections 17.2

Thursday 26th April

The Unprovability of Consistency

Take home final will be given out on 26th of April, and will be due at noon on the 4th of May 2012.

Problem Sets

Homework exercises are listed on the syllabus. They will be due by noon on the Friday that falls 8 days after the date under which they are listed (e.g. the first homework is listed under Thursday 19th January and so it is due by noon on Friday 27th. Exercises should be completed on paper (i.e. don’t email me your homework) and turned in to the appropriate drawer of the "turn-in" filing cabinent in the philosophy department office (2nd floor of Wilson Hall, opposite my office.)
Please be considerate of the office staff – the office closes for lunch (12.30 – 1.30pm) and at 4pm; we try to discourage students from knocking on the door at 4.01pm and access to the filing cabinets is not allowed when the office is unattended.
You may handwrite your homework (in fact, this is often faster and less prone to unfortunate typing errors) but you should always turn in neat, legible work, clearly marked with your name. Do not turn in "rough" work, or work with lots of crossings-out. Any work that I can’t read will get a zero.
Solutions to the problem sets will be given out in class.
Any homework set received after the solutions have been given out will receive a grade of zero.

Assessment

40% of the grade for this course will come from the homework exercises completed during the semester. (We will drop your worst homework grade and average the rest.) 40% will come from the two in class midterm exams (20% each) and the remaining 20% from a take home final exam, which will be given out on the last day of class. You will have 1 week to complete the final. If you decide to take this course, you will need to make sure that you are able to come to class on the days of the midterms.

For students taking the course pass/fail, the minimum letter grade required for a pass will be a D, which can be obtained with an overall percentage grade of 50%.

Academic Integrity

It is very important that you understand the rules for collaboration on this course. You may work with other students in order to work out solutions to the exercises in your take-home problem sets; in fact, this is encouraged. However, each student must write up his or her solutions to the exercises alone. You may not do it with another student looking over your shoulder to correct you. You may not write your homework from notes which another student has made, nor may you make notes on another student’s written solutions. You may not lend or copy digital or paper homework solutions – at any stage of completion.

Collaboration is not allowed during the midterm and final examinations.

Sometimes it is unclear whether a hypothetical case of collaboration is permissible according to these rules, or whether it counts as misconduct, but it is your duty to ensure that ALL your collaborations are clearly permissible. One good way to do this is not to write anything down on paper whilst investigating problems with other students: use a chalk board or white board to work out ideas, (or, if you use paper, dispose of the written solutions before you separate to write up your individual homeworks alone.)

Students suspected of plagiarism or any other form of academic dishonesty or misconduct will be reported to the academic integrity officer for Arts and Sciences (currently Dean Killen), so that the incident may be handled in a consistent, fair manner, and so that substantiated charges of misconduct may be noted in students’ records.