Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\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.

share|improve this question
    
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. –  MJD Oct 31 '12 at 3:49

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
shouldn't it be $P(c) \vee Q(c)$? –  Gladstone Asder Oct 31 '12 at 17:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.