Universal Quantifiers

Motivation

We make a proposition from a predicate by assigning a particular value to its variable(s). The value we can give to a variable is from a domain. We can also make a proposition from a predicate without assigning a particular value to its variable. One way to do so is by referring to all the domain elements. Universally quantifying a predicate means that the proposition resulting from that predicate is true for every element of the domain. Therefore, we get a proposition by applying a universal quantifier to a predicate. The motivation is to make propositions without referring to a particular domain element.

Universal quantifier

We use universal quantifiers to claim that every domain member has the property mentioned by a predicate. They quantify a variable in a predicate for a particular domain. To say that every student in discrete math class has passed twelfth grade or equivalent, we make a predicate $T(x)$.

• $T(x)$: $x$ has passed twelfth grade or equivalent.

To say that every $x$ in discrete math class has the property $T$, we need to quantify it. We use the symbol $\forall$ to represent universal quantification, and we read this symbol as “for all.”

• $\forall x T(x)$: For all $x, T(x)$.

The domain of this quantification is the discrete math class. The meaning of $T(x)$ is as above, but the part, “$\forall x$,” requires a domain to make sense. Once the domain is explicit, $\forall$ refers to each member of it.

Assume the domain, $D$, has $n$ elements. That is,

$$D = \{e_1,e_2,e_3, \ldots, e_n\}.$$

For some arbitrary predicate $P$, we can interpret $\forall x P\left(x\right)$ as follows:

$$\forall x P(x) = P(e_1)\land P(e_2)\land P(e_3)\land \ldots \land P(e_n).$$

That means $\forall x P(x)$ is true if and only if $P(x)$ is true for every domain element. This way, we can intuitively think about the universal quantifier as a big conjunction of instantiated predicates.

If a predicate has more than one variable, for example, $P(x,y,z)$, we can universally quantify each of them as follows:

• $\forall x \forall y \forall z P(x,y,z):$ For all $x$ and for all $y$ and for all $z$, $P(x,y,z).$

Truth value

The statement $\forall x P(x)$ is true when every element from the considered domain has the property $P$. It is false if we can show at least one element from the domain that does not have the property $P$. We call such an element a counterexample.

Let’s look at a few examples to clarify further the concept of universal quantification and the truth value of quantified statements.

Examples

Let’s take a look at a few examples.

---

Consider the following predicate:

• $S(x)$: The student $x$ is at least 16 years old.

---

Assume that the domain is the department of computer science at Oxford University. We can quantify $S(x)$ as follows:

• $\forall x S(x)$: Every student (in the computer science department) is at least 16 years old.

Be cautious about the domain while interpreting this statement; it can change the meaning and the truth value of the statement.

Let’s take another example with more than one variable.

---

Consider Mr. John’s family. Mr. and Mrs. John have three kids. All five of them are friends with each other. We want to write this fact as a mathematical statement. We define the following predicate:

• $F(x,y)$: $x$ and $y$ are friends.

---

If the domain is Mr. John’s family, then the universal quantification of $F(x,y)$ can be interpreted as follows:

• $\forall x \forall y F(x,y)$: Everyone (in Mr. John’s family) is friends with everyone (in Mr. John’s family).

• $\forall x \forall y F(x,y)$ is true for Mr. John’s family. But if we take the domain to be all citizens of the USA. Then, $\forall x \forall y F(x,y)$ is false if we can find only two citizens of the USA who are not friends with each other.

---

For the following example, note that the predecessor of a number is the one that is preceding it. For example, the predecessor of twelve is eleven.

• $C(x)$: if $x>1$ then $x$ has a predecessor.

---

There are two properties in the above statement. The first one is “$x>1$,” and the second one is, “$x$ has a predecessor.” Let’s make separate predicates for each of them.

• $G(x)$: $x>1$, and $R(x)$: $x$ has a predecessor.

Now we can write $C(x)$ as follows.

$$C(x): G(x) \Rightarrow R(x).$$

If we consider the integers to be the domain, we can see that $\forall xC(x)$ is true.

---

Consider the following statement:

• $\forall x S(x)$, where $S(x): x^2 \ge x$.

---

If the domain is integers, this statement is true, but if it is rational numbers or real numbers, it is false. As $(0.5)^2 \ngeqslant 0.5$, therefore, $0.5$ is a counterexample for both rational and real numbers. Similarly, because $\left(\frac{1}{\sqrt 2} \right)^2 \ngeqslant \frac{1}{\sqrt 2}$, therefore, $\frac{1}{\sqrt 2}$ is another counterexample for real numbers.

We should notice that the domain set is infinite in the last example. As explained in the following example, we can restrict the domain by putting a condition right after the quantifier.

---

Consider the predicate,

• $S(x)$: $x^3 < 50.$

---

Assume the set of integers as the domain. We make the following proposition, $g$, by quantification.

$$g: \forall_{x < 5} S(x).$$

Is $g$ true or false? The variable $x$ can be any negative integer, zero, or positive integer less than five.

• The cube of a negative integer is also a negative integer, which is less than fifty.
• The rest of the possibilities are shown in the following table:

Value	$S(x)$	Truth-Value
$0$	$0^3<50$	T
$1$	$1^3<50$	T
$2$	$2^3<50$	T
$3$	$3^3<50$	T
$4$	$4^3<50$	F

Therefore, $x=4$ is a counterexample, as $4^3\nless 50$. Therefore, $g$ is false.

We can write $g$ in another way. Make another predicate as follows.

$$C(x): x<5.$$

Now,

$$g: \forall x\left(C\left(x\right)\Rightarrow S(x)\right).$$

We can put the counterexample to verify that $g$ is still false.