Review Sheet for Test 3

Math 310

11-18-2017

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. Let n be a positive integer, and let , , ..., , and B be sets. Prove that

2. Consider the set

Write S as a single interval in the real line and prove that your result is correct.

3. Prove that

4. Prove that

5. Define a relation on by

Consider each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom fails, give a counterexample.

6. Define a relation on by

Consider each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom fails, give a counterexample.

7. Let . A equivalence relation is defined on by

List the elements of the equivalence classes of under this relation.

8. For each positive integer n, define a subset of by

Consider each axiom for a partition. If the axiom holds, prove it; if the axiom fails, give a counterexample.

9. Consider the relation on whose graph is shown below. Is an equivalence relation?

10. A relation is defined on by

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

11. Prove that if n is a prime number and , then or .

12. Prove that if , then is either 1 or 2. Show by specific example that both cases can occur.

13. Compute . (Don't factor the numbers!)

14. Prove that if , then .

15. (a) Let m and n be integers. Prove that

(b) Prove that if , then .

16. Show that if , then does not leave a remainder of 2 when it is divided by 5.

17. (a) Find .

(b) Show that 8 does not have a multiplicative inverse mod 10.

18. Let m and n be integers, and suppose . Prove that implies .

19. Suppose . Is it necessarily true that ?

20. Prove that if , then is not divisible by 5.

21. The following functions take real numbers as inputs and produce real numbers as outputs. Taking the domain to be the largest set of valid inputs, find the domain and the range for each function.

(a) .

(b) .

(c) .

22. Define by . Prove directly using the definition that f is injective.

23. Define by . Prove that f is not injective.

24. Define by . Prove that f is injective.

25. Define by . Prove that directly using the definition that f is surjective.

26. Define by . Prove that f is surjective.

27. Define by . Prove that f is injective. Is f surjective?

28. Define by . Prove that f is not injective, but that f is surjective.

29. Define by . Prove that f is injective, but is not surjective.

30. Define by

Is f surjective? Why or why not?

31. Define by

Prove that f is bijective by constructing an inverse.

32. Let and be functions. Suppose f and g are injective. Prove that the composite is injective.

33. Give a specific example of sets X, Y, and Z and functions and such that g is surjective, but the composite is not.

34. Prove that the following sets have the same cardinality by constructing a bijection from A to B:

35. Prove that has the same cardinality as by constructing a bijection from to .

36. Prove that has the same cardinality as by constructing a bijection from to .

Solutions to the Review Sheet for Test 3

1. Let n be a positive integer, and let , , ..., , and B be sets. Prove that

For ,

The result is true for .

The induction step will also need the result for , so I'll prove it here. For , the result says that

Now I'll prove the general result by induction. Take , and suppose the result is true for . This means that

I want to prove that

The proof proceeds in the usual way by "splitting off" the piece and applying the induction hypothesis:

(Notice that the second equality used the result for , which is why I needed to prove it first.) I've proved the result for n; hence, the result is true for all by induction.

2. Consider the set

Write S as a single interval in the real line and prove that your result is correct.

I'll show that .

First, notice that for all , since . This implies that .

Next, I'll show that . Take , so . Since , I can find an integer such that . Then , so . Hence, . This proves that .

Since and , it follows that .

3. Prove that

Let , so . Note that for , I have . Hence, for , and for . Therefore, . This proves that .

Conversely, let . This means that for all , so for all .

Suppose . I have

Hence, for some ,

It follows that . Since , I have , and hence . Thus, .

This proves that .

4. Prove that

The union on the left is .

Let . Then for some , I have . This means that

Hence, . This proves that .

Conversely, suppose , so . Now

Therefore, there is an such that . Now I have

This implies . This proves that .

Hence, .

5. Define a relation on by

Consider each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom fails, give a counterexample.

Reflexivity does not hold: For example, , so .

If , then . Hence, , and so . Therefore, symmetry holds.

Transitivity does not hold. For example, , since ; , since . However, , since .

6. Define a relation on by

Consider each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom fails, give a counterexample.

, but . Therefore,

The relation is not reflexive.

Suppose . Then

Therefore, . Hence, the relation is symmetric.

, since

, since

However, , since

Therefore, the relation is not transitive.

7. Let . A equivalence relation is defined on by

List the elements of the equivalence classes of under this relation.

There are 16 points in :

Two points are in the same equivalence class if the sums of their components are equal mod 4. For example, , because

The four equivalence classes are:

8. For each positive integer n, define a subset of by

Consider each axiom for a partition. If the axiom holds, prove it; if the axiom fails, give a counterexample.

If x is a real number, there is a positive integer n such that --- and hence, . Every point of is in one of the 's.

On the other hand, for every positive integer n, so for all n. There are points which are in more than one --- in fact, in infinitely many of the 's.

Thus, the 's do not form a partition of .

9. Consider the relation on whose graph is shown below. Is an equivalence relation?

The relation is reflexive (all the diagonal points are filled in) and symmetric (the graph is symmetric about the diagonal). However, it isn't transitive: and , but . Therefore, the relation is not an equivalence relation.

10. A relation is defined on by

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

It may be helpful if you label the pairs by position:

Also, remember that

Let . Since , it follows that . Hence, is reflexive.

Suppose and . Then

Therefore, . Hence, is symmetric.

Note that

However, , because

Therefore, is not transitive.

11. Prove that if n is a prime number and , then or .

Every integer is congruent mod 4 to 0, 1, 2, or 3.

Suppose n is prime and . Since n is an integer, n is congruent mod 4 to 0, 1, 2, or 3.

Suppose . Then , contradicting the fact that n is prime.

Suppose . Then , where . Thus, , so n is even. Since , this contradicts the fact that n is prime.

It follows that or . Both cases can occur, since and (for example).

12. Prove that if , then is either 1 or 2. Show by specific example that both cases can occur.

Dividing by , I have

Now divides both and , so it divides . But the only positive integers which divide 2 are 1 and 2. Hence, is either 1 or 2.

If , I have and , and .

If , I have and , and .

These examples show that both cases can occur.

13. Compute . (Don't factor the numbers!)

Hence, .

14. Prove that if , then .

and , so

Since , it follows that .

In general, if a linear combination of two integers is equal to 1, the two integers are relatively prime (their greatest common divisor is 1).

15. (a) Let m and n be integers. Prove that

(b) Prove that if , then .

(a) First, and . So . Since divides both and n, it's a common divisor of and n. Therefore, it must be less than or equal to the greatest common divisor of and n; that is,

Similarly, and . So

Since divides both m and n, it's a common divisor of m and n. Therefore, it must be less than or equal to the greatest common divisor of m and n; that is,

The two inequalities I've proved combine to show that .

In words, the result of (a) says that the greatest common divisor of two numbers doesn't change if you replace the first number with the first number minus the second number. This provides a way of "simplifying" a greatest common divisor expression.

(b) Using the result of (a), I have

Now , so . Therefore, .

16. Show that if , then does not leave a remainder of 2 when it is divided by 5.

Consider n mod 5. There are 5 cases:

As the table shows, . Therefore, does not leave a remainder of 2 when it is divided by 5.

17. (a) Find .

(b) Show that 8 does not have a multiplicative inverse mod 10.

(a) By trial and error, you can show that . Therefore, .

(b) Suppose for some x (so that ). Multiplying both sides by 5, I get

This contradiction shows that 8 does not have a multiplicative inverse mod 10.

18. Let m and n be integers, and suppose . Prove that implies .

Since , I have for some integer p. If , then for some integer k. Substituting yields ; this means that , which is what I wanted to prove.

19. Suppose . Is it necessarily true that ?

No. , but , while .

20. Prove that if , then is not divisible by 5.

If , then n is congruent mod 5 to 0, 1, 2, 3, or 4. Take cases:

Since , it follows that for all .

21. The following functions take real numbers as inputs and produce real numbers as outputs. Taking the domain to be the largest set of valid inputs, find the domain and the range for each function.

(a) .

(b) .

(c) .

(a) The domain is .

An even power can't be negative, so . On the other hand, if , then

Therefore, every is an output of f, and the range is .

(b) The domain is . (Note that plugging 1 into gives , which is undefined.)

The range is , since if ,

(c) The domain is .

Note that . This suggests that the range is .

First, I'll show that is not in the range. Suppose it is. Then for some x, I have . So

This contradiction shows that there is no such x, so is not in the range.

Next, I'll show if , then y is in the range. Since , the quantity is defined. (I found it by setting and solving for x.) Moreover,

This proves that y is in the range.

Therefore, the range of f is .

22. Define by . Prove directly using the definition that f is injective.

23. Define by . Prove that f is not injective.

Thus, , but . Hence, f is not injective.

24. Define by . Prove that f is injective.

It would be difficult to do this directly. Instead, use derivatives:

Hence, f increases for all x, and hence f is injective.

25. Define by . Prove that directly using the definition that f is surjective.

Let . Then

Hence, f is surjective.

26. Define by . Prove that f is surjective.

Let . I must show that there is an such that .

Note that f is continuous, and

Hence, there are numbers c and d such that

By the Intermediate Value Theorem, there is a number x such that and .

Therefore, f is surjective.

27. Define by . Prove that f is injective. Is f surjective?

Suppose . Then

Therefore, f is injective.

However, f is not surjective. For example, I'll show that there is no such that . For if , then

The last equation is a contradiction, since for all x.

28. Define by . Prove that f is not injective, but that f is surjective.

First, and , but . Since different inputs can give the same output, f is not injective.

To show that f is surjective, let . I have to find an input such that . There are many that work; here's one:

Hence, f is surjective.

29. Define by . Prove that f is injective, but is not surjective.

First, suppose . Then

Equate the first components to get . Subtracting 1 from both sides, I get . Therefore, f is injective.

On the other hand, I'll show that there is no input x such that . Suppose on the contrary that , so . Equating the first components, I get , so . But equating the second components, I get , so . Since x can't be 2 and -4 simultaneously, this is a contradiction, and there is no such x. Hence, f is not surjective.

30. Define by

Is f surjective? Why or why not?

Suppose . Then

Equating the second components, I get , so . Equating the first components and plugging in , I get

The last equation has no solutions.

Therefore, there is no pair such that , and hence f is not surjective.

31. Define by

Prove that f is bijective by constructing an inverse.

First, I'll work backwards to guess the inverse. If , then . So I'll set and solve for x and y:

gives , so . Then

Thus, I'll define by

Next, I'll check that the inverse actually works:

Therefore, f and are inverses, and f is bijective.

32. Let and be functions. Suppose f and g are injective. Prove that the composite is injective.

Suppose that . I must show . I have

Therefore, is injective.

33. Give a specific example of sets X, Y, and Z and functions and such that g is surjective, but the composite is not.

Let be defined by . Let be defined by .

g is surjective, because if , then

However, is not surjective. In fact,

But since is an even power, it's always nonnegative. Therefore, there is no such that .

34. Prove that the following sets have the same cardinality by constructing a bijection from A to B:

Note that is even for all . (In the third case, if n is odd, then is odd, so is even.)

In words, f sends 0 to 0, positive even numbers to themselves, and positive odd numbers to negative even numbers.

Define by

Note that for all .

I'll show that f and g are inverses.

First, let . I must show . There are 3 cases.

If , then

If and n is even, then

Finally, if and n is odd, then

Thus, in all cases .

Next, let . I must show that . There are 3 cases.

If , then

If and n is even, then

If and n is even, then is positive and odd. Hence,

Thus, in all cases .

Therefore, f and g are inverses. Hence, f is bijective. This proves that .

35. Prove that has the same cardinality as by constructing a bijection from to .

Define by

First, I have to show that f takes into . Suppose that , so . Then

Thus, .

Next, I'll show that f is bijective. I'll do this by constructing the inverse. Set . Swapping x and y gives . Solving for y, I get

Thus, . Note that if , then . Hence,

Thus, , and takes into .

Check that the functions are inverses:

Thus, f and are inverses, f is bijective, that .

36. Prove that has the same cardinality as by constructing a bijection from to .

Define by

Note that if , then

Hence, .

Define by

If , then

Hence, .

I'll check that f and g are inverses.

Hence, f and g are inverses. Therefore, f is bijective. Thus, .

To think is not enough; you must think of something. - Jules Renard

Contact information