Let L be a language with two unary predicates A and B Consid

Let L be a language with two unary predicates, A and B. Consider the equivalence Forall x(A(x) B(x)) doubleheadarrow Forall x A(x) Forall x B(x). Show that one direction is valid. In particular, your answer should make it clear that you know what \"valid\" means! Show that the other direction is not valid.

Solution

Recall that if any of the predicates is true, then so is the OR conjugation; but if both the predicates are false, then so is the OR conjugation.

Now the left hand statement reads \"If any of A(x) or B(x) is true for every chosen x, then i) is true. But if there is an x for which both A(x) and B(x) are false, then i) is false.\", while the right hand one reads \"If A(x) is true for all x, or B(x) is true for all x, then ii) is true. But if there is an x for which both A(x) and B(x) are false, then ii) is false.\"

Suppose that we take a subset S of the set X of all the x. Let A(x) be true for all x in S, and false otherwise. Also let B(x) be false for all x in S, and be true otherwise. In this case, the left hand statement is valid, but the right hand one is not. So the left-to-right direction is not valid.

On the other hand, consider the right hand statement, and choose an x in X. Then for any such x, any of A(x) or B(x) will be true. So the right-to-left direction is valid.