Question

If X does not occur free in Q, then ∀X(P(X) -> Q) is semantically equivalent with∃XP(X) -> Q. Give an example to show that these formulas will not necessarily be equivalent if X does occur free in Q.

Answer 1

Let M a structure whatever, with domain D.

Two cases :

(i) ∃xP(x) is False.

Thus ∃xP(x)→Q is True.

But to say that ∃xP(x) is False in M means that for a∈D whatever, we have that P(x)[a/x] is False, and thus (P(x)→Q)[a/x] is True in M.

And this means in turn that M⊨∀x(P(x)→Q).

And for the second case

(ii) ∃xP(x) is True, i.e. there is an object a∈D such that P(x)[a/x] is True.

Two sub-cases :

(a) Q is False. Thus ∃xP(x)→Q is False.

But (P(x)→Q)[a/x] is False for the a∈D above, and thus ∀x(P(x)→Q) is False in M.

(b) Q is True. Thus ∃xP(x)→Q is True.

But if Q is True, also (P(x)→Q)[a/x] is True, for a∈D whatever.

And this means that ∀x(P(x)→Q) is True in M.