Negating Nested Quantifiers: Find a Whole Failed Row

Negate the whole claim, not just one relation cell

To deny “every x has some y,” find an x with no y. The negation of ∀x∃yRxy is ∃x∀y¬Rxy. Its witness is an object whose entire relation row is false. One false cell only says that a particular y does not work for a particular x.

The examples use a nonempty domain and ordinary two-valued classical first-order logic. They contain no missing observations or third truth value. All listed relation cells are fully specified, deliberately constructed classroom data.

Definitions and rules: [1] [2].

Move negation across one quantifier at a time

¬∀x∃yRxy
≡ ∃x¬∃yRxy
≡ ∃x∀y¬Rxy

First, “not every x satisfies the inner claim” becomes “some x does not satisfy it.” Keep the whole inner formula ∃yRxy intact during that first step. Second, “there is no y related to that x” becomes “every y is not related to that x.” Both variable names and the order of relation places stay fixed.

Do not stop at ∃x∃y¬Rxy. That formula asks for one false pair, which is much easier to satisfy. Also do not change the last formula to ∀x∀y¬Rxy: that denies every pair for every x, rather than finding one failed x.

Definitions and rules: [2].

Compare a missing cell with a whole failed row

On a narrow screen, scroll inside this table. Keyboard users can focus the region and use the arrow keys.

Download the complete true/false relation records

In the first model, R(A,B) is false, so ∃x∃y¬Rxy is true. Nevertheless, A has witness A and B has witness B. The original ∀x∃yRxy is true and its negation is false.

In the second model, take x=B. Both possible values of y fail. Hence ∀y¬R(B,y) holds for that B, and ∃x∀y¬Rxy is true. The original claim is false because B has no witness.

On a narrow screen, scroll inside this table. Keyboard users can focus the region and use the arrow keys.

The equivalence gives matching truth values for the middle two columns in every interpretation. This table illustrates it; the quantifier conversion rules supply the general reason.

Locate a counterexample without mixing x and y

Write down which variable each quantifier controls. For the negation, the outer ∃x lets you select one failed object. After selecting it, ∀y requires you to test every possible partner for that same x. You cannot change x between cells and combine failures from different rows.

For a finite domain, a checklist works: choose a candidate row, inspect every column, reject the candidate immediately if a true cell appears, and accept it only after all cells are false. If you do not know the full domain or some relation facts, report that the evaluation is incomplete. Unknown is a limit on your information, not the false truth value in these models.

For an infinite domain, a finite row inspection is unavailable. You need an argument covering every y, rather than an arbitrary sample. The logical form stays the same; the method for establishing its truth may differ.

Check related quantified denials

¬∃x∀yRxy ≡ ∀x∃y¬Rxy
¬∀xPx ≡ ∃x¬Px
¬∃xPx ≡ ∀x¬Px

To deny one shared y for every x, every proposed shared y must fail somewhere. If the formula is written ∃y∀xRxy, its negation is ∀y∃x¬Rxy: for each y, find an x that rejects it. The names matter because they identify the relation places; the same conversion rule applies.

“Not all are P” and “none are P” are different. With two objects and P true only of A, not all are P is true, while none are P is false. Keep the original sentence, its scope and its domain together instead of translating “not” by instinct.

Try three negation checks

Use two objects A and B, and ordinary true/false cells.