# 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.)

## Reading assignments

By Tuesday, 16 Dec, you should have read through chapter 9 of the textbook.

Last modified: Thu Dec 11 15:45:33 EST 1997
Stephen Bloch / sbloch@boethius.adelphi.edu