text:
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 mentioned by German mathematician Georg Cantor in 1883.

Through consideration of this set, Cantor and others helped lay the foundations of modern point-set topology. The most common construction is the Cantor ternary set, built by removing the middle third of a line segment and then repeating the process with the remaining shorter segments. Cantor mentioned this ternary construction only in passing, as an example of a perfect set that is nowhere dense (, Anmerkungen zu §10, /p. 590).

More generally, in topology, a Cantor space is a topological space homeomorphic to the Cantor ternary set (equipped with its subspace topology). By a theorem of L. E. J. Brouwer, this is equivalent to being perfect, nonempty, compact, metrizable and zero dimensional.

Construction and formula of the ternary set
The Cantor ternary set $$\mathcal{C}$$ is created by iteratively deleting the open middle third from a set of line segments. One starts by deleting the open middle third $\left(\frac{1}{3}, \frac{2}{3}\right)$ from the interval $$\textstyle\left[0, 1\right]$$, leaving two line segments: $\left[0, \frac{1}{3}\right]\cup\left[\frac{2}{3}, 1\right]$. Next, the open middle third of each of these remaining segments is deleted, leaving four line segments: $\left[0, \frac{1}{9}\right]\cup\left[\frac{2}{9}, \frac{1}{3}\right]\cup\left[\frac{2}{3}, \frac{7}{9}\right]\cup\left[\frac{8}{9}, 1\right]$. The Cantor ternary set contains all points in the interval $$[0,1]$$ that are not deleted at any step in this infinite process. The same facts can be described recursively by setting
 * $$C_0 := [0,1]$$

and
 * $$C_n := \frac{C_{n-1}} 3 \cup \left(\frac 2 {3} +\frac{C_{n-1}} 3 \right) = \frac13 \bigl(C_{n-1} \cup \left(2 + C_{n-1} \right)\bigr)$$

for $$n \ge 1$$, so that
 * $$\mathcal{C} :=$$ ${\color{Blue}\lim_{n\to\infty}C_n}$ $$= \bigcap_{n=0}^\infty C_n = \bigcap_{n=m}^\infty C_n $$   for any   $$m \ge 0$$.

The first six steps of this process are illustrated below.

Using the idea of self-similar transformations, $$T_L(x)=x/3,$$ $$T_R(x)=(2+x)/3$$ and $$C_n =T_L(C_{n-1})\cup T_R(C_{n-1}),$$ the explicit closed formulas for the Cantor set are
 * $$\mathcal{C}=[0,1] \,\setminus\, \bigcup_{n=0}^\infty \bigcup_{k=0}^{3^n-1} \left(\frac{3k+1}{3^{n+1}},\frac{3k+2}{3^{n+1}} \right)\!,$$

where every middle third is removed as the open interval $\left(\frac{3k+1}{3^{n+1}},\frac{3k+2}{3^{n+1}}\right)$ from the closed interval $\left[\frac{3k+0}{3^{n+1}},\frac{3k+3}{3^{n+1}}\right] = \left[\frac{k+0}{3^n},\frac{k+1}{3^n}\right]$  surrounding it, or
 * $$\mathcal{C}=\bigcap_{n=1}^\infty \bigcup_{k=0}^{3^{n-1}-1} \left( \left[\frac{3k+0}{3^n},\frac{3k+1}{3^n}\right] \cup \left[\frac{3k+2}{3^n},\frac{3k+3}{3^n}\right] \right)\!,$$

where the middle third $\left(\frac{3k+1}{3^n},\frac{3k+2}{3^n}\right) $ of the foregoing closed interval $\left[\frac{k+0}{3^{n-1}},\frac{k+1}{3^{n-1}}\right] = \left[\frac{3k+0}{3^n},\frac{3k+3}{3^n}\right]$  is removed by intersecting with $\left[\frac{3k+0}{3^n},\frac{3k+1}{3^n}\right] \cup \left[\frac{3k+2}{3^n},\frac{3k+3}{3^n}\right]\!.$

This process of removing middle thirds is a simple example of a finite subdivision rule. The complement of the Cantor ternary set is an example of a fractal string.

In arithmetical terms, the Cantor set consists of all real numbers of the unit interval $$[0,1]$$ that do not require the digit 1 in order to be expressed as a ternary (base 3) fraction. As the above diagram illustrates, each point in the Cantor set is uniquely located by a path through an infinitely deep binary tree, where the path turns left or right at each level according to which side of a deleted segment the point lies on. Representing each left turn with 0 and each right turn with 2 yields the ternary fraction for a point.

Mandelbrot's construction by "curdling"
In The Fractal Geometry of Nature, mathematician Benoit Mandelbrot provides a whimsical thought experiment to assist non-mathematical readers in imagining the construction of $$\mathcal{C}$$. His narrative begins with imagining a bar, perhaps of lightweight metal, in which the bar's matter "curdles" by iteratively shifting towards its extremities. As the bar's segments become smaller, they become thin, dense slugs that eventually grow too small and faint to see."CURDLING: The construction of the Cantor bar results from the process I call curdling. It begins with a round bar. It is best to think of it as having a very low density. Then matter 'curdles' out of this bar's middle third into the end thirds, so that the positions of the latter remain unchanged. Next matter curdles out of the middle third of each end third into its end thirds, and so on ad infinitum until one is left with an infinitely large number of infinitely thin slugs of infinitely high density. These slugs are spaced along the line in the very specific fashion induced by the generating process. In this illustration, curdling (which eventually requires hammering!) stops when both the printer's press and our eye cease to follow; the last line is indistinguishable from the last but one: each of its ultimate parts is seen as a gray slug rather than two parallel black slugs."

Composition
Since the Cantor set is defined as the set of points not excluded, the proportion (i.e., measure) of the unit interval remaining can be found by total length removed. This total is the geometric progression

 * $$\sum_{n=0}^\infty \frac{2^n}{3^{n+1}} = \frac{1}{3} + \frac{2}{9} + \frac{4}{27} + \frac{8}{81} + \cdots = \frac{1}{3}\left(\frac{1}{1-\frac{2}{3}}\right) = 1.$$

So that the proportion left is 1 − 1 = 0.

This calculation suggests that the Cantor set cannot contain any interval of non-zero length. It may seem surprising that there should be anything left—after all, the sum of the lengths of the removed intervals is equal to the length of the original interval. However, a closer look at the process reveals that there must be something left, since removing the "middle third" of each interval involved removing open sets (sets that do not include their endpoints). So removing the line segment ($1⁄3$, $2⁄3$) from the original interval [0, 1] leaves behind the points $1⁄3$ and $2⁄3$. Subsequent steps do not remove these (or other) endpoints, since the intervals removed are always internal to the intervals remaining. So the Cantor set is not empty, and in fact contains an uncountably infinite number of points (as follows from the above description in terms of paths in an infinite binary tree).

It may appear that only the endpoints of the construction segments are left, but that is not the case either. The number $1⁄4$, for example, has the unique ternary form 0.020202... = $\overline{0.|02}$. It is in the bottom third, and the top third of that third, and the bottom third of that top third, and so on. Since it is never in one of the middle segments, it is never removed. Yet it is also not an endpoint of any middle segment, because it is not a multiple of any power of 1/3. All endpoints of segments are terminating ternary fractions and are contained in the set
 * $$ \left\{x \in [0,1] \mid \exists i \in \N_0: x \, 3^i \in \Z \right\} \qquad \Bigl(\subset \N_0 \, 3^{-\N_0} \Bigr) $$

which is a countably infinite set. As to cardinality, almost all elements of the Cantor set are not endpoints of intervals, nor rational points like 1/4. The whole Cantor set is in fact not countable.

Cardinality
It can be shown that there are as many points left behind in this process as there were to begin with, and that therefore, the Cantor set is uncountable. To see this, we show that there is a function f from the Cantor set $$\mathcal{C}$$ to the closed interval [0,1] that is surjective (i.e. f maps from $$\mathcal{C}$$ onto [0,1]) so that the cardinality of $$\mathcal{C}$$ is no less than that of [0,1]. Since $$\mathcal{C}$$ is a subset of [0,1], its cardinality is also no greater, so the two cardinalities must in fact be equal, by the Cantor–Bernstein–Schröder theorem.

To construct this function, consider the points in the [0, 1] interval in terms of base 3 (or ternary) notation. Recall that the proper ternary fractions, more precisely: the elements of $$\bigl(\Z \setminus \{0\}\bigr) \cdot 3^{-\N_0}$$, admit more than one representation in this notation, as for example $1⁄3$, that can be written as 0.13 = $\overline{0.1|0}$3, but also as 0.0222...3 = $\overline{0.0|2}$3, and $2⁄3$, that can be written as 0.23 = $\overline{0.2|0}$3 but also as 0.1222...3 = $\overline{0.1|2}$3. When we remove the middle third, this contains the numbers with ternary numerals of the form 0.1xxxxx...3 where xxxxx...3 is strictly between 00000...3 and 22222...3. So the numbers remaining after the first step consist of
 * Numbers of the form 0.0xxxxx...3 (including 0.022222...3 = 1/3)
 * Numbers of the form 0.2xxxxx...3 (including 0.222222...3 = 1)

This can be summarized by saying that those numbers with a ternary representation such that the first digit after the radix point is not 1 are the ones remaining after the first step.

The second step removes numbers of the form 0.01xxxx...3 and 0.21xxxx...3, and (with appropriate care for the endpoints) it can be concluded that the remaining numbers are those with a ternary numeral where neither of the first two digits is 1.

Continuing in this way, for a number not to be excluded at step n, it must have a ternary representation whose nth digit is not 1. For a number to be in the Cantor set, it must not be excluded at any step, it must admit a numeral representation consisting entirely of 0s and 2s.

It is worth emphasizing that numbers like 1, $1⁄3$ = 0.13 and $7⁄9$ = 0.213 are in the Cantor set, as they have ternary numerals consisting entirely of 0s and 2s: 1 = 0.222...3 = $\overline{0.|2}$3, $1⁄3$ = 0.0222...3 = $\overline{0.0|2}$3 and $7⁄9$ = 0.20222...3 = $\overline{0.20|2}$3. All the latter numbers are "endpoints", and these examples are right limit points of $$\mathcal{C}$$. The same is true for the left limit points of $$\mathcal{C}$$, e.g. $2⁄3$ = 0.1222...3 = $\overline{0.1|2}$3 = $\overline{0.2|0}$3 and $8⁄9$ = 0.21222...3 = $\overline{0.21|2}$3 = $\overline{0.22|0}$3. All these endpoints are proper ternary fractions (elements of $$\Z \cdot 3^{-\N_0}$$) of the form $p⁄q$, where denominator q is a power of 3 when the fraction is in its irreducible form. The ternary representation of these fractions terminates (i.e., is finite) or — recall from above that proper ternary fractions each have 2 representations — is infinite and "ends" in either infinitely many recurring 0s or infinitely many recurring 2s. Such a fraction is a left limit point of $$\mathcal{C}$$ if its ternary representation contains no 1's and "ends" in infinitely many recurring 0s. Similarly, a proper ternary fraction is a right limit point of $$\mathcal{C}$$ if it again its ternary expansion contains no 1's and "ends" in infinitely many recurring 2s.

This set of endpoints is dense in $$\mathcal{C}$$ (but not dense in [0, 1]) and makes up a countably infinite set. The numbers in $$\mathcal{C}$$ which are not endpoints also have only 0s and 2s in their ternary representation, but they cannot end in an infinite repetition of the digit 0, nor of the digit 2, because then it would be an endpoint.

The function from $$\mathcal{C}$$ to [0,1] is defined by taking the ternary numerals that do consist entirely of 0s and 2s, replacing all the 2s by 1s, and interpreting the sequence as a binary representation of a real number. In a formula,

 * $$f \bigg( \sum_{k\in \N} a_k 3^{-k} \bigg) = \sum_{k\in \N} \frac{a_k}{2} 2^{-k}$$  where   $$\forall k\in \N : a_k \in \{0,2\} .$$

For any number y in [0,1], its binary representation can be translated into a ternary representation of a number x in $$\mathcal{C}$$ by replacing all the 1s by 2s. With this, f(x) = y so that y is in the range of f. For instance if y = $3⁄5$ = 0.100110011001...2 = $\overline{0.|1001}$, we write x = $\overline{0.|2002}$ = 0.200220022002...3 = $7⁄10$. Consequently, f is surjective. However, f is not injective — the values for which f(x) coincides are those at opposing ends of one of the middle thirds removed. For instance, take
 * $1⁄3$ = $\overline{0.0|2}$3 (which is a right limit point of $$\mathcal{C}$$ and a left limit point of the middle third [$1⁄3$, $2⁄3$]) and
 * $2⁄3$ = $\overline{0.2|0}$3 (which is a left limit point of $$\mathcal{C}$$ and a right limit point of the middle third [$1⁄3$, $2⁄3$])

so
 * $$\begin{array}{lcl}

f\bigl({}^1\!\!/\!_3 \bigr) = f(0.0\overline{2}_3) = 0.0\overline{1}_2 = \!\! & \!\! 0.1_2 \!\! & \!\! = 0.1\overline{0}_2 = f(0.2\overline{0}_3) = f\bigl({}^2\!\!/\!_3 \bigr). \\ & \parallel \\ & {}^1\!\!/\!_2 \end{array}$$ Thus there are as many points in the Cantor set as there are in the interval [0, 1] (which has the uncountable cardinality $\mathfrak{c} = 2^{\aleph_0}$). However, the set of endpoints of the removed intervals is countable, so there must be uncountably many numbers in the Cantor set which are not interval endpoints. As noted above, one example of such a number is $1⁄4$, which can be written as 0.020202...3 = $\overline{0.|02}$ in ternary notation. In fact, given any $$a\in[-1,1]$$, there exist $$x,y\in\mathcal{C}$$ such that $$a = y-x$$. This was first demonstrated by Steinhaus in 1917, who proved, via a geometric argument, the equivalent assertion that $$\{(x,y)\in\mathbb{R}^2 \mid y=x+a\} \; \cap \; (\mathcal{C}\times\mathcal{C}) \neq\emptyset$$ for every $$a\in[-1,1]$$. Since this construction provides an injection from $$[-1,1]$$ to $$\mathcal{C}\times\mathcal{C}$$, we have $$|\mathcal{C}\times\mathcal{C}|\geq|[-1,1]|=\mathfrak{c}$$ as an immediate corollary. Assuming that $$|A\times A|=|A|$$ for any infinite set $$A$$ (a statement shown to be equivalent to the axiom of choice by Tarski), this provides another demonstration that $$|\mathcal{C}|=\mathfrak{c}$$.

The Cantor set contains as many points as the interval from which it is taken, yet itself contains no interval of nonzero length. The irrational numbers have the same property, but the Cantor set has the additional property of being closed, so it is not even dense in any interval, unlike the irrational numbers which are dense in every interval.

It has been conjectured that all algebraic irrational numbers are normal. Since members of the Cantor set are not normal, this would imply that all members of the Cantor set are either rational or transcendental.

Self-similarity
The Cantor set is the prototype of a fractal. It is self-similar, because it is equal to two copies of itself, if each copy is shrunk by a factor of 3 and translated. More precisely, the Cantor set is equal to the union of two functions, the left and right self-similarity transformations of itself, $$T_L(x)=x/3$$ and $$T_R(x)=(2+x)/3$$, which leave the Cantor set invariant up to homeomorphism: $$T_L(\mathcal{C})\cong T_R(\mathcal{C})\cong \mathcal{C}=T_L(\mathcal{C})\cup T_R(\mathcal{C}).$$

Repeated iteration of $$T_L$$ and $$T_R$$ can be visualized as an infinite binary tree. That is, at each node of the tree, one may consider the subtree to the left or to the right. Taking the set $$\{T_L, T_R\}$$ together with function composition forms a monoid, the dyadic monoid.

The automorphisms of the binary tree are its hyperbolic rotations, and are given by the modular group. Thus, the Cantor set is a homogeneous space in the sense that for any two points $$x$$ and $$y$$ in the Cantor set $$\mathcal{C}$$, there exists a homeomorphism $$h:\mathcal{C}\to \mathcal{C}$$ with $$h(x)=y$$. An explicit construction of $$h$$ can be described more easily if we see the Cantor set as a product space of countably many copies of the discrete space $$\{0,1\}$$. Then the map $$h:\{0,1\}^\N\to\{0,1\}^\N $$ defined by $$h_n(u):=u_n+x_n+y_n \mod 2$$ is an involutive homeomorphism exchanging $$x$$ and $$y$$.

Conservation law
It has been found that some form of conservation law is always responsible behind scaling and self-similarity. In the case of Cantor set it can be seen that the $$d_f$$th moment (where $$d_f=\ln(2)/\ln(3)$$ is the fractal dimension) of all the surviving intervals at any stage of the construction process is equal to a constant which is one in the case of the Cantor set. We know that there are $$N=2^n$$ intervals of size $$1/3^n$$ present in the system at the $$n$$th step of its construction. Then if we label the surviving intervals as $$x_1, x_2, \ldots, x_{2^n}$$ then the $$d_f$$th moment is $$x_1^{d_f}+x_2^{d_f}+\cdots+x_{2^n}^{d_f}=1$$ since $$x_1=x_2= \cdots =x_{2^n}=1/3^n$$.

The Hausdorff dimension of the Cantor set is equal to ln(2)/ln(3) ≈ 0.631.

Topological and analytical properties
Although "the" Cantor set typically refers to the original, middle-thirds Cantor set described above, topologists often talk about "a" Cantor set, which means any topological space that is homeomorphic (topologically equivalent) to it.

As the above summation argument shows, the Cantor set is uncountable but has Lebesgue measure 0. Since the Cantor set is the complement of a union of open sets, it itself is a closed subset of the reals, and therefore a complete metric space. Since it is also totally bounded, the Heine–Borel theorem says that it must be compact.

For any point in the Cantor set and any arbitrarily small neighborhood of the point, there is some other number with a ternary numeral of only 0s and 2s, as well as numbers whose ternary numerals contain 1s. Hence, every point in the Cantor set is an accumulation point (also called a cluster point or limit point) of the Cantor set, but none is an interior point. A closed set in which every point is an accumulation point is also called a perfect set in topology, while a closed subset of the interval with no interior points is nowhere dense in the interval.

Every point of the Cantor set is also an accumulation point of the complement of the Cantor set.

For any two points in the Cantor set, there will be some ternary digit where they differ — one will have 0 and the other 2. By splitting the Cantor set into "halves" depending on the value of this digit, one obtains a partition of the Cantor set into two closed sets that separate the original two points. In the relative topology on the Cantor set, the points have been separated by a clopen set. Consequently, the Cantor set is totally disconnected. As a compact totally disconnected Hausdorff space, the Cantor set is an example of a Stone space.

As a topological space, the Cantor set is naturally homeomorphic to the product of countably many copies of the space $$\{0, 1\}$$, where each copy carries the discrete topology. This is the space of all sequences in two digits
 * $$2^\mathbb{N} = \{(x_n) \mid x_n \in \{0,1\} \text{ for } n \in \mathbb{N}\},$$

which can also be identified with the set of 2-adic integers. The basis for the open sets of the product topology are cylinder sets; the homeomorphism maps these to the subspace topology that the Cantor set inherits from the natural topology on the real line. This characterization of the Cantor space as a product of compact spaces gives a second proof that Cantor space is compact, via Tychonoff's theorem.

From the above characterization, the Cantor set is homeomorphic to the p-adic integers, and, if one point is removed from it, to the p-adic numbers.

The Cantor set is a subset of the reals, which are a metric space with respect to the ordinary distance metric; therefore the Cantor set itself is a metric space, by using that same metric. Alternatively, one can use the p-adic metric on $$2^\mathbb{N}$$: given two sequences $$(x_n),(y_n)\in 2^\mathbb{N}$$, the distance between them is $$d((x_n),(y_n)) = 2^{-k}$$, where $$k$$ is the smallest index such that $$x_k \ne y_k$$; if there is no such index, then the two sequences are the same, and one defines the distance to be zero. These two metrics generate the same topology on the Cantor set.

We have seen above that the Cantor set is a totally disconnected perfect compact metric space. Indeed, in a sense it is the only one: every nonempty totally disconnected perfect compact metric space is homeomorphic to the Cantor set. See Cantor space for more on spaces homeomorphic to the Cantor set.

The Cantor set is sometimes regarded as "universal" in the category of compact metric spaces, since any compact metric space is a continuous image of the Cantor set; however this construction is not unique and so the Cantor set is not universal in the precise categorical sense. The "universal" property has important applications in functional analysis, where it is sometimes known as the representation theorem for compact metric spaces.

For any integer q ≥ 2, the topology on the group G = Zqω (the countable direct sum) is discrete. Although the Pontrjagin dual Γ is also Zqω, the topology of Γ is compact. One can see that Γ is totally disconnected and perfect - thus it is homeomorphic to the Cantor set. It is easiest to write out the homeomorphism explicitly in the case q = 2. (See Rudin 1962 p 40.)

Measure and probability
The Cantor set can be seen as the compact group of binary sequences, and as such, it is endowed with a natural Haar measure. When normalized so that the measure of the set is 1, it is a model of an infinite sequence of coin tosses. Furthermore, one can show that the usual Lebesgue measure on the interval is an image of the Haar measure on the Cantor set, while the natural injection into the ternary set is a canonical example of a singular measure. It can also be shown that the Haar measure is an image of any probability, making the Cantor set a universal probability space in some ways.

In Lebesgue measure theory, the Cantor set is an example of a set which is uncountable and has zero measure. In contrast, the set has a Hausdorff measure of 1 in its dimension of log 2 / log 3.

Cantor numbers
If we define a Cantor number as a member of the Cantor set, then
 * 1) Every real number in [0, 2] is the sum of two Cantor numbers.
 * 2) Between any two Cantor numbers there is a number that is not a Cantor number.

Descriptive set theory
The Cantor set is a meagre set (or a set of first category) as a subset of [0,1] (although not as a subset of itself, since it is a Baire space). The Cantor set thus demonstrates that notions of "size" in terms of cardinality, measure, and (Baire) category need not coincide. Like the set $$\mathbb{Q}\cap[0,1]$$, the Cantor set $$\mathcal{C}$$ is "small" in the sense that it is a null set (a set of measure zero) and it is a meagre subset of [0,1]. However, unlike $$\mathbb{Q}\cap[0,1]$$, which is countable and has a "small" cardinality, $$\aleph_0$$, the cardinality of $$\mathcal{C}$$ is the same as that of [0,1], the continuum $$\mathfrak{c}$$, and is "large" in the sense of cardinality. In fact, it is also possible to construct a subset of [0,1] that is meagre but of positive measure and a subset that is non-meagre but of measure zero: By taking the countable union of "fat" Cantor sets $$\mathcal{C}^{(n)}$$ of measure $$\lambda = (n-1)/n$$ (see Smith–Volterra–Cantor set below for the construction), we obtain a set $\mathcal{A} := \bigcup_{n=1}^{\infty}\mathcal{C}^{(n)}$ which has a positive measure (equal to 1) but is meagre in [0,1], since each $$\mathcal{C}^{(n)}$$ is nowhere dense. Then consider the set $\mathcal{A}^{\mathrm{c}} = [0,1] \setminus\bigcup_{n=1}^\infty \mathcal{C}^{(n)}$. Since $$\mathcal{A}\cup\mathcal{A}^{\mathrm{c}} = [0,1]$$, $$\mathcal{A}^{\mathrm{c}}$$ cannot be meagre, but since $$\mu(\mathcal{A})=1$$, $$\mathcal{A}^{\mathrm{c}}$$ must have measure zero.

Smith–Volterra–Cantor set
Instead of repeatedly removing the middle third of every piece as in the Cantor set, we could also keep removing any other fixed percentage (other than 0% and 100%) from the middle. In the case where the middle $8⁄10$ of the interval is removed, we get a remarkably accessible case — the set consists of all numbers in [0,1] that can be written as a decimal consisting entirely of 0s and 9s. If a fixed percentage is removed at each stage, then the limiting set will have measure zero, since the length of the remainder $$(1-f)^n\to 0$$ as $$n\to\infty$$ for any $$f$$ such that $$0<f\leq 1$$.

On the other hand, "fat Cantor sets" of positive measure can be generated by removal of smaller fractions of the middle of the segment in each iteration. Thus, one can construct sets homeomorphic to the Cantor set that have positive Lebesgue measure while still being nowhere dense. If an interval of length $$r^n$$ ($$r\leq 1/3$$) is removed from the middle of each segment at the nth iteration, then the total length removed is $\sum_{n=1}^\infty 2^{n-1}r^n=r/(1-2r)$, and the limiting set will have a Lebesgue measure of $$\lambda=(1-3r)/(1-2r)$$. Thus, in a sense, the middle-thirds Cantor set is a limiting case with $$r=1/3$$. If $$0<r<1/3$$, then the remainder will have positive measure with $$0<\lambda<1$$. The case $$r=1/4$$ is known as the Smith–Volterra–Cantor set, which has a Lebesgue measure of $$1/2$$.

Stochastic Cantor set
One can modify the construction of the Cantor set by dividing randomly instead of equally. Besides, to incorporate time we can divide only one of the available intervals at each step instead of dividing all the available intervals. In the case of stochastic triadic Cantor set the resulting process can be described by the following rate equation

 * $$\frac{\partial c(x,t)}{\partial t} =-\frac{x^2}{2} c(x,t) + 2\int_x^\infty (y-x)c(y,t) \, dy,$$

and for the stochastic dyadic Cantor set

 * $${{\partial c(x,t)}\over{\partial t}}=-xc(x,t)+(1+p)\int_x^\infty c(y,t) \, dy,$$

where $$c(x,t)dx$$ is the number of intervals of size between $$x$$ and $$x+dx$$. In the case of triadic Cantor set the fractal dimension is $$0.5616$$ which is less than its deterministic counterpart $$0.6309$$. In the case of stochastic dyadic Cantor set the fractal dimension is $$p$$ which is again less than that of its deterministic counterpart $$\ln (1+p)/\ln 2$$. In the case of stochastic dyadic Cantor set the solution for $$c(x,t)$$ exhibits dynamic scaling as its solution in the long-time limit is $$t^{-(1+d_f)}e^{-xt}$$ where the fractal dimension of the stochastic dyadic Cantor set $$d_f=p$$. In either case, like triadic Cantor set, the $$d_f$$th moment ($\int x^{d_f} c(x,t) \, dx = \text{constant}$ ) of stochastic triadic and dyadic Cantor set too are conserved quantities.

Cantor dust
Cantor dust is a multi-dimensional version of the Cantor set. It can be formed by taking a finite Cartesian product of the Cantor set with itself, making it a Cantor space. Like the Cantor set, Cantor dust has zero measure.

A different 2D analogue of the Cantor set is the Sierpinski carpet, where a square is divided up into nine smaller squares, and the middle one removed. The remaining squares are then further divided into nine each and the middle removed, and so on ad infinitum. One 3D analogue of this is the Menger sponge.

Historical remarks
Cantor introduced what we call today the Cantor ternary set $$\mathcal C$$ as an example "of a perfect point-set, which is not everywhere-dense in any interval, however small." Cantor described $$\mathcal C$$ in terms of ternary expansions, as "the set of all real numbers given by the formula: $$z=c_1/3 +c_2/3^2 + \cdots + c_\nu/3^\nu +\cdots $$where the coefficients $$c_\nu$$ arbitrarily take the two values 0 and 2, and the series can consist of a finite number or an infinite number of elements."

A topological space $$P$$ is perfect if all its points are limit points or, equivalently, if it coincides with its derived set $$P'$$. Subsets of the real line, like $$\mathcal C$$, can be seen as topological spaces under the induced subspace topology.

Cantor was led to the study of derived sets by his results on uniqueness of trigonometric series. The latter did much to set him on the course for developing an abstract, general theory of infinite sets.

Benoit Mandelbrot wrote much on Cantor dusts and their relation to natural fractals and statistical physics. He further reflected on the puzzling or even upsetting nature of such structures to those in the mathematics and physics community. In The Fractal geometry of Nature, he described how "When I started on this topic in 1962, everyone was agreeing that Cantor dusts are at least as monstrous as the Koch and Peano curves," and added that "every self-respecting physicist was automatically turned off by a mention of Cantor, ready to run a mile from anyone claiming $$\mathcal C$$ to be interesting in science."

title: Cantor set


text:
Cardinal number

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter $$\aleph$$ (aleph) marked with subscript indicating their rank among the infinite cardinals.

Cardinality is defined in terms of bijective functions. Two sets have the same cardinality if, and only if, there is a one-to-one correspondence (bijection) between the elements of the two sets. In the case of finite sets, this agrees with the intuitive notion of number of elements. In the case of infinite sets, the behavior is more complex. A fundamental theorem due to Georg Cantor shows that it is possible for infinite sets to have different cardinalities, and in particular the cardinality of the set of real numbers is greater than the cardinality of the set of natural numbers. It is also possible for a proper subset of an infinite set to have the same cardinality as the original set—something that cannot happen with proper subsets of finite sets.

There is a transfinite sequence of cardinal numbers:
 * $$0, 1, 2, 3, \ldots, n, \ldots ; \aleph_0, \aleph_1, \aleph_2, \ldots, \aleph_{\alpha}, \ldots.\ $$

This sequence starts with the natural numbers including zero (finite cardinals), which are followed by the aleph numbers. The aleph numbers are indexed by ordinal numbers. If the axiom of choice is true, this transfinite sequence includes every cardinal number. If the axiom of choice is not true (see ), there are infinite cardinals that are not aleph numbers.

Cardinality is studied for its own sake as part of set theory. It is also a tool used in branches of mathematics including model theory, combinatorics, abstract algebra and mathematical analysis. In category theory, the cardinal numbers form a skeleton of the category of sets.

History
The notion of cardinality, as now understood, was formulated by Georg Cantor, the originator of set theory, in 1874–1884. Cardinality can be used to compare an aspect of finite sets. For example, the sets {1,2,3} and {4,5,6} are not equal, but have the same cardinality, namely three. This is established by the existence of a bijection (i.e., a one-to-one correspondence) between the two sets, such as the correspondence {1→4, 2→5, 3→6}.

Cantor applied his concept of bijection to infinite sets (for example the set of natural numbers N = {0, 1, 2, 3, ...}). Thus, he called all sets having a bijection with N denumerable (countably infinite) sets, which all share the same cardinal number. This cardinal number is called $$\aleph_0$$, aleph-null. He called the cardinal numbers of infinite sets transfinite cardinal numbers.

Cantor proved that any unbounded subset of N has the same cardinality as N, even though this might appear to run contrary to intuition. He also proved that the set of all ordered pairs of natural numbers is denumerable; this implies that the set of all rational numbers is also denumerable, since every rational can be represented by a pair of integers. He later proved that the set of all real algebraic numbers is also denumerable. Each real algebraic number z may be encoded as a finite sequence of integers, which are the coefficients in the polynomial equation of which it is a solution, i.e. the ordered n-tuple (a0, a1, ..., an), ai ∈ Z together with a pair of rationals (b0, b1) such that z is the unique root of the polynomial with coefficients (a0, a1, ..., an) that lies in the interval (b0, b1).

In his 1874 paper "On a Property of the Collection of All Real Algebraic Numbers", Cantor proved that there exist higher-order cardinal numbers, by showing that the set of real numbers has cardinality greater than that of N. His proof used an argument with nested intervals, but in an 1891 paper, he proved the same result using his ingenious and much simpler diagonal argument. The new cardinal number of the set of real numbers is called the cardinality of the continuum and Cantor used the symbol $$\mathfrak{c}$$ for it.

Cantor also developed a large portion of the general theory of cardinal numbers; he proved that there is a smallest transfinite cardinal number ($$\aleph_0$$, aleph-null), and that for every cardinal number there is a next-larger cardinal

 * $$(\aleph_1, \aleph_2, \aleph_3, \ldots).$$

His continuum hypothesis is the proposition that the cardinality $$\mathfrak{c}$$ of the set of real numbers is the same as $$\aleph_1$$. This hypothesis is independent of the standard axioms of mathematical set theory, that is, it can neither be proved nor disproved from them. This was shown in 1963 by Paul Cohen, complementing earlier work by Kurt Gödel in 1940.

Motivation
In informal use, a cardinal number is what is normally referred to as a counting number, provided that 0 is included: 0, 1, 2, .... They may be identified with the natural numbers beginning with 0. The counting numbers are exactly what can be defined formally as the finite cardinal numbers. Infinite cardinals only occur in higher-level mathematics and logic.

More formally, a non-zero number can be used for two purposes: to describe the size of a set, or to describe the position of an element in a sequence. For finite sets and sequences it is easy to see that these two notions coincide, since for every number describing a position in a sequence we can construct a set that has exactly the right size. For example, 3 describes the position of 'c' in the sequence <'a','b','c','d',...>, and we can construct the set {a,b,c}, which has 3 elements.

However, when dealing with infinite sets, it is essential to distinguish between the two, since the two notions are in fact different for infinite sets. Considering the position aspect leads to ordinal numbers, while the size aspect is generalized by the cardinal numbers described here.

The intuition behind the formal definition of cardinal is the construction of a notion of the relative size or "bigness" of a set, without reference to the kind of members which it has. For finite sets this is easy; one simply counts the number of elements a set has. In order to compare the sizes of larger sets, it is necessary to appeal to more refined notions.

A set Y is at least as big as a set X if there is an injective mapping from the elements of X to the elements of Y. An injective mapping identifies each element of the set X with a unique element of the set Y. This is most easily understood by an example; suppose we have the sets X = {1,2,3} and Y = {a,b,c,d}, then using this notion of size, we would observe that there is a mapping:
 * 1 → a
 * 2 → b
 * 3 → c

which is injective, and hence conclude that Y has cardinality greater than or equal to X. The element d has no element mapping to it, but this is permitted as we only require an injective mapping, and not necessarily a bijective mapping. The advantage of this notion is that it can be extended to infinite sets.

We can then extend this to an equality-style relation. Two sets X and Y are said to have the same cardinality if there exists a bijection between X and Y. By the Schroeder–Bernstein theorem, this is equivalent to there being both an injective mapping from X to Y, and an injective mapping from Y to X. We then write |X| = |Y|. The cardinal number of X itself is often defined as the least ordinal a with |a| = |X|. This is called the von Neumann cardinal assignment; for this definition to make sense, it must be proved that every set has the same cardinality as some ordinal; this statement is the well-ordering principle. It is however possible to discuss the relative cardinality of sets without explicitly assigning names to objects.

The classic example used is that of the infinite hotel paradox, also called Hilbert's paradox of the Grand Hotel. Supposing there is an innkeeper at a hotel with an infinite number of rooms. The hotel is full, and then a new guest arrives. It is possible to fit the extra guest in by asking the guest who was in room 1 to move to room 2, the guest in room 2 to move to room 3, and so on, leaving room 1 vacant. We can explicitly write a segment of this mapping:
 * 1 → 2
 * 2 → 3
 * 3 → 4
 * n → n + 1
 * n → n + 1

With this assignment, we can see that the set {1,2,3,...} has the same cardinality as the set {2,3,4,...}, since a bijection between the first and the second has been shown. This motivates the definition of an infinite set being any set that has a proper subset of the same cardinality (i.e., a Dedekind-infinite set); in this case {2,3,4,...} is a proper subset of {1,2,3,...}.

When considering these large objects, one might also want to see if the notion of counting order coincides with that of cardinal defined above for these infinite sets. It happens that it does not; by considering the above example we can see that if some object "one greater than infinity" exists, then it must have the same cardinality as the infinite set we started out with. It is possible to use a different formal notion for number, called ordinals, based on the ideas of counting and considering each number in turn, and we discover that the notions of cardinality and ordinality are divergent once we move out of the finite numbers.

It can be proved that the cardinality of the real numbers is greater than that of the natural numbers just described. This can be visualized using Cantor's diagonal argument; classic questions of cardinality (for instance the continuum hypothesis) are concerned with discovering whether there is some cardinal between some pair of other infinite cardinals. In more recent times, mathematicians have been describing the properties of larger and larger cardinals.

Since cardinality is such a common concept in mathematics, a variety of names are in use. Sameness of cardinality is sometimes referred to as equipotence, equipollence, or equinumerosity. It is thus said that two sets with the same cardinality are, respectively, equipotent, equipollent, or equinumerous.

Formal definition
Formally, assuming the axiom of choice, the cardinality of a set X is the least ordinal number α such that there is a bijection between X and α. This definition is known as the von Neumann cardinal assignment. If the axiom of choice is not assumed, then a different approach is needed. The oldest definition of the cardinality of a set X (implicit in Cantor and explicit in Frege and Principia Mathematica) is as the class [X] of all sets that are equinumerous with X. This does not work in ZFC or other related systems of axiomatic set theory because if X is non-empty, this collection is too large to be a set. In fact, for X ≠ ∅ there is an injection from the universe into [X] by mapping a set m to {m} × X, and so by the axiom of limitation of size, [X] is a proper class. The definition does work however in type theory and in New Foundations and related systems. However, if we restrict from this class to those equinumerous with X that have the least rank, then it will work (this is a trick due to Dana Scott: it works because the collection of objects with any given rank is a set).

Von Neumann cardinal assignment implies that the cardinal number of a finite set is the common ordinal number of all possible well-orderings of that set, and cardinal and ordinal arithmetic (addition, multiplication, power, proper subtraction) then give the same answers for finite numbers. However, they differ for infinite numbers. For example, $$2^\omega=\omega<\omega^2$$ in ordinal arithmetic while $$2^{\aleph_0}>\aleph_0=\aleph_0^2$$ in cardinal arithmetic, although the von Neumann assignment puts $$\aleph_0=\omega$$. On the other hand, Scott's trick implies that the cardinal number 0 is $$\{\emptyset\}$$, which is also the ordinal number 1, and this may be confusing. A possible compromise (to take advantage of the alignment in finite arithmetic while avoiding reliance on the axiom of choice and confusion in infinite arithmetic) is to apply von Neumann assignment to the cardinal numbers of finite sets (those which can be well ordered and are not equipotent to proper subsets) and to use Scott's trick for the cardinal numbers of other sets.

Formally, the order among cardinal numbers is defined as follows: |X| ≤ |Y| means that there exists an injective function from X to Y. The Cantor–Bernstein–Schroeder theorem states that if |X| ≤ |Y| and |Y| ≤ |X| then |X| = |Y|. The axiom of choice is equivalent to the statement that given two sets X and Y, either |X| ≤ |Y| or |Y| ≤ |X|.

A set X is Dedekind-infinite if there exists a proper subset Y of X with |X| = |Y|, and Dedekind-finite if such a subset does not exist. The finite cardinals are just the natural numbers, in the sense that a set X is finite if and only if |X| = |n| = n for some natural number n. Any other set is infinite.

Assuming the axiom of choice, it can be proved that the Dedekind notions correspond to the standard ones. It can also be proved that the cardinal $$\aleph_0$$ (aleph null or aleph-0, where aleph is the first letter in the Hebrew alphabet, represented $$\aleph$$) of the set of natural numbers is the smallest infinite cardinal (i.e., any infinite set has a subset of cardinality $$\aleph_0$$). The next larger cardinal is denoted by $$\aleph_1$$, and so on. For every ordinal α, there is a cardinal number $$\aleph_{\alpha},$$ and this list exhausts all infinite cardinal numbers.

Cardinal arithmetic
We can define arithmetic operations on cardinal numbers that generalize the ordinary operations for natural numbers. It can be shown that for finite cardinals, these operations coincide with the usual operations for natural numbers. Furthermore, these operations share many properties with ordinary arithmetic.

Successor cardinal
If the axiom of choice holds, then every cardinal κ has a successor, denoted κ+, where κ+ > κ and there are no cardinals between κ and its successor. (Without the axiom of choice, using Hartogs' theorem, it can be shown that for any cardinal number κ, there is a minimal cardinal κ+ such that $$\kappa^+\nleq\kappa. $$) For finite cardinals, the successor is simply κ + 1. For infinite cardinals, the successor cardinal differs from the successor ordinal.

Cardinal addition
If X and Y are disjoint, addition is given by the union of X and Y. If the two sets are not already disjoint, then they can be replaced by disjoint sets of the same cardinality (e.g., replace X by X×{0} and Y by Y×{1}).
 * $$|X| + |Y| = | X \cup Y|.$$

Zero is an additive identity κ + 0 = 0 + κ = κ.

Addition is associative (κ + μ) + ν = κ + (μ + ν).

Addition is commutative κ + μ = μ + κ.

Addition is non-decreasing in both arguments:
 * $$(\kappa \le \mu) \rightarrow ((\kappa + \nu \le \mu + \nu) \mbox{ and } (\nu + \kappa \le \nu + \mu)).$$

Assuming the axiom of choice, addition of infinite cardinal numbers is easy. If either κ or μ is infinite, then
 * $$\kappa + \mu = \max\{\kappa, \mu\}\,.$$

Subtraction
Assuming the axiom of choice and, given an infinite cardinal σ and a cardinal μ, there exists a cardinal κ such that μ + κ = σ if and only if μ ≤ σ. It will be unique (and equal to σ) if and only if μ < σ.

Cardinal multiplication
The product of cardinals comes from the Cartesian product.
 * $$|X|\cdot|Y| = |X \times Y|$$

κ·0 = 0·κ = 0.

κ·μ = 0 → (κ = 0 or μ = 0).

One is a multiplicative identity κ·1 = 1·κ = κ.

Multiplication is associative (κ·μ)·ν = κ·(μ·ν).

Multiplication is commutative κ·μ = μ·κ.

Multiplication is non-decreasing in both arguments: κ ≤ μ → (κ·ν ≤ μ·ν and ν·κ ≤ ν·μ).

Multiplication distributes over addition: κ·(μ + ν) = κ·μ + κ·ν and (μ + ν)·κ = μ·κ + ν·κ.

Assuming the axiom of choice, multiplication of infinite cardinal numbers is also easy. If either κ or μ is infinite and both are non-zero, then
 * $$\kappa\cdot\mu = \max\{\kappa, \mu\}.$$

Division
Assuming the axiom of choice and, given an infinite cardinal π and a non-zero cardinal μ, there exists a cardinal κ such that μ · κ = π if and only if μ ≤ π. It will be unique (and equal to π) if and only if μ < π.

Cardinal exponentiation
Exponentiation is given by
 * $$|X|^{|Y|} = \left|X^Y\right|,$$

where XY is the set of all functions from Y to X. It is easy to check that the right-hand side depends only on $${|X|}$$ and $${|Y|}$$.

 * κ0 = 1 (in particular 00 = 1), see empty function.
 * If 1 ≤ μ, then 0μ = 0.
 * 1μ = 1.
 * κ1 = κ.
 * κμ + ν = κμ·κν.
 * κμ · ν = (κμ)ν.
 * (κ·μ)ν = κν·μν.

Exponentiation is non-decreasing in both arguments:
 * (1 ≤ ν and κ ≤ μ) → (νκ ≤ νμ) and
 * (κ ≤ μ) → (κν ≤ μν).

2undefined is the cardinality of the power set of the set X and Cantor's diagonal argument shows that 2undefined > |X| for any set X. This proves that no largest cardinal exists (because for any cardinal κ, we can always find a larger cardinal 2κ). In fact, the class of cardinals is a proper class. (This proof fails in some set theories, notably New Foundations.)

All the remaining propositions in this section assume the axiom of choice:

 * If κ and μ are both finite and greater than 1, and ν is infinite, then κν = μν.
 * If κ is infinite and μ is finite and non-zero, then κμ = κ.

If 2 ≤ κ and 1 ≤ μ and at least one of them is infinite, then:
 * Max (κ, 2μ) ≤ κμ ≤ Max (2κ, 2μ).

Using König's theorem, one can prove κ < κcf(κ) and κ < cf(2κ) for any infinite cardinal κ, where cf(κ) is the cofinality of κ.

Roots
Assuming the axiom of choice and, given an infinite cardinal κ and a finite cardinal μ greater than 0, the cardinal ν satisfying $$\nu^\mu = \kappa$$ will be $$\kappa$$.

Logarithms
Assuming the axiom of choice and, given an infinite cardinal κ and a finite cardinal μ greater than 1, there may or may not be a cardinal λ satisfying $$\mu^\lambda = \kappa$$. However, if such a cardinal exists, it is infinite and less than κ, and any finite cardinality ν greater than 1 will also satisfy $$\nu^\lambda = \kappa$$.

The logarithm of an infinite cardinal number κ is defined as the least cardinal number μ such that κ ≤ 2μ. Logarithms of infinite cardinals are useful in some fields of mathematics, for example in the study of cardinal invariants of topological spaces, though they lack some of the properties that logarithms of positive real numbers possess.

The continuum hypothesis
The continuum hypothesis (CH) states that there are no cardinals strictly between $$\aleph_0$$ and $$2^{\aleph_0}.$$ The latter cardinal number is also often denoted by $$\mathfrak{c}$$; it is the cardinality of the continuum (the set of real numbers). In this case $$2^{\aleph_0} = \aleph_1.$$

Similarly, the generalized continuum hypothesis (GCH) states that for every infinite cardinal $$\kappa$$, there are no cardinals strictly between $$\kappa$$ and $$2^\kappa$$. Both the continuum hypothesis and the generalized continuum hypothesis have been proved to be independent of the usual axioms of set theory, the Zermelo–Fraenkel axioms together with the axiom of choice (ZFC).

Indeed, Easton's theorem shows that, for regular cardinals $$\kappa$$, the only restrictions ZFC places on the cardinality of $$2^\kappa$$ are that $$ \kappa < \operatorname{cf}(2^\kappa) $$, and that the exponential function is non-decreasing.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Cardinal number


text:
Cardinality

In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set $$A = \{2, 4, 6\}$$ contains 3 elements, and therefore $$A$$ has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers. The cardinality of a set may also be called its size, when no confusion with other notions of size is possible.

The cardinality of a set $$A$$ is usually denoted $$|A|$$, with a vertical bar on each side; this is the same notation as absolute value, and the meaning depends on context. The cardinality of a set $$A$$ may alternatively be denoted by $$n(A)$$, $$A$$, $$\operatorname{card}(A)$$, or $$\#A$$.

History
A crude sense of cardinality, an awareness that groups of things or events compare with other groups by containing more, fewer, or the same number of instances, is observed in a variety of present-day animal species, suggesting an origin millions of years ago. Human expression of cardinality is seen as early as $40,000$ years ago, with equating the size of a group with a group of recorded notches, or a representative collection of other things, such as sticks and shells. The abstraction of cardinality as a number is evident by 3000 BCE, in Sumerian mathematics and the manipulation of numbers without reference to a specific group of things or events.

From the 6th century BCE, the writings of Greek philosophers show hints of the cardinality of infinite sets. While they considered the notion of infinity as an endless series of actions, such as adding 1 to a number repeatedly, they did not consider the size of an infinite set of numbers to be a thing. The ancient Greek notion of infinity also considered the division of things into parts repeated without limit. In Euclid's Elements, commensurability was described as the ability to compare the length of two line segments, a and b, as a ratio, as long as there were a third segment, no matter how small, that could be laid end-to-end a whole number of times into both a and b. But with the discovery of irrational numbers, it was seen that even the infinite set of all rational numbers was not enough to describe the length of every possible line segment. Still, there was no concept of infinite sets as something that had cardinality.

To better understand infinite sets, a notion of cardinality was formulated c. 1880 by Georg Cantor, the originator of set theory. He examined the process of equating two sets with bijection, a one-to-one correspondence between the elements of two sets based on a unique relationship. In 1891, with the publication of Cantor's diagonal argument, he demonstrated that there are sets of numbers that cannot be placed in one-to-one correspondence with the set of natural numbers, i.e. uncountable sets that contain more elements than there are in the infinite set of natural numbers.

Comparing sets

While the cardinality of a finite set is just the number of its elements, extending the notion to infinite sets usually starts with defining the notion of comparison of arbitrary sets (some of which are possibly infinite).

Definition 1: $|A|$ = $|B|$

 * Two sets A and B have the same cardinality if there exists a bijection (a.k.a., one-to-one correspondence) from A to B, that is, a function from A to B that is both injective and surjective. Such sets are said to be equipotent, equipollent, or equinumerous. This relationship can also be denoted A ≈ B or A ~ B.

 * For example, the set E = {0, 2, 4, 6, ...} of non-negative even numbers has the same cardinality as the set N = {0, 1, 2, 3, ...} of natural numbers, since the function f(n) = 2n is a bijection from N to E (see picture).

 * For finite sets A and B, if some bijection exists from A to B, then each injective or surjective function from A to B is a bijection. This is no longer true for infinite A and B. For example, the function g from N to E, defined by g(n) = 4n is injective, but not surjective, and h from N to E, defined by h(n) = n - (n mod 2) is surjective, but not injective. Neither g nor h can challenge $|E|$ = $|N|$, which was established by the existence of f.

Definition 2: $|A|$ ≤ $|B|$

 * A has cardinality less than or equal to the cardinality of B, if there exists an injective function from A into B.

Definition 3: $|A|$ < $|B|$

 * A has cardinality strictly less than the cardinality of B, if there is an injective function, but no bijective function, from A to B.

 * For example, the set N of all natural numbers has cardinality strictly less than its power set P(N), because g(n) = { n } is an injective function from N to P(N), and it can be shown that no function from N to P(N) can be bijective (see picture). By a similar argument, N has cardinality strictly less than the cardinality of the set R of all real numbers. For proofs, see Cantor's diagonal argument or Cantor's first uncountability proof.

If $|A|$ ≤ $|B|$ and $|B|$ ≤ $|A|$, then $|A|$ = $|B|$ (a fact known as Schröder–Bernstein theorem). The axiom of choice is equivalent to the statement that $|A|$ ≤ $|B|$ or $|B|$ ≤ $|A|$ for every A, B.

Cardinal numbers
In the above section, "cardinality" of a set was defined functionally. In other words, it was not defined as a specific object itself. However, such an object can be defined as follows.

The relation of having the same cardinality is called equinumerosity, and this is an equivalence relation on the class of all sets. The equivalence class of a set A under this relation, then, consists of all those sets which have the same cardinality as A. There are two ways to define the "cardinality of a set":

 * 1) The cardinality of a set A is defined as its equivalence class under equinumerosity.
 * 2) A representative set is designated for each equivalence class. The most common choice is the initial ordinal in that class. This is usually taken as the definition of cardinal number in axiomatic set theory.

Assuming the axiom of choice, the cardinalities of the infinite sets are denoted
 * $$\aleph_0 < \aleph_1 < \aleph_2 < \ldots . $$

For each ordinal $$\alpha$$, $$\aleph_{\alpha + 1}$$ is the least cardinal number greater than $$\aleph_\alpha$$.

The cardinality of the natural numbers is denoted aleph-null ($$\aleph_0$$), while the cardinality of the real numbers is denoted by "$$\mathfrak c$$" (a lowercase fraktur script "c"), and is also referred to as the cardinality of the continuum. Cantor showed, using the diagonal argument, that $${\mathfrak c} >\aleph_0$$. We can show that $$\mathfrak c = 2^{\aleph_0}$$, this also being the cardinality of the set of all subsets of the natural numbers.

The continuum hypothesis says that $$\aleph_1 = 2^{\aleph_0}$$, i.e. $$2^{\aleph_0}$$ is the smallest cardinal number bigger than $$\aleph_0$$, i.e. there is no set whose cardinality is strictly between that of the integers and that of the real numbers. The continuum hypothesis is independent of ZFC, a standard axiomatization of set theory; that is, it is impossible to prove the continuum hypothesis or its negation from ZFC—provided that ZFC is consistent. For more detail, see § Cardinality of the continuum below.

Finite, countable and uncountable sets
If the axiom of choice holds, the law of trichotomy holds for cardinality. Thus we can make the following definitions:

 * Any set X with cardinality less than that of the natural numbers, or | X | < | N |, is said to be a finite set.
 * Any set X that has the same cardinality as the set of the natural numbers, or | X | = | N | = $$\aleph_0$$, is said to be a countably infinite set.
 * Any set X with cardinality greater than that of the natural numbers, or | X | > | N |, for example | R | = $$\mathfrak c $$ > | N |, is said to be uncountable.

Infinite sets
Our intuition gained from finite sets breaks down when dealing with infinite sets. In the late 19th century Georg Cantor, Gottlob Frege, Richard Dedekind and others rejected the view that the whole cannot be the same size as the part. One example of this is Hilbert's paradox of the Grand Hotel. Indeed, Dedekind defined an infinite set as one that can be placed into a one-to-one correspondence with a strict subset (that is, having the same size in Cantor's sense); this notion of infinity is called Dedekind infinite. Cantor introduced the cardinal numbers, and showed—according to his bijection-based definition of size—that some infinite sets are greater than others. The smallest infinite cardinality is that of the natural numbers ($$\aleph_0$$).

Cardinality of the continuum
One of Cantor's most important results was that the cardinality of the continuum ($$\mathfrak{c}$$) is greater than that of the natural numbers ($$\aleph_0$$); that is, there are more real numbers R than natural numbers N. Namely, Cantor showed that $$\mathfrak{c} = 2^{\aleph_0} = \beth_1$$ (see Beth one) satisfies:
 * $$2^{\aleph_0} > \aleph_0$$
 * (see Cantor's diagonal argument or Cantor's first uncountability proof).

The continuum hypothesis states that there is no cardinal number between the cardinality of the reals and the cardinality of the natural numbers, that is,
 * $$2^{\aleph_0} = \aleph_1$$

However, this hypothesis can neither be proved nor disproved within the widely accepted ZFC axiomatic set theory, if ZFC is consistent.

Cardinal arithmetic can be used to show not only that the number of points in a real number line is equal to the number of points in any segment of that line, but that this is equal to the number of points on a plane and, indeed, in any finite-dimensional space. These results are highly counterintuitive, because they imply that there exist proper subsets and proper supersets of an infinite set S that have the same size as S, although S contains elements that do not belong to its subsets, and the supersets of S contain elements that are not included in it.

The first of these results is apparent by considering, for instance, the tangent function, which provides a one-to-one correspondence between the interval (−½π, ½π) and R (see also Hilbert's paradox of the Grand Hotel).

The second result was first demonstrated by Cantor in 1878, but it became more apparent in 1890, when Giuseppe Peano introduced the space-filling curves, curved lines that twist and turn enough to fill the whole of any square, or cube, or hypercube, or finite-dimensional space. These curves are not a direct proof that a line has the same number of points as a finite-dimensional space, but they can be used to obtain such a proof.

Cantor also showed that sets with cardinality strictly greater than $$\mathfrak c$$ exist (see his generalized diagonal argument and theorem). They include, for instance:

 * the set of all subsets of R, i.e., the power set of R, written P(R) or 2R
 * the set RR of all functions from R to R

Both have cardinality
 * $$2^\mathfrak {c} = \beth_2 > \mathfrak c $$
 * (see Beth two).

The cardinal equalities $$\mathfrak{c}^2 = \mathfrak{c},$$ $$\mathfrak c^{\aleph_0} = \mathfrak c,$$ and $$\mathfrak c ^{\mathfrak c} = 2^{\mathfrak c}$$ can be demonstrated using cardinal arithmetic:
 * $$\mathfrak{c}^2 = \left(2^{\aleph_0}\right)^2 = 2^{2\times{\aleph_0}} = 2^{\aleph_0} = \mathfrak{c},$$
 * $$\mathfrak c^{\aleph_0} = \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{{\aleph_0}\times{\aleph_0}} = 2^{\aleph_0} = \mathfrak{c},$$
 * $$ \mathfrak c ^{\mathfrak c} = \left(2^{\aleph_0}\right)^{\mathfrak c} = 2^{\mathfrak c\times\aleph_0} = 2^{\mathfrak c}.$$

Examples and properties

 * If X = {a, b, c} and Y = {apples, oranges, peaches}, where a, b, and c are distinct, then | X | = | Y | because { (a, apples), (b, oranges), (c, peaches)} is a bijection between the sets X and Y. The cardinality of each of X and Y is 3.
 * If | X | ≤ | Y |, then there exists Z such that | X | = | Z | and Z ⊆ Y.
 * If | X | ≤ | Y | and | Y | ≤ | X |, then | X | = | Y |. This holds even for infinite cardinals, and is known as Cantor–Bernstein–Schroeder theorem.
 * Sets with cardinality of the continuum include the set of all real numbers, the set of all irrational numbers and the interval $$[0, 1]$$.

Union and intersection
If A and B are disjoint sets, then
 * $$\left\vert A \cup B \right\vert = \left\vert A \right\vert + \left\vert B \right\vert.$$

From this, one can show that in general, the cardinalities of unions and intersections are related by the following equation:
 * $$ \left\vert C \cup D \right\vert + \left\vert C \cap D \right\vert = \left\vert C \right\vert + \left\vert D \right\vert.$$

Definition of cardinality in class theory (NBG or MK)
Here $$V$$ denote a class of all sets, and $$\mbox{Ord}$$ denotes the class of all ordinal numbers.
 * $$|A|:=\mbox{Ord}\cap\bigcap \{\alpha\in\mbox{Ord}|\exists (f:A\to\alpha):(f\mbox{ injective})\}$$

We use the intersection of a class which is defined by $$(x\in\bigcap Q)\iff(\forall q\in Q:x\in q)$$, therefore $$\bigcap\emptyset = V$$. In this case
 * $$(x\mapsto|x|):V\to\mbox{Ord}$$.

This definition allows also obtain a cardinality of any proper class $$P$$, in particular
 * $$|P|=\mbox{Ord}$$

This definition is natural since it agrees with the axiom of limitation of size which implies bijection between $$V$$ and any proper class.

title: Cardinality


text:
Talk:Cardinal

Old stuff
How is the Cessna a sub-heading of the bird? SkyDot 19:13, 30 October 2006 (UTC)

 * The consistency of the existence of strongly inaccessible cardinals can not be proved under ZFC.

 * Is that correct? I thought the existence of strongly inaccessible cardinals can (provably) not be proved, while it is open whether their non-existence can be proved. In other words, "the consistency of the existence of strongly inaccessible cardinals" has not yet been proved while the consistency of their non-existence has been proved.
 * Yes, your version is correct. That existence of inacc. cardinals cannot be proved is a direct consequence of the 2nd incompleteness theorem (one observes that the set of all sets with rank less than that of an inacc. cardinal form a model of ZFC). Incidentally, wouldn't it be better to have the main article at Cardinal number? "Cardinal" has a pretty well-defined religious meaning as well, and "cardinal number" is not outdated.

 * not to mention the bird. And the baseball team.--MichaelTinkler
 * Ok, I'm convinced. Cardinal number it is. --AxelBoldt
 * As this refers to a subdivision/less obvious definition of the term, could it be emphasised that it is the number that is being referred to, not a religious person being away from their phone (g). Jackiespeel 18:08, 9 January 2006 (UTC)

Deleting Mike Cline Contributions
I am deleting or reverting any contributions I have previously made to this article for the following reason. I work for a company that practices and teaches Strategic Planning methodologies thus making my contribution to any article related to Strategy topics a conflict of interest an in violation of Wikipedia Conflict of Interest guidelines WP:COI --Mike Cline 13:25, 4 February 2007 (UTC)

Cardinal is also a popular swiss beer brand, should I add it?

Revert
Anon. IP removed a link with no explanation. I reverted. -- SECisek 01:25, 4 October 2007 (UTC)

Requested move
Cardinal → Cardinal (disambiguation) — We should really give the main article to what is now Cardinal (Catholicism). A look at "what links here" shows this is overwhemingly the main use involved. The mathmatical use is at Cardinal number, & if there were a predominant sports team using the term they could have "Cardinals" (I don't have a view on that). Few people can really link to "Cardinal" when they mean "cardinal bird", and the other uses are minor. This page should herefore become "Cardinal (disambiguation)" —Johnbod 20:05, 2 December 2007 (UTC)

Please centralize voting and discussion at the survey at Talk:Cardinal_%28Catholicism%29 Johnbod 23:37, 2 December 2007 (UTC)

 * A move proposal for this page was listed at Requested moves, but there was no consensus found for the move. Dekimasu よ! 00:34, 7 December 2007 (UTC)

Passenger Train Entry
The passenger train entry reads “Cardinal (passenger train), an Amtrak route connecting Chicago with New York via Cincinnati and Washington” -- it mentions Cincinnati and Washington to avoid confusion with Amtrak’s other Chicago-New York routes: For reference purposes, note that the Cardinal service is 28h 50m. —Preceding unsigned comment added by 69.205.54.39 (talk) 13:15, 28 May 2008 (UTC)
 * Lake Shore Limited (18h 45m)
 * Pennsylvanian and Capitol Limited (19h)
 * Regional Service and Capitol Limited (21h)

Move discussion in progress
There is a move discussion in progress on Talk:Cardinal (Catholic Church) which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 19:46, 2 February 2017 (UTC)

title: Talk:Cardinal