Rules of Inference for Quantified Statements

Universal instantiation

Assume for a domain $D$, $\forall x P(x)$ is known to be true. In that case, we can conclude that $P(c)$ is true, where $c$ is any domain element. Since it is known that all the elements of $D$ have the property $P$, any particular element $c$ from $D$ indeed has the property $P$. The process of concluding that an element of the domain has a certain property when it is known that all the elements of that domain have that property is called universal instantiation. Let’s explore this idea further with the help of a few examples.

Examples

Let’s have a look at a few examples.

---

Assume students of physics class as domain, and Maria is one of those students. Consider the statement $s$, stated below, to be true.

• $P(x)$: $x$ has passed the course.

• $s = \forall x P(x)$: All students of the physics class have passed the course.

---

Using universal instantiation, we can conclude that Maria has passed the course. Because Maria is among the students in the physics class, therefore $P($Maria$)$ is true.

---

Assume a set of all teachers as domain, and Jerry is a music teacher. Consider the following predicate:

• $N(x)$: $x$ is a nice person.

---

Given that the following statement $t$ is true.

• $t=\forall x N(x)$: All the teachers are nice.

Because Jerry is a teacher, using universal instantiation, we can conclude that Jerry is a nice person.

Universal generalization

If for some arbitrary element $c$ of the domain $P(c)$ is true, then we can conclude that $\forall x P(x)$ is true. It is important to note that $c$ is an arbitrary element, and we can not assume anything specific about $c$ other than its domain membership. The process of concluding that all the domain elements have a property by showing that a generic element has that property is a universal generalization.

Examples

Let’s look at some examples.

---

Assume a set of students taking a mathematics course as the domain. Consider the following predicate:

• $P(x)$: $x$ knows integer multiplication.

---

If it is a fact that any student $c$, who is taking a mathematics course $P(c)$, is true. Then, we can conclude that all the students taking a mathematics course have the property $P$. That is,

• $\forall x P(x)$: Every student taking a mathematics course knows integer multiplication.

---

Take the set of birds as the domain to make the following predicate:

• $B(x)$: $x$ has feathers.

---

Now, consider an arbitrary bird $c$. Be cautious that it is not a specific bird; rather, it is any bird who is a domain member. It is given that $B(c)$ is true. If it is true that we pick any member of the domain, it has the property $B$; then by using universal generalization, we can conclude that all birds have feathers. That is, $\forall x B(x)$ is true.

Existential instantiation

If $\exists x P(x)$ is true, we can conclude that $P(c)$ is true for some domain element. Note that $c$ is not any domain member; rather, it is some specific element from the domain for which $P(c)$ is true. In mathematical arguments, usually, we do not know about the specific element that holds the desired property; however, we know that it exists, and we give it a name to continue the argument with the evidence of its existence.

Examples

Let’s have a look at some examples.

---

Assume the domain to be the first hundred positive integers.

• $D=\{1,2,3,4,\ldots,100\}.$

---

We define the following predicate:

• $P(x)$: $x$ is a prime number, and $x^2+1$ is also a prime number.

Let’s quantify this predicate as follows:

• $\exists x P(x)$: There is some prime number $x\in D$ such that $x^2+1$ is also a prime number.

If the above statement is true, we can assume an element $a \in D$ that has property $P$. We know that two is a prime number and $(2^2+1=5)$ five is also a prime number. If we do not even know the element, sometimes mere evidence of its existence is of great help in constructing mathematical arguments.

Existential generalization

Assume a domain and a predicate $P$. If we have the evidence that for some element $c$ of the domain, $P(c)$ is true, then we can conclude that $\exists x P(x)$ is true. After knowing that an element of the domain has the property $P$, asserting that $\exists x P(x)$ is true is an existential generalization. We can apply existential generalization if the element $c$ with property $P$ is in our knowledge. Otherwise, we can apply existential generalization if we only know that an element with property $P$ exists without knowing exactly which element it is.

Examples

Let’s have a look at a few examples.

---

Assume the set of natural numbers as the domain and define the following predicate:

• $P(x)$: $x$ is an even prime number.

---

We know that two is an even prime number. Therefore, $P(2)$ is true. We can use existential generalization to establish that the following statement is true.

• $\exists x P(x):$ There exists a natural number that is an even prime.

---

Assume any non-empty finite subset of natural numbers as the domain and define the following predicate:

• $P(x)$: $x$ is the minimum number.

---

We know that whatever non-empty finite subset of natural numbers we take, there will be an element that is the smallest number. Which number would this be? It depends on the selection of the domain set. As we know that the smallest number exists, we assert that the following statement is true.

• $\exists x P(x)$: Any non-empty finite subset of natural numbers has a minimum.

Universal modus ponens

Assume that we have two predicates $P$ and $Q$ for a domain, and we are given the following statement.

$$\forall x\left(P(x)\Rightarrow Q(x)\right).$$

And for some domain element $c$, we have $P(c)$, then we can conclude $Q(c)$ by universal modus ponens. We break it down into two steps to see the reason behind it. First, use universal instantiation to get the following statement:

$$P(c)\Rightarrow Q(c).$$

We also have $P(c)$; therefore, as the second step, we use normal modus ponens to conclude $Q(c)$.

Examples

Let’s have a look at some examples.

---

Assume a class of students taking linear algebra as the domain. Define the following two predicates:

• $P(x)$: $x$ has secured an A grade.
• $Q(x)$: $x$ has worked hard.

---

Lois is taking linear algebra and has secured an A grade. Consider the following two statements as true:

• $\forall x \left(P(x)\Rightarrow Q(x)\right)$: Every student who secured an A grade has worked hard.

• $P($Lois$)$: Lois has secured an A grade.

We can use universal modus ponens to conclude the following statement:

• $Q($Lois$)$: Lois has worked hard.

---

Consider the set of natural numbers as the domain and define the following predicates:

• $P(x)$: $x$ is a composite number.

• $Q(x)$: $x$ has a factor that is greater than one.

---

Now consider the following two statements as true:

• $\forall x (P(x)\Rightarrow Q(x))$: If a natural number is composite, then it has a factor that is greater than one.

• $P(93)$: 93 is a composite number.

By using universal modus ponens, we can conclude the following statement.

• $Q(93)$: 93 has a factor that is greater than one.

We know that both $3$ and $31$ are factors of $93$.

Universal modus tollens

Assume that we have two predicates $P$ and $Q$ for a domain, and we are given the following statement:

$$\forall x\left(P(x)\Rightarrow Q(x)\right).$$

And for some domain element $c$, we have $\neg Q(c)$; then we can conclude $\neg P(c)$ by universal modus tollens. We break it down into two steps to see the reason behind it. First, use universal instantiation to get the following statement:

$$P(c)\Rightarrow Q(c).$$

We also have $\neg Q(c)$, so as the second step, we use normal modus tollens to conclude $\neg P(c)$.

Examples

Let’s have a look at a few examples.

---

Consider the domain is all living things. We define the following predicates:

• $P(x)$: $x$ is a bird.
• $Q(x)$: $x$ has feathers.

---

• $\forall x \left(P(x)\Rightarrow Q(x)\right):$ All birds have feathers.

• $\neg Q($Thomas$)$: Thomas does not have feathers.

We can conclude the following statement by applying universal modus tollens to the above-mentioned statements.

• $\neg P($Thomas$)$: Thomas is not a bird.

---

In Euclidean geometry, a regular polygon has all sides equal and angles equal. Consider the set of polygons as the domain. Define the following predicates:

• $R(x)$: $x$ is a regular polygon.
• $E(x)$: $x$ has all sides of equal length.

---

• $\forall x \left(R(x)\Rightarrow E(x)\right)$: Every regular polygon has all sides equal.

Let $r$ be any right-angled triangle. We know that.

• $\neg E(r)$: $r$ does not have all sides of equal length.

By applying universal modus tollens, we can conclude the following statement:

• $\neg R(r)$: $r$ is not a regular polygon.