# Review Sheet for the Final

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. (a) Negate the following statement, simplifying so that only simple statements are negated:

(b) Negate the following statement, simplifying so that only simple statements are negated:

(c) Negate the following statement, simplifying so that only simple statements are negated, and write your answer in words:

"Every soccer fan either likes pizza or dislikes writing proofs."

2. (a) Prove or disprove by specific counterexample: If x is rational and y is irrational, then is irrational.

(b) Prove or disprove by specific counterexample: If x is rational and y is rational, then is irrational.

3. Show that is a tautology.

4. Prove that .

5. Prove that .

6. Prove: .

Premises:

7. Prove that if , then

8. Show that there do not exist real numbers x and y such that

9. The Fibonacci numbers are defined recursively by

Prove that for ,

10. Prove that if , then

11. Prove that the sum of the cubes of three consecutive positive integers is divisible by 9.

12. A sequence of integers is defined by

Prove that

13. Prove that if , then

14. Suppose that A is a set and . Which set has more elements --- or ?

15. Let A and B be sets. Prove that .

16. Let A, B, and C be sets.

(a) Draw a general Venn diagram for .

(b) Prove that .

17. Prove that .

18. Prove that .

19. In each case, give a counterexample to the statement.

(a) "If , then ."

(b) "If , then ."

(c) "If a, b, and c are positive integers, then ."

20. Bonzo McTavish observes that if n is an integer, then

He concludes that is either 1 or 2. Can ? Why or why not?

21. Define by

Prove by example that f is neither injective nor surjective.

22. Define by

Prove that g is bijective by:

(a) Proving that g is injective and surjective.

(b) Constructing an inverse for g.

23. Define by

Prove that h is surjective.

24. Define by

Prove that f is injective.

25. Define by

Prove that f is surjective.

26. Prove that has the same cardinality as .

27. Prove by constructing a bijection that .

28. Prove that has the same cardinality as .

29. Define a relation on by

Take each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

30. Consider the equivalence relation defined by writing to mean on the set

List the elements of the equivalence classes.

31. A relation is defined on by

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom doesn't hold, give a specific counterexample.

32. Define a relation on by

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

33. Define a relation on by

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

34. Prove that the square of an odd number leaves a remainder of 1 when it's divided by 4.

35. Prove that if n is an integer, then does not leave a remainder of 1 or 2 when it's divided by 5.

36. Prove that if and neither m nor n is divisible by 3, then is not divisible by 3.

37. Compute .

38. Using the fact that for some , prove:

(a) If d is a common divisor of a and b, then .

(b) If and , then .

39. If and , does it follow that ?

40. Prove that if , then .

41. Prove that if , then .

42. Prove that if , then .

43. Prove that if , then

[Hint: Find the absolute min of .]

44. Use the limit definition to prove that

45. Phoebe Small has proved that

But Bonzo McTavish is confused. "The point 0.9 is in . But for , the interval is , and that doesn't contain 0.9." Does Bonzo have a valid objection?

46. Prove that .

# Solutions to the Review Sheet for the Final

1. (a) Negate the following statement, simplifying so that only simple statements are negated:

(b) Negate the following statement, simplifying so that only simple statements are negated:

(c) Negate the following statement, simplifying so that only simple statements are negated, and write your answer in words:

"Every soccer fan either likes pizza or dislikes writing proofs."

(a)

(b)

(c) Let

mean "x is a soccer fan."

mean "x likes pizza."

means "x likes writing proofs."

The original statement is . Negate it:

The last statement says: "There is a soccer fan who dislikes pizza and likes writing proofs."

2. (a) Prove or disprove by specific counterexample: If x is rational and y is irrational, then is irrational.

(b) Prove or disprove by specific counterexample: If x is rational and y is rational, then is irrational.

(a) The claim is false. is rational and is irrational, but is rational.

(b) Suppose x is rational and y is rational. Then

So

Since , it follows that is rational.

3. Show that is a tautology.

Since the column for contains only T's, the statement is a tautology.

4. Prove that .

Let . I want to find such that if , then .

Here's the scratch work. I want . I can use to control . To control , assume . Then , so . Then , so .

Now if I can make , then gives . But is equivalent to , and I could get this if .

Putting my two requirements on together, I'll take .

Here's the real proof. Suppose . Take . If , then

Therefore, .

Also, . Since all the numbers involved are positive, I can multiply inequalities to get

This proves that .

5. Prove that .

Let . I must find such that if , then .

Here's the scratch work. I want

As usual, I suppose . Then gives , so , and . But now I have a problem: I want to estimate how big could be, but I can't take reciprocals in ! In fact, gets infinitely large on this interval.

So I rewind and try again with a smaller . Suppose . Then gives , so , and . Taking reciprocals gives , so .

If I had , then gives , which is what I want. I could get if , and this in turn I could get if I had .

Thus, I ought to take .

Now here's the proof. Take . Since , I get

Therefore, .

This proves that .

6. Prove: .

Premises:

7. Prove that if , then

Note that

Case 1: .

Hence, .

Case 2: .

Now

Hence, .

Case 3: .

Hence, .

This proves for all .

8. Show that there do not exist real numbers x and y such that

Suppose that for ,

Complete the square in x and in y:

Each of the squared terms on the left are nonnegative, so the left side must be greater than or equal to . Therefore, it can't be equal to 0. This contradiction show that there do not exist such that .

9. The Fibonacci numbers are defined recursively by

Prove that for ,

For ,

Thus, the result is true for .

Assume , and suppose the result is true for n. I'll prove the result for .

The result for n says that

Adding to both sides, I get

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

10. Prove that if , then

For , the left side is , while the right side is . Thus, the result holds for .

Assume that the result is true for n:

I will prove it for :

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

11. Prove that the sum of the cubes of three consecutive positive integers is divisible by 9.

I'll use induction.

The first three consecutive positive integers are 1, 2, and 3, and

This is divisible by 9.

Take , and assume the result is true for n. In other words, assume that

I want to prove the result for : I want to show that is divisible by 9.

Note that

Thus,

Hence,

is divisible by 9 by the induction hypothesis, and is divisible by 9. Hence, the sum is divisible by 9. This proves the result for , so the result is true for all , by induction.

12. A sequence of integers is defined by

Prove that

Use induction. For , the formula gives

For , the formula gives

Now assume the formula holds for all . In particular, it is true for and for . Then

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

13. Prove that if , then

For ,

The result holds for .

Assume that and the result is true for n:

I will prove the result for :

Note that and follow from .

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

14. Suppose that A is a set and . Which set has more elements --- or ?

, while . So has more elements.

15. Let A and B be sets. Prove that .

I want to prove that is empty. Suppose on the contrary that .

Since , I have and . Since , I have and . But in particular, I have the contrary assertions " " and " ". This contradiction shows that .

16. Let A, B, and C be sets.

(a) Draw a general Venn diagram for .

(b) Prove that .

(a)

(b) Before starting the proof, I'll prove an easy lemma.

Lemma. if and only if or .

Proof. Now means . By definition of complement, this is equivalent to . By DeMorgan, this is equivalent to or .

Let . By definition of complement, and . By the lemma, gives or .

Suppose first that . Since , the definition of complement gives .

Next, suppose . Since , the definition of intersection gives .

By the definition of union, . This proves that .

Conversely, suppose . By definition of union, I have or .

Suppose first that . By definition of intersection, and . Now " or " is true, so by the lemma . By definition of complement, .

Next, suppose . By definition of complement, and . Now " or " is true, so by the lemma . By definition of complement, .

In both cases, . This proves that .

Hence, .

Here is an alternate proof written in a different style:

Therefore, .

17. Prove that .

Let . Then or .

Suppose . Then

Hence, .

Suppose . Then

Hence, .

In both cases, .

Thus, .

Conversely, let , so . Thus, and . I'll consider two cases.

Suppose . Then

Hence, .

Suppose . Then

Hence, .

This proves that . Hence, .

18. Prove that .

Let . I'll show that .

Since , the definition of intersection gives and . The definition of intervals gives and , so and and and .

In particular, and give , so .

Next, let . I'll show that .

Since , I have . First,

So .

Next,

So .

By definition of intersection, .

Since and are contained in each other, I have .

19. In each case, give a counterexample to the statement.

(a) "If , then ."

(b) "If , then ."

(c) "If a, b, and c are positive integers, then ."

(a) If , then , but , so .

(b) , but .

(c)

20. Bonzo McTavish observes that if n is an integer, then

He concludes that is either 1 or 2. Can ? Why or why not?

The equation only shows that could be either 1 or 2. It does not mean that both of these numbers are possible.

In fact,

Since divides both and , it must divide ; since is positive, .

Thus, is never equal to 2.

21. Define by

Prove by example that f is neither injective nor surjective.

Since f takes the different inputs and to the same output , f is not injective.

, so the second component of cannot be negative. Therefore, for no does . Hence, f is not surjective.

22. Define by

Prove that g is bijective by:

(a) Proving that g is injective and surjective.

(b) Constructing an inverse for g.

(a) Suppose that . This means that

Equating the second components, I get , so . Equating the first components gives . But , so , and therefore .

Hence, , which proves that g is injective.

Next, take . I want to find such that .

I'll work backwards, then check by plugging back in. I want

The second component equation gives . Plugging this into the first component equation gives

Thus, .

Now I'll check that this works:

This proves that g is surjective.

(b) To guess an inverse, I use the same approach I used above to show that g is surjective. I'll repeat it so you can see how the whole proof would look like in this case.

I have , and I want a formula for . This means I want p and q in terms of a and b. Working backwards,

So

The second equation gives . Plugging this into the first equation and solving gives . So define

Now check that g and really are inverses:

23. Define by

Prove that h is surjective.

Let . I need to find such that .

I'll work backwards to guess formulas for x and y in terms of a and b, then confirm that my guesses work.

I want , so

The second equation gives ; plugging this into the first equation, I get

Now I'll check that these formulas for x and y work:

This proves that h is surjective.

24. Define by

Prove that f is injective.

It is too hard to do this directly, so I'll use calculus. Suppose and . There is no harm in assuming --- if instead , then just rewrite the rest of the proof with a and b switched.

Since f is differentiable, I can apply Rolle's Theorem to f on the interval to conclude that for some c in .

But

Now for all x, I have , , and . So

This contradicts . It follows that , so f is injective.

25. Define by

Prove that f is surjective.

Let . I must show that for some .

Note that

Therefore, there are numbers a and b such that

Since f is continuous, by the Intermediate Value Theorem there is a number x between a and b such that . Hence, f is surjective.

26. Prove that has the same cardinality as .

consists of all ordered pairs or , where . Thus, looks like two copies of the real line:

I'll use the Schr\"oder-Bernstein theorem.

Define by

If , then , so . Therefore, f is injective.

Define by

g maps the first copy of to and the second copy to . Here's the picture:

To show that g is injective, suppose . I must show that .

First, I'll show that . a and c are each either 0 or 1. If , then one is 0 and the other is 1.

Suppose and . Then

Now

Likewise,

But and contradict the assumption that . Hence, and is impossible.

A symmetrical argument shows that and is impossible.

Therefore, either or .

Suppose . Then

Now , so

Since , it follows that .

A similar argument shows that if , then .

Hence, g is injective.

Therefore, by the Schr\"oder-Bernstein theorem, has the same cardinality as .

27. Prove by constructing a bijection that .

Define by

Note that if , then

Hence, , so f does map into .

Define by

Note that if , then

Hence, , so f does map into .

I have

Hence, f and g are inverses, so they are bijections. Therefore, .

28. Prove that has the same cardinality as .

Define by

Note that if , then

Therefore, , so f does map into .

If , then

Therefore, f is injective.

Define by

If , then

Therefore, , so g does map into .

If , then

Therefore, g is injective.

By the Schr\"oder-Bernstein theorem, has the same cardinality as .

29. Define a relation on by

Take each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

The graph of this relation is pretty complicated; I'll give it even though it's not necessary for the problem, since it's kind of interesting.

In this contour plot, the light areas represent points where is positive; dark areas represents points where the function is negative. Thus, if a point is in a light area, then .

For reflexivity, note that for all . Therefore, for all , and the relation is reflexive.

Suppose . Then , so , and hence . Therefore, is symmetric.

On the other hand,

But

Hence, is not transitive. Thus, is not an equivalence relation.

30. Consider the equivalence relation defined by writing to mean on the set

List the elements of the equivalence classes.

31. A relation is defined on by

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom doesn't hold, give a specific counterexample.

If , then

Hence, , and is reflexive.

Suppose . Then

Hence, , and is symmetric.

because .

because .

But , because while . Hence, is not transitive.

32. Define a relation on by

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

If , then , so . Therefore, reflexivity holds.

Take and . and , so and . Thus, and . However, . Therefore, antisymmetry fails.

Suppose that and . This means that

Therefore, , so . Hence, the relation is transitive.

33. Define a relation on by

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

For all , I have , so . The relation is reflexive.

I have , since . I have , since . But . Hence, the relation is not antisymmetric.

Suppose , and and . Then

Hence, , so the relation is transitive.

34. Prove that the square of an odd number leaves a remainder of 1 when it's divided by 4.

Let be an odd number, where . Then

Therefore, when is divided by 4, the remainder is 1.

35. Prove that if n is an integer, then does not leave a remainder of 1 or 2 when it's divided by 5.

I consider the cases mod 5. Since I'm interested in the remainder when is divided by 5, I look at mod 5. Here's the table:

The table shows that never equals 1 or 2 mod 5. This completes the proof.

36. Prove that if and neither m nor n is divisible by 3, then is not divisible by 3.

Since , I have or 2 mod 3. Likewise, since , I have or 2 mod 3.

It follows that , so .

37. Compute .

Use the Euclidean algorithm:

Thus, .

38. Using the fact that for some , prove:

(a) If d is a common divisor of a and b, then .

(b) If and , then .

(a) Write , where . Then and , so .

(b) I'll show that and divide each other. Since they are both positive numbers, it will follow that they're equal.

and , so and . Therefore, is a common divisor of and , so .

On the other hand, I have for some . So . Now and , so

Therefore, .

39. If and , does it follow that ?

No. For example, take , , , and . Then

But .

40. Prove that if , then .

Note that

Now and . From the equation above, it follows that . Hence, .

41. Prove that if , then .

42. Prove that if , then .

Let . Then , and for all x. Thus, f is always increasing. But , so if , then . Hence, if , then , i.e. .

43. Prove that if , then

[Hint: Find the absolute min of .]

Following the hint, I take . Note that the domain of f is . The derivative is

The only critical point is .

The function decreases for and increases for . is a local min; since it's the only critical point, it's an absolute min.

Now . Since this is the absolute min, for all . In other words, for , or for .

Remark. Many inequalities involving real functions can be proved using calculus in this way by finding absolute maxima or minima.

44. Use the limit definition to prove that

Let . Set . Suppose that . Note that since , it follows that , so . Then

This proves that .

45. Phoebe Small has proved that

But Bonzo McTavish is confused. "The point 0.9 is in . But for , the interval is , and that doesn't contain 0.9." Does Bonzo have a valid objection?

Bonzo is confused. For 0.9 to be in , it does not need to be in all the intervals in the union --- it only has to be in at least one of the intervals.

In fact, . (Can you prove that if , then ?)

And Phoebe's claim is correct --- see if you can prove it.

46. Prove that .

Let , so . Since for all n, I have

Therefore, for all n, so .

This proves that .

Conversely, suppose . Then for all n, so

Suppose that . Note that

In the limit definition, let . Then there is a number M such that if ,

Then

But this contradicts the fact that for all n.

Therefore, . Since , I have , and so . This proves that .

Hence, .

The best thing for being sad is to learn something. - Merlyn, in T. H. White's The Once and Future King

Contact information