Relationship between universal quantifier and existential quantification. Is it always equivalent by just moving the negation symbol?

Question

Say C: set of courses

P(x,y): 'x is a prerequisite for course y'

Statement:

No course is a prerequisite for itself.

is same as:

For all x in C, ¬P(x,x)

But is this correct?

There doesn't exist x in C, P(x,x)

And if this is correct, is it true for all cases that moving the ¬ to flip between a universal quantification to existential one will be equivalent?

Answer 1

This works, it's basically $$\begin{align*} \forall x : \neg\Phi(x) & \Longleftrightarrow \nexists x : \Phi(x) \\ \forall x : \Psi(x) & \Longleftrightarrow \exists x : \neg\Psi(x) \end{align*}$$

Answer 2

Yes, there is equivalence between $\lnot (\forall x B)$ and $\exists x (\lnot B)$. You should convince yourself that this makes sense.

Answer 3

$$\forall x: p(x)\iff \lnot \exists x :\lnot p(x)$$ $$\exists x: p(x)\iff \lnot \forall x :\lnot p(x)$$

Given one, one may prove the other. We can see the first one is true, because if something is true for all things, there can't be anything for which it is false. Also if there is nothing for which it is false, it must be true for all values. A proof from first principles can be found at http://us.metamath.org/mpegif/alex.html.

Answer 4

Yes, that’s correct: $\forall x(\neg\varphi(x))$ and $\neg\exists x(\varphi(x))$ are logically equivalent. Similarly, $\exists x(\neg\varphi(x))$ and $\neg\forall x(\varphi(x))$ are logically equivalent.

These are essentially infinitary versions of De Morgan’s laws: the first equivalence corresponds to $$(\neg\varphi\land\neg\psi)\leftrightarrow\neg(\varphi\lor\psi)\;,$$ the second to $$(\neg\varphi\lor\neg\psi)\leftrightarrow\neg(\varphi\land\psi)\;.$$