0 votes 0 votes second one is uncountable? abhishekmehta4u asked Sep 29, 2018 abhishekmehta4u 959 views answer comment Share Follow See all 22 Comments See all 22 22 Comments reply Mk Utkarsh commented Sep 29, 2018 reply Follow Share S is not uncountable. Set of S has one to one correspondence with $\mathbb{N}$ 0 votes 0 votes srestha commented Sep 29, 2018 reply Follow Share how S is countable? Can u derive plz 0 votes 0 votes Deepanshu commented Sep 29, 2018 reply Follow Share if Set of S has one to one correspondence with N natural no. then it is countable simple words we can derive some function by which we can show correspondence S= 2^i i,=0,1............................ 0 votes 0 votes Mk Utkarsh commented Sep 29, 2018 reply Follow Share $\left ( 2^i, i \right )$ $(1,0), (2,1), (4,2), (8,3), (16,4),(25,5),...$ one to one from S to $\mathbb{N}$ 0 votes 0 votes srestha commented Sep 29, 2018 reply Follow Share where u got such mapping is done here? Moreover, for countable set ,it should be bijective function too 0 votes 0 votes Mk Utkarsh commented Sep 29, 2018 reply Follow Share srestha please check definition also it is a valid proof if you show one to one correspondence with $\mathbb{N}$, but if you still feel its uncountable then you can prove it with Cantor's diagonalization. 0 votes 0 votes srestha commented Sep 29, 2018 reply Follow Share A set of infinite number cannot be countable until and unless it is bijective but how here u prove set of natural numbers is bijective? 0 votes 0 votes Mk Utkarsh commented Sep 29, 2018 reply Follow Share A set is countably infinite if its elements can be put in one-to-one correspondence with the set of natural numbers. 0 votes 0 votes Nishikant commented Sep 30, 2018 reply Follow Share According to definations S is countable beacause 1)You can give one-to-one correspondance of the values present in S for any i,with the natural numbers: ex for i=0,1 ,2 ,3,4,5,6,7...... S={1,2,4,8,16,32,64,128....} so 0 can be mapped to 1, 1 mapped to 2, 2 mapped to 4....and so on.. 2)For a given Set to be countable you should be able to say that with this finite # of steps I can derive the given element in S ex: lets take 128 in S, then you can definitely say that you can reach to it or derive it within 7 steps. That is the enumeration method for the given set is also present. Therefore the SET is countable. 2 votes 2 votes srestha commented Sep 30, 2018 reply Follow Share @ Mk Utkarsh Countable set for infinite number must satisfy bijection property as per Cantor theorem But is it satisfying bijective property Moreover what about membership property here? chk this http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf 0 votes 0 votes Mk Utkarsh commented Sep 30, 2018 reply Follow Share that pdf is of 250+ pages obviously it is bijective, all natural numbers are mapped with its square from set S 1 votes 1 votes Mk Utkarsh commented Sep 30, 2018 reply Follow Share $1 \rightarrow 0$ $2 \rightarrow 1$ $4 \rightarrow 2$ $8 \rightarrow 3$ $16 \rightarrow 4$ 0 votes 0 votes Mk Utkarsh commented Sep 30, 2018 reply Follow Share $0$ is not a natural number so you can increment the value which is being mapped like $(1 \rightarrow 1)$, $(2 \rightarrow 2)$ and so on 0 votes 0 votes srestha commented Sep 30, 2018 reply Follow Share But as per membership , we need to map every element ----------------------------------- no just chk countable part pg no-164-and next 2-3 pages 0 votes 0 votes Mk Utkarsh commented Sep 30, 2018 reply Follow Share srestha tell me which element is not mapped 0 votes 0 votes srestha commented Sep 30, 2018 reply Follow Share 3,5,6?? 0 votes 0 votes Mk Utkarsh commented Sep 30, 2018 reply Follow Share First of all set S does not contain 3,5 second 3,4,5 are mapped by 4,8,16 $1 \rightarrow 1$ $2 \rightarrow 2$ $4 \rightarrow 3$ $8 \rightarrow 4$ $16 \rightarrow 5$ 0 votes 0 votes Mk Utkarsh commented Sep 30, 2018 reply Follow Share there is bijection from $S$ to $\mathbb{N}$ or $\mathbb{N}$ to $S$ 0 votes 0 votes srestha commented Oct 1, 2018 i edited by srestha Oct 1, 2018 reply Follow Share @Mk Utkarsh Power set is uncountable See here https://gateoverflow.in/2050/gate2014-3-16 0 votes 0 votes Mk Utkarsh commented Oct 1, 2018 reply Follow Share different question. i can write a proof but still you'll not believe so what's the point 0 votes 0 votes Mk Utkarsh commented Oct 1, 2018 reply Follow Share variety of explanations for this question, https://www.quora.com/How-would-I-prove-the-set-of-numbers-that-are-powers-of-2-are-a-countably-infinite-set 0 votes 0 votes srestha commented Oct 3, 2018 reply Follow Share @Mk Utkharsh yes it will be countable as it is set of natural number ans given plz chk 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes All regular languages are countable sets of words. Finite languages are trivially countable. Infinite languages are countable because the corresponding DFA can be walked over, enumerating the entire language in an ordered manner, allowing all strings to be mapped to the natural numbers. So, Though powerset is not countable for all sets,but power set of Natural number and integer are countable Though if there are possibility of rational number , it will be uncountable infinite set So, here 1st one is finite set and 2nd one power set of Natural number, which are integer. So, both (i) and (ii) need to be countable Ref:https://stackoverflow.com/questions/52567805/can-countable-string-is-countable-always https://cs.stackexchange.com/questions/97914/is-countable-set-always-countable?noredirect=1#comment208658_97914 srestha answered Oct 3, 2018 srestha comment Share Follow See all 0 reply Please log in or register to add a comment.