Katana VentraIP

Countable set

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers.[a] Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

"Countable" redirects here. For the linguistic concept, see Count noun. For the statistical concept, see Count data. For the company, see Countable (app). Not to be confused with (recursively) enumerable sets.

In more technical terms, assuming the axiom of countable choice, a set is countable if its cardinality (the number of elements of the set) is not greater than that of the natural numbers. A countable set that is not finite is said to be countably infinite.


The concept is attributed to Georg Cantor, who proved the existence of uncountable sets, that is, sets that are not countable; for example the set of the real numbers.

A note on terminology [edit]

Although the terms "countable" and "countably infinite" as defined here are quite common, the terminology is not universal.[1] An alternative style uses countable to mean what is here called countably infinite, and at most countable to mean what is here called countable.[2][3]


The terms enumerable[4] and denumerable[5][6] may also be used, e.g. referring to countable and countably infinite respectively,[7] definitions vary and care is needed respecting the difference with recursively enumerable.[8]

Its is less than or equal to (aleph-null), the cardinality of the set of natural numbers .[9]

cardinality

There exists an from to .[10][11]

injective function

is empty or there exists a from to .[11]

surjective function

There exists a mapping between and a subset of .[12]

bijective

is either () or countably infinite.[5]

finite

A set is countable if:


All of these definitions are equivalent.


A set is countably infinite if:


A set is uncountable if it is not countable, i.e. its cardinality is greater than .[9]

History[edit]

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.[16] In 1878, he used one-to-one correspondences to define and compare cardinalities.[17] 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.[18]

subsets of M, hence countable,

but uncountable from the point of view of M,

If there is a set that is a standard model (see inner model) of ZFC set theory, then there is a minimal standard model (see Constructible universe). The Löwenheim–Skolem theorem can be used to show that this minimal model is countable. The fact that the notion of "uncountability" makes sense even in this model, and in particular that this model M contains elements that are:


was seen as paradoxical in the early days of set theory; see Skolem's paradox for more.


The minimal standard model includes all the algebraic numbers and all effectively computable transcendental numbers, as well as many other kinds of numbers.

Well-orders

Countable sets can be totally ordered in various ways, for example:


In both examples of well orders here, any subset has a least element; and in both examples of non-well orders, some subsets do not have a least element. This is the key definition that determines whether a total order is also a well order.

Aleph number

Counting

Hilbert's paradox of the Grand Hotel

Uncountable set

(June 1969), Multi-Variable Calculus and Linear Algebra with Applications, Calculus, vol. 2 (2nd ed.), New York: John Wiley + Sons, ISBN 978-0-471-00007-5

Apostol, Tom M.

Avelsgaard, Carol (1990), Foundations for Advanced Mathematics, Scott, Foresman and Company,  0-673-38152-8

ISBN

Cantor, Georg (1878), , Journal für die Reine und Angewandte Mathematik, 1878 (84): 242–248, doi:10.1515/crelle-1878-18788413, S2CID 123695365

"Ein Beitrag zur Mannigfaltigkeitslehre"

Ferreirós, José (2007), Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised ed.), Birkhäuser,  978-3-7643-8349-7

ISBN

Fletcher, Peter; Patty, C. Wayne (1988), Foundations of Higher Mathematics, Boston: PWS-KENT Publishing Company,  0-87150-164-3

ISBN

(1960), Naive Set Theory, D. Van Nostrand Company, Inc Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).

Halmos, Paul R.

(1950), Theory of Sets, Dover series in mathematics and physics, New York: Dover, ISBN 978-0486601410

Kamke, Erich

(1993), Real and Functional Analysis, Berlin, New York: Springer-Verlag, ISBN 0-387-94001-4

Lang, Serge

(1976), Principles of Mathematical Analysis, New York: McGraw-Hill, ISBN 0-07-054235-X

Rudin, Walter

Tao, Terence (2016). . Analysis I. Texts and Readings in Mathematics. Vol. 37 (Third ed.). Singapore: Springer. pp. 181–210. doi:10.1007/978-981-10-1789-6_8. ISBN 978-981-10-1789-6.

"Infinite sets"