0
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Jan 17 '16 at 20:39
  • $\begingroup$ 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? $\endgroup$ – Aggelos Sfakianos Jan 17 '16 at 21:00
  • $\begingroup$ well even if i do this,i dont really know how to start a proof by contradiction in this one. Help me please $\endgroup$ – Aggelos Sfakianos Jan 17 '16 at 21:02
  • $\begingroup$ 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. $\endgroup$ – fleablood Jan 17 '16 at 21:43
  • $\begingroup$ @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 ... $\endgroup$ – Mauro ALLEGRANZA Jan 21 '16 at 10:10
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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

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