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$ Jan 17, 2016 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$ Jan 17, 2016 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$ Jan 17, 2016 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, 2016 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$ Jan 21, 2016 at 10:10

2 Answers 2

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.