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.