Skip to main content

Section 5.2 Quantifiers

In Activity 5.1.A there were statements involving variables in which the truth of the statement depended on whether the statement was about all values, some values, or no values of the variables. Each of the words “all”, “some”, and “no” has a specific meaning in mathematics and computer science. In this section, we consider such quantifiers and their negations and formally introduce the idea of a counterexample. We also look at how to prove quantified statements.

Subsection 5.2.A The Game SET!

Let’s start with a puzzle.
The game SET! is produced by SET Enterprises™, part of Monster Play. You can learn to play SET! online. There is a lot of information about this game on the Internet. Resist the temptation to use any resources to find answers to this (or any) activity. The fun part is figuring it out for yourself!

Activity 5.2.A The game SET!

In the game SET!, there is a deck of special cards. Each card has the image of some number of a colored shape with some level of shading. If there is more than one shape on a card, the others shapes on the card are repeats of that shape with the same color and level of shading. For example, there is a card that has two striped, purple ovals, as shown in Figure 5.2.2.
Figure 5.2.2. The SET! card with two striped, purple ovals. (2SPO)
There are four characteristic of the image on each card: number, shading, color, and shape. Each characteristic has three options as summarized in Table 5.2.3.
Table 5.2.3. The options for each characteristic for the image on each card in the game SET!
characteristic options (with their abbreviations)
number 1, 2, or 3
shading none (N), striped (S), or full (F)
color red (R), purple (P), or green (G)
symbol oval (O), diamond (D), or squiggle (Q)
  1. Write the abbreviation for each card shown in Figure 5.2.4. The card on the left is green and the card on the right is red.
    Figure 5.2.4. Two cards from the game SET!
  2. For each combination of options there is exactly one card in the deck with that combination. How many cards are there in the game SET!? Explain.
  3. A set of three cards is a SET if for each of the characteristics either the images on the three cards all agree or are all different. That is, all four of the following conditions must be met.
    • All three cards have the same number or there is one with 1, one with 2, and one with 3.
    • All three cards have the same shading or there is one with none, one striped, and one full.
    • All three cards have the same color or there is one red, one purple, and one green.
    • All three cards have the same symbol or there is one oval, one diamond, and one squiggle.
    Check that the set of three cards shown in Figure 5.2.5 is a SET. The cards are abbreviated 2NRO, 2SRO, and 2FRO.
    Figure 5.2.5. An example of a SET.
  4. Is the set of three cards shown in Figure 5.2.6 a SET? Justify your answer. The cards are abbreviated 1SGQ, 2SPO, and 3SRD.
    Figure 5.2.6. Is this set of three cards a SET?
  5. Explain why the set of three cards shown in Figure 5.2.7 is not a SET. The cards are abbreviated 1FGD, 1NPD, and 1 NRD.
    Figure 5.2.7. An example of three cards that are not a SET.
  6. Is the set of three cards shown in Figure 5.2.8 a SET? Justify your answer. The cards are abbreviated 1SPO, 2FGD, and 3NRQ.
    Figure 5.2.8. Is this different set of three cards a SET?
  7. What third card makes a SET with the pair of cards from Figure 5.2.4?
  8. Given a pair of cards, explain how we can find a third card that makes a SET with the given pair. Be sure to explain in general (tell someone step-by-step how to find the missing third card.)

Subsection 5.2.B Quantifiers

In the game SET!, a set of three cards forms a SET if for each characteristic, all the cards agree or none of the cards agree. A set of three cards is not a SET if, for some characteristic, the cards have two of one kind and one of a different kind. Part of the challenge of learning the game is grappling with words like “each”, “all”, “none”, and “some” which are examples of quantifiers.

Definition 5.2.9 Quantifiers.

Quantifiers can be defined on any set. Throughout this definition, our examples use the set of integers.
  1. We indicate that a statement \(P\) depends on a variable \(n\) by writing \(P(n)\) instead of \(P\text{.}\) The notation \(P(n)\) is predicate notation. For example, if \(P(n)\) is the statement “the integer \(n\) is odd”, then \(P(3)\) is the statement “the integer \(3\) is odd”, which is true, but \(P(10)\) is the statement “the integer \(10\) is odd”, which is false.
  2. The universal quantifier, denoted \(\forall\text{,}\) means “for all”.
    • The statement \(\forall n P(n)\) is the statement “\(P(n)\) is true for all values of \(n\)”. For example, if \(P(n)\) is the statement “the integer \(2n\) is even”, then \(\forall n ~ P(n)\) is the statement “every integer of the form \(2n\) is even”, which is true. On the other hand, if \(Q(n)\) is the statement “\(3 \mid n\)”, then \(\forall n ~ Q(n)\) is the statement “every integer is divisible by three”, which is false because, for example, 17 is not divisible by three.
    • The statement \(\forall n(\neg P(n))\) means \(P(n)\) is false for all values of \(n\text{.}\) For example, if \(R(n)\) is the statement “the integer \(2n+1\) is even”, then \(\forall n (\neg R(n))\) is the statement “no integer of the form \(2n+1\) is even”, which is true.
  3. The existential quantifier, denoted \(\exists\) means “there exists.”
    • The statement \(\exists n ~ P(n)\) means that \(P(n)\) is true for some value(s) of \(n\text{.}\) For example, if \(Q(n)\) means that \(3 \mid n\text{,}\) then \(\exists n ~ Q(n)\) means that some integer is divisible by three, which is true because, for example, 12 is divisible by three.
    • The statement \(\exists n (\neg P(n))\) means that \(P(n)\) is false for some value(s) of \(n\text{.}\) For example, if \(Q(n)\) means \(3 \mid n\text{,}\) then \(\exists n (\neg Q(n))\) means that some integer is not divisible by three, which is true because, for example, 17 is not divisible by three.
There are many different English words and phrases that indicate quantifiers.

Remark 5.2.10 English words indicating quantifiers.

 
  1. Words and phrases that indicate a universal quantifier include: a, all, always, any, each, every, everyone, etc.
  2. Words and phrases that indicate a universal quantifier followed by a negation include: impossible, never, no, no one, none, nothing, etc.
  3. Words and phrases that indicate an existential quantifier include: at least one, can, contains, has, possible, some, someone, sometimes, there exist, there exists there is, there are, etc.
  4. Note that some words and phrases that indicate the existential quantifier are plural, but it takes only one value of \(n\) where \(S(n)\) is true to make the statement \(\exists n ~ S(n)\) true. For example, in mathematics, some means at least one.
Universally quantified statements are sometimes written without an explicit quantifier. For example, we might say \(2n\) is even when we really mean \(2n\) is even for all integers \(n\text{.}\)

Remark 5.2.11 Default universal.

If a statement about variables does not explicitly state a quantifier, the default assumption is that the quantifier is universal.
Practice working with quantified statements.

Activity 5.2.B More true or false?

Identify a word or phrase that indicates a quantifier, decide if each statement is true or false, and discuss how to justify your answer.
  1. There is a graph that has five vertices and five edges.
  2. Any graph with five vertices has five edges.
  3. No graph has more edges than vertices.
  4. Some square integers have exactly three positive divisors.
  5. Any square integer has exactly three positive divisors.
  6. Some graphs are regular. Recall that in a regular graph, every vertex has the same degree.
  7. Some graphs are not regular.
Let’s look at a few more examples identifying words or phrases that indicate a quantifier.

Example 5.2.13 Identifying quantifiers.

In each statement, find a word or phrase that indicates a quantifier and say which: \(\forall\) or \(\exists\text{.}\) In some parts, both quantifiers are involved. (We saw these statements in Activity 5.1.A and Activity 5.2.B.)
  1. There are three distinct digits whose sum is 23.
    Solution.
    The phrase “there are” indicates an existential quantifier \(\exists\text{.}\)
  2. Some integers are divisible by three and five.
    Solution.
    The word “some” indicates an existential quantifier \(\exists\text{.}\)
  3. A graph with five vertices is the cycle \(C_5\) or the complete graph \(K_5\text{.}\)
    Solution.
    The word “a” indicates a universal quantifier \(\forall\text{.}\)
  4. No graph has more edges than vertices.
    Solution.
    The word “no” indicates a universal quantifier \(\forall\text{.}\)
  5. Every bit string of length five contains at least one \(\bs{1}\text{.}\)
    Solution.
    The word “every” indicates a universal quantifier \(\forall\) and the word “contains” indicates an existential quantifier \(\exists\text{.}\)

Subsection 5.2.C Proof Formats: Quantified Statements

How do we prove that a quantified statement is true?
To prove an existentially quantified statement, all we need to do is provide an example. Here is the proof format.
In the first sentence of Theorem 5.2.14 we present an example without any explanation of how we found that example. Mathematicians sometimes explain where the example came from, but that explanation is not a required part of the proof. Let’s look at a quick example.

Example 5.2.15 There is a graph with five vertices and five edges.

Prove Activity 5.2.B (a) that there is a graph that has five vertices and five edges.
Solution.
The phrase “there is” indicates an existentially quantified statement, so we follow Theorem 5.2.14.
Proof. Consider the cycle \(C_5\text{.}\) Recall that \(C_5\) has five vertices and five edges. Therefore, there is a graph that has five vertices and five edges, namely \(C_5\text{.}\)
The proof of a universally quantified statement is more complicated because we have to prove that the statement holds for all possible examples. In some cases, we can simply check every example.

Example 5.2.16 Checking every example.

In Section 4.3, we introduced the integers mod 5, \(\mathbb{Z}_5=\{0,1,2,3,4\}\text{.}\) In \(\mathbb{Z}_5\text{,}\) multiplication is defined by \(a \otimes b = ab \fn{ mod } 5\text{.}\) Prove that there is no solution to \(x^2=2\) in \(\mathbb{Z}_5\text{.}\) Note that \(x^2 = x \otimes x\text{.}\)
Solution.
We can check each element of \(\mathbb{Z}_5\) to see if it is a solution. Our work is displayed in Table 5.2.17. Since none of the elements of \(\mathbb{Z}_5\) is a solution, we can conclude that there is no solution to \(x^2=2\) in \(\mathbb{Z}_5\text{.}\)
Table 5.2.17. Checking that \(x^2=2\) has no solution in \(\mathbb{Z}_5\)
\(x\) evaluate \(x^2\) in \(\mathbb{Z}_5\) does \(x^2=2\text{?}\)
0 \(0^2 = 0\fn{ mod } 5= 0\) no
1 \(1^2 = 1\fn{ mod } 5= 1\) no
2 \(2^2 = 4\fn{ mod } 5= 4\) no
3 \(3^2 = 9\fn{ mod } 5= 4\) no
4 \(4^2 = 16\fn{ mod } 5= 1\) no
In the previous example, we were able to check all five possible examples. But if the list of possible examples is very long or infinite, it is not reasonable or possible to check every example, and it is not enough to just check some examples. Here is the proof format.
The proof begins by naming an arbitrary object, \(n\text{,}\) of the type described. This first sentence invites the reader to select any value of \(n\text{.}\) Next, we show that the statement is true for that particular but unknown \(n\text{.}\) Our proof must work for whatever value \(n\) the reader selected.
Let’s look at a quick example.

Example 5.2.19 \(6q-10\) is even.

Use the definition of even to prove that for every integer \(q\text{,}\) the integer \(6q-10\) is even. (This proof was Section 4.1 Exercise 6 6.(a).)
Solution.
The phrase “for every” indicates a universally quantified statement, so we follow Theorem 5.2.18.
Proof. Let \(q\) be an integer. Then \(6q-10=2(3q-5)=2k\) where \(k=3q-5\) is an integer. By the definition of even, it follows that \(6q-10\) is even. Therefore, for every integer \(q\text{,}\) the integer \(6q-10\) is even.
As usual, after we introduce new proof formats, we give you the opportunity to practice.

Activity 5.2.C Proofs of quantified statements.

 
  1. Copy the following proof. Note that the phrase “there is” indicates an existentially quantified statement, so we use Theorem 5.2.14. Prove that there is an integer that has exactly four positive divisors.

    Proof.
    Consider the integer six. The positive divisors of six are 1, 2, 3, and 6. Thus, six has exactly four positive divisors. Therefore, there is an integer that has exactly four positive divisors.
  2. Edit the proof in (a) to prove that there is an integer with exactly three positive divisors.
  3. Copy the following proof. Note that the phrase “for any” indicates a universally quantified statement, so we use Theorem 5.2.18. Prove \(n \mid n!\) for any integer \(n\text{.}\)

    Proof.
    Let \(n\) be an integer. Note that \(n!=n(n-1)!=nk\) where \(k=(n-1)!\) By the definition of divides, it follows that \(n \mid n!\) Therefore, \(n \mid n!\) for every integer \(n\text{.}\)
  4. Edit the proof in (c) to prove \(2 \mid 2^n\) for any integer \(n\text{.}\)

Subsection 5.2.D Proof Format: Mixed Quantifiers

Many interesting mathematical statements involve both existential and universal quantifiers. Fortunately, we do not need new proof formats. Instead, we can nest proof formats one inside the other, as if they were Matryoshka dolls
 1 
See wikipedia Matryoshka doll.
or nested loops in computer programming. Try writing proofs that nest the proof formats for existentially and universally quantified statements.

Activity 5.2.D Proofs of mixed quantified statements.

 
  1. Copy the following proof. Note that we use Theorem 5.2.18 and, within that format, we use Theorem 5.2.14. We have indented the lines to highlight the nesting. Prove that for any integer \(n\) there is an integer \(m\) such that \(n+m=100\text{.}\)

    Proof.
    Let \(n\) be an integer.
    “
    Consider the integer \(m=100-n\text{.}\)
    Then \(n+m=n+(100-n)=100\text{.}\)
    Thus, there is an integer \(m\) with \(n+m=100\text{,}\) namely \(m=100-n\text{.}\)
    ”
    Therefore, for any integer \(n\) there is an integer \(m\) such that \(n+m=100\text{.}\)
  2. Edit the proof in (a) to prove that for any integer \(n\) there is an integer \(k\) such that \(n-k=100\text{.}\) Hint: Solve for \(k\) before starting to write the proof.
  3. Copy the following proof. Note that we use Theorem 5.2.14 and, within that format, we use Theorem 5.2.18. Notice that we are nesting the quantifiers in the opposite order from (a). We have indented the lines to highlight the nesting. Prove that there exists an integer \(z\) such that \(zn=z\) for any integer \(n\text{.}\)

    Proof.
    Consider the integer \(z=0\text{.}\)
    “
    Let \(n\) be an integer.
    Then \(zn=(0)(n)=0=z\text{.}\)
    Thus, \(zn=z\) for any integer \(n\text{.}\)
    ”
    Therefore, there exists an integer \(z\) such that \(zn=z\) for any integer \(n\text{,}\) namely \(z=0\text{.}\)
  4. Edit the proof in (c) to prove that there exists an integer \(w\) such that \(wn=n\) for any integer \(n\text{.}\) Hint: Solve for \(w\) before starting to write to write the proof.
The last sentences of the proofs in Activity 5.2.D may seem repetitive. They are logically necessary and a good idea for you to write as you are first learning proofs, but in practice mathematicians often omit those final sentences.

Remark 5.2.22 Omitting the concluding sentence of proofs of quantified statements.

It is common to omit the concluding sentence(s) of a proof of a quantified statement.
Here is an example using Remark 5.2.22.

Example 5.2.23 Omitting the concluding lines of a proof of a quantified statement.

Write a shorter version of the proof from Activity 5.2.D (a).
Solution.
Prove that there exists an integer \(z\) such that \(zn=z\) for any integer \(n\text{.}\)
Proof. Consider the integer \(z=0\) and let \(n\) be any integer. Then \(zn=(0)(n)=0=z\text{.}\)

Subsection 5.2.E Negating Quantified Statements and Counterexamples

How do we prove that a quantified statement is false? To answer this question, we need to recognize the negations of quantified statements. You may want to revisit Activity 5.1.A and Activity 5.2.B to see if you can state these negations for yourself before reading on.
Let’s unpack this theorem a bit.

Example 5.2.25 Negating a universally quantified statement.

 
  1. Explain why Theorem 5.2.24 (a) is correct.
    Solution.
    The statement \(\forall n ~ P(n)\) says \(P(n)\) is always true. The negation would say \(P(n)\) is not always true which is equivalent to saying \(P(n)\) is sometimes false.
    The statement \(\exists n (\neg P(n))\) says \(\neg P(n)\) is sometimes true which is equivalent to saying \(P(n)\) is sometimes false.
    Thus \(\neg(\forall n ~ P(n)) \equiv \exists n (\neg P(n))\text{.}\)
  2. Explain why Theorem 5.2.24 (b) is correct.
    Solution.
    The statement \(\exists n ~ P(n)\) says \(P(n)\) is sometimes true. The negation would say \(P(n)\) is never true which is equivalent to saying \(P(n)\) is always false.
    The statement \(\forall n (\neg P(n))\) says \(\neg P(n)\) is always true which is equivalent to saying \(P(n)\) is always false.
    Thus \(\neg(\exists n ~ P(n)) \equiv \forall n (\neg P(n))\text{.}\)
By Theorem 5.2.24, to prove that a universally quantified statement is false, all it takes is one example where it is false. There is a special name for an example that shows that a universally quantified statement is false.

Definition 5.2.26 Counterexample.

A counterexample is an example where a universally-quantified statement is false. For example, a counterexample to the false statement “Every square integer has exactly three positive divisors” from Activity 5.1.A (d) is the integer 16 because \(16=4^2\) is a square, but 16 has five positive divisors: 1, 2, 4, 8, and 16.
Practice finding counterexamples.

Activity 5.2.E Counterexamples.

Each of the following universally quantified statements is false. Find a specific counterexample to each statement. Hints: It might help to write the negation. Make sure to use DeMorgan’s Laws Theorem 5.1.23 if the statement involves “and” or “or”.
  1. Every integer is divisible by three.
  2. No integer is divisible by three and five.
  3. Any integer is divisible by three or five.
  4. Every prime is odd.
  5. Any composite is even.
  6. Each integer has at least two positive divisors.
  7. No integer has more than five positive divisors.
While a counterexample is enough to prove that a universally quantified statement is false, to prove that an existentially quantified statement is false, we have to prove that a universally quantified statement is true using Theorem 5.2.18.

Subsection 5.2.F Exercises

Subsubsection Exercises for 5.2.A The Game SET!

1. Practice.

Play the game SET™. Invite friends to join you or play on your own. Note that once someone finds a SET, those three cards are removed and replaced by three new cards, which is how the in-person game works. Play for at least 15 minutes and tell me how that went for you.

2. Understand.

Try to solve the Daily SET Puzzle . Note that each time you find a SET, it is recorded in a table on the side. There will be exactly six different SETs you can find. Cards may be repeated in different SETs. You have to wait until the next day to try it again. Try to solve this Daily Puzzle for at least 15 minutes (or until you solve it) and tell me how that went for you.

3. Explore.

A plane is a collection of four cards that they can be grouped in two pairs where each pair is “missing” the same third card to create a SET. Give an example of a plane whose missing card is 2SPO shown in Figure 5.2.2.

4. Explore.

 
  1. Create a deal of eight purple cards that does not contain any SET. Briefly justify why there is no SET.
  2. Create a deal of 12 cards that does not contain any SET. Briefly justify why there is no SET. Hint: Use at least two different colors.

5. Explore.

 
  1. Given one card, how many different SETs could it be in? Justify your answer. Caution: It is easy to count each SET twice by mistake. If so, just divide by two to get the correct count.
  2. How many different SETs could be made from cards in the deck (not all at the same time). Explain your reasoning. Caution: It is easy to over count by mistake. If so, figure out what to divide by to get the correct count.

Subsubsection Exercises for 5.2.B Quantifiers

6. Practice.

Consider the graph \(G\) drawn in Figure 5.2.34. Recall that a leaf is a vertex with degree one. For each statement about \(G\text{,}\) identify a word or phrase that indicates a quantifier and decide if each statement is true or false. Briefly justify your answer.
Figure 5.2.34. The graph \(G\) for Section 5.2 Exercise 6.
  1. There is a vertex of degree four in \(G\text{.}\)
  2. No vertex in \(G\) has degree two.
  3. Every degree leaf in \(G\) is adjacent to a degree four vertex.
  4. Some degree three vertices in \(G\) are adjacent to a leaf.
Check.
  1. “There is” indicates an existential quantifier. The statement is true. For example, the vertex \(s_2\) has degree four.
  2. Hint: “No” indicates a universal quantifier.
  3. Hint: The leaves are \(s_1\) and \(s_2\text{.}\)

7. Practice.

For each statement, identify a word or phrase that indicates a quantifier and decide if each statement is true or false. Briefly justify your answer.
  1. The integers \(n\) and \(n+1\) are always coprime.
  2. Sometimes, the integers \(n\) and \(n+2\) are coprime.
  3. The integers \(n\) and \(n+3\) are never coprime.
Check.
  1. “Always” indicates a universal quantifier. The statement is true. We proved it in Activity 5.1.E.
  2. Hint: It is true.
  3. Hint: It is false.

8. Practice.

For any integer \(n\text{,}\) \(S(n)\) is the statement “\(n^2=n\)”. Decide if each statement is true or false. Briefly justify your answers.
  1. \(\displaystyle S(1)\)
  2. \(\displaystyle S(-1)\)
  3. \(\displaystyle S(2)\)
  4. \(\displaystyle S(0)\)

9. Practice.

For any integer \(n\text{,}\) the statement \(T(n)\) means that \(n^2>n\text{.}\) Decide if each statement is true or false. Briefly justify your answers.
  1. \(\displaystyle \forall n ~ T(n)\)
  2. \(\displaystyle \exists n ~ T(n)\)
  3. \(\displaystyle \exists n ~ \neg T(n)\)
Check.
  1. Hint: You can find an example of an integer \(n\) with \(n^2=n\text{.}\)
  2. True. For example \(3^2>3\text{.}\)
  3. Hint: True.

10. Understand.

For any integer \(n\text{,}\) the statement \(S(n)\) means that \(n\) is greater than six and \(E(n)\) means that \(n\) is less than 11. For what value(s) of \(n\text{,}\) if any, is each statement true? Report your answer as a list, using \(\ldots\) to indicate an infinite set. No explanation required.
  1. \(\displaystyle S(n) \land E(n)\)
  2. \(\displaystyle \neg S(n)\)
  3. \(\displaystyle \neg S(n) \land \neg T(n)\)
  4. \(\displaystyle S(n) \oplus E(n)\)
  5. \(S(n) \lor E(n)\) (think!)

11. Recap.

Do you know …
  1. What the symbols \(\forall\) and \(\exists\) stand for?
  2. Which common words indicate an existential or universal quantifier?
  3. Whether a statement with “no” or “none” is universally quantified or existentially quantified?
  4. When a statement of the form \(\forall n ~ P(n)\) is true and when it is false?
  5. When a statement of the form \(\exists n ~ P(n)\) is true and when it is false?

12. Explore.

Give an example of predicates \(P(n)\) and \(Q(n)\) such that \(\forall n (P(n) \lor Q(n))\) is true, but \((\forall n~ P(n)) \lor (\forall n~ Q(n))\) is false.

13. Explore.

The predicate \(F(a,b)\) means that person \(a\) follows person \(b\) on social media.
  1. Write as a sentence: \(\forall a ~ F(a, \text{ Selena Gomez } )\)
  2. Write as a sentence: \(\exists b ~ F(\text{ Selena Gomez } , b)\)
  3. Explain the difference between \(\forall a ~ \exists b ~ F(a,b)\) and \(\exists b ~ \forall a ~ F(a,b)\text{.}\)
Check.
  1. Everybody follows Selena Gomez on social media.
  2. Hint: Your answer should be different from (a).
  3. Hint: Try using words “everybody” and “somebody”.

Subsubsection Exercises for 5.2.C Proof Formats: Quantified Statements

14. Practice.

Use Theorem 5.2.14 to prove each of the following statements.
  1. There is a prime greater than 20.
  2. There is a prime that divides 20.
  3. Some bit strings have length 20.
  4. There exists a graph with 20 vertices.
Check.
  1. Proof. Consider \(n=23\text{.}\) Note that \(23 > 20\) and 23 is prime because \(2 \nmid 23\text{,}\) \(3 \nmid 23\text{,}\) and \(\sqrt{23} \lt 5\text{.}\) (It is okay if you just wrote “23 is prime”.) Therefore, there is a prime greater than 20, namely 23.
  2. Hint: \(2 \mid 20\text{.}\)
  3. Hint: Find a bit string of length 20.
  4. Hint: Use a standard graph with 20 vertices.

15. Practice.

In the graph \(G\) drawn in Figure 5.2.44, prove that every vertex in \(G\) has odd degree by checking every example, as in Example 5.2.16.
Figure 5.2.44. The graph \(G\) in Section 5.2 Exercise 15.
Check.
Hint: Copy and complete Table 5.2.45.
Table 5.2.45. Checking that every vertex of the graph \(G\) from Figure 5.2.44 has odd degree
vertex degree odd?
\(a\)
\(b\)
\(c\)
\(d\)
\(e\) 3 yes
\(f\)

17. Recap.

Do you know …
  1. How to prove that a universally quantified statement is true?
  2. How to prove that an existentially quantified statement is true?

Subsubsection Exercises for 5.2.D Proof Formats: Mixed Quantifiers

Subsubsection Exercises for 5.2.E Negating Quantified Statements and Counterexamples

20. Practice.

Each of the following statements is false. Provide a counterexample.
  1. Any graph with five vertices has five edges.
  2. No graph has more edges than vertices.
  3. A graph with five vertices is the cycle \(C_5\) or the complete graph \(K_5\text{.}\)
  4. Every graph is regular. Recall that a graph is regular if every vertex has the same degree.
  5. No graph has chromatic number greater than four.
Check.
  1. Hint: Your graph should have five vertices but not five edges.
  2. Hint: Your graph should have more edges than vertices.
  3. Hint: Your graph should have five vertices and not be \(C_5\) or \(K_5\text{.}\)
  4. Hint: Your graph should have at least two different numbers in its degree sequence.
  5. Hint: Look at Example 3.3.6 (c). That is not a counterexample, but you can generalize to find a counterexample.

21. Practice.

Each of the following statements is false. Provide a counterexample.
  1. Every prime is odd.
  2. Any composite is even.
  3. No two composites are coprime.
  4. Every integer has a prime divisor.
Check.
  1. Hint: There is only one even prime.
  2. Hint: One counterexample is \(15=3 \times 5\text{.}\) Find a different counterexample.
  3. Hint: Find two composites that are not coprime.
  4. Hint: The number 1 is not prime.

22. Understand.

Each of the following statements is false. Provide a counterexample.
  1. All bit strings of length six have an even number of \(\bs{0}\) s.
  2. No bit string of length seven can both begin and end with \(\bs{00}\text{.}\)
  3. Every bit string of length five begins or ends with \(\bs{0}\text{.}\)

23. Understand.

Each of the following statements is false. Write the negation. Hint: The negation should be true. Another hint: Use DeMorgan’s Laws Theorem 5.1.23.
  1. Every integer is divisible by three and five.
  2. Any integer is divisible by three or five.
  3. No integer is divisible by three and five.
  4. Some integer is divisible by three but not divisible by six.
Check.
  1. Some integers are divisible by three or five.
  3. Hint: “No” indicates the universal quantifier.
  4. Hint: Try starting the negation with “No”.

24. Understand.

 
  1. Give an example to prove that the following statement is true: There is a 3-letter word where there are 3! ways to arrange the letters (not all of which have to be real words).
  2. Give a counterexample to prove that the following statement is false: For any 3-letter word, there are 3! ways to arrange the letters (not all of which have to be real words.)

25. Recap.

Do you know …
  1. Why the negation of a universally quantified statement is an existentially quantified statement, and vice versa?
  2. How to prove that a universally quantified statement is false?
  3. How to prove that an existentially quantified statement is false?
  4. What a counterexample is?
  5. Which theorem can help us negate a statement involving “and” or “or”?

26. Explore.

Let \(G\) be a graph with \(n \ge 2\) vertices.
  1. What is the largest possible degree of a vertex in \(G\text{?}\) Hint: Your answer should involve \(n\text{.}\)
  2. Could \(G\) have a vertex of degree zero and a vertex of degree \(n-1\text{?}\) Explain.
  3. State the negation of the statement: There are at least two vertices in \(G\) that have equal degree.
  4. Use contradiction to prove that there are at least two vertices in \(G\) that have equal degree. Hint: Consider what would happen if the \(n\) vertices each had different degrees.

27. Explore.

Each of the following statements is false. Provide a counterexample.
  1. Consider the statement \(\fn{gcd}(a,2b) = \fn{gcd}(a,b)\text{.}\) Give an example of integers \(a\) and \(b\) where the statement is true and give a counterexample to show the statement is not true in general.
  2. Consider the statement \(\fn{gcd}(a,2b) = 2\fn{gcd}(a,b)\text{.}\) Give an example of integers \(a\) and \(b\) where the statement is true and give a counterexample to show the statement is not true in general.
  3. When is \(\fn{gcd}(a,2b) = \fn{gcd}(a,b)\) and when is \(\fn{gcd}(a,2b) = 2\fn{gcd}(a,b)\text{?}\) Your answers should involve \(a\) and \(b\text{.}\) Hint: Prime factorization.
PrevTopNext