What is the meaning of ∀x(∃y(A(x)))

Question

At first English is not my native language if something is not perfectly formulated or described I'm sorry.

Could somebody please tell me what the generally valid statement of this is?

$$ \forall x(\exists y(A(x))) $$

I personally believe that it could mean something like

Forall x there is one y that I get when i put x into A(x)

Answer 1

For all $x$, there exist an $y$ such that the property $A$ is true on $x$. But this is strange since $y$ is not used... Maybe the statement should be: $$\forall x, \exists y, A(x,y).$$

which means: for all $x$, there exist an $y$ such that the property $A$ is true on the pair $(x,y)$.

For example, if your property is $A(x,y) \Leftrightarrow x+y = 0$, then the statement $\forall x, \exists y, A(x,y)$ is true. Indeed, for all $x$, choosing $y = -x$ makes $A(x,y)$ true.

Answer 2

The way your statement is written now, it simply means:

For all values of $x$, there exists such a value of $y$ that $A(x)$ is true.

This is a strange, but technically completely correct statement, which is always equivalent to the statement

$$\forall x: A(x)$$

Answer 3

The details may vary according to the syntactical specifications of the language but, in general, nothing forbid to have $\exists y A(x)$ when $y$ is not free in $A(x)$; the usual recursive definition of formula in FOL is :

(i) if $t_1,\ldots,t_n$ are terms and $P^n$ is an $n$-ary predicate symbol, then $t_1=t_2$ and $P^n(t_1,\ldots,t_n)$ are atomic formulae;

(ii) if $\varphi$ is a formula, then $\lnot \varphi$ is a formula;

[...]

(iv) if $\varphi$ is a formula, then $\forall x \varphi$ and $\exists x \varphi$ are formulae.

---

Intuitively, if $y$ is not free in $\alpha$, then $\forall y \alpha$ and $\exists y \alpha$ have the "same meaning" of $\alpha$.

We can prove it "formally" showing that :

if $y$ is not free in $\alpha$, then $\vDash \alpha \leftrightarrow \forall y \alpha$,

i.e. $\alpha$ and $\forall y \alpha$ are logically equivalent, and the same for $\exists y \alpha$.

---

We can apply the above result to : $∀x(∃y(A(x)))$ and we get that it is equivalent to : $∀x(A(x))$.

The semantical specifications for the quantifiers are [according to Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)), page 83-84] :

We say that a structure $\mathcal A$ satisfy a formula $\varphi$ with an assignment function $s$, in symbols : $\mathcal A \vDash \varphi [s]$, when :

[...]

$\mathcal A \vDash \forall x \varphi[s]$ iff for every $d \in |\mathcal A|$, we have $\mathcal A \vDash \varphi[s(x|d)]$

and :

$\mathcal A \vDash \exists x \varphi[s]$ iff for some $d \in |\mathcal A|$, we have $\mathcal A \vDash \varphi[s(x|d)]$.

Thus, consider a structure $\mathcal A$ and a function $s$ and apply the above definition; $\mathcal A$ satisfies $\forall x (\exists y A(x))$ with $s$ if

$\mathcal A \vDash \exists y A(x)[s(x|d)]$, for every $d \in |\mathcal A|$.

And this, in turn, means :

$\mathcal A \vDash A(x)[s(x|d)(y|e)]$, for every $d \in |\mathcal A|$ and some $e \in |\mathcal A|$.

But the variable $y$ does not occurr free in $A(x)$ and thus it does not matter what is the "denotation" that $s(x|d)$ assign to it. So we can discard $e$ and we have :

$\mathcal A \vDash A(x)[s(x|d)]$, for every $d \in |\mathcal A|$,

and this amounts to : $\mathcal A \vDash \forall x A(x)[s]$.