Problem 1. Let A be a finite set and B be an infinite set and let A B. Prove that B A is infinite.

Problem 2. Let A be a countably infinite set and x A be an element of the same universe. Prove that

A {x} is countably infinite.

Problem 3. You own a restaurant which has seats numbered 1, 2, 3, 4, . . . .

One night all of the seats are occupied. Someone shows up at the restaurant and asks for a seat. How can you

accommodate that person? (Hint: problems 2 and 3 are more-or-less equivalent.)

Problem 4. Prove that NN is countably infinite in two different ways (one, by repeating the "diagonalization

argument" as we did for Q, you do not need to write a explicit bijection, but you should draw a convincing

picture)