Quantifier Order: Every Object Has a Witness vs One Shared Witness

Read the witnesses in the order required

Quantifier order changes what counts as a witness. In ∀x∃yRxy, first take an arbitrary x; then find a y related to that x. You may use different y objects for different x objects. In ∃y∀xRxy, choose one y first; it must work for every x.

We use classical first-order logic with a nonempty domain and a two-place relation R. Rxy means that the ordered pair (x,y) belongs to R. It is not automatically symmetric, and the two variables may refer to the same object unless you add a distinctness condition.

Definitions and rules: [1] [2].

For every x, some y:  ∀x∃yRxy
One y for every x:   ∃y∀xRxy

The outermost quantifier is read first. Moving ∃y in front of ∀x is a stronger commitment about one shared object, not a harmless change of notation.

Inspect all pairs in three original models

All three deliberately constructed models have the domain {A,B}. A and B are labels for two distinct domain objects here. A true cell records membership in the relation. Every other cell is false; there are no unknown or omitted cells.

Download this original labelled diagram

On a narrow screen, scroll inside this table. Keyboard users can focus the region and use the arrow keys.

Download every ordered pair in the three models

In the diagonal model, A can choose A and B can choose B. That makes ∀x∃yRxy true. But choosing A as the shared y fails at x=B, and choosing B fails at x=A. There is no third object available. Thus ∃y∀xRxy is false.

Check every row, then look for one complete column

On a narrow screen, scroll inside this table. Keyboard users can focus the region and use the arrow keys.

For the shared-A model, y=A works for both x values. The second formula is true, and each row consequently has a witness too. For the failed-B-row model, B has no related y at all. Both claims fail.

Do not count total true cells as a substitute for their positions. The diagonal and shared-A models each contain two true cells, but only the shared-A model has a shared witness. Distribution across rows and columns is the decisive information.

Explain the valid direction beyond the small example

The implication from ∃y∀xRxy to ∀x∃yRxy holds for any interpretation, including an infinite domain. Suppose a single object d satisfies R(x,d) for every x. For any particular x, that same d is an available existential witness. Therefore every x has some y. This argument does not depend on the domain having two objects.

The reverse implication fails because the diagonal interpretation makes its premise true and its conclusion false. One complete countermodel suffices to refute an inference claimed to be valid. Merely testing many models where the inference happens to work would not establish validity.

Definitions and rules: [3].

This is why “there were two successful examples” is weaker evidence than the general witness argument. Use the examples to understand the distinction; use an all-interpretation argument or a licensed proof for the valid direction.

Keep the intended relation and distinctness explicit

If Rxy means “x is assigned reviewer y,” the first sentence allows separate reviewers for separate submissions. The second requires one reviewer assigned to every submission. That is a constructed interpretation of the wording, not a claim about a real review system.

If an object must have a different partner, write ∀x∃y(y≠x∧Rxy). The diagonal relation would then stop being an example of success. A self-related object was allowed in our original formulas, so silently adding “someone else” changes the task.

Likewise, do not replace Rxy with Ryx while rearranging the quantifiers. That changes the direction of the relation as well as its witness requirements. Work from a written domain and interpretation key before evaluating a formula.

Try three witness checks

Use the complete domain {A,B} and the displayed relation cells.