Comp 230: Logic and Computability, Fall 2012

Schedule

The schedule below is tentative and might be updated during the semester. The readings refer to the textbook (Gödel, Escher, Bach). Additional literature and handouts are available on MyCourses.

w d Day Date Content Readings HW

Part I: Fundamentals and Formal Systems

1 Thu Sep 6 Introduction to the course. Gödel's Theorem. sqrt(2) is irrational

1 2 Tue Sep 11 Definition by recursion. Mathematical induction Handout 1

3 Thu Sep 13 Sets: Relations, functions, cardinality MyCourses

2 4 Tue Sep 18 Denumerable and non-denumerable sets: Diagonalization

5 Thu Sep 20 Syntax. A simple formal system. The MIU system Ch. 1

3 6 Tue Sep 25 Semantics. Interpretations. Infinitude of primes (Euclid) Ch. 2 1

7 Thu Sep 27 R.e. sets vs. recursive sets Ch. 3

4 8 Tue Oct 2 Multiple interpretations, non-Euclidean geometry, consistency, completeness Ch. 4

Part II: Logic and Formal Arithmetic

9 Thu Oct 7 Propositional logic: Semantics Handout 2

5 10 Tue Oct 9 Propositional logic: Natural deduction Ch. 7 2

11 Thu Oct 11 Propositional logic: Soundness and completeness

6 12 Tue Oct 16 First-order logic: Expressions Ch. 8 (204-214)

13 Thu Oct 18 First-order logic: Semantics, substitutions Handout 3

7 14 Tue Oct 23 First-order logic: Proof systems, completeness 3

15 Thu Oct 25 Review

8 16 Tue Oct 30 Midterm Exam (SADB M-1 240)

17 Thu Nov 1 First-order arithmetic Ch. 8 (215-230)

9 18 Tue Nov 6 Solution to MU puzzle. Gödel numbering Ch. 9

Part III: Computability and Incompleteness

19 Thu Nov 8 Turing machines. Halting problem Handouts 4 and 5 4

10 20 Tue Nov 13 Primitive recursive functions (BlooP) Ch. 13 (406-418)

21 Thu Nov 15 Recursive functions (FlooP) Ch. 13 (418-430)

11 22 Tue Nov 20 Gödel's First Incompleteness Theorem (Part 1) Ch. 14 (438-443) 5

23 Thu Nov 22 Gödel's First Incompleteness Theorem (Part 2) Ch. 14 (443-449)

12 24 Tue Nov 27 Gödel's Second Incompleteness Theorem Ch. 14 (449-460)

25 Thu Nov 29 Church-Turing thesis. Tarski's Theorem Ch. 17

13 26 Tue Dec 4 Review 6

E Tue Dec 18 Final Exam: 9am-noon, Location tba

Home

Syllabus

Schedule

Assignments

Links

w	d	Day	Date		Content	Readings	HW
					Part I: Fundamentals and Formal Systems
	1	Thu	Sep	6	Introduction to the course. Gödel's Theorem. sqrt(2) is irrational
1	2	Tue	Sep	11	Definition by recursion. Mathematical induction	Handout 1
	3	Thu	Sep	13	Sets: Relations, functions, cardinality	MyCourses
2	4	Tue	Sep	18	Denumerable and non-denumerable sets: Diagonalization
	5	Thu	Sep	20	Syntax. A simple formal system. The MIU system	Ch. 1
3	6	Tue	Sep	25	Semantics. Interpretations. Infinitude of primes (Euclid)	Ch. 2	1
	7	Thu	Sep	27	R.e. sets vs. recursive sets	Ch. 3
4	8	Tue	Oct	2	Multiple interpretations, non-Euclidean geometry, consistency, completeness	Ch. 4
					Part II: Logic and Formal Arithmetic
	9	Thu	Oct	7	Propositional logic: Semantics	Handout 2
5	10	Tue	Oct	9	Propositional logic: Natural deduction	Ch. 7	2
	11	Thu	Oct	11	Propositional logic: Soundness and completeness
6	12	Tue	Oct	16	First-order logic: Expressions	Ch. 8 (204-214)
	13	Thu	Oct	18	First-order logic: Semantics, substitutions	Handout 3
7	14	Tue	Oct	23	First-order logic: Proof systems, completeness		3
	15	Thu	Oct	25	Review
8	16	Tue	Oct	30	Midterm Exam (SADB M-1 240)
	17	Thu	Nov	1	First-order arithmetic	Ch. 8 (215-230)
9	18	Tue	Nov	6	Solution to MU puzzle. Gödel numbering	Ch. 9
					Part III: Computability and Incompleteness
	19	Thu	Nov	8	Turing machines. Halting problem	Handouts 4 and 5	4
10	20	Tue	Nov	13	Primitive recursive functions (BlooP)	Ch. 13 (406-418)
	21	Thu	Nov	15	Recursive functions (FlooP)	Ch. 13 (418-430)
11	22	Tue	Nov	20	Gödel's First Incompleteness Theorem (Part 1)	Ch. 14 (438-443)	5
	23	Thu	Nov	22	Gödel's First Incompleteness Theorem (Part 2)	Ch. 14 (443-449)
12	24	Tue	Nov	27	Gödel's Second Incompleteness Theorem	Ch. 14 (449-460)
	25	Thu	Nov	29	Church-Turing thesis. Tarski's Theorem	Ch. 17
13	26	Tue	Dec	4	Review		6
	E	Tue	Dec	18	Final Exam: 9am-noon, Location tba