Incorrect Answer.


The formula set { x y (P(x,y) P(y,y)), x P(x,x), x y (P(x,y)} is satisfied in a model M, if all the formulas in that set are satisfied by that same model. Thus, we seek a model, M, that satisfies the three formulas For the third formula to be satisfied in M, we need values, a for x and b for y, such that (a,b) is in PM. But then we can infer that (a,a) is in PM as well, provided that our model satisfies the first formula. However, the latter makes it impossible for M to satisfy the second formula, which states (if re-expressed with quantifier equivalences) that no pair of the form (a,a) is in PM.

Thus, there cannot be a model M that satisfies all three formulas. (Choosing any two formulas above, can you find models that satisfy these two formulas?)
Back to Question.
Next Question.