1.3 Quantifiers and negation

Let $D=\{1,2\}$ and let $P(x,y)$ mean $x=y$. Under the assignment $x=1$, $y=2$, the open formula $P(x,y)$ is false. In $\forall x\in D\,P(x,y)$, $x$ is bound but $y$ is free. Assigning $y=1$ makes this formula false because $x=2$ fails.

By contrast, $\forall x\in D\,\exists y\in D\,P(x,y)$ is a true closed sentence: for each $x$, choose $y=x$. The quantifiers bind the variables without changing the predicate.

Keep $D=\{1,2\}$, but take $\mathbb Z$ as the ambient domain for assignments. In $\forall x\in D\,(x=y)$, the bound on $x$ does not restrict the free variable $y$: $y=3$ is an allowed assignment even though it is outside $D$.

The formula $\forall x\in\mathbb Z\,(x=y)$ is also open because $y$ is free, yet it is false for every integer assignment to $y$: the choice $x=y+1$ is a counterexample. Being open is a syntactic property; it does not assert that changing the assignment must change the truth value.

Fix a natural number $n\ge 2$ throughout. The lower bound is essential because 1 is not prime. A standard definition says that every natural divisor of $n$ is trivial:

Negate in three steps. First flip the quantifier. Next negate the implication, which keeps its hypothesis and negates its conclusion. Finally apply De Morgan's law:

In English, there is a natural number $d$ which divides $n$ and is neither 1 nor $n$. That is a concrete non-trivial divisor, exactly the witness needed to show that $n$ is not prime. The assumption $n\ge2$ is a hypothesis of this example, not a condition that should disappear during negation.

Let $Student(x)$ mean “$x$ is a student,” $Enrolls(x)$ mean “$x$ enrolls,” and $Prereq(x)$ mean “$x$ satisfies the prerequisite.” Consider the statement

The negation is

Its witness is a student who enrolls and does not satisfy the prerequisite. A student who does not enroll is not a counterexample, because the original implication makes no claim about that person. This is why replacing the implication by a conjunction, or dropping the hypothesis while negating, gives the wrong condition.

The two bounded forms have different connectives. For a set $S$,

Negating $\forall n\in\mathbb Z\,(n\gt 0\to n^2\gt n)$ gives

The witness $n=1$ satisfies both requirements. The integer 0 satisfies $0^2\le0$ but fails $n\gt 0$, so it cannot witness the negation. This example shows why the antecedent of an implication becomes part of a counterexample.

Over the natural numbers, compare

with

The first is true: after an arbitrary $x$ is presented, choose $y=x+1$. The choice depends on $x$. The second is false: a proposed fixed natural number $y$ is defeated by the allowed choice $x=y$, for which $x\lt y$ is false. A proof of the first statement therefore cannot be reused as a proof of the second; it constructs a function of the input rather than one uniform witness.

The finite example makes the same point without an unbounded domain. Let $X=\{1,2\}$ and $P(x,y)$ mean $x=y$. Then

is true by choosing $y=x$. But

is false: $y=1$ fails at $x=2$, while $y=2$ fails at $x=1$.

Over a fixed domain, the following identities

follow from the proof obligations. For the first, take an arbitrary $x$: the conjunction is true exactly when both predicates hold for that same element. For the second, a witness for the disjunction lies in one case, and a witness for either case works in reverse. Same-type blocks also commute, but their meanings differ:

The universal statement checks every ordered pair; the existential statement asks for one ordered pair. Neither fact licenses swapping mixed quantifiers. For the crossed failure on $\{1,2\}$, let $P(x)$ mean $x=1$ and $Q(x)$ mean $x=2$. Then $\forall x(P(x)\lor Q(x))$ is true while $(\forall xP(x))\lor(\forall xQ(x))$ is false. Likewise, $\exists x(P(x)\land Q(x))$ is false while $(\exists xP(x))\land(\exists xQ(x))$ is true.

The outside-in rules and De Morgan's law give

The final sentence says that every object fails at least one of the two properties; it does not say that every object fails both.

The formula

says that one value $y$ is at least as large as every domain value $x$. Its truth depends on the stated domain, so report the domain with the translation.

Let $People$ and $Books$ be the sets of people and books. The two statements are

and

The first says every book has a borrower; the second says one person borrows all books. With two books, separate borrowers can borrow one each, neither both, so the first is true while the second is false.

“Everyone is reading at least two books” requires distinct book witnesses:

Let the domain be all students at a university. If $S(x)$ means “$x$ studies mathematics” and $P(x)$ means “$x$ passed the exam,” consider these three statements, respectively: every mathematics student passed; at least one student passed; and at least one mathematics student did not pass. Their translations are

The domain supplies “student”; the predicates add the requested properties.

Assume the domain contains students, professors, courses, exams, and questions, and use predicates to restrict each kind of object. The following sentences illustrate three different dependencies.

“Every student has taken at least one mathematics course” becomes

“There is a professor who teaches every course in the department” becomes

“Every exam has a question that every student finds difficult” becomes

The difficult question may depend on the exam, but it must work for every student for that exam. Moving $\exists q$ before $\forall e$ claims one question works for all exams, a stronger statement.

Consider three errors that change the intended claim. The formula

does not define primality. Keep the intended hypothesis $n\ge2$. The witness $d=n+1$ is natural and does not divide $n$, so the implication is true vacuously; the existential formula is satisfied without checking all divisors. (For $n=0$, do not use this particular witness: $1$ divides $0$.) The prime definition requires $\forall d$.

In fact, $d=1$ witnesses this existential formula for every $n$, since both $1\mid n$ and $d=1$ hold. The $d=n+1$ choice highlights the separate vacuous truth under the intended $n\ge2$ hypothesis.

The formula $\forall x\,\exists y\,Attends(x,y)$ says that each $x$ attends at least one $y$, with the types and dependency left unclear. If the intended statement is that every lecture has a student attending it, write

Finally, $\forall a\,\exists d\,SubmittedBefore(a,d)$ allows the deadline to depend on the assignment. A single deadline before which all assignments are submitted is

Each correction makes the dependency order explicit.

Bound variable names are local labels. If $z$ does not occur anywhere in the body of $\forall x\,P(x)$, replacing the occurrences controlled by that outer quantifier gives the equivalent formula $\forall z\,P(z)$. Occurrences bound by an inner quantifier are left alone. The same rule applies to $\exists$.

Global absence of the replacement letter from the body is a sufficient safeguard, not a necessary rule. What is necessary is that the renaming avoid capturing an occurrence whose binding or free status changes. On $X=\{1,2\}$,

is true because each element has the other element as a witness. Replacing the outer $x$ by the already-used $y$ produces

which is false: the inner quantifier captures both occurrences. A genuinely fresh $z$ gives $\forall z\in X\,\exists y\in X\,(z\ne y)$ and preserves the truth conditions.

“There exists a unique $x\in D$ satisfying $P(x)$” means both existence and at-most-one:

To prove it, first exhibit one witness $x$ and verify $P(x)$. Then let $y$ be an arbitrary element of $D$ satisfying $P(y)$ and prove $y=x$. To disprove uniqueness, two distinct witnesses are enough. Over $\mathbb Z$, $x^2=1$ has witnesses $1$ and $-1$, so existence holds but uniqueness fails. Over $\mathbb Z$, $x^2=0$ has the single witness $0$: substitution verifies existence, and $y^2=0$ implies $y=0$. The statement “my classmate has exactly one friend” uses the same pattern: $\exists!x\,Friend(o,x)$ abbreviates existence plus at-most-one.

With people as the domain,

says every person has a distinct friend; the distinctness condition is inside the existential scope.

With people as the domain and $Student(y)$ identifying the students,

says one person is older than every student. It does not require $x$ to be a student unless that predicate is added.