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

- A. Skolemize (1) above. Identify which of the resultant clauses are
Horn clauses. Let H be the theory containing these Horn clause together
with (2) and (3).
- B. Prove the statement "a(e,w)" from H using backward chaining.
- C. Prove the statement "a(e,w)" from H using forward chaining.

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