Which of the following first order formula is logically valid? Here α(x) is a…

Correct formula: [(∃x α(x))→β]→[∀x (α(x)→β)]

Why this formula is valid:

• Assume (∃x α(x))→β holds in an arbitrary structure.

• Take an arbitrary element t of the domain. If α(t) holds, then ∃x α(x) holds, so by the assumption β holds. Hence α(t)→β.

• Because t was arbitrary, ∀x (α(x)→β) holds. Therefore the implication is valid in every structure.

Why the other formulas are not valid:

• Counterexample for [β→(∃x α(x))]→[∀x (β→α(x))]: Let the domain be {a,b}, let β be true, let α(a) be true and α(b) be false. Then β→∃x α(x) is true, but ∀x (β→α(x)) is false (fails at x = b).

• Counterexample for [∃x (β→α(x))]→[β→∀x α(x)]: With the same domain and assignment (β true, α true only at a), ∃x (β→α(x)) holds (witness a) but β→∀x α(x) fails because β is true while ∀x α(x) is false.

• Counterexample for [(∀x α(x))→β]→[∀x (α(x)→β)]: Let the domain be {a,b}, let β be false, let α(a) be true and α(b) be false. Then (∀x α(x))→β is true (since ∀x α(x) is false), but ∀x (α(x)→β) is false (fails at x = a).

Conclusion: Only the formula [(∃x α(x))→β]→[∀x (α(x)→β)] is logically valid; the other three can be shown false by simple finite-domain counterexamples.