I am thinking about whether this is valid or not;

∃x∀y (P(x,y)) ↔ ∀x∃y (P(x,y))

My attempt so far; Let's assume that P(x,y) function represents that x and y are friends, on the left side of the statement it says "At least 1 person in the world is friend with everybody on earth. " and on the right "Whole world is friend with at least 1 common person". Do these mean that right should support left and left should support right, I am confused and can't think of any other function suiting the statement right now. I guess in this case, the statement is valid but I am not sure at all..

  • 2
    $\begingroup$ You've written a double-sided implication, that both sides are logically equivalent to one another. Do you really think your example supports that interpretation? Also note that many predicates are not symmetric, as one might arguably consider "is friend of", so that the use of universal quantification on a different variable is significant. $\endgroup$ – hardmath Oct 9 '12 at 18:13
  • 1
    $\begingroup$ Even in the given symmetric relation, equivalence fails because the right side means everyone has (at least) one friend, not "friend with at least 1 common person". It is conceivable that the right side might be true without the left side being the case. $\endgroup$ – hardmath Oct 9 '12 at 18:30
  • $\begingroup$ When I thought about the right side, yes you are right, it should mean everyone has a friend that does not necessarily a common one, I guess it fails to be valid. $\endgroup$ – Karavana Oct 9 '12 at 19:00

"Friends with" is a confusing example because it is normally a symmetric relation: if I am "friends with" Joe I usually expect it to be true that Joe is friends with me also.

Try a different relation, one that is not symmetric. For example, try making $P(x,y)$ mean that $x$ is older than $y$.

  • $\begingroup$ The two sides of the OPs question mean different things even if $P$ is symmetric. I think that it is good for understanding to find as nice a counterexample as possible. $\endgroup$ – Henning Makholm Oct 9 '12 at 18:45
  • $\begingroup$ Your example made it very clear for me to understand, I thought that since it is a symmetric quantifier, I made myself believe that I should pick a symmetric relation, so this one holds for now. $\endgroup$ – Karavana Oct 9 '12 at 19:03

Your "right" interpretation of $\forall x\exists y \; P(x,y)$

Whole world is friend with at least 1 common person

is wrong, or at least misleading. It should be something like

Anyone has at least one friend

However, the it doesn't need to be the same friend everybody has.

The rule is that whenever you see a $\exists x$ the value of $x$ is allowed to depend on the values of all variables that are bound before $\exists x$ -- so in $\forall y\exists x$ there can be a different $x$ for each $y$, but in $\exists x\forall y$ there must be a single $x$ that works for all $y$.

  • $\begingroup$ Very beautiful clarification about ∃x, thank you. This explained many things. $\endgroup$ – Karavana Oct 9 '12 at 19:04

Suppose we use a non-symmetric relation like $P(x,y)$ meaning $x$ is divisible by $y$ in the positive natural numbers, often written $y|x$.

Now $∃x∀y (P(x,y))$ means there exists a positive natural number $x$ that is divisible by every positive natural number $y$, which is untrue.

But $∀x∃y (P(x,y))$ means for every positive natural number $x$, there exists a positive natural number $y$ that divides $x$, and this is true.

So there is not logical equivalence between the two formulas, since that would imply equality of truth in any possible interpretation (which we see here is not the case).

  • $\begingroup$ Yet another nice example, my mind is very clear about choosing function topics now. $\endgroup$ – Karavana Oct 9 '12 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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