Cantor function: Difference between revisions

Revision as of 23:14, 20 September 2020

Latest revision as of 20:21, 20 August 2025

(48 intermediate revisions by 32 users not shown)

Line 1:

{{Use American English|date = March 2019}}

{{Short description|Continuous function that is not absolutely continuous}}

[[File:CantorEscalier-2.svg|thumb|right|400px| The graph of the Cantor function on the [[unit interval]] ]]

In [[mathematics]], the '''Cantor function''' is an example of a [[function (mathematics)|function]] that is [[continuous function|continuous]], but not [[absolute continuity|absolutely continuous]]. It is a notorious [[Pathological_(mathematics)#Pathological_example|counterexample]] in analysis, because it challenges naive intuitions about continuity, [[derivative]], and [[Measure (mathematics)|measure]]. ThoughAlthough it is continuous everywhere, and has zero derivative almost everywhere, its value still goes from 0 to 1 as its argument reachesgoes from 0 to 1. Thus, in one sensewhile the function seems very much like a constant one whichthat cannot grow, and in another, it does indeed [[Monotonic function|monotonically]] grow, by construction.

It is also referred to ascalled the '''Cantor ternary function''', the '''Lebesgue function''',<ref>{{harvnb|Vestrup|2003|loc=Section 4.6.}}</ref> '''Lebesgue's singular function''', the '''Cantor–Vitali function''', the '''Devil's staircase''',<ref>{{harvnb|Thomson|Bruckner|Bruckner|2008|p=252}}.</ref> the '''Cantor staircase function''',<ref>{{Cite web|url=http://mathworld.wolfram.com/CantorStaircaseFunction.html|title=Cantor Staircase Function}}</ref> and the '''Cantor–Lebesgue function'''.<ref>{{harvnb|Bass|2013|p=28}}.</ref> {{harvs|txt|first=Georg |last=Cantor|authorlink=Georg Cantor|year=1884}} introduced the Cantor function and mentioned that Scheeffer pointed out that it was a [[counterexample]] to an extension of the [[fundamental theorem of calculus]] claimed by [[Carl Gustav Axel Harnack|Harnack]]. The Cantor function was discussed and popularized by {{harvtxt|Scheeffer|1884}}, {{harvtxt|Lebesgue|1904}}, and {{harvtxt|Vitali|1905}}.

==Definition==

[[File:Cantor function.gif|300pxthumb|rightupright=1.35|Iterated construction of the Cantor function]]

See figure. To formally define the Cantor function ''<math>c'' : [0,1] → \to[0,1]</math>, let ''<math>x''</math> be any number in <math>[0,1]</math> and obtain ''<math>c''(''x'')</math> by the following steps:

#Express <math>x</math> in base 3, using digits 0, 1, 2.

See figure. To formally define the Cantor function ''c'' : [0,1] → [0,1], let ''x'' be in [0,1] and obtain ''c''(''x'') by the following steps:

#If ''the base-3 representation of <math>x''</math> contains a 1, replace every digit strictly after the first 1 bywith 0.

#Express ''x'' in base 3.

#If ''x'' contains a 1, replace every digit strictly after the first 1 by 0.

#Replace any remaining 2s with 1s.

#Interpret the result as a binary number. The result is ''<math>c''(''x'')</math>.

For example:

* 1<math>\tfrac14</4math> ishas the ternary representation 0.02020202... in base 3. There are no 1s so the next stage is still 0.02020202... This is rewritten as 0.01010101... WhenThis readis inthe basebinary 2,representation thisof corresponds to 1<math>\tfrac13</3math>, so ''<math>c''(1/4\tfrac14) = 1\tfrac13</3math>.

* 1<math>\tfrac15</5math> ishas the ternary representation 0.01210121... in base 3. The digits after the first 1 are replaced by 0s to produce 0.01000000... This is not rewritten since thereit arehas no 2s. WhenThis readis inthe basebinary 2,representation thisof corresponds to 1<math>\tfrac14</4math>, so ''<math>c''(1/5\tfrac15) = 1\tfrac14</4math>.

* <math>\tfrac{200/}{243}</math> ishas the ternary representation 0.21102 (or 0.211012222...) in base 3. The digits after the first 1 are replaced by 0s to produce 0.21. This is rewritten as 0.11. WhenThis readis inthe basebinary 2,representation this corresponds toof 3<math>\tfrac34</4math>, so ''<math>c''(\tfrac{200/}{243}) = 3\tfrac34</4math>.

Equivalently, if <math>\mathcal{C}</math> is the [[Cantor set]] on [0,1], then the Cantor function ''c''<nowikimath> c: [0,1] → \to[0,1]</math> can be defined as</nowiki>

:<math display="block">c(x) =\begin{cases}

\displaystyle \sum_{n=1}^\infty \frac{a_n}{2^n}, & x = \sum_{n=1}^\infty

& \displaystyle \text{if } x = \sum_{n=1}^\infty

\frac{2a_n}{3^n}\in\mathcal{C}\ \mathrm{for}\ a_n\in\{0,1\};

\\ \sup_frac{y\leq x,\, y2a_n}{3^n}\in\mathcal{C}} c(y), & x\in [0,1]\setminus \mathcaltext{Cfor}.\\ a_n\in\end{cases0,1\};

\\

\displaystyle \sup_{y\leq x,\, y\in\mathcal{C}} c(y),

& \displaystyle \text{if } x\in [0,1] \setminus \mathcal{C}.

\end{cases}

</math>

This formula is well-defined, since every member of the Cantor set has a ''unique'' base 3 representation that only contains the digits 0 or 2. (For some members of <math>\mathcal{C}</math>, the ternary expansion is repeating with trailing 2's and there is an alternative non-repeating expansion ending in 1. For example, 1<math>\tfrac13</3math> = 0.1₃ = 0.02222...₃ is a member of the Cantor set). Since ''<math>c''(0) = 0</math> and ''<math>c''(1) = 1</math>, and ''<math>c''</math> is monotonic on <math>\mathcal{C}</math>, it is clear that <math>0\le ≤ ''c''(''x'') ≤\le 1</math> also holds for all <math>x\in[0,1]\setminussmallsetminus\mathcal{C}</math>.

==Properties==

The Cantor function challenges naive intuitions about [[continuous function|continuity]] and [[measure (mathematics)|measure]]; though it is continuous everywhere and has zero derivative [[almost everywhere]], <math display="inline">c(x)</math> goes from 0 to 1 as <math display="inline>x</math> goes from 0 to 1, and takes on every value in between. The Cantor function is the most frequently cited example of a real function that is [[uniformly continuous]] (precisely, it is [[Hölder continuous]] of exponent <math>\alpha ''α''&nbsp;=&nbsp;log&nbsp; \log_3(2)</log&nbsp;3math>) but not [[absolute continuity|absolutely continuous]]. It is constant on intervals of the form (0.''x''₁''x''₂''x''₃...''x''_n022222..., 0.''x''₁''x''₂''x''₃...''x''_n200000...), and every point not in the Cantor set is in one of these intervals, so its derivative is 0 outside of the Cantor set. On the other hand, it has no [[derivative]] at any point in an [[uncountable]] subset of the [[Cantor set]] containing the interval endpoints described above.

The Cantor function can also be seen as the [[cumulative distribution function|cumulative probability distribution function]] of the 1/2-1/2 [[Bernoulli measure]] ''μ'' supported on the Cantor set: <math display="inline">c(x)=\mu([0,x])</math>. This probability distribution, called the [[Cantor distribution]], has no discrete part. That is, the corresponding measure is [[Atom (measure theory)|atomless]]. This is why there are no jump discontinuities in the function; any such jump would correspond to an atom in the measure.

Line 40 ⟶ 43:

The Cantor function is the standard example of a [[singular function]].

The Cantor function is also a standard example of a function with [[bounded variation]] but, as mentioned above, is not absolutely continuous. However, every absolutely continuous function is continuous with bounded variation.

The Cantor function is non-decreasing, and so in particular its graph defines a [[rectifiable curve]]. {{harvtxt|Scheeffer|1884}} showed that the arc length of its graph is 2.

The Cantor function is non-decreasing, and so in particular its graph defines a [[rectifiable curve]]. {{harvtxt|Scheeffer|1884}} showed that the arc length of its graph is 2. Note that the graph of any nondecreasing function such that <math>f(0)=0</math> and <math>f(1)=1</math> has length not greater than 2. In this sense, the Cantor function is extremal.

===Lack of absolute continuity===

Because theThe [[Lebesgue measure]] of the [[Uncountable set|uncountably infinite]] [[Cantor set]] is 0. Therefore, for any positive ''ε''&nbsp;<&nbsp;1 and any ''δ'' > 0, there exists a finite sequence of [[pairwise disjoint]] sub-intervals with total length <&nbsp;''δ'' over which the Cantor function cumulatively rises more than&nbsp;''ε''.

In fact, for every ''δ''&nbsp;>&nbsp;0 there are finitely many pairwise disjoint intervals (''x<SUB>k</SUB>'',''y<SUB>k</SUB>'') (1&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;''M'') with <math>\sum\limits_{k=1}^M (y_k-x_k)<\delta</math> and <math>\sum\limits_{k=1}^M (c(y_k)-c(x_k))=1</math>.

Line 52 ⟶ 57:

[[File:Cantor function sequence.png|250px|right]]

Below we define a sequence {''f''<submath>''n''(f_n)_n</submath>} of functions on the unit interval that converges to the Cantor function.

Let ''f''<sub>0</submath>f_0(''x'') = ''x''</math>.

Then, for every integer <math>n \geq 0</math>, the next function <math>f_{n + 1}(x)</math> will be defined in terms of <math>f_n(x)</math> as follows:<math display="block">f_{n + 1}(x) = \begin{cases} \displaystyle \frac{1}{2} f_n(3 x) &\text{if } 0 \leq x \leq \frac{1}{3} \\ \displaystyle \frac{1}{2} &\text{if } \frac{1}{3} \leq x \leq \frac{2}{3} \\ \displaystyle \frac{1}{2} + \frac{1}{2} f_n(3 x - 2) &\text{if } \frac{2}{3} \leq x \leq 1 \end{cases}</math>The three definitions are compatible at the end-points <math>\tfrac{1}{3}</math> and <math>\tfrac{2}{3}</math>, because <math>f_n(0) = 0</math> and <math>f_n(1) = 1</math> for every <math>n</math>, by induction. One may check that <math>(f_n)_n</math> converges pointwise to the Cantor function defined above. Furthermore, the convergence is uniform. Indeed, separating into three cases, according to the definition of <math>f_{n + 1}</math>, one sees that

Then, for every integer {{nowrap|''n'' &ge; 0}}, the next function ''f''_''n''+1(''x'') will be defined in terms of ''f''_''n''(''x'') as follows:

Let ''f''_''n''+1(''x'')&nbsp;= {{nowrap|1/2 &times; ''f''_''n''(3''x'')}},&nbsp; when {{nowrap|0 ≤ ''x'' ≤ 1/3&thinsp;}};

Let ''f''_''n''+1(''x'')&nbsp;= 1/2,&nbsp; when {{nowrap|1/3 ≤ ''x'' ≤ 2/3&thinsp;}};

Let ''f''_''n''+1(''x'')&nbsp;= {{nowrap|1/2 + 1/2 &times; ''f''_''n''(3&thinsp;''x'' &minus; 2)}},&nbsp; when {{nowrap|2/3 ≤ ''x'' ≤ 1}}.

The three definitions are compatible at the end-points 1/3 and 2/3, because ''f''_''n''(0)&nbsp;= 0 and ''f''_''n''(1)&nbsp;= 1 for every&nbsp;''n'', by induction. One may check that ''f''_''n'' converges pointwise to the Cantor function defined above. Furthermore, the convergence is uniform. Indeed, separating into three cases, according to the definition of ''f''_''n''+1, one sees that

:<math>\max_{x \in [0, 1]} |f_{n+1}(x) - f_n(x)| \le \frac 1 2 \, \max_{x \in [0, 1]} |f_{n}(x) - f_{n-1}(x)|, \quad n \ge 1.</math>

If ''<math>f''</math> denotes the limit function, it follows that, for every ''<math>n''&nbsp;&ge;&nbsp; \geq 0</math>,

:<math>\max_{x \in [0, 1]} |f(x) - f_n(x)| \le 2^{-n+1} \, \max_{x \in [0, 1]} |f_1(x) - f_0(x)|.</math>

Also the choice of starting function does not really matter, provided ''f''₀(0)&nbsp;= 0, ''f''₀(1)&nbsp;= 1 and ''f''₀ is [[Bounded function|bounded]]{{citation needed|date=September 2014}}.

=== Fractal volume ===

The Cantor function is closely related to the [[Cantor set]]. The Cantor set ''C'' can be defined as the set of those numbers in the interval [0,&nbsp;1] that do not contain the digit 1 in their [[base (exponentiation)radix|base]]-3 (triadic) expansion]], except if the 1 is followed by zeros only (in which case the tail 1000<math>\ldots</math> can be replaced by 0222<math>\ldots</math> to get rid of any 1). It turns out that the Cantor set is a [[fractal]] with (uncountably) infinitely many points (zero-dimensional volume), but zero length (one-dimensional volume). Only the ''D''-dimensional volume <math> H_D </math> (in the sense of a [[Hausdorff dimension|Hausdorff-measure]]) takes a finite value, where <math> D = \loglog_3(2)/\log(3) </math> is the fractal dimension of ''C''. We may define the Cantor function alternatively as the ''D''-dimensional volume of sections of the Cantor set

: <math>

Line 82 ⟶ 77:

==Self-similarity==

The Cantor function possespossesses several [[symmetry|symmetries]]. For <math>0\le x\le 1</math>, there is a reflection symmetry

:<math>c(x)=1-c(1-x)</math>

and a pair of magnifications, one on the left and one on the right:

Line 88 ⟶ 83:

and

:<math>c\left(\frac{x+2}{3}\right) = \frac{1+c(x)}{2}</math>

The magnifications can be cascaded; they generate the [[dyadic monoid]]. This is exhibited by defining several helper functions. Define the reflection as

:<math>r(x)=1-x</math>

The first self-symmetry can be expressed as

:<math>r\circ c = c\circ r</math>

where the symbol <math>\circ</math> denotes function composition. That is, <math>(r\circ c)(x)=r(c(x))=1-c(x)</math> and likewise for the other cases. For the left and right magnifications, write the left-mappings

:<math>L_D(x)= \frac{x}{2}</math> and <math>L_C(x)= \frac{x}{3}</math>

Then the Cantor function obeys

Line 108 ⟶ 103:

Arbitrary finite-length strings in the letters L and R correspond to the [[dyadic rationals]], in that every dyadic rational can be written as both <math>y=n/2^m</math> for integer ''n'' and ''m'' and as finite length of bits <math>y=0.b_1b_2b_3\cdots b_m</math> with <math>b_k\in \{0,1\}.</math> Thus, every dyadic rational is in one-to-one correspondence with some self-symmetry of the Cantor function.

Some notational rearrangements can make the above slightly easier to express. Let <math>g_0</math> and <math>g_1</math> stand for L and R. Function composition extends this to a [[monoid]], in that one can write <math>g_{010}=g_0g_1g_0</math> and generally, <math>g_Ag_B=g_{AB}</math> for some binary strings of digits ''A'', ''B'', where ''AB'' is just the ordinary [[concatenation]] of such strings. The dyadic monoid ''M'' is then the monoid of all such finite-length left-right moves. Writing <math>\gamma\in M</math> as a general element of the monoid, there is a corresponding self-symmetry of the Cantor function:

:<math>\gamma_D\circ c= c\circ \gamma_C</math>

The dyadic monoid itself has several interesting properties. It can be viewed as a finite number of left-right moves down an infinite [[binary tree]]; the infinitely distant "leaves" on the tree correspond to the points on the Cantor set, and so, the monoid also represents the self-symmetries of the Cantor set. In fact, a large class of commonly occurring fractals are described by the dyadic monoid; additonaladditional examples can be found in the article on [[de Rham curve]]s. Other fractals possessing self-similarity are described with other kinds of monoids. The dyadic monoid is itself a sub-monoid of the [[modular group]] <math>SL(2,\mathbb{Z}).</math>

Note that the Cantor function bears more than a passing resemblance to [[Minkowski's question-mark function]]. In particular, it obeys analogous symmetry relations, with only a slightly altered form.

== Generalizations ==

Line 124 ⟶ 121:

For ''z''&nbsp;=&nbsp;1/3, the inverse of the function ''x'' = 2&nbsp;''C''_1/3(''y'') is the Cantor function. That is, ''y''&nbsp;=&nbsp;''y''(''x'') is the Cantor function. In general, for any ''z''&nbsp;&lt;&nbsp;1/2, ''C''_''z''(''y'') looks like the Cantor function turned on its side, with the width of the steps getting wider as ''z'' approaches zero.

As mentioned above, the Cantor function is also the cumulative distribution function of a measure on the Cantor set. Different Cantor functions, or Devil's Staircases, can be obtained by considering different atom-less probability measures supported on the Cantor set or other fractals. While the Cantor function has derivative 0 almost everywhere, current research focussesfocuses on the question of the size of the set of points where the upper right derivative is distinct from the lower right derivative, causing the derivative to not exist. This analysis of differentiability is usually given in terms of [[fractal dimension]], with the Hausdorff dimension the most popular choice. This line of research was started in the 1990s by Darst,<ref>{{Cite journal|title = The Hausdorff Dimension of the Nondifferentiability Set of the Cantor Function is [ ln(2)/ln(3) ]2|jstor = 2159830|journal = [[Proceedings of the American Mathematical Society]]|date = 1993-09-01|pages = 105–108|volume = 119|issue = 1|doi = 10.2307/2159830|first = Richard|last = Darst}}</ref> who showed that the Hausdorff dimension of the set of non-differentiability of the Cantor function is the square of the dimension of the Cantor set, <math>(\log2/\log3log_3(2))^2</math>. Subsequently [[Kenneth Falconer (mathematician)|Falconer]]<ref>{{Cite journal|title = One-sided multifractal analysis and points of non-differentiability of devil's staircases|journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]| date = 2004-01-01|issn = 1469-8064|pages = 167–174|volume = 136|issue = 1|doi = 10.1017/S0305004103006960|first = Kenneth J.|last = Falconer|authorlink=Kenneth Falconer (mathematician)|bibcode = 2004MPCPS.136..167F|s2cid = 122381614}}</ref> showed that this squaring relationship holds for all AhlforAhlfors's regular, singular measures, i.e.<math display="block">\dim_H\left\{x : f'(x)=\lim_{h\to0^+}\frac{\mu([x,x+h])}{h}\text{ does not exist}\right\}=\left(\dim_H\operatorname{supp}(\mu)\right)^2</math>Later, Troscheit<ref>{{Cite journal|title = Hölder differentiability of self-conformal devil's staircases|journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]|date = 2014-03-01|issn = 1469-8064|pages = 295–311|volume = 156|issue = 2|doi = 10.1017/S0305004113000698|first = Sascha|last = Troscheit|arxiv = 1301.1286|bibcode = 2014MPCPS.156..295T|s2cid = 56402751}}</ref> obtain a more comprehensive picture of the set where the derivative does not exist for more general normalized Gibb's measures supported on self-conformal and [[Self-similarity|self-similar sets]].

[[Hermann Minkowski]]'s [[Minkowski's question mark function|question mark function]] loosely resembles the Cantor function visually, appearing as a "smoothed out" form of the latter; it can be constructed by passing from a continued fraction expansion to a binary expansion, just as the Cantor function can be constructed by passing from a ternary expansion to a binary expansion. The question mark function has the interesting property of having vanishing derivatives at all rational numbers.

Line 130 ⟶ 127:

== See also==

* [[Dyadic transformation]]

* [[Weierstrass function]], a function that is continuous everywhere but differentiable nowhere.

==Notes==

Line 135 ⟶ 133:

==References==

* {{cite book|ref=harv|first1=Richard Franklin|last1=Bass|author1-link=Richard F. Bass|title=Real analysis for graduate students|year=2013|origyearorig-year=2011|edition=Second|publisher=Createspace Independent Publishing|isbn=978-1-4818-6914-0}}

*{{cite journal | last=Cantor | first=G. | title=De la puissance des ensembles parfaits de points: Extrait d'une lettre adressée à l'éditeur | journal=Acta Mathematica | publisher=International Press of Boston | volume=4 | year=1884 | issn=0001-5962 | doi=10.1007/bf02418423 | pages=381–392 |trans-title=The power of perfect sets of points: Extract from a letter addressed to the editor| doi-access=free }} Reprinted in: E. Zermelo (Ed.), Gesammelte Abhandlungen Mathematischen und Philosophischen Inhalts, Springer, New York, 1980.

*{{citation|mr=2681574

|lastlast1=Darst|firstfirst1= Richard B.|last2= Palagallo|first2= Judith A.|last3= Price|first3= Thomas E.

|title=Curious curves|publisher= World Scientific Publishing Co. Pte. Ltd.|place= Hackensack, NJ |year=2010|isbn= 978-981-4291-28-6}}

*{{cite journal | lastlast1=Dovgoshey | firstfirst1=O. | last2=Martio | first2=O. | last3=Ryazanov | first3=V. | last4=Vuorinen | first4=M. | title=The Cantor function | journal=Expositiones Mathematicae | publisher=Elsevier BV | volume=24 | issue=1 | year=2006 | issn=0723-0869 | doi=10.1016/j.exmath.2005.05.002 | pages=1–37 | mr=2195181 |url doi-access=http://users.utu.fi/vuorinen/REA12/107.pdf }}

*{{cite journal | last=Fleron | first=Julian F. | title=A Note on the History of the Cantor Set and Cantor Function | journal=Mathematics Magazine | publisher=Informa UK Limited | volume=67 | issue=2 | pages=136–140 | date=1994-04-01 | issn=0025-570X | doi=10.2307/2690689 |jstor=2690689}}

*{{citation|first=H.|last= Lebesgue |title=Leçons sur l'intégration et la recherche des fonctions primitives|place= Paris|publisher= Gauthier-Villars|year= 1904 |trans-title=Lessons on integration and search for primitive functions}}

*{{cite book | last=Leoni | first=Giovanni | title=A first course in Sobolev spaces | publisher=American Mathematical Society | ___location=Providence, Rhode Island | year=2017 | isbn=978-1-4704-2921-8 | oclc=976406106 | page=734 |edition=2nd |url=http://bookstore.ams.org/gsm-181/ |volume=181}}

*{{cite journal | last=Scheeffer | first=Ludwig | title=Allgemeine Untersuchungen über Rectification der Curven | journal=Acta Mathematica | publisher=International Press of Boston | volume=5 | year=1884 | issn=0001-5962 | doi=10.1007/bf02421552 | pages=49–82 |trans-title=General investigations on rectification of the curves| doi-access=free }}

* {{cite book|ref=harv|last1=Thomson|first1=Brian S.|last2=Bruckner|first2=Judith B.|last3=Bruckner|first3=Andrew M.|title=Elementary real analysis|publisher=ClassicalRealAnalysis.com|edition=Second|year=2008|origyearorig-year=2001|isbn=978-1-4348-4367-8}}

*{{cite book|ref=harv|title=The theory of measures and integration|last=Vestrup|first=E.M.|series=Wiley series in probability and statistics|publisher=John Wiley & sons|year=2003|isbn=978-0471249771}}

*{{citation|first=A.|last= Vitali|title=Sulle funzioni integrali|journal=Atti Accad. Sci. Torino Cl. Sci. Fis. Mat. Natur.|volume= 40 |year=1905 |pages= 1021–1034 |trans-title=On the integral functions}}

Line 153 ⟶ 151:

* [http://demonstrations.wolfram.com/CantorFunction/ Cantor Function] by Douglas Rivers, the [[Wolfram Demonstrations Project]].

* {{MathWorld |title= Cantor Function |urlname= CantorFunction}}

{{fractals|state=collapsed}}

[[Category:Fractals]]