Let P(x) and Q(x) be arbitrary predicates. Which of the following statements…

Correct statement and proof: (∀x (P(x) → Q(x))) → ((∀x P(x)) → (∀x Q(x))).

• Proof:

• Assume ∀x (P(x) → Q(x)) and assume ∀x P(x). Let a be an arbitrary element of the domain.

• From ∀x P(x) we have P(a). From ∀x (P(x) → Q(x)) we have P(a) → Q(a). Hence Q(a).

• Because a was arbitrary, we conclude ∀x Q(x). Therefore (∀x P(x)) → (∀x Q(x)) follows, establishing the implication.

Counterexamples for the other formulas:

• For ((∀x (P(x) ∨ Q(x)))) → ((∀x P(x)) ∨ (∀x Q(x))): let the domain be {1,2}, set P true only at 1 and Q true only at 2. Then ∀x (P(x) ∨ Q(x)) holds, but neither ∀x P(x) nor ∀x Q(x) holds, so the implication fails.

• For ( (∀x P(x) → ∀x Q(x)) → ∀x (P(x) → Q(x)) ): use domain {1,2} with P true only at 1 and Q true only at 2. Both ∀x P(x) and ∀x Q(x) are false, so the antecedent is true, but ∀x (P(x) → Q(x)) is false (fails at x=1).

• For ( (∀x P(x) ⇔ ∀x Q(x)) → ∀x (P(x) ⇔ Q(x)) ): with domain {1,2}, P true only at 1 and Q true only at 2, both ∀x P(x) and ∀x Q(x) are false so the antecedent holds, but ∀x (P(x) ⇔ Q(x)) fails at individual elements.

Conclusion: the only formula that is always true is (∀x (P(x) → Q(x))) → ((∀x P(x)) → (∀x Q(x))).