1
$\begingroup$

$\exists y \forall x (P(x) \vee Q(y)) \equiv \forall xP(x) \vee \exists x Q(x)$

If the LHS is true, then there are two cases: P(x) is true, in which case $\forall$ P(x) is true and the RHS is true, and Q(y) is true, in which case $\exists$ x Q(x) is true and the RHS is true.

If the RHS is true, then there are two cases $\forall$ P(x) is true, in which case P(x) is true and the LHS is true, and $\exists$ x Q(x) is true, in which case Q(y) is true and the LHS is true.

$\endgroup$
1
  • $\begingroup$ I hope it's not rude to ask if you are not the same user as Mathilda Pitt, and, if so, why you are using two accounts instead of one. $\endgroup$
    – MJD
    Commented Oct 31, 2012 at 3:49

1 Answer 1

2
$\begingroup$

I think the easiest way to prove this is to use the rules for manipulating quantifiers. Starting with the LHS, we have

$$ \begin{align*} \exists y[\forall x(P(x)\vee Q(y))] &\equiv \exists y [\forall x P(x) \vee \forall x Q(y)]\\ &\equiv \exists y [\forall x P(x) \vee Q(y)] \\ &\equiv \exists y\forall x P(x) \vee \exists y Q(y) \\ &\equiv \forall xP(x) \vee \exists yQ(y) \\ &\equiv \forall xP(x) \vee \exists xQ(x). \end{align*} $$

This is because $\mathbf{Q}\mathbf{v}(\mathbf{P}(\mathbf{v})\ \mathbf{B}\ \phi)\equiv (\mathbf{Q}\mathbf{v}\mathbf{P}(\mathbf{v}))\ \mathbf{B}\ \phi$ is valid where $\mathbf{Q}$ is a quantifier, $\mathbf{v}$ is a variable, $\mathbf{P}$ is a predicate, $\mathbf{B}$ is either the conjunction or disjunction operator, and $\phi$ is a formula where $\mathbf{v}$ isn't free.

For your proof, when assuming the LHS, splitting directly into cases isn't possible because the disjunction is "trapped" by the quantifiers. We must say: let $c$ be an object such that $\forall x(P(x)\vee Q(c))$ is true (we know such a $c$ exists because of the assumption). Now let $a$ be an arbitrary object. We know $P(a)\vee Q(c)$ is true. Suppose now that $Q(c)$ is true. Then certainly $\exists xQ(x)$. Now suppose $P(a)$ is true. Since $a$ was arbitrary, $\forall xP(x)$ is true.

$\endgroup$
1
  • $\begingroup$ shouldn't it be $P(c) \vee Q(c)$? $\endgroup$ Commented Oct 31, 2012 at 17:29

You must log in to answer this question.

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