Concept

How do universal and existential quantifiers express claims about many objects?

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

"One powerful feature of predicate logic is the ability to make grandiose statements about many things at once. There are two kinds of quantifiers in predicate logic, the first of which is called the universal quantifier. It’s written “∀” and pronounced “for all.” For example, ∀x HasGovernor(x) asserts that for every x, HasGovernor is true. To be precise about the states, we should say: ∀x ∈ S HasGovernor(x), where S is the set of all fifty states in the U.S. We can use a quantifier for any complex expression, not just a simple predicate. For instance, if H is the set of all humans, then ∀h ∈ H Adult(h) ⊕ Child(h) states that every human is either an adult or a child, but not both. Another way to write this is to define another predicate Human and say: ∀h Human(h) ⇒ Adult(h) ⊕ Child(h). This expression is true for all objects because the implication is true whenever the premise is false or the conclusion is true. The other kind of quantifier is called the existential quantifier. It asserts the existence of something and is written “∃,” pronounced “there exists.” For example, ∃x HasGovernor(x) asserts that there is at least one state that has a governor. In compound expressions, a variable always stands for a single entity wherever it appears. Thus, ∃x President(x) ∧ African-American(x) means that there is at least one individual who is both African-American and President of the United States at the same time."

Related Ideas

How do universal and existential quantifiers express claims about many objects? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm