Multiple quantifiers

evaluate a two-quantifier formula in a finite model

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.

1. What you will learn

You will evaluate a two-quantifier formula in a finite model, recording the intermediate model values and the precise reason each conclusion follows.

2. Before using the new notation

Recall the truth conditions for not, and, or and if-then. Those rules still govern compound formulas here, but atomic truth now comes from objects and predicate extensions or from a world's valuation. Identify which new structure this lesson introduces before using a familiar propositional rule.

3. Words used in this model audit

Term	What it means
Interpretation	A declared domain and meanings for the nonlogical symbols; a modal interpretation also specifies worlds, accessibility and valuations.
Assignment	A choice of domain object for a free variable during an evaluation; it is not itself another domain object.
Witness	An eligible object or accessible world satisfying the property required by an existential or possibility claim.
Counterexample	An eligible case where the required condition fails; a countermodel to an inference additionally makes every premise true.
Validity	Truth in every interpretation of the specified kind, a stronger claim than truth in one supplied model.

4. Evaluate nested formulas from the inside out

A formula with several quantifiers can be evaluated systematically. Hold a value for the outer variable, evaluate the inner quantified formula under that assignment, and then combine those inner results according to the outer quantifier. For forall x exists y R(x,y), each row gives an inner existential result and the outer universal requires every row result to be true.

For exists y forall x R(x,y), each column gives an inner universal result and the outer existential requires at least one successful column. Two universals require every cell in the relation table to be true. Two existentials require at least one true cell. These four patterns explain why a total count of true cells is not enough to evaluate every two-quantifier formula: their placement matters.

Negation can occur inside the nested formula. In forall x exists y not R(x,y), every row needs a false relation cell. It does not say that every cell is false, and it does not say that one column is false for every row. Write the inner test explicitly before searching. A copied quantifier pattern with the wrong inner predicate can reverse the intended criterion.

When a finite table has n objects in each argument position, there are n squared ordered pairs to consider. A full evaluation can stop early when a decisive failure or witness is found, but the justification must explain why stopping is legitimate for that quantifier. Keeping a row-result or column-result list is a useful check on both the computation and the scope.

Another way: An explicit audit sheet

Keep four parts on the page: the declared objects or worlds, the meaning of each symbol, the intermediate values, and the conclusion. A changed interpretation belongs on a new sheet so the premises and conclusion are never checked in different models.

5. Model study 1: forall x exists y R(x,y)

Domain: a, b, all distinct. R holds exactly for these ordered pairs: (a,a), (b,b). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.

Fix the first argument at a. Its row has targets a, so there are 1 true entries in this row. The statement exists y R(a,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Fix the first argument at b. Its row has targets b, so there are 1 true entries in this row. The statement exists y R(b,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Rows with some true entry: 2. The nested expression exists y R(x,y) produces a truth value for each fixed x. Compute that inner expression row by row and store the resulting list. This intermediate list is useful even when the outer formula changes: universal combination asks whether every entry succeeds, whereas existential combination asks whether at least one does. Do not skip the intermediate calculation when two quantifiers look similar.

Columns with every entry true: 0. For each fixed target y, inspect every possible x. A column contributes to this count only if none of its entries is false. These successful columns are the possible witnesses for exists y forall x R(x,y). Counting true cells across the entire table would answer a different question. Their distribution by row and column is what determines the quantified formulas.

forall x exists y R(x,y): T. Combine the row results using the outer universal, so every row must have a witness. This nested calculation can be expressed as a short loop: for each source, search all targets until one works; reject the formula if a row has no target. The procedure is justified by the quantifiers' meanings, not by a shortcut involving the total number of relation pairs.

For this interpretation, the number of targets shared by every source is 0. Compare that with the 2 successful rows. If each source has a target but no target is shared by all sources, the two quantifier orders differ in truth value. Adding one common target to every row repairs the stronger column claim. Deleting every entry in one row refutes the row claim. These changes explain which structural feature each formula measures.

6. Model study 2: forall x exists y R(x,y)

Domain: a, b, c, all distinct. R holds exactly for these ordered pairs: (a,c), (b,c), (c,c). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.

Fix the first argument at a. Its row has targets c, so there are 1 true entries in this row. The statement exists y R(a,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Fix the first argument at b. Its row has targets c, so there are 1 true entries in this row. The statement exists y R(b,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Fix the first argument at c. Its row has targets c, so there are 1 true entries in this row. The statement exists y R(c,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Rows with some true entry: 3. The nested expression exists y R(x,y) produces a truth value for each fixed x.

Columns with every entry true: 1. For each fixed target y, inspect every possible x.

forall x exists y R(x,y): T. Combine the row results using the outer universal, so every row must have a witness.

For this interpretation, the number of targets shared by every source is 1. Compare that with the 3 successful rows. If each source has a target but no target is shared by all sources, the two quantifier orders differ in truth value. Adding one common target to every row repairs the stronger column claim. Deleting every entry in one row refutes the row claim. These changes explain which structural feature each formula measures.

7. Model study 3: forall x exists y R(x,y)

Domain: a, b, c, d, all distinct. R holds exactly for these ordered pairs: (a,b), (b,c), (c,d), (d,a). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.

Fix the first argument at a. Its row has targets b, so there are 1 true entries in this row. The statement exists y R(a,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Fix the first argument at c. Its row has targets d, so there are 1 true entries in this row. The statement exists y R(c,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Fix the first argument at d. Its row has targets a, so there are 1 true entries in this row. The statement exists y R(d,y) is T. The inner existential can choose from this row only; it cannot borrow a target from a row belonging to a different first argument.

Rows with some true entry: 4. The nested expression exists y R(x,y) produces a truth value for each fixed x.

Columns with every entry true: 0. For each fixed target y, inspect every possible x.

forall x exists y R(x,y): T. Combine the row results using the outer universal, so every row must have a witness.

For this interpretation, the number of targets shared by every source is 0. Compare that with the 4 successful rows. If each source has a target but no target is shared by all sources, the two quantifier orders differ in truth value. Adding one common target to every row repairs the stronger column claim. Deleting every entry in one row refutes the row claim. These changes explain which structural feature each formula measures.

8. Why the arrangement of cells matters

Two relation tables can have the same number of true cells and disagree on a nested formula. Over a two-object domain, put two true cells on the diagonal of the first table. Put two true cells in the first row of the second. Each table has two true pairs. The first satisfies forall x exists y R(x,y); the second fails because its second row has no witness.

Now put the two true cells in one column. Every row has a true entry, and one column is entirely true. This model satisfies both the row-witness formula and exists y forall x R(x,y). Counting the two true cells still would not distinguish it from the diagonal arrangement. The shape of the support is the relevant information.

When adding a third quantifier, preserve the same discipline. For each outer assignment, evaluate the remaining inner formula under that assignment. Intermediate tables or lists can record these results. You need not invent a new meaning for every quantifier depth; you repeatedly apply the same universal and existential clauses while keeping variable assignments separate.

An early stopping rule follows from the clause being applied. A single false inner result defeats an outer universal. A single true inner result establishes an outer existential. The opposite results require exhaustive coverage of the relevant finite range. This distinction can make an evaluation efficient without making it incomplete. Explain why the discovered cell, row or column is decisive. A quick answer is trustworthy when its stopping point follows from the quantifier rather than from impatience or the accidental order of the table.

9. Assigning reviewers to project files

A project group has three members and three files, with a stated assignment table showing which member can review which file. Treat this as a relation from members to files, using a two-sorted explanation for the application. The requirement that every file has some eligible reviewer asks for a witness for each file. Those witnesses need not be the same person.

The requirement that one member can review every file instead asks for one common reviewer. A table with one different eligible member for each file satisfies the first requirement but fails the second. Counting three eligible pairings alone does not tell you which requirement is met. You must inspect how those three pairs are arranged.

Now consider the much stronger claim that every member can review every file. It needs all nine cells true. A single missing eligibility pair refutes it, even if the group still has a perfectly workable assignment for completing all reviews. Logical strength and practical adequacy are different questions: a plan may meet its actual goal without satisfying every stronger formula one could write.

To turn the application into a single-domain first-order model, include both members and files and use predicates to restrict their roles. Do not let a member accidentally serve as a file witness merely because both belong to the domain. The exercises use one explicitly declared domain for both arguments so that their arithmetic is transparent. The application shows why realistic modeling also requires deciding which objects are eligible for each role before evaluating the quantifiers.

10. Keep the result at its proper level

A correct evaluation answers the stated question for its stated interpretation. Do not turn a true instance into a universal rule or a successful example into a proof of validity. When the task is a proof audit, keep local assumptions and fresh parameters within their declared scope.

11. Evaluation 3: forall x exists y R(x,y)

Record the interpretation and the question.
Domain: a, b, c, all distinct. R holds exactly for these ordered pairs: (a,a), (a,b), (a,c), (b,a), (b,b), (b,c). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.
Use the declared objects and meanings throughout this calculation: Rows with some true entry is the first requested result.
Determine the requested value: Rows with some true entry.
2
The nested expression exists y R(x,y) produces a truth value for each fixed x.
Determine the requested value: Columns with every entry true.
0
For each fixed target y, inspect every possible x.
Determine the requested value: forall x exists y R(x,y).
F
Combine the row results using the outer universal, so every row must have a witness.
Collect the results in the requested order.
2 / 0 / F
Each result belongs to its own entry: Rows with some true entry; Columns with every entry true; forall x exists y R(x,y).

12. Evaluation 4: forall x exists y R(x,y)

Record the interpretation and the question.
Domain: a, b, c, d, all distinct. R holds exactly for these ordered pairs: (a,a), (b,b), (c,c), (d,d). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.
Use the declared objects and meanings throughout this calculation: Rows with some true entry is the first requested result.
Determine the requested value: Rows with some true entry.
4
The nested expression exists y R(x,y) produces a truth value for each fixed x.
Determine the requested value: Columns with every entry true.
0
For each fixed target y, inspect every possible x.
Determine the requested value: forall x exists y R(x,y).
T
Combine the row results using the outer universal, so every row must have a witness.
Collect the results in the requested order.
4 / 0 / T
Each result belongs to its own entry: Rows with some true entry; Columns with every entry true; forall x exists y R(x,y).

13. Evaluation 5: forall x exists y R(x,y)

Record the interpretation and the question.
Domain: a, b, c, d, e, all distinct. R holds exactly for these ordered pairs: (a,e), (b,e), (c,e), (d,e), (e,e). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.
Use the declared objects and meanings throughout this calculation: Rows with some true entry is the first requested result.
Determine the requested value: Rows with some true entry.
5
The nested expression exists y R(x,y) produces a truth value for each fixed x.
Determine the requested value: Columns with every entry true.
1
For each fixed target y, inspect every possible x.
Determine the requested value: forall x exists y R(x,y).
T
Combine the row results using the outer universal, so every row must have a witness.
Collect the results in the requested order.
5 / 1 / T
Each result belongs to its own entry: Rows with some true entry; Columns with every entry true; forall x exists y R(x,y).
Test which alteration would change the conclusion.
For this interpretation, the number of targets shared by every source is 1. Compare that with the 5 successful rows. If each source has a target but no target is shared by all sources, the two quantifier orders differ in truth value. Adding one common target to every row repairs the stronger column claim. Deleting every entry in one row refutes the row claim. These changes explain which structural feature each formula measures.
The altered interpretation checks the dependence of these answers on the stated model, rather than replacing it during the calculation.

14. Complete the next model audit

Determine the requested value: Rows with some true entry.
4
The nested expression exists y R(x,y) produces a truth value for each fixed x.
Your turn: work this step out. Its working is at the end of the packet.
Determine the requested value: Columns with every entry true.
Your turn: work this step out. Its working is at the end of the packet.
Determine the requested value: forall x exists y R(x,y).

15. Guided practice

Domain: a, b, c, d, e, all distinct. R holds exactly for these ordered pairs: (a,a), (a,b), (a,c), (a,d), (a,e), (b,a), (b,b), (b,c), (b,d), (b,e), (c,a), (c,b), (c,c), (c,d), (c,e), (d,a), (d,b), (d,c), (d,d), (d,e). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.

	Computed result
Rows with some true entry
Columns with every entry true
forall x exists y R(x,y)

16. Guided practice

Domain: a, b, c, d, e, f, g, all distinct. R holds exactly for these ordered pairs: (a,a), (a,b), (a,c), (a,d), (a,e), (a,f), (a,g), (b,a), (b,b), (b,c), (b,d), (b,e), (b,f), (b,g), (c,a), (c,b), (c,c), (c,d), (c,e), (c,f), (c,g), (d,a), (d,b), (d,c), (d,d), (d,e), (d,f), (d,g), (e,a), (e,b), (e,c), (e,d), (e,e), (e,f), (e,g), (f,a), (f,b), (f,c), (f,d), (f,e), (f,f), (f,g). Every unlisted pair is false, and self-pairs are permitted. Complete the three quantified-model entries named below. Use T or F for sentence truth.

Evaluate the inner existential separately in each row.
_b0
The requested entry concerns rows with some true entry; retain its stated scope.
Evaluate the inner universal separately in each column.
_b1
The requested entry concerns columns with every entry true; retain its stated scope.
Combine the row results with the outer universal.
_b2
The requested entry concerns forall x exists y r(x,y); retain its stated scope.

23. What you can do now

You can evaluate a two-quantifier formula in a finite model. Reconstruct the three audit entries from a fresh model without consulting the examples; explain what change to the interpretation would change one answer.

Working for the steps left to you

14. Complete the next model audit, step 2

For each fixed target y, inspect every possible x.

14. Complete the next model audit, step 3

Combine the row results using the outer universal, so every row must have a witness.