∃x∃y (yRf(x) ---> xRx)

I have to prove that this is a tautology formally, but I don't even understand what it means.. Are R and f arbitrary relations / functions, or are we free to choose them? Is f a function going from X to Y? What is the universal set in our case?


  • $\begingroup$ Is there more context to this task? $R$ should be a relations-symbol and $f$ a function-symbol. It means that there exist $x$ and $y$ such that if $y$ is in relation to $f(x)$ then $x$ is in relation to $x$. I guess you can choose $y=f(x)$ for the proof, but I am not sure. $\endgroup$ – Cornman Sep 26 '17 at 14:04
  • $\begingroup$ The only other thing mentioned is that I have to make a derivation of valid arguments to prove it. Also, I don't know whether we can choose y= f(x), but even if we could, would that necessarily imply xRx, given that we don't know what R is? $\endgroup$ – Saad Sep 26 '17 at 14:10

If $R$ and $f$ have not been given, then they're arbitrary. $f$ is just a function - there is no $X$ or $Y$ to think about, and the universal set isn't relevant. In general, when asked to prove a statement in first-order logic, you are intended to prove that the statement holds no matter what, so the universal set can't possibly be relevant. $f$ is just a function that turns things into other things. For all we know, $f(2)$ might be $3$, or it might be "hamster".

Let's translate the sentence. $\exists x\exists y(yRf(x) \rightarrow xRx)$ begins with an existential quantifier, so it means that for some $x$, $\exists y(yRf(x) \rightarrow xRx)$. Peeling away the second quantifier, we have that for some $x$ and some $y$, $yRf(x) \rightarrow xRx$.

When I don't know what a relation is, I like to translate it as "is related to" (so $xRy$ means "$x$ is related to $y$"). So this conditional statement $yRf(x) \rightarrow xRx$ reads as "if $y$ is related to $f(x)$, then $x$ is related to $y$". So the entire sentence translates to "for some $x$ and some $y$, if $y$ is related to $f(x)$ then $x$ is related to $x$".

This is actually quite difficult to think about - what's particularly confusing, and what I imagine is making it hard for you, is that the phrases "$y$ is related to $f(x)$" and "$x$ is related to $x$" don't really seem to have anything to do with each other, without knowing more about $R$ and $f$. So concentrate on vacuous truth - remember, there's a couple of "cheaty" ways to make an "if-then" sentence true. First, you could make the consequent true; or, you could make the antecedent false. In that case, that means that we would only need $xRx$ or $\neg yRf(x)$. Translating again, this is our new sentence:

"For some $x$ and some $y$, either $x$ is related to $x$ or $y$ isn't related to $f(x)$".

Now, that "some $x$ and some $y$" means we just need one pair for which this works - we're not talking about everything. If we can find one thing to be $x$ so that $xRx$, we're done, and we don't care about $f$! If not, well then that means that $yRy$ never holds. Can you find a way to use that to find a $y$ so that $yRf(x)$ does not hold?

  • $\begingroup$ Thank you for the answer. I understood only some of the last paragraph.. We can choose y=f(x) so, we get yRy, which is false because xRx is not true for any x. But the statement says : 'For some x and some y .. ' And we're also assuming that the function f is arbitrary. So how can we then choose y = f(x)? $\endgroup$ – Saad Sep 26 '17 at 14:34
  • 2
    $\begingroup$ @Saad To show that "there is a red shirt in the drawer", pick a shirt - if it's red, you've proven the claim. If not, you've shown nothing (a blue shirt doesn't prove it wrong). Likewise, to show that "for some $x$ and some $y$...", pick an $x$ and a $y$. If they satisfy the rest of the sentence, you've proven the sentence. We can choose $y = f(x)$ because we know that there is a thing that is $f(x)$ (that's what a function does, it turns things into other things!) and we are free to "name" this thing $y$. We're not making any deduction or anything, just re-naming. $\endgroup$ – Reese Sep 26 '17 at 14:51
  • $\begingroup$ Nevermind. Upon reading it again, I think I understand it. Could you tell me how, in first order logic, would we show that the negation of xRx implies the negation of yRy? $\endgroup$ – Saad Sep 26 '17 at 14:51
  • $\begingroup$ @Saad, it is universal instantiation, $\forall x\,(x\not R x)\implies y\not R y$. $\endgroup$ – Ennar Sep 26 '17 at 15:01

If this helps any, here's a formal proof in Fitch:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.