Let A be the collection of all sequences of 0\'s and 1\'s. Oneexample of an elem

Question

Let A be the collection of all sequences of 0's and 1's. Oneexample of an element of the set A is the sequence: 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0... Let B be the subset of A that consists of all squences of 0's and1's for which the number of 1's is finite. One example of anelement of the set B is the sequence: 1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,....
c)Prove that the collection of all subsets of positive integers isuncountable by establishing a one-to-one correspondence betweenthis set and the set A. Let A be the collection of all sequences of 0's and 1's. Oneexample of an element of the set A is the sequence: 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0... Let B be the subset of A that consists of all squences of 0's and1's for which the number of 1's is finite. One example of anelement of the set B is the sequence: 1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,....
c)Prove that the collection of all subsets of positive integers isuncountable by establishing a one-to-one correspondence betweenthis set and the set A.

Explanation / Answer

  Let S denote this set of all sequences of 0's and1's.   Let T denote ths all subsets of positiveintegers.   Now define a map f: T ----> S asfollows    For any set Ain T Let f(A) denote the sequence in S which isconstructed as follows:    The nth entry of f(A) is 1 if n belong to A and 0 if ndoesnot belong to A.    Clearly it is awelldefined map.    f is one to one:    Suppose f(A) =f(B) for some sets A and B in T.    Then ifn belong to A then the nth enty of f(A) =1 which implies the nthentry of f(B) is 1 and by definition we have n belong toB.    So A is contained in B.------(1)    Suppose m does not belong to A then the mth entryof f(A) is zero which implies the mth entry of f(B) is zero andtherfore m doesnot belong to B.    So B is contained inA.-------------(2) From (1) and (2) we have A =B.   This shows f is one to one.   For any sequence s in S let A = { n | the nthentry of s is 1}    Slearly A is subset of positive integers and f(A)= s.    So f is onto.   That is f is one to one coresspondence between San T. Since S is uncountable T is also have uncountable number ofelements.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.