Back to the on-screen lesson ·
The two equivalences that take a negation past a quantifier, what happens to the connective inside, and why the quantifiers flip without ever changing places.
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 write the negation of a quantified formula, push a negation all the way in one move at a time, pair each formula with its negation, tell a genuine negation from a formula that merely denies the inside, evaluate a formula and its negation in a structure, and negate a formula whose quantifiers are mixed.
You can read a quantified formula and evaluate it in a structure, and you can push a propositional negation inward with De Morgan. This lesson adds the two rules that take a negation past a quantifier.
To push a negation inward is to rewrite a formula so that every negation sign stands on an atomic formula. A quantifier flips when a negation passes it: $\forall$ becomes $\exists$ and $\exists$ becomes $\forall$. A counterexample to a universal claim is an object witnessing its negation.
Two equivalences do the work, and they are the quantifier form of De Morgan: $\neg \forall x\, \phi \equiv \exists x\, \neg \phi$ and $\neg \exists x\, \phi \equiv \forall x\, \neg \phi$. Over a finite domain the reason is visible — a universal is a conjunction of instances and an existential a disjunction, and De Morgan turns each into the other — and over an infinite domain the equivalence is taken as the definition of what the quantifiers demand. Applying them repeatedly pushes a negation all the way in: each quantifier it passes flips, none of them moves, and the negation left on the inner formula is then pushed through the connectives as before. The pattern that matters most in practice is $\neg \forall x\,(Fx \to Gx) \equiv \exists x\,(Fx \wedge \neg Gx)$: denying that every $F$ is a $G$ is producing an $F$ that is not one, and a conditional has become a conjunction.
Another way: steps
Another way: example
$\neg \exists x\,(Fx \wedge \neg Gx)$ becomes $\forall x\, \neg(Fx \wedge \neg Gx)$, then $\forall x\,(\neg Fx \vee \neg \neg Gx)$, then $\forall x\,(Fx \to Gx)$ — denying a counterexample is asserting the universal.
The first error is negating the inside and leaving the quantifier as it was: $\neg \forall x\, Fx$ is not $\forall x\, \neg Fx$, and in a structure where some objects are $F$ and some are not, both of those are false — which no formula and its negation can be. The second is keeping the conditional when negating a universal about a kind; the negation asserts an $F$ and denies a $G$, so it is a conjunction. The third is reordering mixed quantifiers while flipping them, which is a different operation and not one negation performs.
Every prime is odd is $\forall x\,(Px \to Ox)$. Deny it.
Flip the quantifier first.
$\exists x\, \neg(Px \to Ox)$; the negation of a conditional asserts the antecedent and denies the consequent.
Now push through the arrow.
$\exists x\,(Px \wedge \neg Ox)$ — there is an even prime, which is exactly what a counterexample would be.
A conjunction, not a conditional.
$\neg \exists x \forall y\, Rxy$: the negation passes $\exists x$, which flips.
Outside in.
$\forall x\, \neg \forall y\, Rxy$, and the second quantifier flips too.
One at a time.
$\forall x \exists y\, \neg Rxy$. Both flipped; neither moved.
The order is untouched.
The formula is $\exists x\,(Sx \wedge \forall y\,(Py \to Axy))$, so the outer $\exists$ flips.
Pushing on gives $\forall x\,(Sx \to \exists y\,(Py \wedge \neg Axy))$: every student failed some paper.
Which formula is equivalent to the negation of $\forall x\,(Fx \to Gx)$?
These four formulas are a chain of equivalences, each obtained from the one before by a single move, starting from $\neg \forall x\,(Fx \to Gx)$. Put them in order.
Number the steps in order (write the number in the box):
Match each formula to its negation.
| $\exists x\, \neg Fx$ | $\forall x\, \neg Fx$ | $\exists x \forall y\, \neg Rxy$ | $\forall x \exists y\, \neg Rxy$ | |
|---|---|---|---|---|
| $\forall x\, Fx$ | ||||
| $\exists x\, Fx$ | ||||
| $\forall x \exists y\, Rxy$ | ||||
| $\exists x \forall y\, Rxy$ |
Mark every pair below whose two formulas are negations of each other.
This task has no paper form; do it on a device.
The domain is $\{a, b, c\}$. $F$ holds of all three objects and $G$ holds of $a$ alone. For each formula, give its value and the value of its negation.
| The formula | Its negation | |
|---|---|---|
| $\forall x\, Fx$ | ||
| $\exists x\, Fx$ | ||
| $\forall x\,(Fx \to Gx)$ |
What is the negation of $\forall x \exists y\, Rxy$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A formula begins with $2$ quantifiers, one after another, in front of a formula containing no quantifiers at all. Its negation is pushed all the way in until the negation sign stands on that inner formula. Complete the sentence.
Exactly m quantifiers change from one kind to the other.
You can negate a quantified statement and push the negation onto the atomic formulas. Say in your own words why denying that every F is a G produces a conjunction rather than a conditional.
8. Your turn: negate *some student passed every paper*, step 2