Why some sets are countable and some are not countable? Say regular set are countable but how (0+1)* will be countable? It is an infinite string, then how it could be a countable set? How the set of all non-decreasing functions from N to N are countable? How the set of all finite partitions of N are uncountable?

  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it is a question about pure mathematics that has no computational content. $\endgroup$ – David Richerby Sep 29 '18 at 13:05
  • $\begingroup$ This lives on Mathematics. $\endgroup$ – David Richerby Sep 29 '18 at 13:05
  • $\begingroup$ Regular sets need not be countable. The set of all non-decreasing functions from $\mathbb{N}$ to itself is also not countable. $\endgroup$ – Yuval Filmus Oct 3 '18 at 2:52
  • $\begingroup$ @YuvalFilmus Recursive Enumerable set is countable. Right? and all other language like regular, CFL, CSL, Rcursive language can be uncountable. $\endgroup$ – Srestha1 Jul 10 at 4:53
  • $\begingroup$ The language of all words is countable. $\endgroup$ – Yuval Filmus Jul 10 at 14:59

As said the question completely belongs to mathematical sector , specifically to discrete mathematics but in my opinion information has no bounds , so does the question

coming to your question ,its indeed an application of discrete mathematics in theory of automata ,so here is your answer. loosely speaking that countability of has little to no relation with being a set is finite or infinite. first thing , if a set is countable then the only condition associated of being it countable is that the cardinality the set ( total number of elements in set) should be lower or equal to that of natural number of positive integers. To simplify it more we can assign a unique natural number to all the elements of the set (please bear that although you may argue that the the list will go to infinte but as said in that infinite list we will have one-to-one correspondence on natural number to that of the elements of set. loosely speaking the condition of being countable is more of a theoritical aspect )

Now if the set is finite then off course its cardinality (number of elements in set) will be less than that of natural numbers, because we can assign a unique natural number which are equal to number of element of the given . The definition of countable set for infinite set may get tricky,but it could be understood . i will take the example of language given by the regex ( 0+1) *. firstly the set of strings in language L =( 0+1) * are infinite which makes the set an infinite set. now apply the definition of being countable set we get that the language is indeed countable reason being we could have a unique list in which each element of the language is assign a unique natural number , however the list is infinitely long but this does not mean we have not assigned a unique natural number to elements of set. so yeah the language is counatble.

Now you may say that this could be done to all infinite set ,making all infinite set counatble, but actually this is not true. for your sake take one more example , this being the countability of set of real numbers. well you cannot assign a number to each real number reason being say you are numbering all the real number between 0 and 1, you will always find a real number which you have not numbered , say you have numbered like 1= 0.01,2 = 0.011, and so on but you missed 0.001 , now suppose you assigned a number to it also say, 3=0.001, well you lost many more numbers which being say ,0.0001,0.000001....and so on, so you will not able to list all the numbers hence the set is uncountable.

for just sake of clarity you can try a question like power set of language L and if you reach the conclusion that power set of language L= (0+1)* is uncountable then you have got what is countable and uncountable set.

  • $\begingroup$ @yuvalfilmus i want you to reconsider your statement that "regular set are not countable". reason being every regular set is a subset of complete language defined over alphabets like any regular set over (0,1) will be subset of (0+1)* which is itself countable and we know that subset of any countable set is countable thus making every regular set countable $\endgroup$ – Noob Oct 5 '18 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.