Negation of some quantifiers implies negation of all quantifiers

70 Views Asked by At

Suppose there exists a list of quantifiers and a predicate statement, for example

$\begin{align*} \forall\epsilon>0\exists n_0\in\mathbb{N}\forall x\in\mathbb{A}\forall n\geq n_0 \implies P(\epsilon,x,n) \end{align*}$

Does it suffice to flip only 1 quantifier and that predicate statement to prove otherwise.

So for example if I am able to offer an example which satisfies the following

$\begin{align*} \forall\epsilon>0\exists n_0\in\mathbb{N}\exists x\in\mathbb{A}\forall n\geq n_0 \implies \lnot P(\epsilon,x,n) \end{align*}$

Does it mean that the original statement is false?

1

There are 1 best solutions below

0
On BEST ANSWER

If you have got a formula with nested quantifiers $\textbf{Q}_1x_1\dots\textbf{Q}_nx_nA,\:\textbf{Q}_i\in\{\exists,\forall\}$ then the negation looks like $\overline{\textbf{Q}_1}x_1\dots\overline{\textbf{Q}_n}x_n\neg A$ where $\overline{\textbf{Q}_i}\in\{\exists,\forall\}\setminus\{\textbf{Q}_i\}$ (you can easily prove this using induction on $n$). In your example this would be $$\exists\epsilon>0\forall n_0\in\mathbb{N}\exists x\in\mathbb{A}\exists n\ge n_0:\neg P(\epsilon,x,n).$$

Your scheme is not valid: you've found a counterexample only for some particular $n_0$ when you need to show that is exists for any of $n_0$.

However, if all the quantifiers standing before a replaced one are $\forall$ then your reasoning is correct. But in the most cases you'll get a false statement or, anyway, it would be much harder to prove.