How to prove $\forall x\; (\phi (x)\land \psi (x) ) \rightarrow \forall x\; \psi (x)$ without using the completeness theorem?

74 Views Asked by At

The statement $\forall x\; (\phi (x)\land \psi (x) ) \rightarrow \forall x\; \psi (x)$ is valid, that is it is true in any structure. Hence, for any $\sum \subseteq Form_{\mathcal{L}}\; \sum \models \forall x\; (\phi (x)\land \psi (x) ) \rightarrow \forall x\; \psi (x)$. This, by completeness theorem, implies that for all $\sum \subseteq Form_{\mathcal{L}}\; \sum \vdash \forall x\; (\phi (x)\land \psi (x) ) \rightarrow \forall x\; \psi (x)$. However, this answer didn’t satisfied me. I look for an answer in which completeness theorem not included. Because I don’t want the manipulation rules to be involved in the metatheory.

1

There are 1 best solutions below

0
On

Here's a direct proof using the system in your book.

  1. $(\forall x\, (\phi(x)\land \psi(x)))\to (\phi(x)\land \psi(x))\quad$ (Q1, substituting $x$ for $x$)
  2. $(\forall x\, (\phi(x)\land \psi(x)))\to \psi(x)\quad$ (Propositional logic, from 1)
  3. $(\forall x\, (\phi(x)\land \psi(x)))\to \forall x\,\psi(x)\quad$ (QR, from 2, since $x$ is not free in $\forall x\, (\phi(x)\land \psi(x))$)