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.
Feed/

How can quantifiers be negated, interchanged, and ordered?

Channel

Brisk

1 page

"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."

Flowchart preview
Series cover
👍
0
0 comments0 shares

Sign in to view and post comments.