Practice question · Put in order
Four statements are built from the same two-place predicate P(x, y). Order them from the weakest claim, which is the easiest to satisfy, to the strongest.
- for all x there exists y with P(x, y)
- there exists x and there exists y with P(x, y)
- there exists y such that for all x, P(x, y)
- for all x and for all y, P(x, y)
Hints
- A claim is stronger when it demands more: one witness is the least demanding, and every pair the most.
- Compare the two middle claims carefully, one allows a different y for each x, the other insists on a single y that serves them all.
Show the answer
- there exists x and there exists y with P(x, y)
- for all x there exists y with P(x, y)
- there exists y such that for all x, P(x, y)
- for all x and for all y, P(x, y)
Why
One pair suffices for the first; the second wants a witness for each x, and it may be a different y each time; the third demands a single y that works for every x, which is far harder; the fourth demands every pair. 'Every person has a mother' is of the second kind and true, while 'there is one mother of everyone' is of the third kind and false, swapping the quantifier order silently changes the meaning.
Practise Predicate Logic and Quantifiers
The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Predicate Logic and Quantifiers
- Select every statement that correctly expresses the negation of 'for all x, P(x)'.
- "Every student who studied passed" is true in a class where nobody studied. Why does the universal claim…
- Match each quantified statement to its correct negation.
- Sort each English claim by the quantifier it uses.
- The negation of "every student passed" is "no student passed".
- A test asserts "every returned record matches the filter" and passes when the query returns nothing at all.…