Countability (Mathematics)

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.

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{{a_1, a_2, a_3, ... }\right\} \ } be a countable set, and let $w\$ be some arbitrarily small number. Construct the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a_1-w/4,a_1+w/4] \ } .

Obviously, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 \ } is contained in this interval, and this interval has length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w/4+w/4 = w/2 \ } .

But around Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_2 \ } , we can construct the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a_2-w/8,a_2+w/8] \ } , around Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_3, [a_3-w/16,a_3+w/16] \ } , and in general, around Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_k \ } , we can construct Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a_k-w/2^{k+1},a_k+w/2^{k+1}] \ } .

The sum of all these lengths will be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w/2 + w/4 + w/8 + w/16 + ... = w \ } , but remember, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.