TheInfoList

OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
: a set is uncountable if its cardinal number is larger than that of the set of all
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s.

# Characterizations

There are many equivalent characterizations of uncountability. A set ''X'' is uncountable if and only if any of the following conditions hold: * There is no injective function (hence no bijection) from ''X'' to the set of natural numbers. * ''X'' is nonempty and for every ω-
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of elements of ''X'', there exists at least one element of X not included in it. That is, ''X'' is nonempty and there is no surjective function from the natural numbers to ''X''. * The cardinality of ''X'' is neither finite nor equal to $\aleph_0$ ( aleph-null, the cardinality of the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s). * The set ''X'' has cardinality strictly greater than $\aleph_0$. The first three of these characterizations can be proven equivalent in Zermelo–Fraenkel set theory without the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, but the equivalence of the third and fourth cannot be proved without additional choice principles.

# Properties

* If an uncountable set ''X'' is a subset of set ''Y'', then ''Y'' is uncountable.

# Examples

The best known example of an uncountable set is the set R of all
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s; Cantor's diagonal argument shows that this set is uncountable. The diagonalization proof technique can also be used to show that several other sets are uncountable, such as the set of all infinite
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
s of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s and the set of all
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s of the set of natural numbers. The cardinality of R is often called the cardinality of the continuum, and denoted by $\mathfrak$, or $2^$, or $\beth_1$ ( beth-one). The Cantor set is an uncountable subset of R. The Cantor set is a fractal and has
Hausdorff dimension In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of ...
greater than zero but less than one (R has dimension one). This is an example of the following fact: any subset of R of Hausdorff dimension strictly greater than zero must be uncountable. Another example of an uncountable set is the set of all functions from R to R. This set is even "more uncountable" than R in the sense that the cardinality of this set is $\beth_2$ ( beth-two), which is larger than $\beth_1$. A more abstract example of an uncountable set is the set of all countable ordinal numbers, denoted by Ω or ω1. The cardinality of Ω is denoted $\aleph_1$ (
aleph-one In mathematics, particularly in set theory, the aleph numbers are a sequence of numbers used to represent the cardinality (or size) of infinite sets that can be well-ordered. They were introduced by the mathematician Georg Cantor and are named a ...
). It can be shown, using the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, that $\aleph_1$ is the ''smallest'' uncountable cardinal number. Thus either $\beth_1$, the cardinality of the reals, is equal to $\aleph_1$ or it is strictly larger.
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance o ...
was the first to propose the question of whether $\beth_1$ is equal to $\aleph_1$. In 1900, David Hilbert posed this question as the first of his 23 problems. The statement that $\aleph_1 = \beth_1$ is now called the continuum hypothesis, and is known to be independent of the Zermelo–Fraenkel axioms for
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
(including the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
).

# Without the axiom of choice

Without the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, there might exist cardinalities incomparable to $\aleph_0$ (namely, the cardinalities of Dedekind-finite infinite sets). Sets of these cardinalities satisfy the first three characterizations above, but not the fourth characterization. Since these sets are not larger than the natural numbers in the sense of cardinality, some may not want to call them uncountable. If the axiom of choice holds, the following conditions on a cardinal $\kappa$ are equivalent: *$\kappa \nleq \aleph_0;$ *$\kappa > \aleph_0;$ and *$\kappa \geq \aleph_1$, where $\aleph_1 = , \omega_1 ,$ and $\omega_1$ is the least initial ordinal greater than $\omega.$ However, these may all be different if the axiom of choice fails. So it is not obvious which one is the appropriate generalization of "uncountability" when the axiom fails. It may be best to avoid using the word in this case and specify which of these one means.

* Aleph number * Beth number *
First uncountable ordinal In mathematics, the first uncountable ordinal, traditionally denoted by \omega_1 or sometimes by \Omega, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum (least upper bound) of all countable ordinals. W ...
* Injective function

# Bibliography

* Halmos, Paul, '' Naive Set Theory''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. (Paperback edition). *