In

_{1}. The cardinality of Ω is denoted $\backslash aleph\_1$ ( aleph-one). 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 o ...

, there might exist cardinalities incomparable to $\backslash aleph\_0$ (namely, the cardinalities of

Proof that R is uncountable

{{Set theory Basic concepts in infinite set theory Infinity Cardinal numbers

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
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only se ...

that contains too many elements to be countable
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. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...

. 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. T ...

: 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 noinjective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contraposit ...

(hence no bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

) 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 cal ...

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
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...

from the natural numbers to ''X''.
* The cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

of ''X'' is neither finite nor equal to $\backslash aleph\_0$ (aleph-null
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 name ...

, 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 $\backslash aleph\_0$.
The first three of these characterizations can be proven equivalent in Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such ...

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 o ...

, 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 allreal 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
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a m ...

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 cal ...

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 o ...

s of the set of natural numbers. The cardinality of R is often called the cardinality of the continuum
In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \mathbb ...

, and denoted by $\backslash mathfrak$, or $2^$, or $\backslash beth\_1$ ( beth-one).
The Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.
T ...

is an uncountable subset of R. The Cantor set is a fractal
In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illu ...

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 $\backslash beth\_2$ ( beth-two), which is larger than $\backslash beth\_1$.
A more abstract example of an uncountable set is the set of all countable ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the leas ...

s, denoted by Ω or ω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 o ...

, that $\backslash aleph\_1$ is the ''smallest'' uncountable cardinal number. Thus either $\backslash beth\_1$, the cardinality of the reals, is equal to $\backslash 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 $\backslash beth\_1$ is equal to $\backslash aleph\_1$. In 1900, David Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many ...

posed this question as the first of his 23 problems. The statement that $\backslash aleph\_1\; =\; \backslash beth\_1$ is now called the continuum hypothesis
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that
or equivalently, that
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...

, 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 o ...

).
Without the axiom of choice

Without theDedekind-finite
In mathematics, a set ''A'' is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset ''B'' of ''A'' is equinumerous to ''A''. Explicitly, this means that there exists a bijective function from ''A'' onto s ...

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 $\backslash kappa$ are equivalent:
*$\backslash kappa\; \backslash nleq\; \backslash aleph\_0;$
*$\backslash kappa\; >\; \backslash aleph\_0;$ and
*$\backslash kappa\; \backslash geq\; \backslash aleph\_1$, where $\backslash aleph\_1\; =\; ,\; \backslash omega\_1\; ,$ and $\backslash omega\_1$ is the least initial ordinal greater than $\backslash 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.
See also

*Aleph number
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 name ...

*Beth number
In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers (also known as transfinite numbers), conventionally written \beth_0,\ \beth_1,\ \beth_2,\ \beth_3,\ \dots, where \beth is the second ...

*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. ...

*Injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contraposit ...

References

Bibliography

* Halmos, Paul, ''Naive Set Theory
Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics.
Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It ...

''. 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).
*
External links

Proof that R is uncountable

{{Set theory Basic concepts in infinite set theory Infinity Cardinal numbers