# what does that statement mean about the relation?

what does this mean about P? $$\forall x \exists y (p(x,y) \rightarrow p(y,x))$$

i know that $$\forall x \forall y (p(x,y) \rightarrow p(y,x))$$ means that P symmetric

but what does the first statement means?

and what does the last statement mean about the relation P?

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

-
Do you know what $\forall$, $\exists$, and $\rightarrow$ mean? – Chris Eagle Jun 8 '12 at 11:19
of course i do :\ – Nahum Litvin Jun 8 '12 at 11:29

$\forall x \exists y (p(x,y) \rightarrow p(y,x))$ says that for each $x$ there is a $y$, which may depend on $x$, such that if $p(x,y)$, then also $p(y,x)$. Let me write $xPy$ to mean $p(x,y)$.

Suppose that the statement is true, and fix a particular $x$. Then there’s some $y$, perhaps only one, such that $xPy\to yPx$. Under what circumstances is this true? The only time it’s false is when $xPy$ is true and $yPx$ is false; it’s true whenever $xPy$ is false, or $yPx$ is true, or both. Thus, if you can find a $y$ such that $x(\lnot P)y$, that $y$ works: $xPy\to yPx$ is vacuously true, because $xPy$ is false.

What if $xPy$ for every $y$, so that you can’t find such a $y$? If you can find a $y$ such that $yPx$, you can use it, because then $xPy\to yPx$ is true.

The only time you’re out of luck is when $xPy$ for every $y$, and there is no $y$ such that $yPx$: then no matter what $y$ you pick, $xPy$ is true and $yPx$ is false, so $xPy\to yPx$ is false.

$\forall x \exists y (p(x,y) \rightarrow p(y,x))$ therefore says that for each $x$ there is a $y$ such that either $x(\lnot P)y$, or $yPx$ (or both). Alternatively, it says that there is no $x$ such that for every $y$, $xPy$ and $y(\lnot P)x$: there is no $x$ that is related to everything but not from anything.

In fact, though, this is trivially true. Pick any $x$; if $xPx$, then $xPx\to xPx$, and we can simply let $y=x$. If $x(\lnot P)x$, then again $xPx\to xPx$, this time vacuously (because the antecedent is false), and we can let $y=x$. Thus, $\forall x \exists y (p(x,y) \rightarrow p(y,x))$ is true of any relation, because for each $x$ we can take $y=x$ and have $p(x,y) \rightarrow p(y,x)$.

The statement $\forall y (\exists x P(x,y) \rightarrow \exists x P(y,x))$ is quite different. In terms of relations it says that each $y$ that is related from something is also related to something, but not necessarily the same thing. Consider, for instance, the relation $P$ on $\{0,1,2,3,4\}$ defined by $0P1P2P3P4P0$; that is, under $P$ the elements $0,1,2,3$, and $4$ form a circular chain. This relation satisfies the statement in question: for each $k\in\{0,1,2,3,4\}$, if there is some $m$ such that $mPk$, then there is some $n$ such that $kPn$. I could throw $5$ into the set without changing $P$, and $P$ would still have the property: there is no $m$ such that $mP5$, so the statement $\forall y (\exists x P(x,y) \rightarrow \exists x P(y,x))$ says nothing about $5$. But if I also add $3P5$, say, in order to keep the property I have to add $5Pk$ for at least one $k$.

-
wow, now I am even more confused :( – Nahum Litvin Jun 8 '12 at 12:00
@Nahum: Can you pin down any of your confusion? – Brian M. Scott Jun 8 '12 at 12:03
after using "Google translate" and several rereadings Iv understood your explanation about the first statement :) I understand the second explanation. i did think about it by myself, but i fail comprehend how use it to solve the full problem (that I didn't show here) the problem involves finding maximal set of such statements form a list. – Nahum Litvin Jun 8 '12 at 12:14
@Nahum: Sorry: I sometimes forget that I’m often writing for people for whom English is a second (or third, or fourth, ...) language. – Brian M. Scott Jun 8 '12 at 12:15
@who voted down with no explanation? – Nahum Litvin Jun 9 '12 at 9:18