Russell's paradox (see the slides for sets and functions) is about the set, R, of all sets that do not contain themselves. The paradox arises when we ask whether R contains itself. Russell gave another popular version of the paradox, known as the Barber's paradox: In a village lives a man who is a barber. He shaves all the men of the village who do not shave themselves and no one else. Does the barber shave himself? Once we understand the pattern, it's not difficult to create our own version of the paradox. Here's an example: in a small town lives a dog owner who runs a dog-walking business. She walks all the dogs in town that are not walked by their owners and no other dog. Does the dog-walker walk her dog?

Generalizing, we have a two-place predicate,

P(x,y), which is interpreted as "xy," "y shaves x," or "y walks x's dog" in the three forms of the paradox we have considered. The state of affairs is then described, in all three cases, by the following sentence of predicate logic:

y x(P(x,y)P(x,x)).

Your task in this exercise is to show that the sentence above is contradictory. All you need to do is to apply two inference rules: existential and universal instantiation.