# Show that $(\phi(\tau)\to\exists x\phi(x))$ is universally valid where $\tau$ is freely substitutable for $x$

I want to show that $$(\phi(\tau)\to\exists x\phi(x))$$ is universally valid where $$\tau$$ is freely substitutable for $$x$$.

I think a relevant theorem is the following:

Let $$\phi$$ be a formula, $$x_1$$ a variable and $$\tau$$ a term which is freely substitutable for $$x_1$$ in $$\phi$$. Let $$\mathcal{A}=\{A,...\}$$ be a structure for the underlying language $$L$$ and let $$\vec{a}$$ be an interpretation of the variables $$\vec{x}$$ of $$L$$. Then, $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x_1/\tau[\vec{x}/\vec{a}]^{\mathcal{A}}]}\phi(x_1)$$ if and only if $$\mathcal{A}\vDash_{\vec{x}/\vec{a}}\phi(\tau).$$

My proof that $$(\phi(\tau)\to\exists x\phi(x))$$ is universally valid is as follows:

We have that $$(\phi(\tau)\to\exists x\phi(x))$$ is universally valid if for all interpretations $$[\vec{x}/\vec{a}]$$, the statement is true. This amounts to saying that the statement is universally valid if $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x/b][x_1/b_1][x_2/b_2]...[x_n/b_n]}(\phi(\tau)\to\exists x\phi(x))$$ for all $$b, b_1, b_2,...,b_n\in A$$. Now, this statement is true only if it satisfies the truth table for implication ($$\to$$). So, if $$\phi(\tau)$$ is always false, we are trivially done. Suppose instead that $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x/b][x_1/b_1][x_2/b_2]...[x_n/b_n]}\phi(\tau),\tag{1}$$ for all $$b,b_1,b_2,...,b_n\in A$$. We want to show that $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x/b][x_1/b_1][x_2/b_2]...[x_n/b_n]}\exists x\phi(x)$$ for all $$b, b_1, b_2,...,b_n\in A$$. But by the theorem, because (1) holds, we have that $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x/b][x_1/b_1][x_2/b_2]...[x_n/b_n][x/\tau[\vec{x}/\vec{a}]^{\mathcal{A}}]}\phi(x)$$ for all $$b,b_1,b_2,...,b_n\in A$$. But this is equivalent to saying that $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x_1/b_1][x_2/b_2]...[x_n/b_n]}\forall x\phi(x).$$ But then certainly, $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x_1/b_1][x_2/b_2]...[x_n/b_n]}\exists x\phi(x),$$ since if it's true for all $$x$$ then it is certainly true that there exists an $$x$$ such that the statement is true, and we are done.

Needless to say, I've been having a very difficult time getting used to this notation as it's fairly dense. As such, I have no idea if I'm on the correct track with this. Any help would be appreciated.

Update: I posted my answer to this question making use of only the theorem given. I was being a bit silly with my understanding of universal validity, which led to a lot of confusion. It has since been cleared up.

• Starting from $\phi(\tau)\vdash\phi(\tau)$, we get $\phi(\tau)\vdash\exists x\phi(x)$ by existential intrudction rule, from which we get $\vdash\phi(\tau)\implies\exists x\phi(x)$. – Fabio Lucchini Oct 15 '18 at 15:17

We note that $$(\phi(\tau)\to\exists x\phi(x))$$ is universally valid if it is true for all structures and all interpretations. For the structures and interpretations of structures where $$\phi(\tau)$$ is false, we are done by the truth table for implication ($$\to$$). It remains to show for the structures and interpretations for which $$\phi(\tau)$$ is true, that $$\exists x\phi(x)$$ is also true. Let $$\mathcal{A}$$ be a structure, and let $$[\vec{x}/\vec{a}]$$ be an interpretation under this structure. Suppose, $$\phi(\tau)$$ is true under this structure and interpretation. Then we have, $$\mathcal{A}\vDash_{\vec{x}/\vec{a}}\phi(\tau).$$ But then, by the theorem, because $$\tau$$ is freely substitutable for $$x$$, we have that $$\mathcal{A}\vDash_{\vec{x}/\vec{a}[x/\tau[\vec{x}/\vec{a}]^{\mathcal{A}}]}\phi(x).$$ And so it follows that $$\mathcal{A}\vDash_{\vec{x}/\vec{a}}\exists x\phi(x),$$ as desired.