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