Problem Set 3

Assigned: Mar. 5
Due: Mar. 26.

Problem 1

One aspect of Russell's paradox is that he proved the following statement:
Let us say that a set S is normal if S is not an element of S. Then there cannot exist a set of all normal sets.

More formally,

There cannot exist a set S0 such that, for every set S, S is an element of S0 if and only if S is not an element of S.

Consider a first-order language L where the entities are sets containing the single predicate e(X,Y), meaning that X is an element of Y. State the above proposition in L and prove it using resolution. (Note: no axioms are needed.)

Problem 2

Let L be a language whose entities are people, containing two predicates: p(X,Y) meaning that X is a parent of Y, and a(X,Y) meaning that X is an ancestor of Y. Consider the theory containing the following recursive definition:
1. forall(X,Y) a(X,Y) < = > p(X,Y) V [exists(Z) a(X,Z) ^ a(Z,Y)].
Suppose that, in addition, we have the following axioms describing a family tree:
2. p(e,c).
3. p(c,w).

Problem 3

Let H1 be the theory containing axioms 1,2,3 above together with the additional axiom
4. ~ exists(Z) p(w,Z).
Let G be the statement "~ exists(Z) a(w,Z)." One might think that G is a consequence of H1. After all, if ancestor is the transitive closure of parent, and W is not anyone's parent then surely W is not anyone's ancestor. However, G is not a consequence of H1. Prove that G is not a consequence of H1 by constructing a model in which H1 is true and G is false. That is, you should list a set of parent and ancestor relations that satisfies H1 but not G. (Hint: this can be done using only the individuals e, w, and c.)

The moral is that first-order recursive definitions don't actually say everything that you would like them to say.