Predicates and Quantifiers

Introduction

Propositional logic does not allow us to go from statements like "All men are mortal" and "Socrates is a man" to a conclusion like "Socrates is mortal."
For that we need predicate logic.

Predicates

Statements involving variables are not propositions so long as the variable is free. Only when the variable is bound do such statements take on a truth value.
x > 3
is neither true nor false if no value has been assigned to x. Only when a value has been assigned to the variable does the predicate (here, "is greater than 3") become true or false of that value.

Quantifiers

From the textbook:
"Quantification expresses the extent to which a predicate is true over a range of elements. We will focus on two types of quantification here: universal quantification, which tells us that a predicate is true for every element under consideration, and existential quantification, which tells us that there is one or more element under consideration for which the predicate is true."

The Universal Quantifier
The black swan

The universal quantifier asserts that some predicate holds for all elements of some set, e.g.:
"For every integer m, there exists an integer n such that n = m + 1."
It is represented by the symbol ∀.

Universe of discourse = swans
Let W(s) be the statement "s is white."
Then, ∀s W(s) means "All swans are white."
A universal quantifier is rendered false by a single counter-example.

The Existential Quantifier

The existentital quantifier asserts that a predicate is true of some member of a set, e.g.:
"There exists a real number x such that y * x = y."
It is represented by the symbol ∃.

Universe of discourse = swans
Let B(s) be the statement "s is black."
Then, ∃s B(s) means "Some swan is black."
An existentital quantifier is made true by a single example.

Quantifiers with Restricted Domains

∀x > 0 (x3 > 0)
is the same as:
∀x(x > 0 → x3 > 0)

∃x > 0 (x2 = 2)
is the same as:
∃x(x > 0 ∧ x2 = 2)

Test Yourself!
  1. To say all fire hydrants are red, where R(x) means "x is red," we would write:
    1. ∃x R(x)
    2. ¬∃x ¬R(x)
    3. ∀x R(x)
  2. To say that there exists a black swan, where B(x) means "x is black," we would write:
    1. ∀x R(x)
    2. ∃x B(x)
    3. ¬∃x ¬R(x)
  3. L(p,q) is a statement "p likes q" where the domain for p and q is all the people in the world. How can you express the statement: "Pam is liked by everyone"?
    1. ∀q L(Pam, q)
    2. ∃q∀p L(Pam,p)
    3. ∀p L(p, Pam)
    4. ∀p∃q L(p,q)
  4. L(p,q) is a statement "p likes q" where the domain for p and q is all the people in the world. How can you express the statement: "Everyone likes everyone"?
    1. ∀q L(p,q)
    2. ∀p L(p,q)
    3. ∀q L(p)
    4. ∀p∀q L(p,q)
  5. Which of the following is not a type of quantifier?
    1. Existential
    2. Nested
    3. Complex
    4. Universal
Answers

1. c; 2. b; 3. c; 4. d; 5. c;