|= (∀xA(x) → ∃yB(x,y)) → ∃x(A(x) → ∃yB(x,y)) is this a correct statement ?

Question

i can't prove or disprove the statement: |= (∀xA(x) → ∃yB(x,y)) → ∃x(A(x) → ∃yB(x,y)) can someone help me to understand whether the statement is valid or not ?

Cheers and thanks in advanced.

Answer 1

Given the free variable $x$ in the first $B(x,y)$, the formula is valid if and only if for any variable assignment $v$ and interpretation $I$:

If $I,v \vDash \forall x A(x) \rightarrow \exists y \ B(x,y)$ then $I,v \vDash \exists x (A(x) \rightarrow \exists y \ B(x,y))$

For a quick and dirty way to see that that is indeed the case, without doing a purely semantical or purely formal syntactical proof:

Suppose $v$ maps variable $x$ to some object that we denote by $c$, and suppose we have an $I$ that sets $\forall x A(x) \rightarrow \exists y \ B(c,y)$ to true.

We'll show by a proof by contradiction that this means that $I$ will set $\exists x(A(x) \rightarrow \exists y \ B(x,y))$ to true. Thus, suppose $\neg \exists x (A(x) \rightarrow \exists y \ B(x,y))$. The latter can be rewritten as:

$$\neg \exists x (A(x) \rightarrow \exists y \ B(x,y)) \Leftrightarrow$$

$$\forall x \neg (A(x) \rightarrow \exists y \ B(x,y)) \Leftrightarrow$$

$$\forall x (A(x) \land \neg \exists y \ B(x,y)) \Leftrightarrow$$

$$\forall x A(x) \land \forall x \neg \exists y \ B(x,y)$$

So, we have $\forall x A(x)$, and thus by the first Assumption we have $\exists y \ B(c,y)$, but we also have $\forall x \neg \exists y \ B(x,y)$, and therefore $\neg \exists y \ B(c,y)$, and thus we obtain a contradiction as desired.

And so yes, this is indeed a valid formula.