1
$\begingroup$

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..

  • 0
    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.2012-10-09

3 Answers 3

3

"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$.

  • 0
    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.2012-10-09
1

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$.

  • 0
    Very beautiful clarification about ∃x, thank you. This explained many things.2012-10-09
0

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).

  • 0
    Yet another nice example, my mind is very clear about choosing function topics now.2012-10-09