Countability

Countable set:

A set 'S' is said to be countable ,if all the element of these set can be put in one to one correspondence with the set of natural number.

 

Uncountable  set:

A set 'S' is said to be Uncountable ,if it is infinite and not countable.

 

for example , every element in even no we can give a element from the natural no as correspondence so we can say even no is countable.

 

NOTE:

Set of all real no is uncountable.

 

Alternative definition of countability:

A set is said to be countable if there exist an enumeration method using which all the element of set can be generated ,and for any particular element ,it takes only finite number of stapes to generate it.

 

            The finite number of step takes to generate an element can be used as its index and hence a mapping into natural number.

 

here are some set of element which are countable :

1)set of all quotients are countable.

2)set of all string over any finite alphabet are countable i.e ∑={a.b}

                     ∑*={ε,a,b,aa,ab,ba,ba,......................................}

NOTE:

Every subset of countable set is either finite or countable.

 

3)set of all turing machine are countable.

as we know,

                a)∑*={ε,a,b,aa,ab,ba,ba,......................................} is countable

                b)every turing machine can be encoded as a string of 0's and 1's.

                 c)set of all turing machine,S⊆∑*

                 d)Every subset of countable set is either finite or countable.

by using these rule we can say that set of all turing machine are countable.

 

here we should know that set of all language are uncountable.

 

 

SOME PROBLEM ON COUNTABILITY

If S1 and S2 are countable sets then S1 union S2 is countable and S1*S2 is countable.

 

1)The cartesian product of finite number of countable sets is countable.

2)The set of all language that are not recursively enumerable is uncountable.

 

0Comment