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

Answer: The statement is

~ [exists(S0) all(S) e(S,S0) < = > ~e(S,S)].
Negating and Skolemizing gives two clauses:
A. e(S,s0) V e(S,S)
B. ~e(S,s0) V ~e(S,S)
(s0 is a Skolem constant.) The proof is then as follows:
C. e(s0,s0). (Factoring A with substitution S=s0).
D. ~e(s0,s0). (Factoring B with substitution S=s0).
E. null.  (Resolving A with B.)

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. Skolemizing (1) gives four clauses:

4. ~a(X,Z) V ~a(Z,Y) V a(X,Y).
5. ~p(X,Y) V a(X,Y)
6. ~a(X,Y) V p(X,Y) V a(X,sk1(X,Y))
7. ~a(X,Y) V p(X,Y) V a(sk1(X,Y),Y)
Clauses 4,5 are Horn; clauses 6,7 are not.

B. One backward chaining proof would be:

G0: ~a(e,w).           (Negated goal)
G1: ~a(e,Z) V ~a(Z,w). (G0+4).
G2: ~p(e,Z) V ~a(Z,w). (G1+5).
G3: ~a(c,w).           (G2+2).
G4: ~p(c,w).           (G3+5).
G5: Null               (G4+3).

C. One forward chaining proof would be:

8. a(e,c)              (2+5)
9. a(c,w)              (3+5)
10. ~a(c,Z) V a(e,Z)   (8+4)
11. a(e,w).            (9+10)
12. Null               (11+G0)

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.

Answer: There are many possible answers. One would be the following model.

This satisfies axiom 1; the condition a(X,Y) < = exists(Z) a(X,Z) ^ a(Z,Y) is satisfied for X=Y=w where Z is also equal to w. However it obviously violates G.