Question

Question: Let B be the set of all infinite sequences over {0 , 1}. Show that B is uncountable using a proof by diagonalization.

Short answer

Answer:

For the set set of $\beta$all infinite sequences over{0 , 1} , in which $\beta$is uncountable is proved by diagonalization.

Step-by-step solution

Diagonalization

Diagonalization is a technique to demonstrate that there are some languages that cannot be decided by a Turing machine. This is used as a way of showing that the (infinite) set of real numbers is larger than the (infinite) set of integers.

proof that sequence is uncountable.

Each element in is an infinite sequence $\left(b_{1,}{b}_2...........\right)$where each$b_i\in \left\{0,1\right\}$ suppose is countable. Then define a correspondence F between $N=\left\{1,2,3......\right\}$and $\beta$. Specifically for $f\left(n\right)=\left(b_{1,}{b}_2...........\right)$ .

Now define infinite sequence that is$c=\left(c_1,c_2,c_3,..........\right)\in$$\beta$ ,set $\beta$set of all infinite sequences over$\left\{0,1\right\}$ , in which is uncountablewhere the opposite of the ith bit is and here the function is defined as$f\left(n\right)=\left(b_{1,}{b}_2...........\right)$ an infinite sequence is given as below,