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

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

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

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

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

share|cite|improve this answer

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.