Which one of the following well formed formulae is a tautology?

Given answer (the indicated tautology): [ ∀x ∃y (P(x,y) → R(x,y)) ] ↔ [ ∀x ∃y (¬P(x,y) ∨ R(x,y)) ]

Key insight: the propositional equivalence (A → B) ≡ (¬A ∨ B) holds for any formulas A and B, and equivalence is preserved when the same quantifiers are applied to both sides.

• Step 1: For every choice of elements x and y, the formula P(x,y) → R(x,y) is logically equivalent to ¬P(x,y) ∨ R(x,y).

• Step 2: Applying the same prefix of quantifiers (∀x ∃y) to two pointwise-equivalent formulas yields two formulas that are equivalent in every structure.

• Conclusion: The biconditional between these two quantified formulas is true in every structure, so it is a tautology.

Brief comments on the other choices:

• The biconditional between 'for all x there exists y R(x,y)' and 'there exists y for all x R(x,y)' is not valid in general. Example: domain {1,2}, let R(x,y) hold iff y = x. Then the first is true (each x has y = x), but the second is false (no single y works for all x).

• The formula (∀x [∃y R(x,y) → S(x,y)]) → ∀x ∃y S(x,y) is not valid. Example: take a one-element domain and make R and S false everywhere. Then the antecedent universal holds (each conditional has a false antecedent and so is true) but the consequent that there exists a y with S(x,y) fails; the implication is false in that model.

• The implication 'if ∀x ∀y P(x,y) then ∀x ∀y P(y,x)' is valid: if P holds for every ordered pair then swapping the names of bound variables yields the same universal claim, so the consequent follows from the antecedent. Therefore that formula is also valid in every structure.

Note: The problem's indicated correct formula is indeed a tautology, but the universal-swap implication just mentioned is valid as well; that means there is more than one formula among the choices that is valid in all structures.