Countable set

From Knowino
Jump to: navigation, search

In mathematics, a set is said to be countable if its elements can be "numbered" using the natural numbers. More precisely, this means that there exists a one-to-one mapping from this set to (not necessarily onto) the set of natural numbers.

A countable set is either finite or countably infinite. A set that is not countable is called uncountable.

Terminology is not uniform, however: Some authors use "countable" in the sense of "countably infinite", and "at most countable" instead of "countable". Also, sometimes "denumerable" is used for "countably infinite".
On the other hand, one must not mix up countable sets with the related, but different, concept of (recursively) enumerable sets from computability theory.

The set of natural numbers is countably infinite (of course), but there are also (only) countably many integers, rational numbers, rational algebraic numbers, and enumerable sets of integers.
On the other hand, the set of real numbers is uncountable, and there are uncountably many sets of integers.

In terms of cardinal numbers and their arithmetic the cardinality of a countably infinite set is aleph-null, and the last two properties (among some others) can, more formally, be written as:

\aleph_0 + n = \aleph_0 + \aleph_0 = \aleph_0 \cdot \aleph_0 = \aleph_0^n = \aleph_0.

Historically, the necessity to distinguish different "sizes" of infinity was first observed by Georg Cantor late in the nineteenth century when he studied sets of real numbers. He showed that the rational numbers are countable while the real numbers are not, using arguments which are now known as Cantor's (first and second) diagonal method.

Contents

[edit] Examples

The basic examples of (finite) countable sets are sets given by a list of their elements:

The empty set is countable even though it contains no elements to be counted.

However, in order to show that a set is countable, it is not necessary to provide such a list. For instance,

[edit] Examples of countably infinite sets

[edit] Perfect squares

The set of perfect squares is countably infinite, as the following correspondence shows:

 n \leftrightarrow n^2
n 0 1 2 3 4 5 \cdots
n2 0 1 4 9 16 25 \cdots

This is an example of a proper subset of an infinite set that has as many elements as the set, a situation addressed by Galileo's paradox.

[edit] Integers

The set of integers is countably infinite. Indeed, the function

 f(n) = (-1)^n\cdot \left\lfloor \frac{n+1}{2}\right\rfloor

is a one-to-one correspondence between all natural numbers and all integers:

n 0 1 2 3 4 5 \cdots
f(n) 0 -1 1 -2 2 -3 \cdots

[edit] Union of two countable sets

The union of the set of natural numbers and any finite set is countable. Given a finite set

 A = \{ a_0, a_1, \ldots, a_{n-1} \}

of n elements, the function

 f(i) \mapsto \begin{cases} a_i, & i < n \\ i-n, & \mbox{otherwise} \end{cases}

shows that the set  B = A \cup \mathbb{N} is countable.

i 0 1 \cdots n-2 n-1 n n+1 n+2 \cdots
f(i) a0 a1 \cdots an-2 an-1 0 1 2 \cdots

If the set A contains no natural numbers then the function f is a one-to-one correspondence between all natural numbers and B. Otherwise f is rather a map from natural numbers onto B, which ensures countability of B even though f is not one-to-one.

Consider two countably infinite sets:

 A = \{a_0, a_1, a_2, \ldots \} and  B = \{b_0, b_1, \ldots \}.

If they are disjoint then the function

 i \leftrightarrow \begin{cases} a_{i/2}, & i \mbox{ is even} \\ b_{(i-1)/2}, & i \mbox{ is odd} \end{cases}

is a one-to-one correspondence between  \mathbb N and  A \cup B . Otherwise the function maps natural numbers onto the union.

i 0 1 2 3 \cdots 2k 2k+1 2k+2 2k+3 \cdots
a0 b0 a1 b1 \cdots ak bk ak+1 bk+1 \cdots


(Note that in the example of the integers the same method has been used: Let A be the positive integers and B be the negative integers.)
This situation is illustrated by Hilbert's hotel.

[edit] Rational numbers

The set of (positive) rational numbers is the set of fractions

 \{ \tfrac p q \mid p,q \in \mathbb N \}.

The fractions can be arranged in an infinite table, the q-th row containing the fractions with denominator q, the p-th column containing the fractions with numerator p.

1 2 3 4 \ldots
1 \tfrac11 \tfrac21 \tfrac31 \tfrac41 \ldots
2 \tfrac12 \tfrac22 \tfrac32 \tfrac42 \ldots
3 \tfrac13 \tfrac23 \tfrac33 \tfrac43 \ldots
4 \tfrac14 \tfrac24 \tfrac34 \tfrac44 \ldots
\vdots \vdots \vdots \vdots \vdots \ddots

These fractions can be arranged in a sequence by sorting them according (p+q) and p like this

p + q 2 3 3 4 4 4 5 5 5 \cdots
p 1 1 2 1 2 3 1 2 3 \cdots
\tfrac pq \tfrac11 \tfrac12 \tfrac21 \tfrac13 \tfrac22 \tfrac31 \tfrac14 \tfrac23 \tfrac32 \cdots
0 1 2 3 4 5 6 7 8 \cdots

This correspondence can be described by the following formula:

 \frac pq \leftrightarrow \frac {(p+q-1)(p+q-2)} 2 + (p-1).

It does not matter that — because the fractions are not reduced — each rational number appears infinitely often. The set of rational numbers corresponds to the set of reduced fractions that is (as subset of a countable set) also countable.

The same argument shows that the countable union of countable sets is countable, and also that the Cartesian product of two countable sets is countable. It is called Cantor's first diagonal method.

[edit] Real numbers

The set of real numbers is not countable. The proof is a proof by contradiction, an indirect proof:

Suppose that the set of real numbers is countably infinite, then the interval of real numbers r with  0 \le r < 1 is (as a subset) also countable, and the interval can be written as a sequence (non-monotonic, of course):

 \{ r \mid 0 \le r < 1 , r \in \mathbb R \} = \{ r_i \mid i \in \mathbb N \}.

Since any real number between 0 and 1 can be written as a decimal number, the sequence ri can be written as an infinitely long list of decimal numbers:

i ri
0 0.32847...
1 0.48284...
2 0.89438...
3 0.00154...
4 0.32425...
... ...
 ? 0.55544...

But this list cannot be complete:
To show this, we construct a real number r with a decimal expansion which differs from each of the decimal numbers in the list by at least one digit, using the following procedure:
If the i-th digit (after the decimal point) of the i-th number in the list is a 5, then we take 4 as the i-th digit of the number, and if not, then we take 5 instead. Thus, for any i the i-th digit of the newly constructed number differs from the i-th digit of the i-th real number in the list, and therefore the expansion of r does not appear in the list. The expansion of r uses only the digits 4 and 5 and hence is unique, therefore the real number r does not occur in the list. Since this contradicts the initial assumption, this assumption, namely, that the set of real numbers is countable, is wrong.

This is known as Cantor's diagonalization argument.

Information.svg Some content on this page may previously have appeared on Citizendium; see the talk page.

Personal tools
Variants
Actions
Navigation
Community
Toolbox