MTH 355 Symbolic Logic

Instructor: Dr. Stephen Bloch Fall, 1997

This course meets from 10:50 AM - 12:05 PM TTh in Business 110.

The syllabus will be available in LaTeX, DVI, and Postscript, and HTML. A schedule of lectures tells what I plan to talk about, and what I expect you to have read, by each class meeting.

Textbook

We're using the textbook The Language of First-Order Logic, by Jon Barwise and John Etchemendy. This book comes with a floppy disk in the back, either for Macintosh or Windows. You may buy and use whichever you prefer: the Macintosh edition has a red cover, while the Windows edition has a blue cover. The authors have set up an on-line errata page for the textbook.

I used this textbook a year ago for the MTP course in Mathematical Logic, and was quite happy with it. It comes with a computer program named "Tarski's World" which allows the user to experiment with logical sentences interpreted in an on-screen "world". Some of your homework assignments will be turned in on floppy disk, while others will be turned in on paper (or, if you prefer, by email).

Homework assignments

Homework 1, assigned 16 Sept, due 30 Sept, extended to 9 Oct because the book hadn't come in yet
Problems from chapter 2 of the textbook:
3,4,5,19 (to be turned in on floppy disk)
6,8,9,10,17,18,21,22,24 (to be turned in on paper or by email)
Note: some of the statements in problem 2.9 cannot be translated; your job is to translate the ones that can, and give some explanation of why the others can't.

Homework 2, assigned 21 Oct, due 4 Nov
Problems 3.9,3.17*,3.18,3.20,3.26* (paper or email)
Problems 3.30,3.31,3.34 (informal proofs on paper or email; counterexamples on disk)
Problems 3.43 (formal proof, paper or email)
Problem 3.60* (paper or email)
Problems 4.4,4.5 (on disk)
Problems 4.11 (paper or email)
Problem 4.14 (informal proofs, paper or email; counterexamples on disk)
Problems 4.25 (formal proofs, paper or email)

Homework 3, assigned 6 Nov, due 25 Nov
Problems 5.18, 5.23, 5.24, 5.25, 6.9, 6.26, 6.37, 6.52 (paper or email)
Problems 6.19, 6.20, 6.23, 6.50 (on disk)

Homework 4, aka take-home final exam, assigned 25 Nov, due at the scheduled exam time, 10:30 AM, 16 December.
Problems 7.2, 7.3, 7.4, 7.9, 7.10, 7.25, 7.27, 7.28, 7.29, 7.30, 7.31,
Problems 8.16, 8.17, 8.18, 8.19, 8.25, 8.26, 8.34, 8.35
And on mathematical induction, the following three:
• Prove that there exists a real number x>1 such that for all sufficiently large n,
Fn >= xn,
where Fn indicates the n-th Fibonacci number, defined by
F0 = F1 = 1 and for n > 1, Fn = Fn-1 + Fn-2.
Hint: You'll need to use a base case larger than 1. How much larger depends on what value of x you choose.
Extra credit: What is the smallest value of x for which you can't make your proof work, even by picking a large base case?
• Prove that for every natural number n, and every square on a 2n x 2n checkerboard, there is a way to tile the checkerboard using 3-square, L-shaped tiles, leaving out only the specified square and not overlapping any tiles.
• Prove the "Pigeonhole Principle": that for any finite set S and any function
g : S --> S, if g is not onto, then g is not one-to-one.
("g is onto" would mean that for every element x of S, there is a y in S such that g(y)=x.
"g is one-to-one" would mean that for every elements x and y of S, if g(x)=g(y) then x=y.)