Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$\exists y \forall xP(x, y) \equiv \forall x \exists yP(x,y)\tag{1}$$ $$\exists y \forall x(P(x) \lor Q(y)) \equiv \forall x P(x) \lor \exists x Q(x)\tag{2}$$

$$\exists x(P(x) \lor Q(x)) \equiv \exists xP(x)\lor \exists yQ(y)\tag{3}$$

Without proving them is there a way to quickly know whether it is true or not?

share|improve this question
    
Proof or counterexample is the best way to know if something is true or false. –  andybenji Nov 28 '12 at 18:43

1 Answer 1

You can use proof by counterexample to rule out (disprove) a given equivalence. All you need is one counterexample in which the equivalence fails to hold to disprove the equivalence.

To do so, try translating the expressions to get a feel for what they are asserting.

If you aren't able to quickly find a counterexample, then you need to try to prove the equivalence; if that proves impossible, you might gain insight into why that is, and then try again to come up with a counterexample.

But, there's no getting around thoroughly understanding quantifiers and predicates. The more you work with exercises like these, the more quickly you'll get at being able to prove or disprove such statements.


Let's work through the first proposed equivalence:

$$\exists y \forall xP(x, y) \equiv \forall x \exists yP(x,y)\tag{1}$$

Let $x, y$ be in the domain of all people. Let $P(x, y)$ denote "$x$ loves $y$". (Counterexample)

Then the left-hand-side translates to: "There is someone whom everyone loves."

The right-hand-side translates to "Everyone loves someone."

Can you see how these are not equivalent statements?


For the next two assertions, think of a predicate which we can denote $P(x)$ and one to denote $Q(x)$, where $x$ is in some domain over which we are quantifying, and try translating into words what each statement is stating.

$$\exists y \forall x(P(x) \lor Q(y)) \equiv \forall x P(x) \lor \exists x Q(x)\tag{2}$$

$$\exists x(P(x) \lor Q(x)) \equiv \exists xP(x)\lor \exists yQ(y)\tag{3}$$


Recall, also, that $a \equiv b$ denotes "double implication": $(a\rightarrow b) \land (b\rightarrow a)$, which means that to be equivalent, either $a$ and $b$ must both be true, or else they must both be false. If one can be true and the other false, then the $a\not\equiv b$.

share|improve this answer
    
+1 Hello, Amy. :-) –  B. S. Sep 1 '13 at 0:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.