Quantifiers and negating propositions

Many mathematical statements concern a whole collection of objects, rather than a single isolated element. For this, we use two fundamental quantifiers.

The universal quantifier, written $\forall$, asserts that a property holds for every element of a set, without any exception. The existential quantifier, written $\exists$, asserts that at least one element satisfies the property: it requires neither uniqueness nor universality.

The order of quantifiers matters enormously, and it is a frequent source of errors. The statement $\forall x,\; \exists y,\; P(x, y)$ does not mean the same thing as $\exists y,\; \forall x,\; P(x, y)$: in the first case, $y$ may depend on $x$; in the second, one and the same $y$ must work for all $x$.

The negation of a quantified proposition obeys a precise rule, to be memorized perfectly:

$$\neg\bigl(\forall x,\; P(x)\bigr) \iff \exists x,\; \neg P(x)$$

$$\neg\bigl(\exists x,\; P(x)\bigr) \iff \forall x,\; \neg P(x)$$

In other words, a single counterexample is enough to refute a universal statement entirely. Symmetrically, to show that no element satisfies a property, you must refute it for each of them, without exception.

This rule also applies in cascade to multiple quantifiers: we flip them one by one, in order of appearance, negating at each step the property that immediately follows:

$$\neg\bigl(\forall x,\; \exists y,\; P(x,y)\bigr) \iff \exists x,\; \neg\bigl(\exists y,\; P(x,y)\bigr) \iff \exists x,\; \forall y,\; \neg P(x,y)$$

This is an essential skill for writing rigorous proofs, especially when it comes to proving that a property is false: you then work out precisely the negated proposition, and construct or exhibit the object that satisfies it.