Let F be the collection of all functions f: N-→ {0,1}. Is F countable ?

Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
icon
Related questions
Question
Problem 3(ii)please!
Math 310 - HW 3 (Due Wednesday 09/22)
1. Let X, Y be sets with a function f: X→Y. Prove that the following are equivalent:
(a) f is 1– 1.
(b) f(A - B) = f(A) f(B) for all subsets A and B of X.
(c) f-(f(E)) = E for all subsets E of X.
(d) f(An B) = f(A) n f(B) for all subsets A and B of X.
2. (i) Show that given finitely many countable sets A1, A2, , An, the set A1 x A2 x .. x An is also
countable.
(ii) Is it true that given countably many countable sets A1, A2,.., the set A1 x A2 x ... is also countable
? Justify your answer.
3. (i) Let F be the collection of all functions f : {0,1} → N. Is F countable ?
(ii) Let F be the collection of all functions f : N {0, 1}. Is F countable ?
(iii) Let F be the collection of all functions f: N → N. Is F countable ? What about f :R →R ?
4. (i) Let (0, 1) be the open interval from 0 to 1. Show that |(0, 1)| = |R+| by finding an explicit bijection.
(ii) [Extra-Credit] Show that |(0, 1)| = |R|, by finding an explicit bijection.
(iii) Show that |P(N)| = R+| (Hint: Use (i) and binary representation of numbers in (0, 1) )
5. A real number x is said to be algebraic (over Q) if it satisfies some polynomial equation ana"+an-1r"-1+
...+ a1x + ao = 0, where each a; E Q, an + 0. If x is not algebraic, it is called transcendental.
(i) Show that the set of all polynomials over Q (as mentioned above) is countable.
(ii) Prove that there are countably many algebraic numbers. (Hint: Use (i) and here you may use the
Fundamental theorem of Algebra, that any polynomial has finitely many roots.)
(iii) Prove that there are uncountably many transcendental numbers. (Remark: e and T are two such num-
bers.)
Not for Credit
6. Prove that the set of points on the unit circle in R2, that is {(x, y) : x² + y? = 1} is uncountable.
7. Is the subset of rational numbers {m : m, n e Z,1 < n < 100} is dense in R ?
8. Prove that is N x N is countably infinite by showing that the function f : N x N → N defined by
f(m, n) = 2"-1(2m – 1) is a bijection.
Transcribed Image Text:Math 310 - HW 3 (Due Wednesday 09/22) 1. Let X, Y be sets with a function f: X→Y. Prove that the following are equivalent: (a) f is 1– 1. (b) f(A - B) = f(A) f(B) for all subsets A and B of X. (c) f-(f(E)) = E for all subsets E of X. (d) f(An B) = f(A) n f(B) for all subsets A and B of X. 2. (i) Show that given finitely many countable sets A1, A2, , An, the set A1 x A2 x .. x An is also countable. (ii) Is it true that given countably many countable sets A1, A2,.., the set A1 x A2 x ... is also countable ? Justify your answer. 3. (i) Let F be the collection of all functions f : {0,1} → N. Is F countable ? (ii) Let F be the collection of all functions f : N {0, 1}. Is F countable ? (iii) Let F be the collection of all functions f: N → N. Is F countable ? What about f :R →R ? 4. (i) Let (0, 1) be the open interval from 0 to 1. Show that |(0, 1)| = |R+| by finding an explicit bijection. (ii) [Extra-Credit] Show that |(0, 1)| = |R|, by finding an explicit bijection. (iii) Show that |P(N)| = R+| (Hint: Use (i) and binary representation of numbers in (0, 1) ) 5. A real number x is said to be algebraic (over Q) if it satisfies some polynomial equation ana"+an-1r"-1+ ...+ a1x + ao = 0, where each a; E Q, an + 0. If x is not algebraic, it is called transcendental. (i) Show that the set of all polynomials over Q (as mentioned above) is countable. (ii) Prove that there are countably many algebraic numbers. (Hint: Use (i) and here you may use the Fundamental theorem of Algebra, that any polynomial has finitely many roots.) (iii) Prove that there are uncountably many transcendental numbers. (Remark: e and T are two such num- bers.) Not for Credit 6. Prove that the set of points on the unit circle in R2, that is {(x, y) : x² + y? = 1} is uncountable. 7. Is the subset of rational numbers {m : m, n e Z,1 < n < 100} is dense in R ? 8. Prove that is N x N is countably infinite by showing that the function f : N x N → N defined by f(m, n) = 2"-1(2m – 1) is a bijection.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

Blurred answer
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,