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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


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.