Cardinality

Induction

#1. Prove by induction that 9 + 12 + 15 + … + 3(n + 2) = 3n(n + 5)/2 for all n N.

#9. Claim: The function f: R R defined by f(x) = 7 4x 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 a = 0 and a' = 1.

f(a) = 7 and f(a') = 3.

Since f(a) f(a' ) and a a' , f is injective.

Proof B:

Let a, a' R and suppose a = a'.

Multiply both sides by 4, so 4a = 4a'

Add 7 to both sides, so 7 4a = 7 4a'

Thus, f(a) = f(a').

Therefore f is injective.

Proof C:

Let a, a' R and suppose a a'.

Then 4a 4a'

and also 7 4a 7 4a'

So, f(a) f(a').

Therefore f is injective.

Proof D:

Let a, a' R and suppose f(a) = f(a').

Then 7 4a = 7 4a'.

Subtract 7 from both sides, so 4a = 4a' .

Divide both sides by 4, so a = a'.

Thus f is injective.

Proof E:

Let a, a' R and suppose f(a) f(a').

Then 7 4a 7 4a'

and 4a 4a'

and so a a'

Thus f is injective.

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

#14(a) Show that the intervals (0, 1) and (3, 8) have the same cardinality by finding a

bijection f:(0, 1) (3, 8).

#14(b) Suppose r < s.

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

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

State a specific function f that is a bijection f: (a, b) (c, d), 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, g1, h1, with an appropriate composition.