Which of the following is a valid first order formula ? (Here α and β are…

Key idea: determine which formula is logically valid (true in every structure).

Why (∀x)[α ⇒ β] ⇒ ((∀x)[α] ⇒ (∀x)[β]) is valid:

• Assume ∀x(α⇒β) and ∀x α hold in some structure.

• Take an arbitrary element c of the domain. From ∀x α we get α[c]. From ∀x(α⇒β) we get α[c]⇒β[c].

• By modus ponens at c we get β[c]. Since c was arbitrary, ∀x β holds. Hence (∀x α ⇒ ∀x β) follows, so the whole implication is true in every structure.

Why the other formulas are not valid (short counterexamples):

• ((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α⇒β]: not valid. Example: domain {a,b}, let α true only at a and β true only at b. Then (∀x α ⇒ ∀x β) is true while ∀x(α⇒β) is false.

• (∀x)[α] ⇒ (∃x)[α ∧ β]: not valid. Example: let α be true everywhere and β false everywhere; then the antecedent holds but the consequent fails.

• ((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]: not valid. Example: domain {a,b}, let α true only at a and β true only at b. Then ∀x(α∨β) and ∃x α hold, but ∀x α fails.