When you have a statement with →, does it matter if you use a quantifier before or after the implication?
ex. the statement "Every man loves a king" (2 different semantic interpretations)
- Every man loves a king and these kings may all differ from each other.
∀x IsMan(x) → ∃y (IsKing(y) ∧ Loves(x,y))
- There is a single king that every man loves.
∃y, ∀x (IsKing(y) ∧ IsMan(x)) → Loves(x,y)
For #1, would it be equally correct to write it as ∀x, ∃y, (IsMan(x) ∧ IsKing(y)) → Loves(x,y)
?
And for #2, what about ∃y IsKing(y) → ∀x (IsMan(x) ∧ Loves(x,y))
?
Yes, the order of quantifier matters to decide the satisfiability/validity of a formula.
One way to be sure of it is to know that
(A → B)
is the same as(not A or B)
and that(not (∀x x))
is the same as(∃x (not x))
.Thus, when you have
(∃x, ∀y x → y)
it is the same as(∀x ∃y ((not x) or y))
.Which is different from
(∃x, x → ∀y y)
which can then be((∀x (not x) or (∀y y))
.