# What does the following statement in first order logic translate to in english?

∃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?

Thanks.

• 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. – Cornman Sep 26 '17 at 14:04
• 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? – Saad Sep 26 '17 at 14:10

## 2 Answers

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?

• 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)? – Saad Sep 26 '17 at 14:34
• @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. – Reese Sep 26 '17 at 14:51
• 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? – Saad Sep 26 '17 at 14:51
• @Saad, it is universal instantiation, $\forall x\,(x\not R x)\implies y\not R y$. – Ennar Sep 26 '17 at 15:01

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