Concept

How can quantifiers be negated, interchanged, and ordered?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"It’s common practice to negate quantifiers, both universal and existential. For example, ¬∃p President(p) ∧ Female(p) conveys that there does not exist a female president. Similarly, ¬∀x HasGovernor(x) says that not everything has a governor. Universal and existential quantifiers can be interchanged through logical equivalences: ∀x P(x) ⇔ ¬∃x ¬P(x); ¬∀x P(x) ⇔ ∃x ¬P(x); ∀x ¬P(x) ⇔ ¬∃x P(x); and ¬∀x ¬P(x) ⇔ ∃x P(x). In words, if P is not true for everything, then it must be false for something; if P is false for everything, then there is nothing for which it is true; and if P is not false for everything, then it must be true for something. The order of quantifiers matters. Consider ∀x ∈ R ∃y ∈ R x + 1 = y. This statement is true because for every real number x, we can find a number y that is one greater than x. If we switch the order, we get ∃y ∈ R ∀x ∈ R x + 1 = y. This says that there exists one magic number y that is one greater than every possible x, which is false. Therefore, expressions with universal and existential quantifiers must be analyzed carefully, because changing their order can change the meaning and truth value of the statement."

Related Ideas

How can quantifiers be negated, interchanged, and ordered? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm