Section1pt3

The Proof Page

by D. A. Kouba

Section 1.3- Universal Quantifier (For all x ...); Existential Quantifier (There exists x ...); Unique Existential Quantifier (There exists a unique x ...)

$\underline { \rm DEFINITION }$ : A sentence containing one or more variables is called an $\underline { \rm open \ sentence }$ .

$\underline { \rm NOTE }$ : An open sentence is NOT a proposition because it is neither true nor false until all of its variables are replaced with values.

$\underline { \rm EXAMPLE }$ : The expression

is an open sentence. Define

to be the open sentence

. Then

means

, which is a true proposition, and

means

, which is a false proposition.

$\underline { \rm EXAMPLE }$ : Define

to be the open sentence

. Then

means

, which is a true proposition, and

means

, which is a false proposition.

$\underline { \rm DEFINITION }$ : The set of objects

(or

) available for consideration (substitution) in an open sentence

(or

) is called a $\underline { \rm universe }$ . The set of elements

(or

) which makes

(or

) true is called the $\underline { \rm truth \ set }$ .

$\underline { \rm EXAMPLE }$ : Let the universe be the set of all real numbers for the open sentence

. Then the truth set is $\{ 2, -3 \}$ . Let the universe be the set of all positive integers for the open sentence

. Then the truth set is $\{ 2 \}$ .

$\underline { \rm DEFINITION }$ : Let

be an open sentence with variable

1.) The $\underline { \rm universal \ quantifier }$ is the sentence $( \forall x ) P(x)$ (`` For all , ") and is true exactly when the truth set for is the entire universe. In other words, all elements in the universe make true.
2.) The $\underline { \rm existential \ quantifier }$ is the sentence $( \exists x ) P(x)$ (`` There exists such that ") and is true exactly when the truth set for is not empty. In other words, there exists at least one element in the universe for which is true.
3.) The $\underline { \rm unique \ existence \ quantifier }$ is the sentence $( \exists ! x ) P(x)$ (`` There exists a unique such that ") and is true exactly when the truth set for has exactly one element. In other words, there exists exactly one element in the universe for which is true.

The previous definitions of quantifiers are somewhat abstract and technical, and may appear to be fairly msysterious. However, careful examination of the following examples will likely make them very understandable.

$\underline { \rm EXAMPLE }$ :

1.) Let the universe be the set of all real numbers and consider the open sentence $P(x) : x^2+1 \ge 0$ . Consider the quantified sentence $( \forall x ) P(x)$ . This sentence is true since it is true for every element in the universe.
2.) Let the universe be the set of all complex numbers and consider the open sentence $P(x) : x^2+1 \ge 0$ . Consider the quantified sentence $( \forall x ) P(x)$ . This sentence is false since it is false for some elements in the universe. For example, is false since .
3.) Let the universe be the set of all real numbers and consider the open sentence . Consider the quantified sentence $( \exists x ) P(x)$ . This sentence is true since it is true for at least one element in the universe. In fact, the truth set is $\{ 0, 5 \}$ .
4.) Let the universe be the set of all real numbers and consider the open sentences is an integer, and is a perfect square. Consider the quantified sentence $( \exists x ) (Q(x) \wedge R(x))$ . This sentence is true since it is true for at least one element in the universe. For example, and make the sentence true. The truth set contains infinitely many elements.
5.) (Pay close attention to the logic in this example.) Let the universe be the set of all real numbers and consider the open sentences is a natural number, and is a natural number. Consider the quantified sentence $( \forall x ) (Q(x) \Rightarrow R(x))$ . This sentence is true since it is true for every element in the universe ! For example, if is a natural number, then $Q(x) \Rightarrow R(x)$ is a true statement since both and are true. If is NOT a natural number, then $Q(x) \Rightarrow R(x)$ is a still a true statement since is false ! Thus, $Q(x) \Rightarrow R(x)$ is a true statement for every element in the universe.
6.) Let the universe be the set of all real numbers and consider the open sentence . Consider the quantified sentence $( \exists ! x ) P(x)$ . This sentence is true since it is true for exactly one element in the universe. It is true for .
7.) Let the universe be the set of all real numbers and consider the open sentence . Consider the quantified sentence $( \forall y)( \exists ! x ) P(x,y)$ . This sentence is true (since is an increasing function). If is any element in the universe, then $x= (y-4)^{1/3}$ is the unique solution to .

$\underline { \rm NOTE }$ : In general, QUANTIFIERS DO NOT COMMUTE. In Example 7 just completed, $( \forall y)( \exists ! x ) P(x,y)$ and $( \exists ! x )( \forall y) P(x,y)$ have distinct meanings. The statement $( \forall y)( \exists ! x ) P(x,y)$ is already explained. The statement $( \exists ! x )( \forall y) P(x,y)$ means that there is a single, unique real number

so that

for all real numbers

. In fact, this second statement is false.

$\underline { \rm EXAMPLE }$ : Let the universe be the set of all animals. Consider the open sentences

is a dog,

chases cars, and

eats vegetables. Rewrite each of the following common sentences in symbolic quantifier form. Find solutions HERE .

1.) Some dogs eat vegetables.
2.) All dogs chase cars.
3.) No dogs chase cars.
4.) There are some animals which chase cars but do not eat vegetables.

$\underline { \rm EXAMPLE }$ : Write a logical, meaningful denial of each sentence in ordinary English. Find solutions HERE .

1.) Some cats like water.
2.) Some cats don't like water.
3.) No cats like water.
4.) All cats like water.

The following theorem formally addresses the negation of quantified sentences.

$\underline { \rm THEOREM \ 1.3 }$ : Let

be an open sentence with variable

a.) $\sim ( \forall x) A(x)$ is equivalent to $( \exists x) ( \sim A(x) )$ .
b.) $\sim ( \exists x) A(x)$ is equivalent to $(\forall x) (\sim A(x))$ .

$\underline { \rm PROOF }$ : a.) (NOTATION : Assume that `` $\Leftrightarrow$ " has the same meaning as `` if and only if " has the same meaning as `` iff .") We will show that $\sim ( \forall x) A(x)$ and $( \exists x) ( \sim A(x) )$ have the same truth values. First,

$\sim ( \forall x) A(x)$ is TRUE

iff

$( \forall x) A(x)$ is FALSE

iff

The truth set for is NOT the entire universe

iff

There is at least one element in the truth set for which $\sim A(x)$

iff

$( \exists x) ( \sim A(x) )$ is TRUE .

Second,

$\sim ( \forall x) A(x)$ is FALSE

iff

$( \forall x) A(x)$ is TRUE

iff

The truth set for is the entire universe

iff

The truth set for $\sim A(x)$ is empty

iff

$( \exists x) ( \sim A(x) )$ is FALSE.

Thus, $\sim ( \forall x) A(x)$ and $( \exists x) ( \sim A(x) )$ have the same truth values.

b.) The proof that $\sim ( \exists x) A(x)$ is equivalent to $(\forall x) (\sim A(x))$ is analogous to the proof of part a.).

$\underline { \rm EXAMPLE }$ : Let the universe be the set of all animals. Consider the open sentences

is a dog ,

chases cars, and

eats vegetables. Rewrite each of the following common sentences in symbolic quantifier form. Use Theorems 1.2 and 1.3 to write formal denials of these statements. Finish by writing a meaningful denial in ordinary English. Find solutions HERE .

1.) Some dogs eat vegetables.
2.) All dogs chase cars.
3.) No dogs chase cars.
4.) There are some animals, which chase cars but do not eat vegetables.

$\underline { \rm EXAMPLE }$ : In calculus we learn that if function

is continuous at

, then the following formal $\epsilon,\delta$ definition is true. For every real number $\epsilon > 0$ there exists another real number $\delta > 0$ so that if $\vert x-a\vert < \delta$ , then $\vert f(x) - f(a) \vert < \epsilon$ . Without loss of generality and for the sake of relative simplicity, assume that

and let the universe be the set of all positive real numbers. Consider the open sentences $Q( \delta, x ) : \vert x-a\vert < \delta$ and $R( \epsilon, x) : \vert f(x) - f(a) \vert < \epsilon$ . We can now rewrite the $\epsilon,\delta$ definition in symbolic quantifier form as

$( \forall \epsilon )( \exists \delta ) [ ( \forall x ) \{ Q( \delta, x) \Rightarrow R( \epsilon, x) \} ]$ .

Next we will use Theorems 1.2 and 1.3 to write a formal denial of this statement, distributing the negation as far as possible, and finish by writing a meaningful denial in ordinary English. Then

$\sim ( \forall \epsilon )( \exists \delta ) [ ( \forall x ) \{ Q( \delta, x) \Rightarrow R( \epsilon, x) \} ]$

iff

$( \exists \epsilon ) \sim ( \exists \delta ) [ ( \forall x ) \{ Q( \delta, x) \Rightarrow R( \epsilon, x) \} ]$ . . . . . . (By Theorem 1.3 a.)

iff

$( \exists \epsilon ) ( \forall \delta ) \sim [ ( \forall x ) \{ Q( \delta, x) \Rightarrow R( \epsilon, x) \} ]$ . . . . . . (By Theorem 1.3 b.)

iff

$( \exists \epsilon ) ( \forall \delta ) [ \sim ( \forall x ) \{ Q( \delta, x) \Rightarrow R( \epsilon, x) \} ]$

iff

$( \exists \epsilon ) ( \forall \delta ) [ ( \exists x ) \sim \{ Q( \delta, x) \Rightarrow R( \epsilon, x) \} ]$

iff

$( \exists \epsilon ) ( \forall \delta ) [ ( \exists x ) \sim \{ R( \epsilon, x) \vee \sim Q( \delta, x) \} ]$ . . . . . . (By Theorem 1.2 d.)

iff

$( \exists \epsilon ) ( \forall \delta ) [ ( \exists x ) \{ \sim R( \epsilon, x) \wedge Q( \delta, x) \} ]$ . . . . . . (By Theorem 1.2 c.)

iff

There exists an $\epsilon > 0$ so that, for all $\delta > 0$ , there exists a real number satisfying $\vert x-a\vert < \delta$ but $\vert f(x) - f(a) \vert \not< \epsilon$ .

$\underline { \rm EXAMPLE }$ : Write each of the following statements in symbolic quantifier form. Write a denial in symbolic quantifier form, distributing the negation as far as possible. Finish by writing a meaningful denial in ordinary English. Let the universe be the set of all real numbers. Find solutions HERE .

1.) For all real numbers there is another real number so that . Consider the open sentence .
2.) For each real number there is another real number so that if $x^2 \le y^2$ , then $x-y \le 0$ or $x+y \le 0$ . Consider the open sentences $P(x, y) : x^2 \le y^2$ , $Q(x, y) : x-y \le 0$ , and $R(x, y) : x+y \le 0$ .

RETURN to The Proof Page .

Please e-mail your comments, questions, or suggestions to D. A. Kouba at kouba@math.ucdavis.edu .

Next: About this document ...

Duane Kouba 2002-06-05