7/9 7. Predicates and Quantifiers

From propositions to predicates

A proposition is a complete statement that is either true or false. A predicate is different: it is a statement form whose truth depends on the values of variables or on the objects being discussed.

For example, let $P(x)$ mean “$x$ is prime.” The expression $P(x)$ is not yet true or false because no value has been assigned to $x$. After substitution, $P(7)$ is true and $P(8)$ is false. A predicate becomes a proposition when its variables are assigned values or bound by quantifiers.

A one-place predicate expresses a property of one object, such as $B(x)$: “$x$ is blue.” A predicate with two variables can express a relation, such as $L(x,y)$: “$x$ is larger than $y$.” The order matters: $L(a,b)$ and $L(b,a)$ generally express different claims.

Takeaway: Predicates provide the flexible statement forms that quantifiers later turn into complete claims.

Variables, domains, and scope

Every variable receives its possible values from a domain of discourse, the collection of objects under discussion. For example, consider $E(x): x>0$. If the domain is the integers, $E(2)$ is true and $E(-3)$ is false. If the domain is the positive integers, $E(x)$ is true for every object in the domain.

A variable may be free or bound. In $P(x)$, $x$ is a free variable because it is not assigned a value or governed by a quantifier. In $\forall x\,P(x)$, $x$ is bound by $\forall$. A formula with no free variables is a closed sentence and has a definite truth value within an interpretation.

When interpreting a formula, identify the domain before evaluating the claim. The same symbolic expression can change meaning when the allowed objects change.

Takeaway: Truth depends not only on the formula but also on the domain and on whether variables are free or bound.

Universal claims

The universal quantifier $\forall$ means “for every.” The expression $\forall x\,P(x)$ asserts that every object in the domain satisfies $P$. A universal claim is false if even one counterexample exists.

When an English sentence restricts the objects being discussed, place the restriction in the antecedent of a conditional. If $C(x)$ means “$x$ is a cat” and $M(x)$ means “$x$ is a mammal,” then “All cats are mammals” becomes

The conditional is essential: the formula does not claim that every object is a cat. Similarly, “No dogs are reptiles,” with $D(x)$ meaning “$x$ is a dog” and $R(x)$ meaning “$x$ is a reptile,” becomes

Takeaway: To disprove a universal statement, find one object in the domain for which the asserted property fails.

Existential claims

The existential quantifier $\exists$ means “there exists at least one.” The expression $\exists x\,P(x)$ is true whenever at least one object in the domain satisfies $P$. It does not mean “exactly one.”

For an English statement involving a restricted group, combine the restriction and the desired property with a conjunction. If $B(x)$ means “$x$ is a bird” and $F(x)$ means “$x$ can fly,” then “Some birds cannot fly” becomes

Likewise, “Some student passed the exam,” with $S(x)$ meaning “$x$ is a student” and $P(x)$ meaning “$x$ passed the exam,” becomes

One witness establishes an existential claim. To show that an existential claim is false, one must establish that no object satisfies the required condition.

Takeaway: Universal translations commonly use implication, while existential translations commonly use conjunction.

Translating ordinary language

Translate ordinary language in a fixed sequence:

1. Specify the domain.

2. Define predicates and relations.

3. Identify whether the sentence says every, none, some, or at least one.

4. Preserve the logical structure with $\land$, $\lor$, $\neg$, and $\rightarrow$.

5. Check the scope of each quantifier.

Common patterns include:

• “Every $F$ is $G$” becomes $\forall x\,(F(x)\rightarrow G(x))$.

• “No $F$ is $G$” becomes $\forall x\,(F(x)\rightarrow \neg G(x))$.

• “Some $F$ is $G$” becomes $\exists x\,(F(x)\land G(x))$.

• “Some $F$ is not $G$” becomes $\exists x\,(F(x)\land \neg G(x))$.

• “Everyone is $F$” becomes $\forall x\,F(x)$.

• “Someone is $F$” becomes $\exists x\,F(x)$.

For example, “No mathematician is careless” can be represented as

where $M(x)$ means “$x$ is a mathematician” and $C(x)$ means “$x$ is careless.” An equivalent formulation is

Avoid writing $\forall x\,(F(x)\land G(x))$ for “Every $F$ is $G$,” because that stronger formula says that everything in the domain is both $F$ and $G$. Also avoid $\exists x\,(F(x)\rightarrow G(x))$ for “Some $F$ is $G$,” because an object that is not $F$ could make the implication true.

Takeaway: Correct translation depends on the domain, the restriction, the connective, and the quantifier’s scope.

Multiple quantifiers and negation

With relations, more than one quantifier may be used. Let $L(x,y)$ mean “$x$ likes $y$.” The statement “Everyone likes someone” can be written

Here, each person may have a different person they like. By contrast, “There is someone whom everyone likes” is

This second statement requires one particular person to be liked by everyone. Thus, quantifier order is significant: $\forall x\,\exists y\,R(x,y)$ generally does not mean the same thing as $\exists y\,\forall x\,R(x,y)$.

Negation reverses quantifiers:

In ordinary language, “Not everything is red” means “Something is not red,” whereas “Nothing is red” means “Everything is not red.”

The most common errors are confusing every with some, treating some as exactly one, reversing a conditional, ignoring the domain, and changing quantifier order without checking the meaning.

Final takeaway: Quantifiers express how broadly a predicate applies; their domains, scopes, order, and interaction with negation determine the exact claim.

• bound variable

• restricted quantifiers