Back to the on-screen lesson ·
Pushing a negation inward one symbol at a time, so that every quantifier flips in order and the finished negation says what to go and find.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to negate any statement in this course by writing the negation sign in front of it and moving it inward one symbol at a time, flipping every quantifier in the order it appears, applying De Morgan to the connectives and destroying the arrow of an implication. You will also be able to read the finished negation as an instruction — produce one thing, or cope with an arbitrary one — which is what decides the shape of a refutation before any mathematics is written.
De Morgan's laws from lesson 3 move a negation through a bracket and flip the connective inside it. Quantifiers from lesson 4 are read left to right as a sequence of choices. This lesson is those two facts joined: a negation moves through a quantifier the same way it moves through a connective, and the two rules together let you negate anything in this course.
A statement is in negation normal form when the only negations left in it sit directly in front of an atom or an inequality — no negated bracket, no negated quantifier. Pushing inward is the process of getting there. A counterexample is what the negation of a universal statement asks you to produce.
Do not try to write the negation of a statement in one move. Write $\neg$ in front of the whole thing and then walk it inward, changing one symbol at each step, until it has nothing left to pass.
| What it meets | What happens |
|---|---|
| $\neg \forall x\, P$ | becomes $\exists x\, \neg P$ |
| $\neg \exists x\, P$ | becomes $\forall x\, \neg P$ |
| $\neg(P \wedge Q)$ | becomes $\neg P \vee \neg Q$ |
| $\neg(P \vee Q)$ | becomes $\neg P \wedge \neg Q$ |
| $\neg(P \Rightarrow Q)$ | becomes $P \wedge \neg Q$ |
| $\neg \neg P$ | becomes $P$ |
| $\neg(x \le a)$ | becomes $x > a$ |
Two things are worth saying about this table. The first is that every quantifier flips, in the order it appears: $\neg \forall \exists$ becomes $\exists \forall$, not $\exists \exists$ and not $\forall \exists$ with the inside negated. The second is that the implication line destroys the arrow. There is no arrow in $P \wedge \neg Q$, and a negation that leaves one behind is wrong.
Why this matters more than it looks: a proof by contradiction begins by negating the statement, and every line after that rests on the negation being right. Get it wrong and the argument is flawless and about something else. Unit 2's contradiction lesson does nothing this lesson has not already taught except spend it.
Another way: steps
To negate a statement:
Another way: example
$\neg[\forall \varepsilon > 0\, \exists N\, \forall n > N\, (|a_n - L| < \varepsilon)]$ becomes, one symbol at a time, $\exists \varepsilon > 0\, \forall N\, \exists n > N\, (|a_n - L| \ge \varepsilon)$: three flips, then the inequality. That is the definition of the sequence does not converge to $L$, and it is how a divergence proof starts.
The finished negation is not only a statement; it is a set of instructions.
$\exists x\, (\ldots)$ at the front says: produce one thing. That is why refuting a universal claim means finding a single counterexample and never means arguing in general.
$\forall x\, (\ldots)$ at the front says: cope with an arbitrary thing. That is why refuting an existence claim is real work, and why 'I could not find one' is not a refutation.
So the shape of the negation decides the shape of the work, before a single line of mathematics is written. It is worth negating a statement first even when you intend to prove it directly, because the negation tells you what you are up against.
Leaving the quantifiers alone. The negation of $\forall x\, P(x)$ is not $\forall x\, \neg P(x)$. That says every $x$ fails, which is far stronger than saying not every $x$ succeeds.
Flipping only the first quantifier. In a statement with three, all three flip.
Keeping the arrow. The negation of $P \Rightarrow Q$ is $P \wedge \neg Q$, with no arrow anywhere in it.
Negating a bound. In $\forall \varepsilon > 0$ the condition $\varepsilon > 0$ says which $\varepsilon$ are being quantified over; it is part of the domain and is not negated. The negation is $\exists \varepsilon > 0$, not $\exists \varepsilon \le 0$.
'Every student passed' negates to 'some student did not pass', not to 'every student failed'. The second is a different and much stronger statement, and reaching for it is the commonest error in the subject because ordinary English encourages it: not all and none are used loosely in speech and are separated by an entire quantifier here. The same trap is waiting in $\neg(P \wedge Q)$, which is at least one fails and not both fail.
'Every key opens some door': $\forall k\, \exists d\, O(k, d)$. Put a negation in front of the whole thing.
Symbols first, negation outermost.
Past the $\forall$: $\exists k\, \neg \exists d\, O(k, d)$. Past the $\exists$: $\exists k\, \forall d\, \neg O(k, d)$.
One quantifier at a time, each flipping.
In words: some key opens no door at all. Note that this is an existence claim, so refuting the original means producing one useless key — not saying something about keys in general.
The shape tells you what to go and find.
'Every prime above two is odd': $\forall n\, [(n \text{ prime} \wedge n > 2) \Rightarrow n \text{ odd}]$.
Write the hypothesis and conclusion out.
Negating: $\exists n\, \neg[(\ldots) \Rightarrow n \text{ odd}]$, and the negated implication is $(n \text{ prime} \wedge n > 2) \wedge n \text{ even}$.
The quantifier flips, then the arrow is destroyed.
So a counterexample would be an even prime above two. Trying to find one is how you see the claim is true — and the negation is what told you precisely what to look for.
The negation is a search specification.
It is a conjunction, so start with $\neg(C \wedge U)$ where $C$ is continuity and $U$ is unboundedness.
Name the halves before touching anything.
De Morgan gives $\neg C \vee \neg U$: the function is discontinuous, or it is bounded, or both.
The connective flips as the negation passes.
Not 'discontinuous and bounded'. A function that is continuous and bounded already fails the original claim, and the wrong negation would have missed it — which is exactly the sort of gap that leaves a proof by contradiction with nothing to contradict.
Negate $\forall x\, (P(x) \Rightarrow Q(x))$. Put the stages of the work in the order they are done.
Number the steps in order (write the number in the box):
What is the negation of $\exists n\, (n \text{ is prime and } n \text{ is even})$?
Let P stand for “the kettle is on” and Q for “the water is heating”. Complete the column for $\neg(P \Rightarrow Q)$, in the usual four-row order.
| P | Q | ~(P -> Q) |
|---|---|---|
P stands for “the switch is up” and Q for “the lamp is lit”. Rewrite $\neg(P \Leftrightarrow Q)$ so that no bracket has a negation in front of it.
Answer:
Match each definition to its negation, pushed all the way in.
| $\forall M\, \exists x\, (|f(x)| > M)$ — no bound survives | $\exists a\, \exists b\, (f(a) = f(b) \wedge a \ne b)$ — two inputs share an output | $\exists y\, \forall x\, (f(x) \ne y)$ — one target is never reached | $\exists \varepsilon\, \forall N\, \exists n > N\, (|a_n - L| \ge \varepsilon)$ — one tolerance the tail keeps escaping | |
|---|---|---|---|---|
| $f$ is bounded | ||||
| $f$ is injective | ||||
| $f$ is surjective | ||||
| $a_n \to L$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Negate $\forall x\, (P(x) \Rightarrow Q(x))$. Put the stages of the work in the order they are done.
Number the steps in order (write the number in the box):
You can negate a statement with several quantifiers and read the result back in words. Say in your own words why the negation of 'every student passed' is not 'every student failed', and what the leading quantifier of a negation tells you to go and do. Next: what a proof is obliged to do, and how a direct proof unfolds a definition.
10. Your turn: negate 'the function is continuous and unbounded', step 3