Assigned: Mar. 5
Due: Mar. 26.
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.
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.)
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:
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.