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.

  • $\begingroup$ 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)$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.