I am struggeling with giving prove for the next statement : $\vdash\exists x (P(x) \rightarrow P(y))$.

This is what I have done but it fails because $\alpha$ isn't a logical sentence.

$\exists x (P(x) \rightarrow P(y)) \equiv \lnot \forall x \lnot (P(x) \rightarrow P(y)) \equiv \alpha$

1) $ \lnot \alpha \equiv \lnot (\forall x \lnot (P(x) \rightarrow P(y))) \equiv \forall x \lnot (P(x) \rightarrow P(y))$

2) $ \forall x \lnot (P(x) \rightarrow P(y)) \rightarrow \lnot (P(x) \rightarrow P(y)) $ (Assignment of x=x + Axiom)

3) $ \lnot (P(x) \rightarrow P(y)) $ (1 + 3 + M.P.)

4) $ P(x) $

5) $ \lnot P(y)$

5 + 6 derived from the following statement: $ \lnot (\alpha \rightarrow \beta) \vdash \alpha , \lnot \beta $

Now $x ,y $ are just random variables so they depends on the specific placement of x or y , and therefore I proved that $ \lnot \alpha \vdash P(x) , \lnot P(x)$ and from lemma we get that: $\vdash \lnot (\lnot\alpha)$ which is exactly as: $\vdash \alpha$

I know how to prove $ \exists x (P(x) \rightarrow \forall P(y))$ but can it help me with this statement?

  • $\begingroup$ Informally, there exists such $x$ because you can pick $x=y$. $\endgroup$ – Hagen von Eitzen May 24 at 6:13
  • $\begingroup$ @HagenvonEitzen And formally, you just do an existential introduction with $y$ as the witness, then you need to prove $P(y)\to P(y)$ which is pretty straightforward, $\to$ introduction, then by assumption. $\endgroup$ – Derek Elkins May 24 at 7:43
  • $\begingroup$ You might try assuming the negation, switching the quantifier, etc. and deriving the contradiction $P(y) \land \neg P(y).$ $\endgroup$ – Dan Christensen May 24 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.