1
$\begingroup$

let $\Sigma$ be a consistent set of formulas in first-order logic and implies $\exists x(\phi (x)→\psi(x))$. which one of these statements is logical implication from $\Sigma$?

a) $\forall x\phi(x)→\forall y\psi(y) $

b) $\exists x\phi(x)→\forall y\psi(y)$

c) $\exists x\phi(x)→\exists x\psi(x) $

d) $\forall x\phi (x)→\exists y\psi(y)$

I think This sentence implies $\exists x\phi(x)→\exists x\psi(x) $ but the answer is $\forall x\phi (x)→\exists y\psi(y)$ how we can imply that for all x exist a y which $y\psi(y)$ ?! I can't understand it.

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ Aug 2, 2020 at 12:28
  • $\begingroup$ Which kinds of deduction systems, if any, have you been using -- tableaus aka truth trees, natural deduction, resolution, ..., or so far just informal argumentations about structures? This will help answerers know what kinds of explanations they can use. $\endgroup$ Aug 2, 2020 at 12:39
  • $\begingroup$ I used Natural deduction @lemontree $\endgroup$
    – Toobatf
    Aug 2, 2020 at 12:42

2 Answers 2

2
$\begingroup$

The inference $\exists x (\phi(x) \to \psi(x)) \nvDash \exists x\phi(x) \to \exists x \psi(x)$ is invalid because there exists a counter model:
Let the domain be $\{a, b\}$ and $\phi$ true of $a$ but not of $b$, and $\psi$ true of none of the elements.
Then for $x \mapsto b$, $\phi(x)$ is false so $\phi(x) \to \psi(x)$ is true, so $\exists x (\phi(x) \to \psi(x))$ is true.
But $\exists x \phi(x)$ is true with $x \mapsto a$ whereas $\exists x \psi(x)$ is false since $\psi$ is true of neither $a$ nor $b$, so $\exists x \phi(x) \to \exists x \psi(x)$ is false.
Since in this structure the premise is true but the conclusion is false, the inference is invalid.

The inference $\exists x (\phi(x) \to \psi(x)) \vDash \forall x\phi(x) \to \exists x \psi(x)$ is valid by the following reasoning:

By assumption, $\phi(x) \to \psi(x)$ holds of some object; let it be $y$. Assume $\forall x \phi(x)$, then in particular $\phi$ holds of $y$. By modus ponens, $\psi$ must also be true of $y$. Hence there exists an object of which $\psi$ holds, so $\exists x \psi(x)$ is true. Thus $\forall x \phi(x) \to \exists x \psi(x)$. Since an object such as $y$ is assumed to exist, $\forall x \phi(x) \to \exists x \psi(x)$ holds regardless of which particular object $\phi(x) \to \psi(x)$ is true of.

As an exercise, you can now try to translate this informal proof into a natural deduction proof.

$\endgroup$
1
$\begingroup$

For a counter-example to (c), you just need a single $x$ for which $\phi(x)$ is false. Then for this $x$, we have $\phi(x)\to$ anything at all. So $\exists x(\phi(x)\to\psi(x))$ is true. But we have no reason to infer that $\exists x(\psi(x))$.

As for your final paragraph: it looks like you are interpreting $$\forall x\phi (x)\to\exists y\psi(y)$$ as $$\forall x(\phi (x)\to\exists y\psi(y))$$ whereas the correct interpretation is $$(\forall x\phi (x))\to(\exists y\psi(y))$$

$\endgroup$
1
  • $\begingroup$ I agreed (∀𝑥𝜙(𝑥))→(∃𝑦𝜓(𝑦)) is true but how we can say ∃𝑥𝜙(𝑥)→∃𝑥𝜓(𝑥) is not true ? @TonyK $\endgroup$ Aug 5, 2020 at 1:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .