Quantifiers
Predicates, the quantifiers ∀, ∃ and ∃!, free and bound variables, quantifier order and negating a quantified statement.
- 24 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
A few cards from the deck
Predicate: what is it?
Show the answer
A statement containing one or more variables that becomes a proposition, true or false, once they are given a value: "x is even".
As long as x has no value, one cannot say whether it is true. A quantifier is the other way to turn it into a proposition.
What is the negation of "every student has passed at least one module"?
- There is a student who has passed no module
- No student has passed any module
- There is a student who has passed all modules
- There is a student who has not passed every module
Show the answer
There is a student who has passed no module
∀ becomes ∃ and "at least one" (∃) becomes "none" (∀, not). "No student has passed any module" is too strong: a single student with no module is enough to refute the statement. "Has not passed every module" negates the wrong quantifier.
The negation of "∀x, P(x)" is "…, not P(x)"; the negation of "∃x, P(x)" is "…, not P(x)".
Show the answer
The negation of "∀x, P(x)" is "∃x, not P(x)"; the negation of "∃x, P(x)" is "∀x, not P(x)".
Negating a quantified statement swaps ∀ and ∃ and negates what follows. It generalises De Morgan: ∀ is a big ∧ and ∃ a big ∨.
Universal quantifier ∀: what is it?
Show the answer
The symbol read "for all": ∀x, P(x) states that P(x) is true for every value of x in the set under consideration.
A single case where P(x) is false is enough to refute it, but no number of examples is enough to establish it.
In ℕ (which contains 0), which of "∀n ∃m, m > n" and "∃m ∀n, m > n" are true?
- Only the first: m = n + 1 works for each n
- Both, because they say the same thing
- Only the second: a large enough m works for all
- Neither
Show the answer
Only the first: m = n + 1 works for each n
In the second, m would have to exceed all integers, itself included (n = m gives m > m). Swapping ∀ and ∃ changes the meaning: ∃m ∀n implies ∀n ∃m, never the reverse.