Editing Cantor set (section)

== Properties ==

=== 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 set|uncountable]]. To see this, we show that there is a [[function (mathematics)|function]] ''f'' from the Cantor set <math>\mathcal{C}</math> to the closed interval <math>[0, 1]</math> that is [[Surjective function|surjective]] (i.e. ''f'' maps from <math>\mathcal{C}</math> onto <math>[0, 1]</math>) so that the cardinality of <math>\mathcal{C}</math> is no less than that of <math>[0, 1]</math>.  Since <math>\mathcal{C}</math> is a [[subset]] of <math>[0, 1]</math>, 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 <math>[0, 1]</math> interval in terms of base 3 (or [[ternary numeral system|ternary]]) notation. Recall that the proper ternary fractions, more precisely: the elements of <math>\bigl(\Z \setminus \{0\}\bigr) \cdot 3^{-\N_0}</math>, admit more than one representation in this notation, as for example {{sfrac|1|3}}, that can be written as 0.1<sub>3</sub> = {{overline|0.1|0}}<sub>3</sub>, but also as 0.0222...<sub>3</sub> = {{overline|0.0|2}}<sub>3</sub>, and {{sfrac|2|3}}, that can be written as 0.2<sub>3</sub> = {{overline|0.2|0}}<sub>3</sub> but also as 0.1222...<sub>3</sub> = {{overline|0.1|2}}<sub>3</sub>.<ref>This alternative recurring representation of a number with a terminating numeral occurs in any [[Numeral system#Positional systems in detail|positional system]] with [[Absolute value (algebra)#Types of absolute value|Archimedean absolute value]].</ref>
When we remove the middle third, this contains the numbers with ternary numerals of the form 0.1xxxxx...<sub>3</sub> where xxxxx...<sub>3</sub> is strictly between 00000...<sub>3</sub> and 22222...<sub>3</sub>. So the numbers remaining after the first step consist of
* Numbers of the form 0.0xxxxx...<sub>3</sub> (including 0.022222...<sub>3</sub> = 1/3)
* Numbers of the form 0.2xxxxx...<sub>3</sub> (including 0.222222...<sub>3</sub> = 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...<sub>3</sub> and 0.21xxxx...<sub>3</sub>, 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 ''n''th 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, {{sfrac|1|3}} = 0.1<sub>3</sub> and {{sfrac|7|9}} = 0.21<sub>3</sub> are in the Cantor set, as they have ternary numerals consisting entirely of 0s and 2s: 1 = 0.222...<sub>3</sub> = {{overline|0.|2}}<sub>3</sub>, {{sfrac|1|3}} = 0.0222...<sub>3</sub> = {{overline|0.0|2}}<sub>3</sub> and {{sfrac|7|9}} = 0.20222...<sub>3</sub> = {{overline|0.20|2}}<sub>3</sub>.
All the latter numbers are "endpoints", and these examples are right [[limit point]]s of <math>\mathcal{C}</math>. The same is true for the left limit points of <math>\mathcal{C}</math>, e.g. {{sfrac|2|3}} = 0.1222...<sub>3</sub> = {{overline|0.1|2}}<sub>3</sub> = {{overline|0.2|0}}<sub>3</sub> and {{sfrac|8|9}} = 0.21222...<sub>3</sub> = {{overline|0.21|2}}<sub>3</sub> = {{overline|0.22|0}}<sub>3</sub>. All these endpoints are ''proper ternary'' fractions (elements of <math>\Z \cdot 3^{-\N_0}</math>) of the form {{sfrac|''p''|''q''}}, where denominator ''q'' is a [[power of 3]] when the fraction is in its [[Irreducible fraction|irreducible]] form.<ref name="College"/> 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 <math>\mathcal{C}</math> 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 <math>\mathcal{C}</math> if it again its ternary expansion contains no 1's and "ends" in infinitely many recurring 2s.

This set of endpoints is [[dense set|dense]] in <math>\mathcal{C}</math> (but not dense in <math>[0, 1]</math>) and makes up a [[countably infinite]] set. The numbers in <math>\mathcal{C}</math> 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 <math>\mathcal{C}</math> to <math>[0, 1]</math> 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 numeral system#Representing real numbers|binary]] representation of a real number.  In a formula,

:<math>f \bigg( \sum_{k\in \N} a_k 3^{-k} \bigg) = \sum_{k\in \N} \frac{a_k}{2} 2^{-k}</math> &nbsp; where &nbsp; <math>\forall k\in \N : a_k \in \{0,2\} .</math>

For any number ''y'' in <math>[0, 1]</math>, its binary representation can be translated into a ternary representation of a number ''x'' in <math>\mathcal{C}</math> by replacing all the 1s by 2s.  With this, ''f''(''x'') = ''y'' so that ''y'' is in the [[Range of a function|range]] of ''f''.  For instance if ''y'' = {{sfrac|3|5}} = 0.100110011001...<sub>2</sub> = {{overline|0.|1001}}, we write ''x'' = {{overline|0.|2002}} = 0.200220022002...<sub>3</sub> = {{sfrac|7|10}}.  Consequently, ''f'' is surjective. However, ''f'' is ''not'' [[injective function|injective]] — the values for which ''f''(''x'') coincides are those at opposing ends of one of the ''middle thirds'' removed.  For instance, take
:{{sfrac|1|3}} = {{overline|0.0|2}}<sub>3</sub> (which is a right limit point of <math>\mathcal{C}</math> and a left limit point of the middle third [{{sfrac|1|3}}, {{sfrac|2|3}}])&nbsp; and
:{{sfrac|2|3}} = {{overline|0.2|0}}<sub>3</sub> (which is a left limit point of <math>\mathcal{C}</math> and a right limit point of the middle third [{{sfrac|1|3}}, {{sfrac|2|3}}])
so
:<math>\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}</math>
Thus there are as many points in the Cantor set as there are in the interval <math>[0, 1]</math> (which has the [[Uncountable set|uncountable]] cardinality {{nowrap|<math>\mathfrak{c} = 2^{\aleph_0}</math>).}} 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 {{sfrac|1|4}}, which can be written as 0.020202...<sub>3</sub> = {{overline|0.|02}} in ternary notation.  In fact, given any <math>a\in[-1,1]</math>, there exist <math>x,y\in\mathcal{C}</math> such that <math>a = y-x</math>.  This was first demonstrated by [[Hugo Steinhaus|Steinhaus]] in 1917, who [[mathematical proof|proved]], via a geometric argument, the equivalent assertion that <math>\{(x,y)\in\mathbb{R}^2 \mid y=x+a\} \; \cap \; (\mathcal{C}\times\mathcal{C}) \neq\emptyset</math> for every <math>a\in[-1,1]</math>.<ref>{{Cite book|title=Real Analysis|url=https://archive.org/details/realanalysis00caro_315|url-access=limited|last=Carothers|first=N. L.|publisher=Cambridge University Press|year=2000|isbn=978-0-521-69624-1|location=Cambridge|pages=[https://archive.org/details/realanalysis00caro_315/page/n41 31]–32}}</ref> Since this construction provides an injection from <math>[-1,1]</math> to <math>\mathcal{C}\times\mathcal{C}</math>, we have <math>|\mathcal{C}\times\mathcal{C}|\geq|[-1,1]|=\mathfrak{c}</math> as an immediate [[corollary]].  Assuming that <math>|A\times A|=|A|</math> for any infinite set <math>A</math> (a statement shown to be equivalent to the [[axiom of choice]] [[Tarski's theorem about choice|by Tarski]]), this provides another demonstration that <math>|\mathcal{C}|=\mathfrak{c}</math>.

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 number]]s have the same property, but the Cantor set has the additional property of being [[Closed set|closed]], so it is not even [[Dense set|dense]] in any interval, unlike the irrational numbers which are dense in every interval.

It has been [[conjecture]]d that all [[algebraic number|algebraic]] irrational numbers are [[normal number|normal]].  Since members of the Cantor set are not normal in base 3, this would imply that all members of the Cantor set are either rational or [[transcendental number|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, <math>T_L(x)=x/3</math> and <math>T_R(x)=(2+x)/3</math>, which leave the Cantor set invariant up to [[homeomorphism]]: <math>T_L(\mathcal{C})\cong T_R(\mathcal{C})\cong \mathcal{C}=T_L(\mathcal{C})\cup T_R(\mathcal{C}).</math>

Repeated [[iterated function|iteration]] of <math>T_L</math> and <math>T_R</math> 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 <math>\{T_L, T_R\}</math> together with [[function composition]] forms a [[monoid]], the [[dyadic monoid]].

The [[automorphism]]s 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 <math>x</math> and <math>y</math> in the Cantor set <math>\mathcal{C}</math>, there exists a homeomorphism <math>h:\mathcal{C}\to \mathcal{C}</math> with <math>h(x)=y</math>. An explicit construction of <math>h</math> can be described more easily if we see the Cantor set [[#Topological and analytical properties|as a product space]] of  countably many copies of the discrete space <math>\{0,1\}</math>. Then the map <math>h:\{0,1\}^\N\to\{0,1\}^\N </math> defined by <math>h_n(u):=u_n+x_n+y_n \mod 2</math> is an [[involution (mathematics)|involutive]] homeomorphism exchanging  <math>x</math> and <math>y</math>.

=== 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 (set theory)|complement]] of a [[union (set theory)|union]] of [[open set]]s, it itself is a [[closed set|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 space|compact]].

For any point in the Cantor set and any arbitrarily small [[neighborhood (mathematics)|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 set|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 [[Homeomorphism|homeomorphic]] to the [[product topology|product]] of countably many copies of the space <math>\{0, 1\}</math>, where each copy carries the [[discrete topology]]. This is the space of all [[sequence]]s in two digits 
:<math>2^\mathbb{N} = \{(x_n) \mid x_n \in \{0,1\} \text{ for } n \in \mathbb{N}\},</math>

which can also be identified with the set of [[p-adic integer|2-adic integers]]. The [[basis (topology)|basis]] for the open sets of the [[product topology]] are [[cylinder set]]s; 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 [[Homeomorphism|homeomorphic]] to the [[p-adic integer|''p''-adic integers]], and, if one point is removed from it, to the [[p-adic number|''p''-adic numbers]].

The Cantor set is a subset of the reals, which are a [[metric space]] with respect to the [[absolute difference|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|''p''-adic metric]] on <math>2^\mathbb{N}</math>: given two sequences <math>(x_n),(y_n)\in 2^\mathbb{N}</math>, the distance between them is <math>d((x_n),(y_n)) = 2^{-k}</math>, where <math>k</math> is the smallest index such that <math>x_k \ne y_k</math>; 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 [[topological space|topology]] on the Cantor set.

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

The Cantor set is sometimes regarded as "universal" in the [[category (mathematics)|category]] of [[compact space|compact]] metric spaces, since any compact metric space is a [[continuous function (topology)|continuous]] [[image (mathematics)|image]] of the Cantor set; however this construction is not unique and so the Cantor set is not [[universal property|universal]] in the precise [[category theory|categorical]] sense. The "universal" property has important applications in [[functional analysis]], where it is sometimes known as the ''representation theorem for compact metric spaces''.<ref>{{cite book | first=Stephen | last=Willard | title=General Topology | publisher=Addison-Wesley | date=1968 | asin=B0000EG7Q0}}</ref>

For any [[integer]] ''q'' ≥ 2, the topology on the [[group (mathematics)|group]] G = '''Z'''<sub>''q''</sub><sup>ω</sup> (the countable direct sum) is discrete.<!-- I don't know how the Z_q^w should be LaTeX-ified. --> Although the [[Pontrjagin dual]] Γ is also '''Z'''<sub>''q''</sub><sup>ω</sup>, the topology of Γ is compact. One can see that Γ is totally disconnected and perfect - thus it is [[Homeomorphism|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.<ref>{{cite web | url=http://theoremoftheweek.wordpress.com/2010/09/30/theorem-36-the-cantor-set-is-an-uncountable-set-with-zero-measure/ | title=Theorem 36: the Cantor set is an uncountable set with zero measure | first=Laura | last=Irvine | website=Theorem of the week | access-date=2012-09-27 | archive-url=https://web.archive.org/web/20160315212203/https://theoremoftheweek.wordpress.com/2010/09/30/theorem-36-the-cantor-set-is-an-uncountable-set-with-zero-measure/ | archive-date=2016-03-15 | url-status=dead }}</ref> In contrast, the set has a [[Hausdorff measure]] of <math>1</math> in its dimension of <math>\log_3(2)</math>.<ref>
{{cite book |last=Falconer |first=K. J. |date=July 24, 1986 |title=The Geometry of Fractal Sets |url=http://mate.dm.uba.ar/~umolter/materias/referencias/1.pdf |pages=14–15 |publisher=Cambridge University Press |isbn=9780521337052}}
</ref>

===Cantor numbers===
If we define a Cantor number as a member of the Cantor set, then<ref>{{cite book | title=Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise  | first=Manfred | last=Schroeder | publisher=Dover | date=1991 | pages=164–165 | isbn=0486472043}}</ref>
# Every real number in <math>[0, 2]</math> is the sum of two Cantor numbers.
# 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 <math>[0, 1]</math> (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 <math>\mathbb{Q}\cap[0,1]</math>, the Cantor set <math>\mathcal{C}</math> is "small" in the sense that it is a null set (a set of measure zero) and it is a meagre subset of <math>[0, 1]</math>.  However, unlike <math>\mathbb{Q}\cap[0,1]</math>, which is countable and has a "small" cardinality, <math>\aleph_0</math>, the cardinality of <math>\mathcal{C}</math> is the same as that of <math>[0, 1]</math>, the continuum <math>\mathfrak{c}</math>, and is "large" in the sense of cardinality.  In fact, it is also possible to construct a subset of <math>[0, 1]</math> that is meagre but of positive measure and a subset that is non-meagre but of measure zero:<ref>{{Cite book|title=Counterexamples in analysis|last=Gelbaum, Bernard R.|date=1964|publisher=Holden-Day|others=Olmsted, John M. H. (John Meigs Hubbell), 1911-1997|isbn=0486428753|location=San Francisco|oclc=527671}}</ref>  By taking the countable union of "fat" Cantor sets <math>\mathcal{C}^{(n)}</math> of measure <math>\lambda = (n-1)/n</math> (see Smith–Volterra–Cantor set below for the construction), we obtain a set <math display="inline">\mathcal{A} := \bigcup_{n=1}^{\infty}\mathcal{C}^{(n)}</math>which has a positive measure (equal to 1) but is meagre in [0,1], since each <math>\mathcal{C}^{(n)}</math> is nowhere dense.  Then consider the set <math display="inline">\mathcal{A}^{\mathrm{c}} = [0,1] \setminus\bigcup_{n=1}^\infty \mathcal{C}^{(n)}</math>.  Since <math>\mathcal{A}\cup\mathcal{A}^{\mathrm{c}} = [0,1]</math>, <math>\mathcal{A}^{\mathrm{c}}</math> cannot be meagre, but since <math>\mu(\mathcal{A})=1</math>, <math>\mathcal{A}^{\mathrm{c}}</math> must have measure zero.