First order expression for functional dependency I'm puzzled with functional dependency formula in first order logic. It is triggered by

http://rjlipton.wordpress.com/2010/01/17/a-limit-of-first-order-logic/

where there seems to be a confusion between dependency and functional dependency. The expression 

$\displaystyle \forall x \exists y : S(x, y) .$

is anything but functional dependency. The formula for functional dependency is

$\displaystyle \forall y_{1} \forall y_{2} \forall x : S(x, y_{1}) \wedge S(x, y_{2}) \implies y_{1} = y_{2} .$

Now, suppose we have ternary predicate Q(x,y,z). How does one express functional dependency y=f(x)?
Apparently, we must project away variable z from ternary relation Q, which is done via existential quantifier:

∀y1∀y2∀x:(∃z:Q(x1,y,z))∧(∃z:Q(x2,y,z))⟹x1=x2.

This is equivalent to standard textbook FD definition:

∀y1∀y2∀x∀z1∀z2:Q(x1,y,z1)∧Q(x2,y,z2)⟹x1=x2.