# Predicate Logic proof: $\forall x\in S\exists y\in S p(x,y)\to \exists y\in Sp(y,y)$

For any non-empty set $S$ and predicate $p$ defined on $S^2$ prove or disprove $\forall x\in S\exists y\in S p(x,y)\to \exists y\in Sp(y,y)$

I'm trying to prove the above. First of all i need to know whether the statement is true or false.. Here how to change $p(x,y)$ to $p(y,y)$?? pretty confused..

-
Please check that I didn't change the meaning of your question by rewriting it in $\LaTeX$. –  Git Gud Jul 28 '13 at 11:07
yeah its ok do you have any idea of whether its true or false ? –  emil Jul 28 '13 at 11:09
Check my answer below. –  Git Gud Jul 28 '13 at 11:10

## 2 Answers

Let $S:=\Bbb Z$ and for all $(x,y)\in S^2$ and let $p(x,y)$ mean $x>y$.

-
Ooops sorry but the sum is given for non-empty set S –  emil Jul 28 '13 at 11:11
@emil Edit that into the question. –  Git Gud Jul 28 '13 at 11:13
Sorry I've just started logic one month ago. So i don't have much knowledge on that. Can you please explain it to me? –  emil Jul 28 '13 at 11:24
@emil Sure, but help me help you. Do you know what a conditional statement is? –  Git Gud Jul 28 '13 at 11:27
guess so.. if one side is true does it imply the other side ? –  emil Jul 28 '13 at 11:37

Your statement would be true in some cases, e.g. if $S$ is a singleton.

Your statement would be false, however, if $S=\{ x,y\}$ where $x\neq y$, and

$\forall a,b\in S(P(a,b)\leftrightarrow a\neq b)$.

This doesn't formally disprove your statement, but it does suggest that it is not true in general. Maybe that will suffice for your purposes, but I don't think it is possible to formally prove or disprove your statement as it stands, using ordinary logic and set theory.

-