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