Induction (#1-3, 24 pts)

#1. Prove by induction that8 + 15 + 22 + 29 + ... +(7n + 1) = n(7n + 9)/2for all n N.

#2.Prove the summation formula for the following particular finite geometric series. (Do not prove the general formula for a geometric progression and then substitute the value for the ratio. Instead, prove this particular formula shown below.)

Prove by induction that for every n N.

.Prove the summation formula for the following particular finite geometric series. (Do not prove the general formula for a geometric progression and then substitute the value for the ratio. Instead, prove this particular formula shown below.)

Prove by induction that for every n N.

#3. Prove by induction the particular inequality for every n N .

Relations and Functions (#4-11,45 pts)

#4. Find an example of a relation on a set S that is symmetric , but not reflexive and not transitive. (Note that you can just specify your set S and list an appropriate set of ordered pairs.)

#5. Let S be a set. LetA and B be subsets of S. Let R be the relation given by A R Biff A B.

That is, A is related to B iff set A contains B.

State which of the three properties (reflexive, symmetric, and transitive) apply. If a property does not hold, provide a counterexample.

#6. State the range of each function f: R R. (no work required to be shown)

#6(a)f(x) = 5 sin (4x)

#6(b)f(x) = (x 3)² + 8

#7. Let X = {1, 2, 3, 4} andY = {7, 8, 9}. Define a functionf: X Y as follows:

f(1) = 8,f(2) = 7,f(3) = 8,f(4) = 9.

For each statement, is it True or False? (no explanation required)

________(a) x Xsuch thatf(x) = 2x + 3.

________ (b) xX, yYsuch thatf (x) =y.

________(c) yYsuch that xX,f(x) =y.

________(d) yY, xXsuch thatf(x) =y.

________(e)fis injective.

________ (f)fis surjective.

#8.Let f: A B.Recall that f is injective iff" r, s A, if f(r) = f(s), then r = s.

Write the contrapositive of the quantified if-then statement (the statement in bold).

#9. Claim: The function f: R R defined by is injective. Consider the following "proofs" of the claim.INSTRUCTIONS: Critique each proof (A, B, C, D, E). For each proof, is it a valid argument establishing the claim or not? What are the flaws, if any?

Proof A:

Let r, s R and supposer = s.

Cube both sides, so .

Subtract from 8, so .

Thus,f(r) = f(s).

Therefore f is injective.

Proof B:

Let r, s R and suppose r s.

Cube both sides, so .

Subtract from 8, so

Thus,f(r) f(s).

Therefore f is injective.

Proof C:

Let r = 1 and s = 2.

and .

Since f(r) f(s) and r s , f is injective.

Proof D:

Let r, s R and suppose f(r) = f(s).

Then

Add 8, so

Multiply by 1, so

Take the cube root, so r = s.

Thus f is injective.

Proof E:

Let r, s R and suppose f(r) f(s).

Then

Add 8, so

Multiply by 1,so

Take the cube root, so r s.

Thus f is injective.

#10.Define f: R R defined by f(x) = 4x². Let A = [0, 4] and B = [-3, 0].

#10(a) Find the sets f(A), f(B), f(A) f(B), and f(A B).Is f(A B) = f(A) f(B)?

#10(b) Find the sets which are inverse images:

f ^-1(A), f ^-1 (B), f ^-1 (A) f ^-1 (B), andf ^-1 (A B). Is f ^-1 (A B) = f ^-1 (A) f ^-1 (B)?

#11. Classify each function as injective, surjective, bijective, or none of these, as appropriate. If not injective, briefly explain. If not surjective, briefly explain. (Otherwise, no explanation required.)

#11 (a)f: Z Z defined by f(n) = n + 3

#11 (b)f: N Z defined by f(n) = n² - 2n

#11 (c)f: Z Z defined by f(n) = n² - 2n

Cardinality (#12-14, 13 pts)

#12. For each statement, is it True or False? (no explanation required)

________(a) is a countable set.

________(b) is a countable set.

________(c){ 3/(k² + 1):k in N} is a countable set.

________(d)If a set of real numbers contains an irrational number, then the set is uncountable

#13. State a specific function f that is a bijection f: (0, 1) (1, ). (Note that you can then conclude that intervals(0, 1) and (1,) have the same cardinality. You are not asked to carry out a formal proof that your f is bijective.)

#14. HINT: Look at page 2 of my posted notes on Cardinality.

#14(a) Show that the intervals (0, 1) and (-2, 6) have the same cardinality by finding a

bijection f:(0, 1) (-2, 6).

#14(b) Suppose a < b.

Prove that the intervals (0, 1) and (a, b) have the same cardinality by finding a bijection f:(0, 1) (a, b).

#14(c) Suppose r < s and t < u. Our goal is to show that open intervals (r, s) and (t, u) have the same cardinality.By part (b), there exist bijections g:(0, 1) (r, s) and h:(0, 1) (t, u).

State a specific function f that is a bijection f: (r, s) (t, u), where f is an appropriate composition of functions involving functions g, h, and/or their inverses. [Recall composition of functions ---see Relations and Functions notes, page 9].You do not need a complicated formula. Just make use some of the functions g, h, g^-1, h^-1, with an appropriate composition and state f as the composition of the appropriate functions.

ORDERED FIELDS (#15-18, 18 pts)

#15. Consult the list of properties A1 - A5, M1 - M5, DL, O1 - O4 from my Ordered Field notes.

Rather than considering those properties applied on the set R of real numbers, restrict the set as indicated below. In other words, check which properties still apply, when R is replaced by the set specified.

#15 (a) Which properties are not satisfied on the set of integers, Z? (Just list the identifying labels.)

#15(b) Let S = [0, ). Which properties are not satisfied on the set S? (Just list the identifying labels.)

#15(c) Let S = [1, 1]. Which properties are not satisfied on the set S? (Just list the identifying labels.)

#16.Prove that 0 < 1/2 < 1.Fill in the blanks of the proof. Refer to the field axioms and order axioms and the Theorem in my Ordered Field notes, pages 1-2.

Proof:

Note that0 < 1 (by Theorem part ___)

Adding 1 to both sides, 0 + 1 < 1 + 1by order axiom ___.

0 + 1 = 1 by field axiom _____,and 1 + 1 = successor of 1, which is designated by 2 (Peano axiom in Induction notes).

So, we have1 < 2.

Since 0 < 1 and 1 < 2, we have 0 < 1 < 2.

Then 0 < 1/2 < 1/1 by Theorem, part ___

Note that1/1 = 1 (because 1 1 = 1).

Thus, we have 0 < 1/2 < 1, as desired.

#17.Let x be a real number.

Claim:If0 x < efor all real numbers e> 0, then x = 0.

Fill in the blanks of the proof of the claim. Refer to the field axioms and order axioms and the Theorem in my Ordered Field notes, pages 1-2.

Proof of Claim, by contradiction:

Let x be a real number.

Suppose not.

Supposefor all real numbers e> 0, we have 0 x < e, but x 0.

Since 0 x and x 0, we must have x __ 0.(fill in blank with <, = or, >, whichever is appropriate)

Sete= (1/2) x.

Since 1/2 > 0 (by problem #16) ,

we havee = (1/2) x > (1/2) 0 by order axiom ____.

= 0since(1/2) 0 = 0 by Theorem, part ___.

Since 1/2 < 1 (by problem #16) and x __ 0, we have e =(1/2) x < 1 xby order axiom ____,

and soe =(1/2) x < __ since 1 x = x by field axiom ____.

In summary, we know x __ 0 and we have found a particular e > 0 for which x __e. (fill in the blanks to show the correct order relationships between the numbers)

We have reached a contradiction of our hypothesis that x < e, so we conclude that x must be equal to 0.

#18.Write a careful proof of the statement: " a, b, c, d R,if a > b and c < d, then ad + bc > ac + bd.

HINTS:What can you deduce about the sign of (a - b)(c - d), and what do you get when you multiply this out?

You can assume that the usual algebraic rules of inequalities apply, without citing an axiom or theorem.