Lesson 4

Often, multiple quantifiers are used in a statement. For example, Goldbach's conjecture can be formally written as: \[\forall n \in \mathbb{E}\ \exists p \in \mathbb{P}\ \exists q \in \mathbb{P}\colon n=p+q \ ,\] where \(\mathbb{E}=\{t \in \mathbb{Z}_{>2}\colon 2 \mid t\}\) is the set of even numbers greater than two. The order of the quantifiers in such statements is important. For example, the statement \[\exists p \in \mathbb{P}\ \exists q \in \mathbb{P}\ \forall n \in \mathbb{E}\colon n=p+q\] is certainly not true: it claims that there exist two prime numbers such that any even number is the sum of them.

To write the negation of a statement with quantifiers, one can use the following De Morgan's laws for quantified formulas: \[\begin{align*}\neg(\forall x\ P(x))&\equiv (\exists x\ \neg P(x))\\ \neg(\exists x\ P(x))&\equiv (\forall x\ \neg P(x))\end{align*}\] The rules are natural. In what case is the statement \((\forall x\ P(x))\) false? Exactly when there exists an \(x\) for which \(P(x)\) is false. In the case when the set from which the quantifier is taken is finite, these laws are equivalent to the usual De Morgan's laws.

There is also a “mechanical” interpretation of this law: when negation passes through a quantifier, the type of quantifier changes to the opposite one. Let's give an example of such negation being pushed inward: \[\neg(\forall x\ \exists y\colon P(x,y)) \equiv \exists x\colon \neg(\exists y \colon P(x,y)) \equiv \exists x\ \forall y \colon \neg P(x,y) \ .\]