First we present a representation of any real number r = [0, 1) in binary, that...

Transcribed Image Text:

First we present a representation of any real number r = [0, 1) in binary, that is infinite sequences of digits 0, 1. Here are steps of a recursive construction: Base: given ar [0,1) recursively the digits of the expansion 0.a1a2a3... as follows (for a given 0 r < 1 : compare r with , if 0 r < let a = 0 otherwise let it be 1. Prove 0 r a < Induction step: having selected a1, A2, A3... an1, with a {0, 1}, such that for each k < n, k ai 1 2k' i=1 Explain how to select an = {0,1} such that 0r- n i=1 V 1 2n Note that at stage n of this construction the number 2n ai 1 is an approximation of r with the maximum 22 error of 21. Present an argument that by continuing this construction, the list a1, a2, a3,... determines the exact location of r, and hence the exact value of r? = Use part (b), and r 0.a1a2a3... where a = {0, 1} to define an bijection between the set of characteristic functions of N and the interval [0, 1). Definition 10.3.34. Let S be a set and So be a subset of S. The characteristic function of So as a subset of S is the function f, with domain S, defined by (s) = 1 if s So and f(s) = 0 ifs & So. Theorem 10.3.31. The cardinality of the set of all sets of natural numbers is the same as the cardinality of the set of real numbers. That is, |P(N)| = c, or or 20 = = C. First we present a representation of any real number r = [0, 1) in binary, that is infinite sequences of digits 0, 1. Here are steps of a recursive construction: Base: given ar [0,1) recursively the digits of the expansion 0.a1a2a3... as follows (for a given 0 r < 1 : compare r with , if 0 r < let a = 0 otherwise let it be 1. Prove 0 r a < Induction step: having selected a1, A2, A3... an1, with a {0, 1}, such that for each k < n, k ai 1 2k' i=1 Explain how to select an = {0,1} such that 0r- n i=1 V 1 2n Note that at stage n of this construction the number 2n ai 1 is an approximation of r with the maximum 22 error of 21. Present an argument that by continuing this construction, the list a1, a2, a3,... determines the exact location of r, and hence the exact value of r? = Use part (b), and r 0.a1a2a3... where a = {0, 1} to define an bijection between the set of characteristic functions of N and the interval [0, 1). Definition 10.3.34. Let S be a set and So be a subset of S. The characteristic function of So as a subset of S is the function f, with domain S, defined by (s) = 1 if s So and f(s) = 0 ifs & So. Theorem 10.3.31. The cardinality of the set of all sets of natural numbers is the same as the cardinality of the set of real numbers. That is, |P(N)| = c, or or 20 = = C.