Math 290 Senior Honors Seminar

Incompleteness, Diagonalization, Self-Reference, and All That Spring, 1996

This course will meet on Mondays from 1:20-2:20 in Alumnae Hall 116. The book Goedel's Proof, by Ernst Nagel & James Newman, is recommended reading (and, incidentally, is brief, light, and inexpensive), but my lectures probably won't follow it at all closely. If you want further reading on the subject, I recommend Douglas Hofstadter's Goedel, Escher, Bach: an Eternal Golden Braid, or almost anything written by Raymond Smullyan.

Homework Assignments

I'll probably assign several "paper" homework assignments during the semester. We may come up with ideas that would work well as computer programming assignments, particularly if you're comfortable with a language like Scheme or Lisp.

Homework 1 assigned 29 Jan, due 5 Feb:
prove that if S is a finite set of exactly n elements, then the set of subsets of S has exactly 2^n elements.
Homework 2 assigned 5 Feb, due 12 Feb:
• Prove that "is the same size as", using the definition in class, is transitive.
• Prove that N (the set of natural numbers) is the same size as N x N (the set of ordered pairs of natural numbers).
Homework 3 assigned 12 Feb, due 19 Feb:
Prove that no two of the sets N, 2^N, 2^2^N, 2^2^2^N, ... are the same size.
Homework 4 assigned 11 Mar, due 25 Mar:
Prove that any expression of propositional logic involving only the variables p and q, and only the connectives ~ and iff must have either 4 F's, 4 T's, or 2 of each in its truth table. (Hint: use mathematical induction on the number of connectives.)
Homework 5 assigned 11 Mar, due 1 Apr:
Prove that if A and B are expressions of propositional logic (with connectives ~, ^, and v), and A logically implies B, then there is a third expression of propositional logic C, such that every variable in C appears in both A and B, A logically implies C, and C logically implies B.
Homework 6 assigned 19 April, due 29 April:
see file ~sbloch/class/290/hw6.

You are visitor number to this and related pages since Feb. 8, 1996.

Last modified: Mon Mar 11 10:59:06 EST 1996
Stephen Bloch / sbloch@boethius.adelphi.edu