Skip to main content

Section 2.4 Predicate equivalence

Once we evaluate a quantifier on a predicate or a predicate on a subject, it becomes a statement. Therefore, rules of inference and equivalence apply in the predicate space as well. In this section we will learn additional rules involving quantifiers.

Hopefully the name of this theorem is familiar to you. In the following proof we will see that this theorem is called DeMorgan's law because it does, essentially, involve negating a disjunction or conjunction.

Consider the universal statement \(\forall x P(x)\) on the domain \(\Omega = \{x_1, x_2, \ldots x_n\}\text{.}\) We may rewrite

\begin{equation*} \forall x P(x) = P(x_1) \wedge P(x_2) \wedge \cdots \wedge P(x_n) \end{equation*}

and

\begin{equation*} \exists x P(x) = P(x_1) \vee P(x_2) \vee \cdots \vee P(x_n) \end{equation*}

Therefore,

\begin{equation*} \neg \forall x P(x) = \neg (P(x_1) \wedge P(x_2) \wedge \cdots \wedge P(x_n)) \end{equation*}

Using DeMorgan's law,

\begin{equation*} \neg \forall x P(x) = \neg P(x_1) \vee \neg P(x_2) \vee \cdots \vee \neg P(x_n) \end{equation*}

which is the same as the statement \(\exists x \neg P(x)\text{.}\)

That \(\neg \exists x P(x) \equiv \forall x \neg P(x)\) may be proven in the same way.

The idea is that a universal statement is a “big conjunction” and an existential statement is a “big disjunction.” The proof follows from the DeMorgan's laws you learned in when you learned propositional logic.

Let \(P(x)\) be the statement “\(x\) likes ice cream.”

Then, \(\forall x P(x)\) is the statement “Everyone likes ice cream” (depending on the domain). If \(\forall x P(x)\) is false, then that means someone doesn't like ice cream. It does not mean that no one likes ice cream! So, \(\neg \forall x P(x)\) is equivalent to \(\exists x \neg P(x)\text{,}\) “There is someone who does not like ice cream.”

On the other hand, \(\exists x P(x)\) is the statement “Someone likes ice cream.” If \(\exists x P(x)\) is false, then that does mean that no one likes ice cream. So, \(\neg \exists x P(x) \equiv \forall x \neg P(x)\text{,}\) “Everyone doesn't like ice cream.”

The next two theorems deal with how universal and existential statements may imply one another.

Let \(\forall x P(x)\text{.}\) If \(P\) is true for every member of its domain and \(a\) is a member of said domain, \(P\) must be true for \(a\text{.}\)

Let \(P(n)\) be the predicate, defined on the set of all numbers that are \(2\) or greater, that “\(n\) is the product of a unique set of prime factors.” The fundamental theorem of arithmetic says that \(\forall n P(n)\) is true on \(\mathbb{N}\text{.}\)

Therefore, universal instantiation says \(P(2)\) is true, \(P(3)\) is true, etc.

Let \(a\) be in the domain of \(P\text{.}\) If \(P(a)\) is true, then \(P\) is true for some member of its domain, so \(\exists x P(x)\text{.}\)

Let \(Q(x)\) be the predicate “\(x\) likes ice cream” and suppose that Carlos, denoted \(c\text{,}\) likes ice cream. Then since \(Q(c)\) is true, we may also conclude that \(\exists x Q(x)\) (“Someone likes ice cream”) is true.

There are two comments to make about these two theorems. First, universal generalization and existential instantiation are not valid. Consider the following example.

“I was able to easily pay for college, therefore everyone should be able to” is an example of invalid universal generalization.

“Someone in this room ate the last cookie, so it must have been you!” is an example of invalid existential instantiation.

The second comment is that transitivity can combine these two theorems.

When we negate quantified statements, good practice states that we push the negation inside the quantifier and end with something “readable”. Let's end on a couple such examples.

Let \(A(x)\) be the predicate “\(x\) attends the dance”, let \(W(x)\) be the predicate “\(x\) is a wallflower” (someone who attends the dance but does not dance), and \(D(x,y)\) be the predicate “\(x\) dances with \(y\text{.}\)”

First let's consider the statement \(\forall x \exists y[A(x) \to D(x,y)]\text{.}\) The statement has he form “Every ... is a” or “Every ... does ...” It seems as though everyone who attends the dance is something or does something. The predicate \(D(x,y)\) stands for “\(x\) dances with \(y\text{,}\)” and \(y\) is existentially quantified. So, “Everyone who attends the dance dances with someone.”

The negation of this statement is “Not everyone who attends the dance dances with someone,” or, “There is someone who attends the dance and dances with no one.” We can use DeMorgan's law to obtain this symbolization:

\begin{equation*} \neg \forall x \exists y [A(x) \to D(x,y)] \equiv \exists x \forall y \neg[A(x) \to D(x,y)] \end{equation*}

The negation of the conditional \(A(x) \to D(x,y)\) is the conjunction \(A(x) \wedge \neg D(x,y)\text{.}\)

\begin{equation*} \exists x \forall y \neg[A(x) \to D(x,y)] \equiv \exists x \forall y [A(x) \wedge \neg D(x,y)] \end{equation*}

This statement says “There is someone who attends the dance that fails to dance with every single person at the dance”, which means “There is someone who attends the dance and dances with no one.” This is the “readable” negation of the statement.

Next, let's consider the statement “There is someone who attends the dance who dances with all and only those people who are not wallflowers.” The quantifiers will be \(\exists x \forall y\text{,}\) but how to symbolize the rest? Well, we can think of “all and only” as an if-and-only-if statement. If this person dances with you, you are not a wallflower; conversely, if you are not a wallflower, then you will dance with this individual. Therefore the statement is

\begin{equation*} \exists x \forall y [A(x) \wedge (D(x,y) \leftrightarrow \neg W(y))] \end{equation*}

The first step in negating this statement is to negate the quantifiers as before:

\begin{equation*} \forall x \exists y \neg[A(x) \wedge (D(x,y) \leftrightarrow \neg W(y))] \end{equation*}

We might be able to immediately recognize the false conditional. If we can't, then instead, we can use DeMorgan's law and material implication:

\begin{align*} \forall x \exists y \neg[A(x) \wedge (D(x,y) \leftrightarrow \neg W(y))] \amp \equiv \forall x \exists y [\neg A(x) \vee \neg(D(x,y) \leftrightarrow \neg W(y))]\\ \amp \equiv \forall x \exists y [A(x) \to \neg(D(x,y) \leftrightarrow \neg W(y))] \end{align*}

The most important thing is we have now symbolized “Everyone who attends the dance does not dance with all and only the non-wallflowers”, which is the “readable” negation of the statement. It is possible to go further. The negations of \(p \leftrightarrow q\) are equivalently \(\neg p \leftrightarrow q\) and \(p \leftrightarrow \neg q\text{.}\) Choosing one, we could say

\begin{equation*} \forall x \exists y [A(x) \to (D(x,y) \leftrightarrow \neg W(y))] \end{equation*}