Math 310

These problems are provided to help you study. The presence of a
problem on this handout does not imply that there *will* be a
similar problem on the test. And the absence of a topic does not
imply that it *won't* appear on the test.

1. Premises:

Prove: P.

2. Premises:

Prove: C.

3. Premises:

Prove: R.

4. Let x and y be positive real numbers. Prove that if , then either or .

5. Prove that the following inequality has no real solutions:

6. * Rolle's theorem* says that if f is a
continuous function on the interval , f is differentiable on
the interval , and , then
for some number c such that .

Use Rolle's theorem to prove that if , then does not have more than one root.

7. Prove that if an integer is squared and divided by 3, the remainder can't be 2. [Hint: Take cases. If the given integer is divided by 3, it leaves a remainder of 0, 1, or 2.]

8. Prove that if n is an integer, then is not divisible by 3.

9. Prove that if , then

10. Prove that for all , .

11. Prove that if and , then is divisible by . Note: This means that there's a polynomial in x and y with integer coefficients such that .

12. Prove that for all .

13. Prove that if , then

14. A sequence of integers is defined by

Prove that for all ,

15. Prove that if , then

16. (a) What would be a counterexample to the statement "Every dog likes cheese"?

(b) Give a counterexample to the following statement: "For all integers a, b, and c, if a divides , then a divides b or a divides c."

17. Give a specific counterexample which shows that the following
equations are *not* algebraic identities.

(a) " ".

(b) " ".

18. Give counterexamples to the following statements:

(a) "If and , then ."

(b) "If and and , then ."

19. Give a counterexample to the following statement: "If , then ."

20. Suppose the universe is , and:

,

,

.

(a) List the elements of .

(b) List the elements of .

(c) List the elements of .

(d) List the elements of .

21. Construct Venn diagrams for the following sets:

(a)

(b)

22. What sets are represented by the shaded regions in the following Venn diagrams?

23. (a) List the elements of the set .

(b) List the elements of the set .

(c) Is a subset of ? Why or why not?

24. (a) Suppose . List the elements of .

(b) How many subsets does the set have?

25. (a) Suppose and . List the elements of .

(b) Are the sets and equal? Are the ordered pairs and equal?

(c) Suppose and . Find and .

26. Let A, B, and C be sets. Prove that

27. Let A, B, and C be sets. Prove that

28. Let A and B be sets. Prove that

29. Let A and B be sets.

(a) Prove that and .

(b) Prove that if and only if .

30. Recall that

Prove that .

31. Recall that

Prove that .

32. Suppose and . List the elements of and .

33. Give a specific example of two sets A and B for which .

34. Prove using the limit definition that

35. Prove using the limit definition that

1. Premises:

Prove: P.

2. Premises:

Prove: C.

3. Premises:

Prove: R.

4. Let x and y be positive real numbers. Prove that if , then either or .

Suppose that x and y are positive real numbers, and . I want to prove that either or .

I will give a proof by contradiction. The negation of "Either or " is " and ". So suppose on the contrary that and .

Since and x is positive, . Since and y is positive, . Therefore,

This contradicts my assumption that . Therefore, either or .

5. Prove that the following inequality has no real solutions:

I'll use proof by contradiction. Suppose that is a solution to the
inequality. I'll rewrite the inequality using basic algebra, the idea
being to try to *complete the squares*:

The last inequality gives a contradiction: The two square terms must be greater than or equal to 0, so adding 5 makes the left side strictly positive. However, the inequality says that the left side is negative.

This contradiction shows that the original inequality has no solutions.

6. * Rolle's theorem* says that if f is a
continuous function on the interval , f is
differentiable on the interval , and , then for some number c such that .

Use Rolle's theorem to prove that if , then does not have more than one root.

Suppose on the contrary that f has more than one root. Then f must
have *at least two different roots*, say a and b. Thus,
and . I'll assume that ; if it's the other way
around, just switch their names.

Now f is a polynomial, so it's differentiable and continuous everywhere. In addition, . Therefore, Rolle's theorem applies, and I know that for some c such that .

On the other hand,

Reason: The first two term are positive numbers multiplied by even powers of x, so they're both greater than or equal to 0. The last term k was given to be greater than 0.

Therefore, can't be equal to 0, which contradicts the existence of a number c where .

Therefore, f does not have more than one root.

7. Prove that if an integer is squared and divided by 3, the remainder can't be 2.

Let n be an integer. I want to show that does not leave a remainder of 2 when it's divided by 3.

When n is divided by 3, it can leave a remainder of 0, 1, or 2. I consider cases.

If n leaves a remainder of 0 when it's divided by 3, then for some integer k. Hence,

Therefore, leaves a remainder of 0 when it's divided by 3.

If n leaves a remainder of 1 when it's divided by 3, then for some integer k. Hence,

Therefore, leaves a remainder of 1 when it's divided by 3.

Finally, if n leaves a remainder of 2 when it's divided by 3, then for some integer k. Hence,

Therefore, leaves a remainder of 1 when it's divided by 3.

I've exhausted all the cases. Hence, if n is an integer, then does not leave a remainder of 2 when it's divided by 3.

Note: This kind of problem is much easier to do using * modular arithmetic*.

8. Prove that if n is an integer, then is not divisible by 3.

Every integer n can be written in one of the forms , , or , where q is an integer.

* Case 1.* If , then

In this case, leaves a remainder of 2 when it's divided by 3.

* Case 2.* If , then

In this case, leaves a remainder of 2 when it's divided by 3.

* Case 3.* If , then

In this case, leaves a remainder of 1 when it's divided by 3.

Therefore, if n is an integer, is not divisible by 3.

9. Prove that if , then

* Case 1.* .

In this case

So

Therefore, .

* Case 2.* .

In this case

So

Now

Therefore, .

* Case 3.* .

In this case

So

Therefore, .

Since the result holds in all three cases, and the cases cover all , it follows that for all .

10. Prove that for all , .

(It is *not* a proof to draw the graph!)

I'll take cases to get rid of the absolute values.

My cases will be , , and . This accounts for all .

Suppose that . Then , and since , . Therefore,

Now

Hence, the result is true for .

Suppose that . Since , . Since , . Therefore,

Now

Hence, the result is true for .

Finally, suppose that . This implies that . Moreover, since , . Therefore,

Now

Hence, the result is true for .

Since in all three cases I have , this is true for all .

11. Prove that if and , then is divisible by .

I'll use induction on n.

For , , which is obviously divisible by . For ,

This is also divisible by .

Let , and assume the result is true for all powers less than n. In particular, assume that and are divisible by . I want to prove that is divisible by .

Since and are divisible by , there are polynomials and in the variables x and y such that

I'll use (*) to build the expression that I'm interested in. I'll make an first: Multiply (*) by x:

Next, make the : Multiply (*) by y:

Now add the expressions for and and do some algebra, substituting eventually for :

Both terms on the right side are divisible by , so is divisible by . By induction, is divisible by for all .

12. Prove that for all .

I'll use induction on n. For ,

Let , and suppose the result is true for . Thus, assume that

I want to prove that result for n. Start with the summation for n, "peel off" the term, and use the induction hypothesis:

This proves the result for n, so the result is true for all , by induction.

13. Prove that if , then

For , I have

Hence, the result is true for .

Assume the result for n:

I need to prove the result for :

I have

This proves the result for , so the result is true for all , by induction.

14. A sequence of integers is defined by

Prove that for all ,

For , the formula gives

For , the formula gives

Therefore, the result is true for and .

Assume , and suppose the result holds for . Then

This proves the result for n, so the result holds for all by induction.

15. Prove that if , then

For ,

Thus, , and the result is true for .

Assume that the result is true for n:

I'll prove the result for :

This proves the result for , so the result is true for all by induction.

16. (a) What would be a counterexample to the statement "Every dog likes cheese"?

(b) Give a counterexample to the following statement: "For all integers a, b, and c, if a divides , then a divides b or a divides c."

(a) A counterexample would be a dog who does not like cheese.

(b) Let , , and . Then 12 divides , but 12 does not divide 6 and 12 does not divide 4.

17. Give a specific counterexample which shows that the following
equations are *not* algebraic identities.

(a) " ".

(b) " ".

(a) If and , then

(b) If and , then

18. Give counterexamples to the following statements:

(a) "If and , then ."

(b) "If and and , then ."

(a) (so ), but and . Therefore, .

(b) (so ) and (so ), but , while . Therefore, .

19. Give a counterexample to the following statement: "If , then ."

A counterexample must make the "if-then" statement * false*. An "if-then" statement is false
exactly when the "if" part is true and the "then"
part is false.

If , then . Thus, the "if" part is true. But since , the "then" part is false. Therefore, is a counterexample to the original statement.

20. Suppose the universe is , and:

,

,

.

(a) List the elements of .

(b) List the elements of .

(c) List the elements of .

(d) List the elements of .

(a)

(b)

(c)

(d)

21. Construct Venn diagrams for the following sets:

(a)

(b)

(a)

(b)

22. What sets are represented by the shaded regions in the following Venn diagrams?

There are many possible answers; here are two.

(a)

(b)

23. (a) List the elements of the set .

(b) List the elements of the set .

(c) Is a subset of ? Why or why not?

(a) The elements are a and .

(b) The only element of is .

(c) is not a subset of : b is an element of , but it is not an element of .

24. (a) Suppose . List the elements of .

(b) How many subsets does the set have?

(a)

(b) The set has 9 elements (not 8!), so it has subsets.

25. (a) Suppose and . List the elements of .

(b) Are the sets and equal? Are the ordered pairs and equal?

(c) Suppose and . Find and .

(a)

(b) , because the sets have the same elements. The order in which the elements are listed doesn't matter.

because ordered pairs are equal if and only if their first components are equal and their second components are equal. These two pairs have different first components ( ) and different second components ( ).

(c) First,

Next,

26. Let A, B, and C be sets. Prove that

Let . I must show that .

This proves that .

27. Let A, B, and C be sets. Prove that

I'll show each set is contained in the other.

First, I'll show .

Let . Then or .

Suppose . Then , so and , so . Hence, .

Suppose . If , then , so .

Otherwise, . Now , so . Hence, . Therefore, .

Thus, in every case, so .

Conversely, suppose . Then or .

Suppose . Then , so .

Alternatively, suppose . Then and . Now means or .

In the first case, and give , so .

In the second case, gives .

In every case, , so .

Therefore, .

Here is a more formal layout of the proof, with the logical connectives written explicitly.

This proves that .

28. Let A and B be sets. Prove that

Since the empty set is a subset of every set, I know that .

Next, I'll show that . Taking
elements, I have to show that if , then
. (Actually, I'll show that this conditional
statement is * vacuously* true by showing that
the "if" part is false.)

By proof by contradiction, the statement is false. This makes the conditional statement "if , then " true! Hence, .

Since and , it follows that .

29. Let A and B be sets.

(a) Prove that and .

(b) Prove that if and only if .

(a) Let . Then or (the logical rule is "constructing a disjunction"), so . Therefore, .

Let . Then or (the logical rule is "constructing a disjunction"), so . Therefore, .

(b) Suppose . I want to show .

Let . Then by (a), . Hence, .

Suppose . I want to show .

I will show each of the sets and B is contained in the other.

First, by (a) .

On the other hand, let . This means that either or . In the first case, . In the second case, . So in either case, . This proves .

This proves that .

30. Recall that

Prove that .

I'll show that and .

Suppose . Then by the definition of intersection, and . By the interval definition, this means that and and and .

In particular, and , so by the interval definition .

This proves that .

Conversely, suppose , so by the interval definition and .

First, . Together with , this means by the interval definition that .

Second, . Together with , this means by the interval definition that .

By the definition of intersection, .

This proves that .

Therefore, .

31. Recall that

Prove that .

Suppose . Then by the definition of union, or .

If , then by the interval definition and . Now , so . Since and , by the interval definition .

If , then by the interval definition and . Now , so . Since and , by the interval definition .

This proves that .

For the opposite inclusion, suppose . By the interval definition, and . Consider two cases.

First, suppose . Since , it follows that . Since and , by the interval definition . By the definition of union, .

Second, suppose . Now , so . Since and , by the interval definition . By the definition of union, .

This proves that .

Hence, .

32. Suppose and . List the elements of and .

33. Give a specific example of two sets A and B for which .

For example, let and . Then

The two sets are not the same.

34. Prove using the limit definition that

Let . Set . If , then I have

Hence,

Since , I have , so I may divide both sides by , then insert absolute values signs:

This proves that .

35. Prove using the limit definition that

Let . Set . If , then I have

Hence,

Sine , I have , so I may multiply both sides by to get

Again, since , I may insert absolute value signs on the right and obtain

This proves that

*He who has overcome his fears will truly be free.* -
*Aristotle*

Copyright 2020 by Bruce Ikenaga