Prove $\exists x P(x) \wedge \forall y(P(y) \rightarrow Q(y)) \rightarrow \exists z Q(z)$ is a tautology

96 Views Asked by At

Is this proof correct?

Proof by contradiction

$\phi = \exists x P(x) \wedge \forall y(P(y) \rightarrow Q(y)) $
$\psi = \exists z Q(z) $

  1. Assume $\phi \rightarrow \psi$ is not a tautology
  2. Then there exists an interpretation $I$ such that $I(\phi) = true$ and $I(\psi) = false$
  3. Under this interpretation, $I(\psi) = true$ as:

$\quad\quad $ $\phi \vDash \psi$ (If the premises are true, then there will exist an element with property Q)

  1. A contradiction is reached
  2. Therefore, $\phi \rightarrow \psi$ is a tautology