Respective Point Values for Problems 1-5 are 20 (5-5-5-5),

26 (11-18), 32 (16-6-10), 42 (6-6-22-8), 40 (6-6-6-16-6).

(Total of 160 points, plus a possible 10 point bonus.)
 
 

1. What is

(a) a proof by contraposition?

(b) an equivalence relation? (Include the definition of

relation.)

(c) a function?

(d) the inverse of a function g?
 
 

2. (a) Give an example of an equivalence relation on the set of

all people in the U.S. Prove your example really is an

equivalence relation.

(b) Which of the following relations are functions? Justify

your answers.

(i) {(x,y) Î P ´ P : y is a child of x} . (P is the set of all

people.)

(ii) {(x,y) Î P ´ P : y is the mother of x} .

(iii) {(p/q, y) Î Q ´ R : y = q} . (Q is the set of rational numbers.)
 
 

3. (a) Proof to Critique

The following ‘proof’ consists of five statements which are

claimed to be equivalent. However, at least one of these

claims is false. Indicate, line by line, those ‘equivalences’

that are correct, and those that are incorrect. Always

give reasons for your claims.

Theorem -- Suppose A, B, and C are sets. Then

C Í A È B iff C Í A or C Í B .

Proof

C Í A È B

Û If x Î C , then x Î A È B

Û If x Î C, then x Î A or x Î B

Û If x Î C, then x Î A or If x Î C, then x Î B

Û C Í A or C Í B .

(b) Not only is the proof in (a) incorrect, but the theorem

itself is false. Give a counterexample that verifies this.
 
 

(c) Prove that in the universe  of real numbers,

(" x) ($ y) (e^x + sin x < y) .
 
 

4. (a) What does it mean to say that the sequence a1, a2, a3, ...

has an upper bound?

(b) What does it mean to say that a1, a2, a3, ... does not have

an upper bound? (That is, write a denial of your answer

to (a).)

(c) We considered in class sequences a1, a2, a3, ... satisfying the recursion:

for all n ? 2, an = 1/8 + (1/2)an-1 .

Suppose a1 = 4. Use induction to prove that

for all n ? 2, 0 < an < an-1 .

(d) Explain why the information in (c) implies that this

sequence is bounded. (You don’t need to have worked (c)

in order to do this part.)
 
 
 
 
 
 
 
 
 
 

5. Define the function f: R ® R by

f(x) = -x² when x < 0

and f(x) = x² when x ? 0 .

(a) What is the value of f(2)? of f(-6)?

(b) Sketch the graph of f.

(c) Write a general formula for f(x²).

(d) Find the inverse of the function f; be as specific as

possible.

(e) Prove that f^-1 is itself a function.
 
 
 
 

BONUS -- (10 points) Prove that if a sequence of real numbers has a limit, then the sequence is bounded.