Coincidence Lemma and universal validity? I'm supposed to say whether the following statement is true or not:
$$ \exists x \exists y f(x) = y \equiv \forall x \exists y (( x = y \vee E(x,y)) \rightarrow \exists z (z=y \vee E(z,y)))$$
I have a couple of questions about the coincidence lemma here:
If you assume that your $\sigma$ structure has elements a, b in its universe so that f(a)=b holds, does it then follow from the coincidence lemma that f(a)=b is true for all interpretations, since there are no free variables in this formula?
If that was the case then the left side would be universally valid. Now the formula on the right side is also universally valid, I think. Because the left side of the implication is the same as the right side of the implication. Does it then even matter whether this is true for all elements x and a given y in the universe of the structure?
So I would say the two formulas are equivalent, since both are universally valid, is that true?
 A: Yes both are universally valid unless you allow for the empty structure. In this case the left hand formula is false since there exist not elements in the empty structure, the right hand formula is though allways true, even in the empty structure. If you however have constant symbols in your language, then you need to have at least one element in the universe, and thus the empty structure is not allowed. 
Regarding question 1. If $a,b$ are elements in the universe of a structure, then the interpretation in the structure is already fixed, and thus talking about "all interpretations" does not make much sense (since we only have one).
Regarding question 2. The right formula we need to actually note that if we, whenever evaluating the formula in a structure, let $z:=x$, then the formula will be true. So just saying "the left and the right formula is the same" is a bit sketchy. For instance if we instead of $\exists z(\ldots)$ had $\forall z(\ldots)$ then the right hand formula would not be true.
A: The lefthand side is true in any (nonempty!) model (= interpretation); the righthand side is true in any model. Function symbols are total functions, and the righthand side is true basically because $\forall x\exists y(whatever(x,y)\to\exists z(z=y \lor whateverElse(y,z)))$ is valid. 
Re your question about the "coincidence lemma" (I don't know this term): something's amiss there. if $a,b$ are elements of a model, not constants of the signature $\sigma$, what do you mean about $f(a) = b$  being true in all models? They must be constants after all, and $f(a)=b$ holds in some model.
Long story short: Yes, they're equivalent, because they're both valid in first order logic, which classically assumes a nonempty universe: ($\exists x)\,x=x$ is a theorem.
