Math 457: Introduction to Mathematical Logic

Homework #1

January 13, 2012

We refer to Chapter 2 of the Mathematical Logic lecture notes.

1. Carefully study Exercise 2.2.14 and verify its solution to your own satisfaction. Then, continue by writing sentences representing the following statements.

(a) Every vehicle (car or truck) has exactly one driver.

(b) Every driver drives at least two cars.

(c) Only human beings drive cars or trucks.

(d) There are at most three people who drive both a car and a truck.

2. Extend the language of Exercise 2.2.14 by adding two predicates: Sy: y is a set. Exy: x is a member of y.

Using this extended language, write sentences representing the following statements.

(a) It is impossible for a set to be a member of itself.

(b) Given any two humans, there exists a set whose members are exactly those two humans.

(c) There exists a set consisting of all vehicles.

(d) For each human, there is a set consisting of all cars which are driven by that human.

(e) For each vehicle, there is one and only one set consisting of all humans

which drive that vehicle.

3. Translate each argument into sentences of the predicate calculus. Which arguments do you think are logically valid? Give reasons for your answers. (You may disregard the part about tableaux and structures.)

(a) Exercise 2.5.12.

(b) Exercise 2.5.13.

(c) Exercise 2.5.14.

(d) Exercise 2.5.15.