I have 3 questions on Induction and Cardinality. I need to see the work and have the answers answered on the word document, scanned or photos of hand written work are too hard to read. I have included the notes that question 14 refers to.Thanks,Patrickcardinality.pdfinduction_week_2_questions.docxCardinality
Sets S and T have the same cardinality (are equinumerous), denoted S ~ T, if there exists a bijective
function from S onto T.
Given a collection of sets ℑ, ~ is an equivalence relation on ℑ.
Then the relation ~ partitions the collection of sets into disjoint equivalence classes. For each set,
associate a cardinal number representing the size of the set.
A set S is finite iff S = empty or there is a bijection f: {1, 2, …, n} → S for some positive integer n.
Essentially, this says that a nonempty set is finite iff we can put the elements of the set in a list of finite
length, labeling one element as element #1 and another as element #2, and so on.
If a set is not finite, then it is infinite.
Notation: Denote {1, 2, …, n} by In.
The cardinal number of In is n, and if S ~ In, we say that S has n elements.
The cardinal number of ∅ is 0.
The cardinal number of an infinite set is called transfinite.
A set S is denumerable iff there exists a bijection f: N → S.
Essentially, this says that a nonempty set is denumerable iff we can put the elements of the set in a list
of infinite length, labeling one element as element #1 and another as element #2, and so on, and never
ending. That is, we can enumerate the elements, using natural number subscripts. S = {s1, s2, s3, s4, …}.
A set S is countable (i.e., countably infinite) iff it is finite or denumerable.
A set S is uncountable iff it is not countable.
infinite sets
countable sets
finite
sets
denumerable
sets
uncountable
sets
The cardinal number of a denumerable set is denoted ℵ0 (“Aleph zero”).
Examples:
N is denumerable. The identity function iN : N → N is a bijection.
The set of odd natural numbers S is denumerable, since f: N → S defined by f(n) = 2n – 1 is a bijection.
The set of integers Z is denumerable — think of Z = {0, 1, -1, 2, -2, 3, -3, …} so we can define a bijection
f: N → Z such that f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 2, etc.
Page 1 of 5
Example: Show that the open interval (-1, 1) and R are equinumerous.
One way to do this is to find a bijection f: (-1, 1) → R.
Consider the following graph:
Visually, notice that the graph represents a function, and since every
horizontal line intersects the graph in exactly one point, the function is
both injective and surjective.
Therefore the function f represented by this graph appears to be a
bijection f: (-1, 1) → R.
Can we guess the formula for this function?
It has vertical asymptotes x = -1 and x = 1, and intercept (0, 0).
This suggests that a rational function may work.
Let = for x ∈ (-1, 1). This function has the desired
asymptotes and intercept. (Checking more points confirms that this is a likely
candidate.)
Let’s check that this is a bijection.
=
Taking the derivative and simplifying, we get
=
< 0 for all x ∈ (-1, 1), so f is strictly decreasing on (-1, 1). Note too that lim → = ∞ and lim → = −∞. So, f must be injective and the range must include all real numbers. Example: Closed intervals [-1, 1] and [c, d] are equinumerous. We want to find a bijection f: [-1, 1] → [c, d]. Can we find a function f so that f(-1) = c and f(1) = d? Yes, a line through the points (-1, c) and (1, d) will work. That line has slope . y = mx + b x + b Substitute the point (1, d) to get + b. Solving for b results in = . = = Let f: (-1, 1) → (c, d) defined by = + . This is a linear function mapping [-1, 1] onto [c, d]. Any linear function with nonzero slope must be injective. So, we have found a bijection between the two intervals. Theorem. If S is a countable set and T ⊆ S, then T is countable. Theorem. Suppose S is a nonempty set. The following statements are equivalent: (a) S is countable. (b) There exists an injection f: S → N (c) There exists a surjection g: N → S Page 2 of 5 Additional results: (a) If S and T are nonempty countable sets, the union S ∪ T is a countable set. See book, pages 81 and 82 (diagram on page 82) (b) The Cartesian product of two countable sets is countable. (c) The set of rational numbers, Q, is countable. (d) The union of a countable family of countable sets is countable. Proof of (d): Suppose ℑ is a countable family of countable sets. Since the family is countable, we can use the natural numbers N as an index. So ℑ = {Sn | n ∈N}, and by hypothesis, each set Sn is countable. Since S1 is countable, we can list the elements {s11, s12, s13, s14, ...}. Since S2 is countable, we can list the elements {s21, s22, s23, s24, ...} : In general, since Sn is countable, we can list the elements {sn1, sn2, sn3, sn4, ...} Now arrange the elements in a rectangular array: s12, s13, s14, ... s11, s21, s22, s23, s24, ... s31, s32, s33, s34, ... s42, s43, s44, ... s41, : We want to show how to choose a first element in the list, then the second, and so on. Follow the arrows: s11, s12, s13, s14, ... s22, s23, s24, ... s21, s31, s32, s33, s34, ... s41, s42, s43, s44, ... : The union is the set {s11, s12, s21, s31, s22, s13, s14, s23, ...} and we have now shown that the set is countable. Proof of (c): We want to show that the set of rational numbers, Q, is countable. Recall that Q = {m/n | m and n ∈ Z and n ≠ 0}. First consider Q+, the set of all positive rational numbers. Let S1 = {positive rational numbers having numerator 1} = {1/1, 1/2, 1/3, 1/4, ...}. Let S2 = {positive rational numbers having numerator 2} = {2/1, 2/2, 2/3, 2/4, ...}. Let S3 = {positive rational numbers having numerator 3} = {3/1, 3/2, 3/3, 3/4, ...}. and in general, Sn = {positive rational numbers having numerator n} = {n/1, n/2, n/3, n/4, ...}. Clearly, each set Sn is countable, and ⋃$∈& #$ = ' . Now we have a countable family of countable sets, so the union Q+ must be countable. Using a similar argument, Q- (the set of negative rational numbers) is countable. Since Q = Q+ U {0} U Q-, the union of three countable sets, Q must be countable. Page 3 of 5 What about R, the set of real numbers? There is a famous proof, called the Cantor diagonalization proof, which leads to the conclusion that the set of real numbers is uncountable. Georg Cantor, a late 19th century mathematician, developed ground-breaking work on the cardinality of sets, but his ideas were so revolutionary that they were controversial, and sadly, he suffered from mental illness. For more, see http://www.mathcs.org/analysis/reals/history/cantor.html and http://www-history.mcs.standrews.ac.uk/Biographies/Cantor.html Theorem. The set R of real numbers is uncountable. Proof: We will show that the open interval (0, 1) is uncountable. Since (0, 1) ⊆ R, we can then conclude that R is uncountable. Claim: The open interval (0, 1) is uncountable. Proof (by contradiction): Suppose the open interval (0, 1) is countable. Then we could make a list x1, x2, x3, ... of the elements, producing a one-to-one correspondence between the natural numbers and the real numbers between 0 and 1. Note that any real number between 0 and 1 can be expressed as decimal value with an infinite decimal expansion involving digits 0 through 9. (In the case of a terminating decimal, all digits beyond a certain point are 0. Some numbers, such as 0.50000000000 and 0.499999999... have more than one representation). So, we can write our list as x1 = 0.a11 a12 a13 a14 … x2 = 0.a21 a22 a23 a24 … x3 = 0.a31 a32 a33 a34 … x4 = 0.a41 a42 a43 a44 … x5 = 0.a51 a52 a53 a54 … : Now we construct a real number y = 0.b1 b2 b3 b4 ... between 0 and 1 as follows: x1 = 0.a11 a12 a13 a14 … x2 = 0.a21 a22 a23 a24 … x3 = 0.a31 a32 a33 a34 … x4 = 0.a41 a42 a43 a44 … : To determine b1, look at a11. If a11 = 2, we set b1 = 3; otherwise we set b1 = 2. To determine b2, look at a22. If a22 = 2, we set b2 = 3; otherwise we set b2 = 2. Continuing in same way, we define bn as follows: $ = ( 3, + ,$$ = 2/ 2, + ,$$ ≠ 2 Now let's compare y = 0.b1 b2 b3 b4 … with the numbers in the list. Is y = x1? No, because the first digits b1 and a11 are different. Is y = x2? No, because second digits b2 and a22 are different. Continuing in the same way, comparing y and xn, we see that they are not equal because the nth digits bn and ann do not match. Page 4 of 5 Therefore, we have constructed a number y which is not in our list of all the real numbers between 0 and 1! But that list was supposed to include all of the real numbers in the interval. This contradicts our assumption that the interval (0, 1) is countable. We conclude that the interval (0, 1) is uncountable. Remark: Was there any particular reason why the digits of y were 2's or 3's? No, we could have worked with 4 and 7, for instance. Page 5 of 5 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, g−1, h−1, with an appropriate composition. Purchase answer to see full attachment
Why Choose Us
- 100% non-plagiarized Papers
- 24/7 /365 Service Available
- Affordable Prices
- Any Paper, Urgency, and Subject
- Will complete your papers in 6 hours
- On-time Delivery
- Money-back and Privacy guarantees
- Unlimited Amendments upon request
- Satisfaction guarantee
How it Works
- Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
- Fill in your paper’s requirements in the "PAPER DETAILS" section.
- Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
- Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
- From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.