A set is countable if and only if it is finite or it has the same cardinality as the set of positive integers. That is,

[answerhappygod]

A Set Is Countable If And Only If It Is Finite Or It Has The Same Cardinality As The Set Of Positive Integers That Is 1 (341.29 KiB) Viewed 20 times

A set is countable if and only if it is finite or it has the same cardinality as the set of positive integers. That is, for an infinite set to be countable, there must be a one-to-one correspondence from the set to the set of positive integers. A set that is not countable is uncountable. Write up the proof that the set of real numbers between 0 and 1 is uncountable. (See Section 7.4 of the text.) The proof is by contradiction and it utilizes a Cantor diagonalization argument. Be sure you understand the proof. Since any set with an uncountable subset is uncountable, we can conclude that the set of all real numbers is uncountable. Application to computer science: A function is computable if there is a computer program in some programming language that finds the values of the function. A function that is not computable is said to be uncomputable. The existence of uncomputable functions can be established: 1) The set of programming languages is countable. It can be shown that the set of computer programs in any particular language is countable. Hence, the set of computer programs is countable. 2) It can be shown that the set of functions from positive integers to {0,1,2,3,4,5,6,7,8,9} is uncountable. This follows from the set of real numbers being uncountable, Putting these two results together, shows that uncomputable functions exist.