# Proof by contradiction in predicate logic

So we are given the following to prove, only by proof by contradiction

$\forall x(Q(x)\to P(y)) \vDash \forall xQ(x)\to P(y)$

Now the first thing that comes to mind in predicate logic when i am on a dead end is to perform Tarski's theorem about truth and see what types of structures ,the given types are true. But when it comes to analyzing the first part: $\forall x(Q(x)\to P(y))$ i am not very sure if i can say which structures(we want to find structures as sets, for example:for every x that makes Q true, there is a y that makes P truth etc) Anyway i need help finding the types for structures these types need to be true so after that i can move forward and start the proof by contradiction.Thanks

• In the proof by contradiction, you have to assume a "generic" structure where both the premise and $∀xQ(x)$ are true, and suppose that $P(y)$ is false. – Mauro ALLEGRANZA Jan 17 '16 at 20:39
• so you are saying i dont have to actually find the types of structures, i just have to assume general structures and advance to the atopic? – Aggelos Sfakianos Jan 17 '16 at 21:00
• well even if i do this,i dont really know how to start a proof by contradiction in this one. Help me please – Aggelos Sfakianos Jan 17 '16 at 21:02
• The opposite of $\forall xQ(x)\to P(y)$ is $- P(y)$ and $\forall xQ(x)$ which would mean there exists an x where Q(x) and not P(x), so there exists an x such that it isn't true Q(x) -> P(x) so it's not the case that $\forall x(Q(x) \implies P(x))$. I think. – fleablood Jan 17 '16 at 21:43
• @GrahamKemp : but $∀x(Q(x)→P(y)) \vdash Q(x)→P(y)$ is a correct application of $\forall$-elim, and $∀xQ(x) \vdash Q(x)$ also is. Thus, by $\to$-elim, we get $P(y)$ and finally, by $\to$-intro, we have $∀xQ(x)→P(y)$. In conclusion : $∀x(Q(x)→P(y)) \vdash ∀xQ(x)→P(y)$ and the result must follow from soundness. I'm not able to manufacture a "semantic" counter-example ... – Mauro ALLEGRANZA Jan 21 '16 at 10:10

Hint:

1. Suppose $\forall x(Q(x)\to P(y))$

2. Suppose $\forall x(Q(x))\land \neg P(y)$

Obtain a contradiction, thus negating (2).

$\forall x(Q(x)\to P(y)) \;\models\; \forall x\,Q(x)\;\to\;P(y)$

To prove by contradiction show that $\neg(\forall x\,Q(x)\to P(y)) \;\models\; \neg\forall x(Q(x)\to P(y))$

$$\begin{array}{l} \neg(\forall x\,Q(x)\to P(y)) \\ \forall x\,Q(x) \wedge P(y) \\ \exists x\, Q(x)\wedge P(y) \\ \exists x\,(Q(x)\wedge P(y)) \\ \exists x\,\neg(Q(x)\to P(y)) \\ \neg \forall x\,(Q(x)\to P(y)) \\ \Box \end{array}$$

(Skeleton only: Justifications and several steps omitted).