I recently read the following article by Terence Tao: https://terrytao.wordpress.com/2007/08/27/printer-friendly-css-and-nonfirstorderizability/#comment-472808
He writes:
“Moving on to a more complicated example, if Q(x,x’,y,y’) is a quaternary relation on four objects x,x’,y,y’, then we can express the statement
For every x and x’, there exists a y depending only on x and a y’ depending on x and x’ such that Q(x,x’,y,y’) is true
as
$\forall x \exists y \forall x' \exists y': Q(x,x',y,y')$
(note that this allows y’ to depend on y also, but this turns out to be moot, because y depends only on x)”
I don’t understand his last comment within the parantheses. Is it even possible for a variable to depend on a variable that is bound by an existential quantifier? I always thought that existential variables are the only type of variable that can depend on another variable and that these existential variables can only depend on universal variables. (“Existential variable” means “variable bound by an existential quantfier”, similarly “universal variable”)
Variables bound by existential quantifiers can depend on any previously bound variable, universal or existential (or otherwise). For a silly example, consider the sentence $$\forall x\exists y\forall z\exists w(w>y+z>x).$$ Clearly the sentence is true in the natural numbers (take $y=x+1$, $w=y+z+1$), but also clearly $w$ depends on $y$.