Back to the on-screen lesson ·
What changes when a for-all and a there-is swap places, which direction the entailment runs, and how a two-object structure settles that they differ.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to read a formula with two quantifiers by playing it as a game, say what each order claims in English, evaluate all four mixed forms in a small structure, put them in order of strength, count the pairs two quantifiers range over, and build a structure that separates the two orders.
You can read a formula with one quantifier and evaluate it in a small structure. With two quantifiers of different kinds, the order they are written in changes what the formula says, and this lesson is about that change.
A two-place predicate $Rxy$ relates objects in an order: $Rab$ and $Rba$ are different claims. A quantifier is inside the scope of one written before it, and a variable it binds may vary with the outer one. A structure separates two formulas when it makes one true and the other false.
With two quantifiers of the same kind the order makes no difference. With one of each it makes all the difference, and the reason is the order of choice. In $\forall x \exists y\, Rxy$ the object $y$ is chosen after $x$ is known, so a different $y$ may serve each $x$; in $\exists y \forall x\, Rxy$ the object $y$ is chosen first and a single one must serve every $x$. So $\exists y \forall x\, Rxy \models \forall x \exists y\, Rxy$ — the fixed object will do each time — and the converse fails. Reading a formula as a game makes this automatic: at $\forall$ your opponent chooses, at $\exists$ you choose, and the leftmost quantifier moves first; the formula is true when you have a winning strategy. Showing that the converse really fails is not a matter of argument but of exhibiting a structure, and a two-object one is usually enough.
Another way: steps
Another way: example
Domain $\{a, b\}$, $R$ holding of $a$ to $b$ and $b$ to $a$: everything is related to something, so $\forall x \exists y\, Rxy$ holds; no single object is related to by both, so $\exists y \forall x\, Rxy$ fails.
The commonest error is reading the two orders as notational variants of one claim, which they are for two quantifiers of the same kind and never for a mixed pair. The second is getting the direction of the entailment backwards: the strong one is the one with $\exists$ written first, and it entails the other. The third is treating $Rab$ and $Rba$ as the same, which quietly turns every relation into a symmetric one.
$\forall x \exists y\, Rxy$ in the cycle $a \to b \to c \to a$: the opponent names an object.
For-all moves first.
Whatever they name, you answer with the object it points to.
You always have a reply.
A winning strategy, so the formula is true — and your reply depended on their choice, which is exactly what the other order forbids.
The reply may vary.
$\exists y \forall x\, Rxy$ in the same cycle: you must name the object first.
There-is moves first.
Name $b$, and the opponent answers $b$: $Rbb$ fails. Every candidate has the same problem.
One object must serve all.
False. So the cycle separates the two orders, which settles that they are different claims.
A structure is the proof.
The first is $\forall x \exists y\, Myx$ and the second is $\exists y \forall x\, Myx$, so the swap runs in the invalid direction.
No. A structure with two people, each the mother of the other, makes the first true and the second false.
The domain is $\{a, b, c\}$, and $R$ holds of exactly three pairs: $a$ to $b$, $b$ to $c$, and $c$ to $a$. Mark every statement that is true in this structure.
This task has no paper form; do it on a device.
Read $Rxy$ as “$x$ admires $y$”. Match each formula to what it says.
| Everyone admires someone or other | There is someone whom everyone admires | There is someone who admires everyone | Everyone admires everyone | |
|---|---|---|---|---|
| $\forall x \exists y\, Rxy$ | ||||
| $\exists y \forall x\, Rxy$ | ||||
| $\exists x \forall y\, Rxy$ | ||||
| $\forall x \forall y\, Rxy$ |
What exactly is the difference between $\forall x \exists y\, Rxy$ and $\exists y \forall x\, Rxy$?
The domain is $\{a, b, c\}$, and $R$ holds of just the three pairs relating $a$ to each object. Write T or F for each statement.
| True in this structure? | |
|---|---|
| $\forall x \exists y\, Rxy$ | |
| $\exists y \forall x\, Rxy$ | |
| $\exists x \forall y\, Rxy$ | |
| $\forall x \forall y\, Rxy$ |
Read $Rxy$ as “$x$ admires $y$”. Put these four statements in order, strongest first, so that each entails the next.
Number the steps in order (write the number in the box):
The domain is $\{a, b\}$. Mark every structure below in which $\forall x \exists y\, Rxy$ is true and $\exists y \forall x\, Rxy$ is false.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A structure has a domain of $3$ objects. To settle $\forall x \forall y\, Rxy$ by checking every case, how many pairs have to be looked at?
Answer:
You can read and evaluate a mixed-quantifier formula and produce a structure separating the two orders. Say in your own words why the quantifier written first is the choice made first.
8. Your turn: does *everyone has a mother* entail *someone is everyone's mother*?, step 2