Countability (Mathematics)

From Conservapedia

Jump to: navigation, search
While some details remain, such as eliminating reducible fractions, this picture shows the idea behind a numbering of all fractions.

In mathematics, a set is called countable if it can be numbered in such a way that every element will eventually receive a unique number.

Georg Cantor developed the concept of countability -- and lack of countability -- in the late 19th century.

Examples of Countable Sets

Obviously, the numbers 1, 2, 3, etc., are countable, but so are all the integers: 0 we call first, 1, second, -1, third, 2, fourth, -2, fifth, 3, sixth, and so on, going outwards. We're sure to hit every integer this way.

Somewhat surprisingly, the rational numbers, also called fractions, are countable as well. See the picture, right.

Examples of Uncountable Sets

The real numbers are not countable, nor is any set with positive Lebesgue measure. This is because any countable set of numbers can be completely contained within a set of arbitrarily small measure. A short proof follows:

Let \left\{{a_1, a_2, a_3, ... }\right\} \ be a countable set, and let w \ be some arbitrarily small number. Construct the interval [a_1-w/4,a_1+w/4] \ .

Obviously, a_1 \ is contained in this interval, and this interval has length w/4+w/4 = w/2 \ .

But around a_2 \ , we can construct the interval [a_2-w/8,a_2+w/8] \ , around a_3, [a_3-w/16,a_3+w/16] \ , and in general, around a_k \ , we can construct [a_k-w/2^{k+1},a_k+w/2^{k+1}] \ .

The sum of all these lengths will be w/2 + w/4 + w/8 + w/16 + ... = w \ , but remember, w \ was chosen to be arbitrarily small, and so a countable set can be contained in a set of arbitrarily small measure.

Since the real numbers, or any set of positive measure, cannot, they must not be countable.

Personal tools