Propositional functions and quantifiers – Introduction to Logic (Senior 4 Mathematics) | Ganzaa

Introduction to Logic

Lessons

Senior 4 · Mathematics

Introduction to Logic

5 lessons

Lesson 4 of 5

Propositional functions and quantifiers

25 min

From open sentences to statements

" $x + 2 = 5$ " is not a statement: its truth depends on $x$ . Yet two small phrases turn it into statements at once. "There is a real number $x$ such that $x + 2 = 5$ " is true (take $x = 3$ ). "For every real number $x$ , $x + 2 = 5$ " is false (take $x = 0$ ). The phrases "for every" and "there is" are quantifiers, and almost every definition and theorem in mathematics uses them. Negating them correctly is one of the most useful skills in this unit.

Definition

Propositional function (predicate): a sentence $P (x)$ containing a variable $x$ that becomes a statement whenever $x$ is replaced by an element of a given set $D$ , the domain (universe of discourse). A predicate may have several variables, such as $Q (x, y)$ .

Truth set: $\{x \in D : P(x) \text{ is true}\}$ .

Example: on $D = \mathbb{R}$ , let $P (x)$ : " $x^{2} - 5 x + 6 = 0$ ". Then $P (2)$ is true, $P (4)$ is false ( $16 - 20 + 6 = 2$ ), and the truth set is ${2, 3}$ .

Definition

Universal quantifier $\forall$ , "for all": the statement $\forall x \in D,\ P(x)$ is true when $P (x)$ is true for every $x$ in $D$ , that is, when the truth set is all of $D$ .

Existential quantifier $\exists$ , "there exists": the statement $\exists x \in D,\ P(x)$ is true when $P (x)$ is true for at least one $x$ in $D$ , that is, when the truth set is not empty. $\exists!$ means "there exists exactly one".

Example: $\forall x \in \mathbb{R},\ x^2 \ge 0$ is true; $\exists x \in \mathbb{R},\ x^2 = -1$ is false.

Reading a quantified statement from its truth set

Take $P (x)$ : " $x^2 \lt 4$ " on $D = \mathbb{R}$ . Its truth set is the interval $] - 2, 2 [$ .

The truth set is not empty, so $\exists x \in \mathbb{R},\ x^2 \lt 4$ is true (for example $x = 0$ ). It is not the whole of $\mathbb{R}$ , so $\forall x \in \mathbb{R},\ x^2 \lt 4$ is false, and $x = 3$ is a counterexample. Change the domain to $D = \{-1, 0, 1\}$ and the universal statement becomes true: the domain is part of the statement.

Worked example 1: truth values

Decide whether each statement is true or false. (a) $\forall n \in \mathbb{N},\ n^2 \ge n$ (b) $\forall x \in \mathbb{R},\ x^2 \ge x$ (c) $\exists x \in \mathbb{Z},\ 2x = 5$ (d) $\exists x \in \mathbb{Q},\ 2x = 5$ .

Solution

True: $n^2 - n = n(n - 1) \ge 0$ for every natural number $n$ (both factors are $\ge 0$ when $n \ge 1$ , and $n = 0$ gives 0).
False: $x = \frac{1}{2}$ gives $\frac{1}{4} \ge \frac{1}{2}$ , which is false. (Every $x$ with $0 \lt x \lt 1$ is a counterexample.)
False: $2 x = 5$ forces $x = 2.5 \notin \mathbb{Z}$ .
True: $x = \frac{5}{2} \in \mathbb{Q}$ .

Important

Negating quantifiers

\neg\big(\forall x \in D,\ P(x)\big) \equiv \exists x \in D,\ \neg P(x), \qquad \neg\big(\exists x \in D,\ P(x)\big) \equiv \forall x \in D,\ \neg P(x).

Why: "it is not true that every $x$ works" means "some $x$ fails"; "there is no $x$ that works" means "every $x$ fails". The quantifier flips, and the negation moves inside. On a finite domain ${a, b}$ this is just De Morgan's law: $\neg(P(a) \wedge P(b)) \equiv \neg P(a) \vee \neg P(b)$ .

Worked example 2: negating in words and symbols

"All the students in this class passed." Negation: "At least one student in this class did not pass." (Not "No student passed".)
"Some prime numbers are even." Negation: "No prime number is even", that is, "every prime number is odd". (The original is true, since 2 is prime, so this negation is false.)
$\forall x \in \mathbb{R},\ x^2 + 1 \gt 0$ . Negation: $\exists x \in \mathbb{R},\ x^2 + 1 \le 0$ .
$\exists n \in \mathbb{N},\ n \text{ is prime and } n \gt 100$ . Negation: $\forall n \in \mathbb{N},\ n \text{ is not prime or } n \le 100$ (De Morgan inside the quantifier).

Worked example 3: two quantifiers, and why order matters

Decide the truth value of (a) $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x + y = 0$ (b) $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ x + y = 0$ . Then negate (a).

Solution

True. Whatever $x$ is chosen, $y = - x$ works: each $x$ has its own $y$ .
False. This claims one single $y$ that works for every $x$ . From $x = 0$ we would need $y = 0$ , but then $x = 1$ gives $1 + 0 \ne 0$ .

Negation of (a): flip each quantifier and negate the predicate: $\exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ x + y \ne 0$ . (It is false, as it must be.)

Warning

"Not all" is not "none". The negation of "all the bridges are safe" is "some bridge is not safe", which one unsafe bridge makes true. Writing "no bridge is safe" claims far too much. Likewise the negation of "some $x$ works" is "no $x$ works", not "some $x$ does not work".

Tip

How to settle a quantified statement: to prove "for all", give an argument that works for an arbitrary $x$ ; to disprove it, one counterexample is enough. To prove "there exists", one example is enough; to disprove it, show that every $x$ fails.

Dr. Trefor Bazett: Negating Universal and Existential Quantifiers. Watch for how 'for all' becomes 'there exists' (and the other way round) while the negation moves inside.

✦

Practice

State the domain whenever you use a quantifier.

On $\mathbb{R}$ , $P (x)$ : " $x^{2} - 4 x + 3 = 0$ ". Find the truth values of $P (1)$ and $P (2)$ , and the truth set.
True or false? (a) $\forall x \in \mathbb{R},\ x^2 + 1 \gt 0$ (b) $\exists x \in \mathbb{N},\ x + 3 = 1$ (c) $\forall x \in \mathbb{R},\ \sqrt{x^2} = x$ (d) $\exists x \in \mathbb{Z},\ x^2 = 2$ .
Write in symbols: (a) The square of every real number is non-negative. (b) Some integer is equal to its own square.
Negate, in symbols: (a) $\forall x \in \mathbb{R},\ x^2 \ge x$ (b) $\exists x \in \mathbb{R},\ x^2 = x + 1$ .
Negate in words: "Every student in S4 has a calculator."
Decide the truth value and write the negation: $\exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ xy = y$ .
True or false: $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y^2 = x$ ? Justify.
Find every counterexample to $\forall x \in \mathbb{R},\ x^2 \ge x$ .

Show answersHide answers

$P (1)$ : $1 - 4 + 3 = 0$ , true. $P (2)$ : $4 - 8 + 3 = - 1$ , false. Truth set ${1, 3}$ .
(a) T (b) F ( $x = -2 \notin \mathbb{N}$ ) (c) F ( $x = - 1$ ) (d) F ( $\sqrt{2} \notin \mathbb{Z}$ ).
(a) $\forall x \in \mathbb{R},\ x^2 \ge 0$ (b) $\exists x \in \mathbb{Z},\ x^2 = x$ .
(a) $\exists x \in \mathbb{R},\ x^2 \lt x$ (b) $\forall x \in \mathbb{R},\ x^2 \ne x + 1$ .
"At least one student in S4 does not have a calculator."
True, with $x = 1$ . Negation: $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ xy \ne y$ .
False: for $x = - 1$ no real $y$ has $y^{2} = - 1$ .
$x^2 \lt x \iff x(x - 1) \lt 0 \iff 0 \lt x \lt 1$ : every $x$ in $] 0, 1 [$ .

Quick check

What is the negation of 'All the students passed'?

Key points

A predicate $P (x)$ becomes a statement when $x$ is given a value from the domain, or when it is quantified.
$\forall x,\ P(x)$ : the truth set is the whole domain; $\exists x,\ P(x)$ : the truth set is not empty.
$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ and $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$ .
The order of different quantifiers matters.

Sources and credits

Written by Ganzaa: the explanations, the diagram, the worked examples, the practice items and the questions.
Video: Negating Universal and Existential Quantifiers, Dr. Trefor Bazett, embedded from YouTube.

1From open sentences to statements

2Reading a quantified statement from its truth set

From open sentences to statements

Reading a quantified statement from its truth set