Every definition in the rest of this course is a chain of quantifiers, and half the work is saying precisely what it would mean for one to fail. Denying such a statement is mechanical rather than creative: walk along the chain from the outside in, turn each "for every" into "there is" and each "there is" into "for every", and finally deny the sentence at the end. Nothing is reordered, and nothing is dropped.

To deny "every door on this corridor is locked" you do not have to say anything about most doors. You have to produce one that is open. To deny "some door is open" you must instead speak about all of them: every one is locked. Denial trades a claim about all for a claim about one, and back again.

The claim "$\forall a\in A,\ a\in B$" is denied by the single point $x$, which lies in $A$ and not in $B$. The denial is $\exists a\in A,\ a\notin B$ — a statement about one element, not about most of them.

Negation passes through a chain of quantifiers from the outside in, swapping each one, until it reaches the sentence at the end, which it denies. A bound such as $\varepsilon>0$ or $x\in A$ is part of the quantifier and is carried along unchanged: the denial of "for every $\varepsilon>0$" is "there is an $\varepsilon>0$", never "there is an ".

• $\neg\forall x\,P(x)\iff\exists x\,\neg P(x)$ and $\neg\exists x\,P(x)\iff\forall x\,\neg P(x)$.

Apply the two one-quantifier rules in turn, from the outside in. The outer quantifier is universal, so denying it produces an existential and pushes the negation onto what follows; what follows is existential, so denying that produces a universal and pushes the negation one step further, onto the sentence itself. Nothing was reordered: the negation simply travelled along the chain.

Start from the denial of the whole statement.

Deny the outer universal: it becomes existential, and the negation moves inside.

Deny the inner existential: it becomes universal, and the negation reaches the sentence.

Read the result: some x defeats every candidate y.

The negation travels along the chain from the outside. Each quantifier flips; the order never changes.

Injectivity is $\forall x\,\forall y\,\big(f(x)=f(y)\implies x=y\big)$. Its denial is what a counterexample must look like.

• Negation walks the chain from the outside in, flipping each quantifier and denying the final sentence.
• The order of the quantifiers never changes, and the bound on each is carried along unchanged.
• $\neg(P\implies Q)$ is $P\land\neg Q$; $\neg(P\land Q)$ is .

Great work! You now know how to:

• Negate a chain of quantifiers by flipping each in turn
• Keep the order and the bounds of the quantifiers unchanged
• Deny an implication and a conjunction correctly
• Read a denial as a description of the counterexample to look for