Existential 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. We can ask if any element in the domain has the desired property or not. We do so by using an existential quantifier. Existentially quantifying a predicate means that the proposition resulting from that predicate is true for at least one domain element. Therefore, we get a proposition by applying an existential quantifier to a predicate. The motivation is to make propositions without referring to a specific domain element.

Existential quantifier

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

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

To mention the existence of an $x$ in discrete math class that has the property $P$, we need to quantify the predicate. We use the symbol $\exists$ to represent existential quantification, and we read this symbol as “there exists.”

• $\exists x P(x)$: There exists an $x, P(x)$.

The domain of this predicate is the discrete math class. The meaning of $P(x)$ is as above, but the part, ‘$\exists x$,’ requires a domain to make sense. Once the domain is explicit, $\exists$ refers to at least one member.

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

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

We can interpret $\exists x P(x)$ as follows:

$$\exists x P(x) = P(e_1)\lor P(e_2)\lor P(e_3)\lor \ldots \lor P(e_n).$$

That means $\exists x P(x)$ is true if and only if $P(x)$ is true for at least one domain element.

If a predicate has more than one variable, we can use an existential quantifier for each of them as follows.

• $\exists x \exists y \exists z P(x,y,z)$: There exists an $x$ and exists a $y$ and exists a $z$, $P(x,y,z).$

Let’s look at a few examples to clarify it further.

Truth value

The existentially quantified statement is true if we can show at least one element from the domain for which the quantified predicate is true. For example, if the domain is $D$,

$$\exists x P(x),$$

is true if, for some $a\in D$, $P(a)$ is true. It is false if, for every element, $e$, in $D$ the proposition $P(e)$ is false.

Examples

Let’s take a look at a few examples.

---

Consider the following statement for real numbers:

• $\exists x S(x)$, where $S(x)$: $x^2 < x.$

---

To establish that the above statement is true, we only have to find one element in the domain with the property $P$. As

$$(0.5)^2<0.5,$$

Therefore, $\exists x S(x)$ is true.

---

Take the set of positive integers as the domain and consider the following statement, $s$.

• $s$: $\exists x \exists y \exists z P(x,y,z)$.

Where, $P(x,y,z): x^2+y^2=z^2.$

---

If we want to show that $s$ is false, we have to show that there are no positive integers $x,y,$ and $z$ for which $P(x,y,z)$ is true. This means looking at all the positive integers, which can be cumbersome.

If we want to show that statement $s$ is true, we only have to present three positive integers $(a,b,c)$, which are not necessarily unique, for which $P(a,b,c)$ is true.

The statement $s$ is true because, $P(3,4,5)$ is true.

$$3^2+4^2 = 5^2.$$

---

Consider the following predicate for the next example:

• $A(x)$: The student $x$ has an A grade in all the subjects on the transcript.

---

Let’s say that Cambridge University is the domain.

The predicate $\exists x A(x)$ is true if there is at least one such student at Cambridge University, and it is false if there is no such student.

---

Consider the following predicate:

• $R(x)$: $x$ is a regular polygon whose all interior angles are acute.

---

If the domain is the regular polygons, we can make the following proposition:

$$q: \exists x R(x).$$

Is $q$ true or false? To show that $q$ is true, we only have to show a regular polygon whose all interior angles are acute. To show that $q$ is false, we have to show that there is no such regular polygon whose all internal angles are acute.

The proposition $q$ is true because we can make a triangle with all three angles equal sixty degrees.

---

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: \exists_{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\ngtr 50$	F
$1$	$1^3\ngtr 50$	F
$2$	$2^3\ngtr 50$	F
$3$	$3^3\ngtr 50$	F
$4$	$4^3>50$	T

Hence, $x=4$ is the instance for which $S(x)$ is true. Therefore, $g$ is true.

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

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

Now,

$$g: \exists x (C(x)\land S(x)).$$

We can put $x=4$ to verify that $g$ is true.

Quiz