Countable set

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 countable set is either a finite set or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number. 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 countable set is either a finite set or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number. Some authors use countable set to mean countably infinite alone. To avoid this ambiguity, the term at most countable may be used when finite sets are included and countably infinite, enumerable, or denumerable otherwise. Georg Cantor introduced the term countable set, contrasting sets that are countable with those that are uncountable (i.e., nonenumerable or nondenumerable). Today, countable sets form the foundation of a branch of mathematics called discrete mathematics. A set S is countable if there exists an injective function f from S to the natural numbers N = {0, 1, 2, 3, ...}. If such an f can be found that is also surjective (and therefore bijective), then S is called countably infinite. In other words, a set is countably infinite if it has one-to-one correspondence with the natural number set, N. As noted above, this terminology is not universal. Some authors use countable to mean what is here called countably infinite, and do not include finite sets. Alternative (equivalent) formulations of the definition in terms of a bijective function or a surjective function can also be given. See below. In 1874, in his first set theory article, Cantor proved that the set of real numbers is uncountable, thus showing that not all infinite sets are countable. In 1878, he used one-to-one correspondences to define and compare cardinalities. In 1883, he extended the natural numbers with his infinite ordinals, and used sets of ordinals to produce an infinity of sets having different infinite cardinalities.