2
$\begingroup$

In Logic In Computer Science (2nd Edition - Michael Huth and Mark Ryan), exercise 2.4.12.k is the following:

For each of the formulas of predicate logic below, either find a model which does not satisfy it, or prove it is valid.

This one is difficult:

(∀x ∃y (P(x) → Q(y))) → (∃y ∀x (P(x) → Q(y)))

Not only am I not sure how to prove this, I'm not sure whether it is valid or not. I came across this question when revising for an exam and always hit a dead end with it.

Any suggestions or insight is appreciated.

$\endgroup$
6
$\begingroup$

The key issue here is whether switching quantifiers is okay. Turn the top-level implication around and see what happens then.

As for this formula, think about what the left- resp. the right-hand side say.

  • Left: "Every $x$ has a $y$ so that... holds."
  • Right: "There is a $y$ so that ... holds for all $x$."

In particular, the left-hand side allows different $y$ -- one for each $x$ -- while the right-hand side requires a single $y$.

With this off the table, try to figure out whether

$\qquad \left(\forall x. \exists y. P(x,y)\right) \to \left(\exists y. \forall x. P(x,y)\right)$

holds for all predicates $P$. If so, your original questions is answered, and if not it should be easy to modify a counter-example to have the necessary form of an implication.

For the simplified formula, there is a simple counter-example: every natural number has a successor, but there is no natural number that is successor to all natural numbers.

Try to utilise this before lifting the next spoiler!

No luck? Well, that is to be expected. The "simplified" formula was a trap as it is not really a simplified formula, as you have hopefully figured out. It allows you to set $x$ and $y$ in relation which your formula does not: the (inner) implications can be read as disjunction, i.e. $\lnot P(x) \lor Q(y)$, so $P$ and $Q$ can fulfill the disjunction independently of another.

Can you prove that the formula holds now?

If the left-hand side is fulfilled -- if it is not, the whole formula is trivially fulfilled -- all $x$ fulfill $\lnot P(x)$ or there is (at least) one $y$ that fulfills $Q(y)$ (to rescue the failing $x$). In either case (they can overlap!) the right hand side is fulfilled. In particular, if $\lnot P(x)$ is true for all $x$, $y$ can be chosen arbitrarily (on the right-hand side), else choose one of the rescuers. Be aware that the empty element domain -- if allowed -- is a special case.

$\endgroup$
  • $\begingroup$ This is a wonderful answer! Note that (and I hope this doesn't give too much away) the reasoning only holds in classical logic. $\endgroup$ – cody Jun 16 '12 at 9:09
1
$\begingroup$

consider the empty {P,Q}-structure ...

$\endgroup$
  • $\begingroup$ For empty domains, the formula holds because $\exists y. \dots$ is always false. $\endgroup$ – Raphael Jun 15 '12 at 15:03
  • $\begingroup$ but the first part is alway true. $\endgroup$ – foo Jun 15 '12 at 15:05
  • $\begingroup$ No, it is not. There is no $y$ to fulfill it; you can fulfill it with arbitrary $Q$ if $P$ is well-chosen, but there as to be one element in $y$'s domain to fulfill the formula. And -- I am not sure how you meant "always" -- you can find plenty of models that do not fulfill the left-hand side, e.g. $P(x) = T$ and $Q(x) = F$ for all $x$. $\endgroup$ – Raphael Jun 15 '12 at 15:09
  • 2
    $\begingroup$ @Raphael For an empty domain, the formula is always false, because $\forall x$ is never instantiated, hence the left-hand side of the implication is true. $\endgroup$ – Gilles 'SO- stop being evil' Jun 15 '12 at 16:22
1
$\begingroup$

Let's try to express $(\forall x, \exists y, (P(x) \rightarrow Q(y))) \to (\exists y, \forall x, (P(x) \rightarrow Q(y)))$ in English:

Premise: suppose that for every $x$, there is a $y$ such that $P(x)$ implies $Q(y)$.
Conclusion: then there is a $y$ such that for every $x$, $P(x)$ implies $Q(y)$.

Suppose the premise holds, and suppose that we have found an $x_0$ such that $P(x_0)$ holds. Then there is a $y_0$ such that $Q(y_0)$ holds. There is nothing specific to $x_0$ about $y_0$: if there is some other $x$ that satisfies $P(x)$, then we can take that same $y_0$, we still have $Q(y_0)$, hence we still have that $P(x)$ implies $Q(y)$.

Or, in other words, if the premise holds and there is an $x_0$ such that $P(x_0)$ holds, then the conclusion holds. We have proved that the formula is always true under the additional assumption $\exists x_0, P(x_0)$.

So all we need to do now is look at what happens if that additional assumption does not hold. By the principle of excluded middle and the well-known principles of inversion of negation and quantifiers, the opposite assumption is $\forall x, \neg P(x)$. Since $P(x)$ never holds, the implication $P(x) \rightarrow Q(y)$ always holds. Are we finished? Almost. If we take any $y_0$ in the model, then the formula $\forall x, (P(x) \rightarrow Q(y_0))$ holds. So the conclusion is true in every non-empty model, hence the formula holds in every non-empty model.

If you allow an empty model, then the formula does not hold, because the premise is true ($\forall x, …$ is vacuously true) and the conclusion is false ($\exists y, …$ is vacuously false).

$\endgroup$

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.