Countable set

related topics
{math, number, function}

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor. The elements of a countable set can be counted one at a time — although the counting may never finish, every element of the set will eventually be associated with a natural number.

Some authors use countable set to mean a set with the same cardinality as the set of natural numbers.[1] The difference between the two definitions is that under the former, finite sets are also considered to be countable, while under the latter definition, they are not considered to be countable. To resolve this ambiguity, the term at most countable is sometimes used for the former notion, and countably infinite for the latter. The term denumerable is also used to mean countably infinite.[2]

Contents

Definition

A set S is called countable if there exists an injective function f from S to the natural numbers \mathbb{N} = \{0,1,2,3,...\}.[3]

If f is also surjective and therefore bijective, then S is called countably infinite.

As noted above, this terminology is not universal: some authors define countable not to include finite sets, i.e. they define countable to mean what is here called "countably infinite".

For alternative (equivalent) formulations of the definition in terms of a bijective function or a surjective function, see the section Formal Definition and Properties below.

Introduction

A set is a collection of elements, and may be described in many ways. One way is simply to list all of its elements; for example, the set consisting of the integers 3, 4, and 5 may be denoted {3,4,5}. This is only effective for small sets, however; for larger sets, this would be time-consuming and error-prone. Instead of listing every single element, sometimes an ellipsis ('…') is used, if the writer believes that the reader can easily guess what is missing; for example, \{ 1, 2, 3, \dots, 100 \} presumably denotes the set of integers from 1 to 100. Even in this case, however, it is still possible to list all the elements, because the set is finite; it has a specific number of elements.

Full article ▸

related documents
Complex analysis
Filter (mathematics)
Exclusive or
Modular arithmetic
Ultrafilter
Partition (number theory)
Absolute convergence
Semigroup
Galois theory
XPath 1.0
Natural transformation
Gaussian quadrature
Homological algebra
Sequence
Elliptic curve
Scope (programming)
Ideal class group
IEEE 754-1985
Key size
Tychonoff's theorem
Database normalization
Linear combination
Algebraic structure
Ordinary differential equation
E (mathematical constant)
Normed vector space
Random variable
Fuzzy logic
Abstract interpretation
Holomorphic function