Bifalgorithm post · Brisk · Chapter 1
How can quantifiers be negated, interchanged, and ordered?
How can quantifiers be negated, interchanged, and ordered? (Brisk · Chapter 1) — "It’s common practice to negate quantifiers, both universal and existential. F…
Ideas in this flowchart
- Negation and ordering of universal and existential quantifiers
- Universal and existential quantifiers are commonly negated.
- ¬∃p President(p) ∧ Female(p) means that there does not exist a female president.
- ¬∀x HasGovernor(x) means that not everything has a governor.
- Logical equivalences interchange universal and existential quantifiers.
- ∀x P(x) ⇔ ¬∃x ¬P(x)
- ¬∀x P(x) ⇔ ∃x ¬P(x)
- ∀x ¬P(x) ⇔ ¬∃x P(x)
- ¬∀x ¬P(x) ⇔ ∃x P(x)
- The verbal interpretations show that failure for everything implies existence of a counterexample or a positive instance.
- The order of universal and existential quantifiers affects meaning and truth value.
- ∀x ∈ R ∃y ∈ R x + 1 = y is true because each real number has a real number that is one greater.
- ∃y ∈ R ∀x ∈ R x + 1 = y is false because no single number is one greater than every real number.
- Quantifier expressions must be analyzed carefully because changing their order can change the statement's meaning and truth value.
