Lessons 4–5 · 2 lessons · M. A. Mirzaahmedov, Sh. N. Ismailov, A. Q. Amanov (algebra and analysis), B. Q. Haydarov (geometry). Mathematics Grade 10, Parts 1 and 2, 1st edition. EXTREMUM PRESS, Tashkent, 2017
5
Predicates and quantifiers
Textbook, Part 1: pp. 29–32
GoalRecognise a predicate; check the truth of statements with ∀ and ∃ and form their negations.
New words
predicate · predikatuniversal quantifier ∀ · umumiylik kvantori ∀existential quantifier ∃ · mavjudlik kvantori ∃counterexample · qarshi misol
Explanation
A sentence with a variable that becomes a statement when a concrete value is substituted is called a predicate, for example P(x): x² > x; with several variables we write P(x, y). The statement ∀xP(x) means “for all x, P(x)” and ∃xP(x) means “there is an x with P(x)”; ∀ is the universal and ∃ the existential quantifier. To refute ∀xP(x) it is enough to find one x for which P(x) is false, a counterexample; to prove ∃xP(x) it is enough to show one suitable x. The negation laws are ¬∀xP(x) ≡ ∃x¬P(x) and ¬∃xP(x) ≡ ∀x¬P(x). With two variables the order of quantifiers matters: ∀x∃yP(x, y) and ∃y∀xP(x, y) are not equivalent.
Worked examples
The predicate P(x): x² − 6x + 8 = 0 on the set {1, 2, 3, 4}: it is true for x = 2 and x = 4 (4 − 12 + 8 = 0 and 16 − 24 + 8 = 0) and false for x = 1 (1 − 6 + 8 = 3). So ∃xP(x) is true, ∀xP(x) is false, and x = 1 is a counterexample.
The negation of “every student in the class likes football” by ¬∀xP(x) ≡ ∃x¬P(x) is “there is a student who does not like football”. Two variables: ∀x∈R ∃y∈R, y > x is true (take y = x + 1), but ∃y∈R ∀x∈R, y > x is false (it fails for x = y, because there is no largest number).
Class activity
Classroom game “All … , some …”: one group states a sentence beginning with ∀ or ∃ (“every student in the class owns a bicycle”), the others look for a counterexample by asking individual students.
Practice
1
What must be done to show that ∀xP(x) is false?
It is enough to find one value, a counterexample, for which P(x) is false.
2
The predicate P(x): x² − 5x + 6 = 0 is given on {1, 2, 3, 4}. For which x is it true? Give the values of the ∀ and ∃ statements.
x = 2 and x = 3 (x² − 5x + 6 = (x − 2)(x − 3)); ∃xP(x) is true, ∀xP(x) is false.
3
Write the negation of “∃x∈R: x² < 0” and say which of the two is true.
Negation: ∀x∈R, x² ≥ 0 — true; the original statement is false.
4
Why are ∀x∃y (y > x) and ∃y∀x (y > x) not equivalent?
In the first, y is chosen after x (y = x + 1) — true; in the second a single y must exceed every x, and no such number exists — false.