Past exam question: 2082 Kartik (Back), Q1(a)(i)
Open in the Padhaiko appDefine countably infinite and uncountable set with example.
Solution
Countably Infinite Set Definition and Example: A set is countably infinite (or denumerable) if it has the same cardinality as the set of positive integers (). That is, there exists a bijective function (one-to-one and onto) .
Equivalently, the elements of a countably infinite set can be arranged in an infinite sequence without repetition or omission: .
Example: The set of all integers is countably infinite under the bijection:
Uncountable Set Definition and Example: A set is uncountable if it is infinite but cannot be put into a one-to-one correspondence with the set of natural numbers (). Any list of elements of an uncountable set necessarily omits elements of the set.
Example: The open interval of real numbers (and the set of all real numbers itself) is uncountable. Cantor's Diagonalization Argument proves that any enumerated list of real numbers in fails to include a newly constructed real number whose -th decimal digit differs from the -th digit of the -th number in the list.
A countably infinite set has a bijection with (cardinality , e.g., or ). An uncountable set is infinite but cannot be put into one-to-one correspondence with (e.g., or ), as established by Cantor's diagonalization argument.