Skip to content
Home

Countable set (mathematics)

A countable set is one whose elements can be put into a list indexed by the natural numbers. This article explains definitions, examples, properties, historical background and key distinctions.

Author: Created: Updated:

Overview

In mathematics a countable set is a collection whose members can be arranged in a sequence so that each element appears at some finite position in the list. Informally this means the elements can be "counted" one by one, possibly without end. The term is used in elementary and advanced areas, including set theory and analysis; see mathematics and set theory for context. When a set is infinite but still listable in this way it is called countably infinite.

Definitions and key properties

There are several equivalent formal ways to say a set S is countable. One common definition: S is countable if it is finite or there exists a bijection between S and the set of natural numbers. Another equivalent notion is the existence of an injection from S into the naturals or a surjection from the naturals onto S. The size of any countably infinite set is traditionally denoted by the symbol aleph-null (aleph-0); the notation and concept are discussed in texts on infinite cardinalities and are associated with aleph numbers.

Examples and non-examples

Typical examples of countable sets include all finite sets, the set of natural numbers itself, the integers, and the rational numbers. Even though some of these sets are infinite, they can be placed in one-to-one correspondence with the naturals and thus enumerated. By contrast, many familiar sets are uncountable: for example, the real numbers form an uncountable set; Cantor's diagonal argument shows no enumeration of the real numbers exists. For foundational discussions of natural numbers and counting, see natural numbers.

  • Countable examples: finite sets; N (naturals); Z (integers); Q (rationals).
  • Uncountable examples: R (real numbers); the set of all sequences of binary digits.

Important results and construction techniques

Several useful closure properties hold for countable sets. A countable union of countable sets is countable under mild set-theoretic assumptions, and the Cartesian product of finitely many countable sets is countable. Explicit enumerations or pairing functions are often used to prove these facts. Proof techniques include constructing explicit bijections, diagonal enumerations for pairs of naturals, and Cantor–Schröder–Bernstein arguments to compare sizes without producing a direct bijection.

History and significance

The systematic study of different sizes of infinity and the vocabulary for countability trace back to the work of Georg Cantor in the late 19th century. Cantor introduced methods to compare infinite sets and demonstrated that infinities can differ in size, distinguishing countable from uncountable infinities. His ideas underpin much of modern set theory and influence topology, measure theory and theoretical computer science, where questions about enumerability and effective listing are central.

Writers sometimes use "countable" to mean "countably infinite," so caution is warranted: some authors include finite sets in the term, while others reserve "countable" for infinite, enumerable sets. Related notions include "denumerable" (another term for countably infinite), "countably infinite," and "uncountable." In computability theory, a set may be computably enumerable (recursively enumerable) if its members can be listed by an algorithm; this is a stronger, effectiveness-oriented refinement of the purely set-theoretic idea. For further reading on Cantor and the origins of these concepts see discussions of Georg Cantor and the development of set theory.

Examples of countably infinite sets

Natural numbers

The set of natural numbers \mathbb {N} is by definition countably infinite, since it has the same power as itself.

Prime numbers

The set of primes \mathbb{P}is also countably infinite, since it is a subset of the natural numbers and, by Euclid's theorem, also infinite.

n

1

2

3

4

5

6

7

8

…

f(n)

2

3

5

7

11

13

17

19

…

Whole numbers

The set of integers \mathbb {Z} is countably infinite, for example, a count is given by

n

1

2

3

4

5

6

8

…

f(n)

0

1

−1

2

−2

3

−3

4

…

The examples of prime numbers and integers show that both real subsets and supersets can have the same power as the basic set, in contrast to the ratios for finite sets.

Pairs of natural numbers

Also, the set of all pairs (i,j)\in\mathbb{N} \times \mathbb{N}of two natural numbers is countably infinite.

Infinity is again obvious. More difficult is the question of countability. For this one uses the Cantor pairing function, which (i,j)bijectively kassigns a natural number each pair of numbers This allows one to uniquely number all pairs of numbers and thus count them.

n

1

2

3

4

5

6

7

8

9

10

…

f(n)

1,1

1,2

2,1

1,3

2,2

3,1

1,4

2,3

3,2

4,1

…

n-tuples of natural numbers

The set of all n-tuples (i_1, i_2, \ldots, i_n)natural numbers \mathbb{N}^n is also countably infinite. This is again shown by (n-1)-times applying Cantor's pairing function.

Rational numbers

Georg Cantor showed by the so-called first diagonal argument that the set of rational numbers is countable, as is any set of the form \mathbb{Z}^n(tuples of integers).

The mapping \mathbb{N}_0^3\rightarrow\mathbb{Q}, (i,j,k)\mapsto {\frac {i-j}{1+k}} is surjective, so the power of \mathbb {Q} at most as large as that of \mathbb{N}_0^3 . Since, on the one hand, there are infinitely many fractions and, on the other hand, the set \mathbb{N}_0^3is countably infinite, \mathbb {Q} countably infinite.

Algebraic numbers

An algebraic number is zero of a polynomial P(x)=a_{0}+\dots +a_{n}x^{n}with integer coefficients. PLet the height of be defined as h(P)=|a_{0}|+\dots +|a_{n}|+n.

For any given height k>0 there are only finitely many polynomials, which in turn have only finitely many zeros; for each of these k, with , a_0 = k-1 the polynomial has P(x)= -a_0 + x^1 the zero x=a_0 \in \mathbb{N} . If Q(k)set as the set of all such zeros, then the set \mathbb{A}of algebraic numbers is the union \bigcup_{k\in\mathbb N\setminus\{0\}} {Q(k)} .

As a countable union of finite sets, \mathbb{A}therefore countable. Since \mathbb{A}on the other hand contains \mathbb {N} , \mathbb{A}countably infinite.

Words above an alphabet

By applying the so-called standard numbering over the alphabet \Sigma one can also count the words of a language in the sense of mathematics.

Computable number functions

The set of all computable number functions is countably infinite. One can specify a standard numbering of all conceivable tape programs. Since the set of tape programs is larger than the set of computable functions (there could be two different programs that compute the same function), the number functions are thus countably infinite.

Example of a countable infinite set

The set of real numbers, on the other hand, is overcountable. This means that there is no bijective mapping that maps each real number to one natural number each, see Cantor's second diagonal argument.

Related articles

Author

AlegsaOnline.com Countable set (mathematics)

URL: https://en.alegsaonline.com/art/23471

Share

Sources