Give a formal derivation of ∃x~P(y) given the premises ~∃x(∀yP(y) ∧ Q(x)) and Q(b)

Question

This is one of the question I was given for homework, and I'm not sure how to do it, I'm not even really sure how to start. I missed some classes, and I've been trying to figure it out for a couple hours, but still haven't gotten anywhere.

Edit 1: so I've come up with this, however I’m not very confident about it

1. ~∃x(∀yP(y)$\wedge$Q(x))
2. Q(b)
3. ∀x~(∀yP(y)$\wedge$Q(x)) 1, change to universal quantification
4. ∀x~(∀yP(y)) 3, specialization
5. ~(∀yP(y)) 4, U.I.
6. ∃y~P(y) 5, change to existential quantification

Answer 1

It is hard without knowing what rules of inference you are allowed to use ...

Assuming that we can use the equivalences between $\forall \lnot$ and $\lnot \exists$ and between $\lnot \forall$ and $\exists \lnot$ and De Morgan's laws, we have first to rewrite the formula :

$\lnot ∃x(∀yP(y) \land Q(x))$

as : $∀x \lnot (∀yP(y) \land Q(x))$ which is equivalent to $∀x (\lnot ∀yP(y) \lor \lnot Q(x))$ and finally to :

$∀x (∃y \lnot P(y) \lor \lnot Q(x))$.

---

Now for the derivation :

1) $∀x (∃y \lnot P(y) \lor \lnot Q(x))$ --- premise [1] (after the transformation)

2) $Q(b)$ --- premise [2]

3) $∃y \lnot P(y) \lor \lnot Q(b)$ --- from [1] by $\forall$E (i.e. UI)

4) $∃y \lnot P(y)$ --- assumed [2]

5) $\lnot Q(b)$ --- assumed [3]

6) $\bot$ --- from 2) and 5) by $\rightarrow$E (or modus ponens)

7) $∃y \lnot P(y)$ --- from 6) by $\bot$E

8) $∃y \lnot P(y)$ --- from 3), 4), 5) and 7) by $\lor$E, discharging assumptions [2] and [3]

Conclusion from 1), 2) and 8) :

$\lnot ∃x(∀yP(y) \land Q(x)), Q(b) \vdash ∃y \lnot P(y)$.

---

Note

In the derivation I have use natural deduction; if your proof system is different, you have to adapt the above proof to it.

For example, the above derivation can be easily adapted to an Hilbert-style proof, using again De Morgan and the equivalences between quantifiers.

We have to start from premise 1 :

$\lnot ∃x(∀yP(y) \land Q(x))$

and apply De Morgan "inside" to get :

$\lnot ∃x \lnot (\lnot ∀yP(y) \lor \lnot Q(x))$

which is :

$\forall x(\exists y \lnot P(y) \lor \lnot Q(x))$.

Now we instantiate the universal quantifier, to get :

$\exists y \lnot P(y) \lor \lnot Q(b)$

and use the equivalence between $\lnot p \lor q$ and $p \rightarrow q$ to rewrite it as :

$Q(b) \rightarrow \exists y \lnot P(y)$.

The conclusion follows from premise 2 and modus ponens.

Answer 2

If we are asked to provide a formal derivation, it's always relevant to know the rules you are asked to use. I'm assuming here you are using standard FOL natural deduction calculus. The proof then goes as follows:

1. $\neg \exists x (\forall y P(y) \wedge Q(x))$, P
2. $Q(b)$, P
3. $\forall x \neg (\forall y P(y) \wedge Q(x))$, 1 $\exists$def
4. $ \neg (\forall y P(y) \wedge Q(b)$ 3 $\forall$E (UI)
5. $\neg \forall y P(y) \vee \neg Q(b)$ 4 De Morgan Laws
6. $\neg \forall y P(y)$ 5 Disjunctive Syllogism
7. $\exists y \neg P(y)$ 6 $\exists$def

As you can see I'm assuming some propositional admissible rules, namely, the De Morgan Laws and Disjunctice Syllogism, hoping that you can complete it as the rest of your homework.