Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 1.3.2 Universal quantification

Quantification expresses the extent to which a propositional function is true; for example, all, some, none, many, and so on.
🔗

Definition 1.3.2.1.

The universal quantification of \(P\) , denoted \(\forall x \, P(x)\) , is the proposition “\(P(x)\) for all \(x\) in the domain.” The symbol \(\forall\) is the universal quantifier The domain of \(P\) specifies the possible values for \(x\) .
🔗
🔗
The domain of a propositional function matters. In Example 1.3.2.2 and Example 1.3.2.4 we consider propositional functions with the same predicate but with a different domain.
🔗

Example 1.3.2.2. For all integers.

Let \(S(x)\) be “\(x \gt-2\)” with domain the integers. Consider the proposition
\begin{equation*} \forall x\, S(x) \end{equation*}
Because \(-5\) is an integer and “\(-5\gt -2\)” is false \(\forall x\,S(x)\) is false.
🔗
🔗
The propositional function in the following example has the domain the natural numbers. We recall their definition:
🔗

Definition 1.3.2.3.

The natural numbers are the numbers:
\begin{equation*} 1, 2, 3, 4, 5, 6, \dots \end{equation*}
🔗
🔗

Example 1.3.2.4. For all natural numbers.

Let \(R(x)\) be “\(x \gt-2\)” with domain the natural numbers. Consider the proposition
\begin{equation*} \forall x\, R(x) \end{equation*}
Because all natural numbers are positive and \(x\gt -2\) is true for all positive numbers we have that \(\forall x\, R(x)\) is true.
🔗
🔗

Remark 1.3.2.5.

The universal quantification of a propositional function is a proposition, since it is a declarative sentence that is either true or false, but not both.
🔗
🔗

Definition 1.3.2.6.

Let \(P(x)\) be a propositional function. A counterexample of \(\forall x \,P(x)\) is an element \(x_0\) such that \(P(x_0)\) is false.
🔗
🔗

Remark 1.3.2.7.

To prove a universal quantification is false, it suffices to exhibit a single counterexample.
🔗
🔗
In Example 1.3.2.2 we haven given the counterexample \(x=-5\) to prove that the proposition “all integers are greater than \(-2\)” is false.
🔗

Example 1.3.2.8. Single counterexample.

Let \(P(x)\) be “\(x^3\ge 0\)” with domain the integers. Then \(\forall x \,P(x)\) is false. To show this, it is enough to provide a single counterexample. Because \((-2)^3=8\) and “\(-8 \gt 0\)” is false, so \(P(-2)\) is false. Thus \(\forall x \,P(x)\) is false.
🔗
🔗

Example 1.3.2.10. All dogs have brown fur.

Consider the statement “All dogs have brown fur.” This universally quantified statement is false. My dog Duey provides a counterexample.
🔗
Let’s examine this in more detail. Let \(B(x)\) be “\(x\) has brown fur,” with domain the set of all dogs. The universally quantified statement “All dogs have brown fur,” can be written as \(\forall x \,B(x)\) . This is false, because we can produce a counterexample, namely my dog Duey. He is a dog, so he is in the domain of \(B\) . He does not have brown fur, so \(B(\text{Duey})\) is false. Thus \(\forall x \,B(x)\) is false. In other words, not all dogs have brown fur.
🔗
🔗

Example 1.3.2.12. Squares of integers are positive.

Let \(P(x)\) be “\(x^2 \geq 0\)” with domain the integers. Then \(\forall x \,P(x)\) is true. To see this, fix a generic integer \(x\) . Then \(x^2\) is non-negative since the square of any real number is non-negative. Thus \(\forall x \,P(x)\) is true.
🔗
🔗

Proof.

Let \(a\) and \(b\) be integers. Starting on the left hand side of \(S(a,b)\) we get
\begin{align*} (a+b)(a-b)\amp = a(a-b)+b(a-b) \text{by the distirbutive law}\\ \amp=a^2-ab+ba-b^2\\ =a^2-b^2. \end{align*}
Thus \(S(a,b)\) is true for all integers \(a\) and \(b\text{.}\)
🔗
🔗
In the proof of Theorem 1.3.2.15 we will apply the following result:
🔗

Proof.

We use a generic element to prove Theorem 1.3.2.15.
  1. Let \(b\) be an integer.
    🔗
    🔗
  2. If \(b=0\) then \(b^2=a\cdot b=0\cdot 0=0\ge 0\) thus \(P(b)=P(0)\) is true.
    🔗
    🔗
🔗
If \(b\) is negative, by Theorem 1.3.2.14, we have that \(b^2=b\cdot b\) is positive. Thus for negative \(b\) we have \(P(b)\) is true.
🔗
If \(b\) is positive, by Theorem 1.3.2.14, we have that \(b^2=b\cdot b\) is positive. Thus for positive \(b\) we have \(P(b)\) is true.
🔗
Because each integer \(b\) is either equal to zero or negative or positive and \(b^2\ge 0\) in each of the three cases we have proven that \(b^2\ge 0\) for all integers \(b\text{.}\)
🔗
🔗
Figure 1.3.2.16. Certainty by Randal Muroe (https://xkcd.com/263/). \(a(b+c)=(ab)+ac\text{.}\) Polticize that bitches.
🔗
🔗
PrevTopNext