How can I prove $\neg \exists x.\phi \vdash \forall x . \neg \phi$?

194 Views Asked by At

I have checked some post in this web but in this particular situation I am finding trouble with the negation. I have tried supossing by hypothesis that $\forall x. \phi$ but the contradictions of this does not mean $\forall x . \neg \phi$. I am also not sure at all of some notation. Once I have supposed something by hypothesis and got a contradiction, how should I justify what I have proved by contradiction in next line?

Thank you for your attention.

1

There are 1 best solutions below

0
On

I am assuming you are talking about derivability in the natural deduction calculus.

Since the conclusion is of the form $\forall x. \neg \phi$, the last step will likely be an application of $(\forall I$). Then what must your second-to-last line be?
To get to that line, you need to provoke a contradiction not to the conclusion of the sequent, but to the premise, by deriving in a subproof $\exists x. \phi$. Which assumption do you think is suitable to get such a contradicting statement?
Then try to meet in the middle by connecting the contradiction with the second-to-last line while discharging the assumption of the contradiction-provoking subproof.


Once I have supposed something by hypothesis and got a contradiction, how should I justify what I have proved by contradiction in next line?

That depends on what your conclusion is. There are two kinds of what is commonly called "proof by contradiction":

  1. Assume $A$, derive a contradiction, conclude $\neg A$.This is an instance of the rule $(\neg I$), negation introduction.

  2. Asssume $\neg A$, derive a contradiction, conclude $A$. This is an instance of the rule $(\bot)$ aka $(RAA)$, reductio ad absurdum. This kind is the "real" proof by contradiction.

In both cases, you are allowed to discharge the hypothesis by leaving the subproof when transitioning from the contradiction to the conclusion.

So think about what kind of conclusion you need after the contradiction, a positive or a negative one, and choose your hypothesis and contradiction rule accordingly.