2 Logical Reasoning

2.4 Quantifiers and Negations

2.4.1 Beginning Activity 1 (An Introduction to Quantifiers)

We have seen that one way to create a statement from an open sentence is to substitute a specific element from the universal set for each variable in the open sentence. Another way is to make some claim about the truth set of the open sentence. This is often done by using a quantifier. For example, if the universal set is $ℝ$, then the following sentence is a statement.

For each real number $x,x^2>0$.

The phrase "For each real number $x$" is said to quantify the variable that follows it in the sense that the sentence is claiming that something is true for all real numbers. So this sentence is a statement (which happens to be false).

Definition. The phrase "for every" (or its equivalents) is called a universal quantifier. The phrase "there exists" (or its equivalents) is called an existential quantifier. The symbol $\forall$ is used to denote a universal quantifier, and the symbol $\exists$ is used to denote an existential quantifier.

Using this notation, the statement "For each real number $x,x^2>0$" could be written in symbolic form as: $(\forall x\in ℝ)\left(x^2>0\right)$. The following is an example of a statement involving an existential quantifier.

$$\text{ There exists an integer }x\text{ such that }3x-2=0\text{. }$$

This could be written in symbolic form as

$$(\exists x\in \mathbb{Z})(3x-2=0).$$

This statement is false because there are no integers that are solutions of the linear equation $3x-2=0$. Table 2.4 summarizes the facts about the two types of quantifiers.

A statement involving	Often has the form	The statement is true provided that
A universal quantifier: $(\forall x,P(x))$	"For every $x,P(x)$," where $P(x)$ is a predicate.	Every value of $x$ in the universal set makes $P(x)$ true .
An existential quantifier: $(\exists x,P(x))$	"There exists an $x$ such that $P(x)$," where $P(x)$ is a predicate.	There is at least one value of $x$ in the universal set that makes $P(x)$ true.

Table 2.4: Properties of Quantifiers

In effect, the table indicates that the universally quantified statement is true provided that the truth set of the predicate equals the universal set, and the existentially quantified statement is true provided that the truth set of the predicate contains at least one element.

Each of the following sentences is a statement or an open sentence. Assume that the universal set for each variable in these sentences is the set of all real numbers. If a sentence is an open sentence (predicate), determine its truth set. If a sentence is a statement, determine whether it is true or false.

1. $(\forall a\in ℝ)(a+0=a)$.

2. $3x-5=9$.

3. $\sqrt{x}\in ℝ$.

4. $\sin (2x)=2(\sin x)(\cos x)$.

5. $(\forall x\in ℝ)(\sin (2x)=2(\sin x)(\cos x))$.

6. $(\exists x\in ℝ)\left(x^2+1=0\right)$.

7. $(\forall x\in ℝ)\left(x^3\ge x^2\right)$.

8. $x^2+1=0$.

9. If $x^2\ge 1$, then $x\ge 1$.

10. $(\forall x\in ℝ)($ If $x^2\ge 1$, then $x\ge 1)$.

2.4.2 Beginning Activity 2 (Attempting to Negate Quantified Statements)

1. Consider the following statement written in symbolic form:
   $(\forall x\in \mathbb{Z})(x$ is a multiple of 2$)$.

   1. Write this statement as an English sentence.

   2. Is the statement true or false? Why?

   3. How would you write the negation of this statement as an English sentence?

   4. If possible, write your negation of this statement from part (2) symbolically (using a quantifier).

2. Consider the following statement written in symbolic form:
   $(\exists x\in \mathbb{Z})\left(x^3>0\right)$.

   1. Write this statement as an English sentence.

   2. Is the statement true or false? Why?

   3. How would you write the negation of this statement as an English sentence?

   4. If possible, write your negation of this statement from part (2) symbolically (using a quantifier).

We introduced the concepts of open sentences and quantifiers in Section 2.3. Review the definitions in Section 2.3 and Section 2.4.

2.4.3 Forms of Quantified Statements in English

There are many ways to write statements involving quantifiers in English. In some cases, the quantifiers are not apparent, and this often happens with conditional
statements. The following examples illustrate these points. Each example contains a quantified statement written in symbolic form followed by several ways to write the statement in English.

1. $(\forall x\in ℝ)\left(x^2>0\right)$.

   • For each real number $x,x^2>0$.

   • The square of every real number is greater than 0 .

   • The square of a real number is greater than 0 .

   • If $x\in ℝ$, then $x^2>0$.

   In the second to the last example, the quantifier is not stated explicitly. Care must be taken when reading this because it really does say the same thing as the previous examples. The last example illustrates the fact that conditional statements often contain a "hidden" universal quantifier.

   If the universal set is $ℝ$, then the truth set of the open sentence $x^2>0$ is the set of all nonzero real numbers. That is, the truth set is

   $$\{x\in ℝ\mid x\ne 0\}.$$

   So the preceding statements are false. For the conditional statement, the example using $x=0$ produces a true hypothesis and a false conclusion. This is a counterexample that shows that the statement with a universal quantifier is false.

2. $(\exists x\in ℝ)\left(x^2=5\right)$.

   • There exists a real number $x$ such that $x^2=5$.

   • $x^2=5$ for some real number $x$.

   • There is a real number whose square equals 5.

   The second example is usually not used since it is not considered good writing practice to start a sentence with a mathematical symbol.

   If the universal set is $ℝ$, then the truth set of the predicate "$x^2=5$" is $\{-\sqrt{5},\sqrt{5}\}$. So these are all true statements.

2.4.4 Negations of Quantified Statements

In Beginning Activity 1, we wrote negations of some quantified statements. This is a very important mathematical activity. As we will see in future sections, it is sometimes just as important to be able to describe when some object does not satisfy a certain property as it is to describe when the object satisfies the property. Our next task is to learn how to write negations of quantified statements in a useful English form.

We first look at the negation of a statement involving a universal quantifier. The general form for such a statement can be written as $(\forall x\in U)(P(x))$, where $P(x)$ is an open sentence and $U$ is the universal set for the variable $x$. When we write

$$\neg (\forall x\in U)[P(x)],$$

we are asserting that the statement $(\forall x\in U)[P(x)]$ is false. This is equivalent to saying that the truth set of the open sentence $P(x)$ is not the universal set. That is, there exists an element $x$ in the universal set $U$ such that $P(x)$ is false. This in turn means that there exists an element $x$ in $U$ such that $\neg P(x)$ is true, which is equivalent to saying that $(\exists x\in U)[\neg P(x)]$ is true. This explains why the following result is true:

$$\neg (\forall x\in U)[P(x)]\equiv (\exists x\in U)[\neg P(x)].$$

Similarly, when we write

$$\neg (\exists x\in U)[P(x)],$$

we are asserting that the statement $(\exists x\in U)[P(x)]$ is false. This is equivalent to saying that the truth set of the open sentence $P(x)$ is the empty set. That is, there is no element $x$ in the universal set $U$ such that $P(x)$ is true. This in turn means that for each element $x$ in $U,\neg P(x)$ is true, and this is equivalent to saying that $(\forall x\in U)[\neg P(x)]$ is true. This explains why the following result is true:

$$\neg (\exists x\in U)[P(x)]\equiv (\forall x\in U)[\neg P(x)].$$

We summarize these results in the following theorem.
Theorem 2.16. For any open sentence $P(x)$,

$\neg (\forall x\in U)[P(x)]\equiv (\exists x\in U)[\neg P(x)],\text{ and}$

$\neg (\exists x\in U)[P(x)]\equiv (\forall x\in U)[\neg P(x)].$

2.4.5 Example 2.17 (Negations of Quantified Statements)

Consider the following statement: $(\forall x\in ℝ)\left(x^3\ge x^2\right)$.
We can write this statement as an English sentence in several ways. Following are two different ways to do so.

• For each real number $x,x^3\ge x^2$.

• If $x$ is a real number, then $x^3$ is greater than or equal to $x^2$.

The second statement shows that in a conditional statement, there is often a hidden universal quantifier. This statement is false since there are real numbers $x$ for which $x^3$ is not greater than or equal to $x^2$. For example, we could use $x=-1$ or $x=\frac{1}{2}$.

This means that the negation must be true. We can form the negation as follows:

$$\neg (\forall x\in ℝ)\left(x^3\ge x^2\right)\equiv (\exists x\in ℝ)\neg \left(x^3\ge x^2\right).$$

In most cases, we want to write this negation in a way that does not use the negation symbol. In this case, we can now write the open sentence $\neg \left(x^3\ge x^2\right)$ as . (That is, the negation of "is greater than or equal to" is "is less than.") So we obtain the following:

The statement could be written in English as follows:

• There exists a real number $x$ such that .

• There exists an $x$ such that $x$ is a real number and .

2.4.6 Progress Check 2.18 (Negating Quantified Statements)

For each of the following statements

• Write the statement in the form of an English sentence that does not use the symbols for quantifiers.

• Write the negation of the statement in a symbolic form that does not use the negation symbol.

• Write the negation of the statement in the form of an English sentence that does not use the symbols for quantifiers.

1. $(\forall a\in ℝ)(a+0=a)$.

2. $(\forall x\in ℝ)[\sin (2x)=2(\sin x)(\cos x)]$.

3. $(\forall x\in ℝ)\left({\tan }^{2}x+1={\sec }^{2}x\right)$.

4. $(\exists x\in \mathbb{Q})\left(x^2-3x-7=0\right)$.

5. $(\exists x\in ℝ)\left(x^2+1=0\right)$.

2.4.7 Counterexamples and Negations of Conditional Statements

The real number $x=-1$ in the previous example was used to show that the statement $(\forall x\in ℝ)\left(x^3\ge x^2\right)$ is false. This is called a counterexample to the statement. In general, a counterexample to a statement of the form $(\forall x)[P(x)]$ is an object $a$ in the universal set $U$ for which $P(a)$ is false. It is an example that proves that $(\forall x)[P(x)]$ is a false statement, and hence its negation, $(\exists x)[\neg P(x)]$, is a true statement.

In the preceding example, we also wrote the universally quantified statement as a conditional statement. The number $x=-1$ is a counterexample for the statement

If $x$ is a real number, then $x^3$ is greater than or equal to $x^2$.

So the number -1 is an example that makes the hypothesis of the conditional statement true and the conclusion false. Remember that a conditional statement often contains a "hidden" universal quantifier. Also, recall that in Section 2.2 we saw that the negation of the conditional statement "If $P$ then $Q$" is the statement "$P$ and not $Q$." Symbolically, this can be written as follows:

$$\neg (P\to Q)\equiv P\wedge \neg Q.$$

So when we specifically include the universal quantifier, the symbolic form of the negation of a conditional statement is

$\neg (\forall x\in U)[P(x)\to Q(x)]$ $\equiv (\exists x\in U)\neg [P(x)\to Q(x)]$

$\equiv (\exists x\in U)[P(x)\wedge \neg Q(x)].$

That is,

$$\neg (\forall x\in U)[P(x)\to Q(x)]\equiv (\exists x\in U)[P(x)\wedge \neg Q(x)].$$

2.4.8 Progress Check 2.19 (Using Counterexamples)

Use counterexamples to explain why each of the following statements is false.

1. For each integer $n,\left(n^2+n+1\right)$ is a prime number.

2. For each real number $x$, if $x$ is positive, then $2x^2>x$.

2.4.9 Quantifiers in Definitions

Definitions of terms in mathematics often involve quantifiers. These definitions are often given in a form that does not use the symbols for quantifiers. Not only is it important to know a definition, it is also important to be able to write a negation of the definition. This will be illustrated with the definition of what it means to say that a natural number is a perfect square.

Definition. A natural number $n$ is a perfect square provided that there exists a natural number $k$ such that $n=k^2$.

This definition can be written in symbolic form using appropriate quantifiers as follows:

A natural number $n$ is a perfect square provided $(\exists k\in \mathbb{N})\left(n=k^2\right)$.

We frequently use the following steps to gain a better understanding of a definition.

1. Examples of natural numbers that are perfect squares are $1,4,9$, and 81 since $1=1^2,4=2^2,9=3^2$, and $81=9^2$.

2. Examples of natural numbers that are not perfect squares are $2,5,10$, and 50 .

3. This definition gives two "conditions." One is that the natural number $n$ is a perfect square and the other is that there exists a natural number $k$ such that $n=k^2$. The definition states that these mean the same thing. So when we say that a natural number $n$ is not a perfect square, we need to negate the condition that there exists a natural number $k$ such that $n=k^2$. We can use the symbolic form to do this.

$$\neg (\exists k\in \mathbb{N})\left(n=k^2\right)\equiv (\forall k\in \mathbb{N})\left(n\ne k^2\right)$$

Notice that instead of writing $\neg \left(n=k^2\right)$, we used the equivalent form of $\left(n\ne k^2\right)$. This will be easier to translate into an English sentence. So we can write,

A natural number $n$ is not a perfect square provided that for every natural number $k,n\ne k^2$.

The preceding method illustrates a good method for trying to understand a new definition. Most textbooks will simply define a concept and leave it to the reader to do the preceding steps. Frequently, it is not sufficient just to read a definition and expect to understand the new term. We must provide examples that satisfy the definition, as well as examples that do not satisfy the definition, and we must be able to write a coherent negation of the definition.

2.4.10 Progress Check 2.20 (Multiples of Three)

Definition. An integer $n$ is a multiple of $\mathrm{𝟑}$ provided that there exists an integer $k$ such that $n=3k$.

1. Write this definition in symbolic form using quantifiers by completing the following:

   An integer $n$ is a multiple of 3 provided that ….

2. Give several examples of integers (including negative integers) that are multiples of 3.

3. Give several examples of integers (including negative integers) that are not multiples of 3.

4. Use the symbolic form of the definition of a multiple of 3 to complete the following sentence: "An integer $n$ is not a multiple of 3 provided that . . . ."

5. Without using the symbols for quantifiers, complete the following sentence: "An integer $n$ is not a multiple of 3 provided that . . ."

2.4.11 Statements with More than One Quantifier

When a predicate contains more than one variable, each variable must be quantified to create a statement. For example, assume the universal set is the set of integers, $\mathbb{Z}$, and let $P(x,y)$ be the predicate, "$x+y=0$." We can create a statement from this predicate in several ways.

1. $(\forall x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y=0)$.

   We could read this as, "For all integers $x$ and $y,x+y=0$." This is a false statement since it is possible to find two integers whose sum is not zero $(2+3\ne 0)$.

2. $(\forall x\in \mathbb{Z})(\exists y\in \mathbb{Z})(x+y=0)$.

   We could read this as, "For every integer $x$, there exists an integer $y$ such that $x+y=0$." This is a true statement.

3. $(\exists x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y=0)$.

   We could read this as, "There exists an integer $x$ such that for each integer This is a false statement since there is no integer whose sum with each integer is zero.

4. $(\exists x\in \mathbb{Z})(\exists y\in \mathbb{Z})(x+y=0)$.

   We could read this as, "There exist integers $x$ and $y$ such that $x+y=0$." This is a true statement. For example, $2+(-2)=0$.

When we negate a statement with more than one quantifier, we consider each quantifier in turn and apply the appropriate part of Theorem 2.16. As an example, we will negate Statement (3) from the preceding list. The statement is

$$(\exists x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y=0)$$

We first treat this as a statement in the following form: $(\exists x\in \mathbb{Z})(P(x))$ where $P(x)$ is the predicate $(\forall y\in \mathbb{Z})(x+y=0)$. Using Theorem 2.16, we have

$$\neg (\exists x\in \mathbb{Z})(P(x))\equiv (\forall x\in \mathbb{Z})(\neg P(x)).$$

Using Theorem 2.16 again, we obtain the following:

$\neg P(x)$ $\equiv \neg (\forall y\in \mathbb{Z})(x+y=0)$

$\equiv (\exists y\in \mathbb{Z})\neg (x+y=0)$

$\equiv (\exists y\in \mathbb{Z})(x+y\ne 0)$

Combining these two results, we obtain

$$\neg (\exists x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y=0)\equiv (\forall x\in \mathbb{Z})(\exists y\in \mathbb{Z})(x+y\ne 0).$$

The results are summarized in the following table.

	Symbolic Form	English Form
Statement	$(\exists x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y=0)$	There exists an integer $x$ such that for each integer $y,x+y=0$.
Negation	$(\forall x\in \mathbb{Z})(\exists y\in \mathbb{Z})(x+y\ne 0)$	For each integer $x$, there exists an integer $y$ such that $x+y\ne 0$.

Since the given statement is false, its negation is true.
We can construct a similar table for each of the four statements. The next table shows Statement (2), which is true, and its negation, which is false.

	Symbolic Form	English Form
Statement	$(\forall x\in \mathbb{Z})(\exists y\in \mathbb{Z})(x+y=0)$	For every integer $x$, there exists an integer $y$ such that $x+y=0$.
Negation	$(\exists x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y\ne 0)$	There exists an integer $x$ such that for every integer $y,x+y\ne 0$.

2.4.12 Progress Check 2.21 (Negating a Statement with Two Quantifiers)

Write the negation of the statement

$$(\forall x\in \mathbb{Z})(\forall y\in \mathbb{Z})(x+y=0)$$

in symbolic form and as a sentence written in English.

2.4.13 Writing Guideline

Try to use English and minimize the use of cumbersome notation. Do not use the special symbols for quantifiers $\forall$ (for all), $\exists$ (there exists), $\ni$ (such that), or $\therefore$ (therefore) in formal mathematical writing. It is often easier to write and usually easier to read, if the English words are used instead of the symbols. For example, why make the reader interpret

$$(\forall x\in ℝ)(\exists y\in ℝ)(x+y=0)$$

when it is possible to write
For each real number $x$, there exists a real number $y$ such that $x+y=0$, or, more succinctly (if appropriate),

Every real number has an additive inverse.

2.4.14 Exercises for Section 2.4

1. $(\star )$ For each of the following, write the statement as an English sentence and then explain why the statement is false.

   1. $(\exists x\in \mathbb{Q})\left(x^2-3x-7=0\right)$.

   2. $(\exists x\in ℝ)\left(x^2+1=0\right)$.

   3. .

2. $(\star )$ For each of the following, use a counterexample to show that the statement is false. Then write the negation of the statement in English, without using symbols for quantifiers.

   1. $(\star )$ $(\forall m\in \mathbb{Z})(m^2$ is even).

   2. $(\star )$ $(\forall x\in ℝ)\left(x^2>0\right)$.

   3. For each real number $x,\sqrt{x}\in ℝ$.

   4. $(\forall m\in \mathbb{Z})\left(\frac{m}{3}\in \mathbb{Z}\right)$.

   5. $(\forall a\in \mathbb{Z})\left(\sqrt{a^2}=a\right)$.

   6. $(\star )$ $(\forall x\in ℝ)\left({\tan }^{2}x+1={\sec }^{2}x\right)$.

3. For each of the following statements

   • Write the statement as an English sentence that does not use the symbols for quantifiers.

   • Write the negation of the statement in symbolic form in which the negation symbol is not used.

   • Write a useful negation of the statement in an English sentence that does not use the symbols for quantifiers.

   1. $(\star )$ $(\exists x\in \mathbb{Q})(x>\sqrt{2})$.

   2. $(\forall x\in \mathbb{Q})\left(x^2-2\ne 0\right)$.

   3. $(\star )$ $(\forall x\in \mathbb{Z})(x$ is even or $x$ is odd).

   4. . Note: The sentence "" is actually a conjunction. It means and .

   5. $(\star )$ $(\forall x\in \mathbb{Z})$ (If $x^2$ is odd, then $x$ is odd).

   6. $(\forall n\in \mathbb{N})[$ If $n$ is a perfect square, then $\left(2^n-1\right)$ is not a prime number].

   7. $(\forall n\in \mathbb{N})(n^2-n+41$ is a prime number).

   8. $(\star )$ $(\exists x\in ℝ)(\cos (2x)=2(\cos x))$.

4. Write each of the following statements as an English sentence that does not use the symbols for quantifiers.

   1. $(\exists m\in \mathbb{Z})(\exists n\in \mathbb{Z})(m>n)$

   2. $(\exists m\in \mathbb{Z})(\forall n\in \mathbb{Z})(m>n)$

   3. $(\forall m\in \mathbb{Z})(\exists n\in \mathbb{Z})(m>n)$

   4. $(\forall m\in \mathbb{Z})(\forall n\in \mathbb{Z})(m>n)$

   5. $(\exists n\in \mathbb{Z})(\forall m\in \mathbb{Z})\left(m^2>n\right)$

   6. $(\forall n\in \mathbb{Z})(\exists m\in \mathbb{Z})\left(m^2>n\right)$

5. $(\star )$ Write the negation of each statement in Exercise (4) in symbolic form and as an English sentence that does not use the symbols for quantifiers.

6. $(\star )$ Assume that the universal set is $\mathbb{Z}$. Consider the following sentence:

   $$(\exists t\in \mathbb{Z})(t\cdot x=20)$$

   1. Explain why this sentence is an open sentence and not a statement.

   2. If 5 is substituted for $x$, is the resulting sentence a statement? If it is a statement, is the statement true or false?

   3. If 8 is substituted for $x$, is the resulting sentence a statement? If it is a statement, is the statement true or false?

   4. If -2 is substituted for $x$, is the resulting sentence a statement? If it is a statement, is the statement true or false?

   5. What is the truth set of the open sentence $(\exists t\in \mathbb{Z})(t\cdot x=20)$?

7. Assume that the universal set is $ℝ$. Consider the following sentence:

   $$(\exists t\in ℝ)(t\cdot x=20)$$

   1. Explain why this sentence is an open sentence and not a statement.

   2. If 5 is substituted for $x$, is the resulting sentence a statement? If it is a statement, is the statement true or false?

   3. If $\pi$ is substituted for $x$, is the resulting sentence a statement? If it is a statement, is the statement true or false?

   4. If 0 is substituted for $x$, is the resulting sentence a statement? If it is a statement, is the statement true or false?

   5. What is the truth set of the open sentence $(\exists t\in ℝ)(t\cdot x=20)$?

8. Let ${\mathbb{Z}}^{\ast }$ be the set of all nonzero integers.

   1. Use a counterexample to explain why the following statement is false:

      For each $x\in {\mathbb{Z}}^{\ast }$, there exists a $y\in {\mathbb{Z}}^{\ast }$ such that $xy=1$.

   2. Write the statement in part (a) in symbolic form using appropriate symbols for quantifiers.

   3. Write the negation of the statement in part

   4. in symbolic form using appropriate symbols for quantifiers.

   5. Write the negation from part

   6. in English without using the symbols for quantifiers.

9. An integer $m$ is said to have the divides property provided that for all integers $a$ and $b$, if $m$ divides $ab$, then $m$ divides $a$ or $m$ divides $b$.

   1. Using the symbols for quantifiers, write what it means to say that the integer $m$ has the divides property.

   2. Using the symbols for quantifiers, write what it means to say that the integer $m$ does not have the divides property.

   3. Write an English sentence stating what it means to say that the integer $m$ does not have the divides property.

10. In calculus, we define a function $f$ with domain $ℝ$ to be strictly increasing provided that for all real numbers $x$ and whenever . Complete each of the following sentences using the appropriate symbols for quantifiers:

    1. $(\star )$ A function $f$ with domain $ℝ$ is strictly increasing provided that ….

    2. A function $f$ with domain $ℝ$ is not strictly increasing provided that ….

       Complete the following sentence in English without using symbols for quantifiers:

    3. A function $f$ with domain $ℝ$ is not strictly increasing provided that . . . .

11. In calculus, we define a function $f$ to be continuous at a real number $a$ provided that for every $\epsilon >0$, there exists a $\delta >0$ such that if , then .

    Note: The symbol $\epsilon$ is the lowercase Greek letter epsilon, and the symbol $\delta$ is the lowercase Greek letter delta.

    Complete each of the following sentences using the appropriate symbols for quantifiers:

    1. A function $f$ is continuous at the real number $a$ provided that ….

    2. A function $f$ is not continuous at the real number $a$ provided that . . . .

       Complete the following sentence in English without using symbols for quantifiers:

    3. A function $f$ is not continuous at the real number $a$ provided that . . . .

12. The following exercises contain definitions or results from more advanced mathematics courses. Even though we may not understand all of the terms involved, it is still possible to recognize the structure of the given statements and write a meaningful negation of that statement.

    1. In abstract algebra, an operation $\ast$ on a set $A$ is called a commutative operation provided that for all $x,y\in A,x\ast y=y\ast x$. Carefully explain what it means to say that an operation $\ast$ on a set $A$ is not a commutative operation.

    2. In abstract algebra, a ring consists of a nonempty set $R$ and two operations called addition and multiplication. A nonzero element $a$ in a ring $R$ is called a zero divisor provided that there exists a nonzero element $b$ in $R$ such that $ab=0$ or $ba=0$. Carefully explain what it means to say that a nonzero element $a$ in a ring $R$ is not a zero divisor.

    3. A set $M$ of real numbers is called a neighborhood of a real number $a$ provided that there exists a positive real number $\epsilon$ such that the open interval $(a-\epsilon ,a+\epsilon )$ is contained in $M$. Carefully explain what it means to say that a set $M$ is not a neighborhood of a real number $a$.

    4. In advanced calculus, a sequence of real numbers $(x_1,x_2,\mathrm{\dots },x_k,\mathrm{\dots })$ is called a Cauchy sequence provided that for each positive real number $\epsilon$, there exists a natural number $N$ such that for all $m,n\in \mathbb{N}$, if $m>N$ and $n>N$, then . Carefully explain what it means to say that the sequence of real numbers $(x_1,x_2,\mathrm{\dots },x_k,\mathrm{\dots })$ is not a Cauchy sequence.

2.4.15 Explorations and Activities

1. Prime Numbers. The following definition of a prime number is very important in many areas of mathematics. We will use this definition at various places in the text. It is introduced now as an example of how to work with a definition in mathematics.

   Definition. A natural number $p$ is a prime number provided that it is greater than 1 and the only natural numbers that are factors of $p$ are 1 and $p$. A natural number other than 1 that is not a prime number is a composite number. The number 1 is neither prime nor composite.

   Using the definition of a prime number, we see that $2,3,5$, and 7 are prime numbers. Also, 4 is a composite number since $4=2\cdot 2$; 10 is a composite number since $10=2\cdot 5$; and 60 is a composite number since $60=4\cdot 15$.

   1. Give examples of four natural numbers other than 2, 3, 5, and 7 that are prime numbers.

   2. Explain why a natural number $p$ that is greater than 1 is a prime number provided that

      For all $d\in \mathbb{N}$, if $d$ is a factor of $p$, then $d=1$ or $d=p$.

   3. Give examples of four natural numbers that are composite numbers and explain why they are composite numbers.

   4. Write a useful description of what it means to say that a natural number is a composite number (other than saying that it is not prime).

2. Upper Bounds for Subsets of $ℝ$. Let $A$ be a subset of the real numbers. A number $b$ is called an upper bound for the set $A$ provided that for each element $x$ in $A$, $x\le b$.

   1. Write this definition in symbolic form by completing the following:

      Let $A$ be a subset of the real numbers. A number $b$ is called an upper bound for the set $A$ provided that . . . .

   2. Give examples of three different upper bounds for the set
      $A=\{x\in ℝ\mid 1\le x\le 3\}$.

   3. Does the set $B=\{x\in ℝ\mid x>0\}$ have an upper bound? Explain.

   4. Give examples of three different real numbers that are not upper bounds for the set $A=\{x\in ℝ\mid 1\le x\le 3\}$.

   5. Complete the following in symbolic form: "Let $A$ be a subset of $ℝ$. A number $b$ is not an upper bound for the set $A$ provided that . . .""

   6. Without using the symbols for quantifiers, complete the following sentence: "Let $A$ be a subset of $ℝ$. A number $b$ is not an upper bound for the set $A$ provided that . . . ."

   7. Are your examples in Part (14d) consistent with your work in Part (14f)? Explain.

3. Least Upper Bound for a Subset of $ℝ$. In Exercise 14, we introduced the definition of an upper bound for a subset of the real numbers. Assume that we know this definition and that we know what it means to say that a number is not an upper bound for a subset of the real numbers.

   Let $A$ be a subset of $ℝ$. A real number $\alpha$ is the least upper bound for $A$ provided that $\alpha$ is an upper bound for $A$, and if $\beta$ is an upper bound for $A$, then $\alpha \le \beta$.

   Note: The symbol $\alpha$ is the lowercase Greek letter alpha, and the symbol $\beta$ is the lowercase Greek letter beta.

   If we define $P(x)$ to be "$x$ is an upper bound for $A$," then we can write the definition for least upper bound as follows:

   A real number $\alpha$ is the least upper bound for $A$ provided that
   $P(\alpha )\wedge [(\forall \beta \in ℝ)(P(\beta )\to (\alpha \le \beta ))]$.

   1. Why is a universal quantifier used for the real number $\beta$?

   2. Complete the following sentence in symbolic form: "A real number $\alpha$ is not the least upper bound for $A$ provided that . . . ."

   3. Complete the following sentence as an English sentence: "A real number $\alpha$ is not the least upper bound for $A$ provided that . . . ."

2.5 Chapter 2 Summary

2.5.1 Important Definitions

• Logically equivalent statements, Section 2.2

• Converse of a conditional statement, Section 2.2

• Contrapositive of a conditional statement, Section 2.2

• Variable, Section 2.3

• Universal set for a variable, Section 2.3

• Constant, Section 2.3

• Equal sets, Section 2.3

• Predicate, Section 2.3

• Open sentence, Section 2.3

• Truth set of a predicate, Section 2.3

• Universal quantifier, Section 2.4

• Existential quantifier, Section 2.4

• Empty set, Section 2.4

• Counterexample, Section 2.4

• Perfect square, Section 2.4

• Prime number, Section 2.4 Exercises

• Composite number, Section 2.4 Exercises

2.5.2 Important Theorems and Results

Theorem 2.8. Important Logical Equivalencies. For statements $P,Q$, and $R$,

De Morgan’s Laws	$\neg (P\wedge Q)\equiv \neg P\vee \neg Q$ $\neg (P\vee Q)\equiv \neg P\wedge \neg Q$
Conditional Statements	$P\to Q\equiv \neg Q\to \neg P\text{ (contrapositive)}$ $P\to Q\equiv \neg P\vee Q$ $\neg (P\to Q)\equiv P\wedge \neg Q$
Biconditional Statement	$(P\leftrightarrow Q)\equiv (P\to Q)\wedge (Q\to P)$
Double Negation	$\neg (\neg P)\equiv P$
Distributive Laws	$P\vee (Q\wedge R)\equiv (P\vee Q)\wedge (P\vee R)$ $P\wedge (Q\vee R)\equiv (P\wedge Q)\vee (P\wedge R)$
Conditionals with Disjunctions	$P\to (Q\vee R)\equiv (P\wedge \neg Q)\to R$ $(P\vee Q)\to R\equiv (P\to R)\wedge (Q\to R)$

Theorem 2.16. Negations of Quantified Statements. For any predicate $P(x)$,

$\neg (\forall x)[P(x)]\equiv (\exists x)[\neg P(x)],\text{ and}$

$\neg (\exists x)[P(x)]\equiv (\forall x)[\neg P(x)].$

2.5.3 Important Set Theory Notation

Notation	Description
$y\in A$	$y$ is an element of the set $A$.
$z\notin A$	$z$ is not an element of the set $A$.
$\{\}$	The roster method
$\{x\in U\mid P(x)\}$	Set builder notation