Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

168 Views Asked by At

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$

I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P is "x likes y" and x is the set of girls and y is the set of guys, then we can say it's not the case that every girl likes every guy.

The first half is more difficult to say. Where could I even begin to translate that? It's not the case that not every guy is liked by a girl? This is assuming the negation is distributed to Ay and P(x,y).

This isn't homework by the way, and I already know this is a false proposition. I just want to get the intuition.

1

There are 1 best solutions below

0
On BEST ANSWER

Let's analyze the two parts of the implication:

  1. $\forall x\lnot(\forall yP(x,y))$ means that for all $x$, it is not true that for all $y$, $x$ likes $y$. In other words, For every $x$ there is some $y$ such that $x$ does not like $y$.

  2. $\forall x\forall y\lnot P(x,y)$, that's simpler. Every $x$ and every $y$ doesn't like each other.

In simpler words, if everyone has someone they don't like, nobody likes nobody.


The problem thinking about $x$ as guys and $y$ as girls is that there are no reserved variables in logic. You can't say that $x$ only quantifies over guys and $y$ over girls. So at the same time, you get that guys may like or dislike guys and girls will like or dislike girls. And in particular $x=y$ is possible, so everyone may like or dislike themselves.