Worked examples · Sheet 1

Negations of propositions with quantifiers

Theory used: Universal and existential quantifier Negation of quantifiers De Morgan's laws

Exercise 1

Write the negation of

\forall x \in R : x^{2} + 1 > 0

and determine which of the proposition and its negation is true.

\neg (\forall x \in R : x^{2} + 1 > 0) \equiv \exists x \in R : x^{2} + 1 \leq 0

x^{2} \geq 0 for every x \in R ⟹ x^{2} + 1 \geq 1 > 0

The original proposition is true.

The negation of a universal proposition is an existential proposition: the quantifier $\forall$ becomes $\exists$ and the predicate is negated, therefore the inequality $x^{2} + 1 > 0$ becomes $x^{2} + 1 \leq 0$ . The negation of “greater than” is “less than or equal to”, because a comparison has three possible cases and negating one leaves the other two.

To decide which of the two propositions is true, one starts from the fact that the square of every real number is greater than or equal to zero; adding $1$ to both sides gives $x^{2} + 1 \geq 1$ , therefore $x^{2} + 1 > 0$ for every real $x$ . The original proposition is thus true and its negation is false.

Exercise 2

Write the negation of

\exists x \in R : x^{2} + 4 x + 5 = 0

and determine which of the proposition and its negation is true.

\neg (\exists x \in R : x^{2} + 4 x + 5 = 0) \equiv \forall x \in R : x^{2} + 4 x + 5 \neq = 0

x^{2} + 4 x + 5 = x^{2} + 4 x + 4 + 1 = (x + 2)^{2} + 1 \geq 1

The negation is true.

Negation swaps $\exists$ with $\forall$ and negates the predicate, therefore the equality $x^{2} + 4 x + 5 = 0$ becomes the relation $x^{2} + 4 x + 5 \neq = 0$ .

To determine which proposition is true, one completes the square: the trinomial contains $x^{2} + 4 x + 4 = (x + 2)^{2}$ , therefore it can be rewritten as $(x + 2)^{2} + 1$ . Since $(x + 2)^{2} \geq 0$ for every real $x$ , the sum is greater than or equal to $1$ , hence the trinomial is different from zero for every $x$ . The equation therefore has no real solutions: the original proposition is false and its negation is true.

Exercise 3

Write the negation of

\forall x \in R \exists y \in R : x + y = 0 \land y \leq 0

and determine which of the proposition and its negation is true.

\neg (\forall x \in R \exists y \in R : x + y = 0 \land y \leq 0) \equiv \exists x \in R \forall y \in R : x + y \neq = 0 \lor y > 0

x = - 1 : x + y = 0 ⟺ y = 1, 1 > 0

The negation is true.

With two quantifiers the negation proceeds from the outside inward: $\forall x$ becomes $\exists x$ , $\exists y$ becomes $\forall y$ , and at the end the predicate is negated. The predicate is a conjunction, therefore by De Morgan’s laws its negation is the disjunction of the negations: $x + y \neq = 0$ or $y > 0$ .

The original proposition requires, for every $x$ , a $y$ that is both the opposite of $x$ and less than or equal to zero. The only $y$ with $x + y = 0$ is $y = - x$ , therefore for $x = - 1$ the only candidate is $y = 1$ , which is positive; for $x = - 1$ the two conditions are thus incompatible and the original proposition is false. Consequently the negation is true, and the direct check with $x = - 1$ confirms it: for every $y$ different from $1$ the sum $x + y$ is different from zero, while for $y = 1$ one has $y > 0$ , therefore every $y$ satisfies at least one of the two alternatives.