Discrete Math

Subsection 2.6.1 Quantifiers

Then,

Then,

Sometimes, if the domain \(D\) is implicit, we simply write, \(\forall x, P(x)\) and \(\exists x, P(x)\text{.}\)

Subsection 2.6.2 Using Quantifiers

To show that a existential statement is true, it is sufficient to provide a single example \(x\) that satisfies \(P(x)\text{.}\) To prove it is false requires proving that \(P(x)\) is false for all values of \(x\text{.}\)

To show that an universal statement is true, this requires proving that \(P(x)\) is true for all values of \(x\text{.}\) To prove it is false, it is sufficient to provide one example where it is false (called a counterexample).

If the domain of \(P(x)\) is finite, say \(\set{x_1, \dots, x_n}\text{,}\) then,

In this case, proving the universal statement can be reduced to showing that each of the statements \(P(x_1), \dots, P(x_n)\) is true (called the method of exhaustion). This brute force technique is particularly more applicable with the rise of computing power, allowing for a large numebr of calculations to be done in a shorter period of time. However, this method can't be used if the set is infinite.

This also makes it clear that \(\forall x, P(x)\) is a stronger statement than \(\exists x, P(x)\text{.}\) In other words,

Subsection 2.6.3 Uniquness Quantifier

Subsection 2.6.4 Quantifiers and Conditionals

The statement, \(\forall x \in S, P(x)\) means that for all elements \(x\) in the set \(S\text{,}\) the statement \(P(x)\) is true. This is equivalent to saying that the conditional, “If \(x\) is any element of \(S\text{,}\) then \(P(x)\) is true”. In symbols, this can be summarized as,

A statement of the form \(x \in S \rightarrow P(x)\) is said to be implicit quantification.

Subsection 2.6.5 Negating Quantifiers (De Morgan's Laws)

Previously, we saw that the universal statement \(\forall x, P(x)\) is false if and only if there is at least one \(x\) such that \(P(x)\) is false. Analogously, the existential statement \(\exists x, P(x)\) is false if and only if \(P(x)\) is false for every value of \(x\text{.}\)

Roughly, this shows that the negation of a universal statement is an existential statement, and the negation of an existential statement is a universal statement. In particular,

Intuitively, this means that to negate a quantified statement, “negate” both parts, i.e. flip \(\forall\) to \(\exists\) and vise versa, and negate the statement \(P(x)\text{.}\)

This duality between universal and existental statements, are analogous to de Morgan's laws, which show a duality between “or” and “and” statements. This similarity can be seen more precisely if the domain of \(P(x)\) is finite, say \(\set{x_1, \dots, x_n}\text{.}\) Then, recall that,

Then, by De Morgan's laws,

and similarly,

This reasoning only applies to finite sets, but the rules for negation of quantified statements applies to any domain set. In this sense, universal statements are a generalization of “and” statements, and existential statements are a generalization of “or” statements.

Subsection 2.6.6 Universal Conditional Statements

Sometimes, universal statements are false, but they are true if the domain \(D\) is restricted by some hypotheses \(P(x)\text{.}\) That is, if \(P(x)\) is satisfied, then the universal statement is true. This leads to the universal conditional.

If \(S\) is defined to be the subset of \(D\) such that \(P(x)\) is true, then an equivalent statement is,

In other words,

Subsection 2.6.7 Negation of a Universal Conditional

Recall that the negation of a universal statement \(\forall x, P(x) \rightarrow Q(x)\text{,}\) is given by,

Then, recall that the negation of a conditional is given by

Then, putting things together,

Subsection 2.6.8 Vacuous Truth of Universal Statements

Here is a comic that illustrates vacuous truth.

Subsection 2.6.9 Nested Quantifiers

With multiple quantifiers, we proceed from left to right.

• \(\exists x, \exists y, P(x,y)\) means that there exists \(x\) and \(y\) such that \(P(x,y)\) is true.

• \(\forall x, \forall y, P(x,y)\) means that for all \(x\) and \(y\text{,}\) \(P(x,y)\) is true.

• \(\forall x, \exists y, P(x,y)\) means that for all \(x\text{,}\) there exists a \(y\) such that \(P(x,y)\) is true.

• \(\exists x, \forall y, P(x,y)\) means that there exists \(x\text{,}\) such that for all \(y\text{,}\) \(P(x,y)\) is true.

The first statement means that given a particular value of \(x\text{,}\) there exists a \(y\) (which can depend on \(x\)) such that \(P(x,y)\) is true. In contrast, the second statement says that there exists a value of \(x\) (which is chosen first), such that \(P(x,y)\) is true for all values of \(y\text{.}\) The difference is the order in which the variables are chosen. The second kind of mixed quantifiers is often a stronger statement.