6.3 Intervals, Cantor set, density, and well-ordering

Chapter 6 has already used bijections, injections, surjections, countability, and the Axiom of Choice to compare sizes of sets. The final part of the chapter makes an important warning explicit:

there is no single mathematical meaning of the word "large".

An interval can be short in length but as large as $R$ in cardinality. The Cantor set can have total removed length $1$ and still have the same cardinality as the real line. The rationals are countable, yet dense in $R$. The natural numbers are well-ordered, while the integers and positive rationals are not well-ordered by their usual orders.

These statements concern different structures. A bijection need not preserve distances or order, so equality of cardinalities does not settle questions about length, approximation, or least elements.

Closed intervals and half-closed intervals

We have already used open intervals such as $(a,b)$. Now add the closed version.

Definition 6.3.1

(Closed interval)

Let $a,b\in R$ with $a\le b$. The closed interval from $a$ to $b$ is

$$[a,b]=\{x\in R\mid a\le x\le b\}.$$

The endpoint convention matters:

• $(a,b)$ excludes both endpoints;
• $[a,b]$ includes both endpoints;
• $[a,b)$ includes $a$ but excludes $b$;
• $(a,b]$ excludes $a$ but includes $b$;
• $[a,\infty)$ and $(-\infty,b]$ are defined analogously.

When $a=b$, the interval $[a,a]=\{a\}$ is a singleton, whereas $(a,a)$, $[a,a)$, and $(a,a]$ are empty. These are the degenerate cases.

This notation matters because later constructions often depend on whether endpoints remain present. That will matter immediately for the Cantor set: at each stage, closed intervals remain, so their endpoints are not removed.

Common mistake

(Do not treat interval notation as decoration)

The intervals $(0,1)$ and $[0,1]$ differ as subsets of $R$. They have the same cardinality, but they are not the same set. In proofs, first decide whether you are proving equality of sets, equality of cardinalities, or a statement about length.

Intervals and cardinality

The interval $(0,1)$ has the same cardinality as $R$.

Theorem 6.3.2

(The interval $(0,1)$ has cardinality $|R|$)

There is a bijection

$$f:(0,1)\to R,\qquad f(x)=\frac{2x-1}{x(x-1)}.$$

Here is the verification. Since

$$f(x)=\frac1x+\frac1{x-1},$$

both terms decrease strictly when $x$ increases in $(0,1)$, so $f$ is injective. For a direct surjectivity check, given $y\in R$ put

$$x=\frac{2}{y+2+\sqrt{y^2+4}}.$$

The denominator is greater than $2$, so $0\lt x\lt1$. Substitution, or solving $yx^2-(y+2)x+1=0$, verifies $f(x)=y$; thus $f$ is surjective by direct formula.

For interval cardinality, begin with the linear reduction. For non-degenerate finite intervals,

$$x\longmapsto \frac{x-a}{b-a}$$

maps $(a,b)$ bijectively onto $(0,1)$ when $a\lt b$. Half-infinite and infinite intervals can then be compared by injections. The endpoint change is explicit: define $g:[0,1]\to(0,1)$ by

$$g(0)=\frac12,\qquad g\left(\frac1n\right)=\frac1{n+2}\ (n\ge1),$$

and let $g(x)=x$ at every other point. It shifts the sequence $1,1/2,1/3,\ldots$ and fixes all remaining points, hence is a bijection. For a non-degenerate interval $I$, the inclusion $I\hookrightarrow R$ is injective. Choose $u\lt v$ with $(u,v)\subset I$; composing $t\mapsto u+(v-u)t$ with $f^{-1}$ gives an injection $R\hookrightarrow I$. Cantor–Bernstein now yields $|I|=|R|$. The only endpoint cases outside this argument are the empty intervals and singleton $[a,a]$.

The Cantor set construction

The Cantor set is introduced to push this distinction further.

Start with

$$C_0=[0,1].$$

At each later stage, remove the open middle third of every interval that remains.

• Stage $0$:

  $$C_0=[0,1].$$

• Stage $1$: remove $(1/3,2/3)$, leaving

  $$C_1=\left[0,\frac13\right]\cup \left[\frac23,1\right].$$

• Stage $2$: remove the middle third from each of the two intervals in $C_1$, leaving

  $$C_2= \left[0,\frac19\right]\cup \left[\frac29,\frac13\right]\cup \left[\frac23,\frac79\right]\cup \left[\frac89,1\right].$$

• Stage $3$:

  $$\begin{aligned} C_3={}&\left[0,\frac1{27}\right]\cup\left[\frac2{27},\frac19\right] \cup\left[\frac29,\frac7{27}\right]\cup\left[\frac8{27},\frac13\right]\\ &\cup\left[\frac23,\frac{19}{27}\right]\cup\left[\frac{20}{27},\frac79\right] \cup\left[\frac89,\frac{25}{27}\right]\cup\left[\frac{26}{27},1\right]. \end{aligned}$$

• Stage $n$: $C_n$ is the union of $2^n$ closed intervals, each of length $(1/3)^n$.

These formulas follow by induction. Stage $0$ has one interval of length $1$; each subsequent stage replaces every interval by two disjoint closed intervals, each one third as long. Multiplying the number of intervals by their common length gives the remaining total length $(2/3)^n$.

Definition 6.3.3

(Cantor set)

The Cantor set is the common intersection

$$C=\bigcap_{n=0}^{\infty} C_n.$$

The sets are nested:

$$C_0\supset C_1\supset C_2\supset \cdots .$$

This nesting is why the intersection is a meaningful object. A point belongs to $C$ exactly when it survives every stage of middle-third removal.

Worked example 6.3.4

(Endpoints survive)

At stage 1, the open interval $(1/3,2/3)$ is removed, but the endpoints $1/3$ and $2/3$ stay.

At later stages, endpoints of remaining closed intervals again stay. Therefore points such as

$$0,\quad 1,\quad \frac13,\quad \frac23,\quad \frac19,\quad \frac29$$

are not removed at the stage where they first appear as endpoints.

Figure. Each stage removes the middle third from every interval that survived the previous stage.

Ternary expansions and membership in $C$

At every stage, a surviving point lies in the left or right closed third of its current interval. Ternary digits record these successive choices.

Every $x\in[0,1]$ can be written in ternary form

$$x=\sum_{k=1}^{\infty}\frac{a_k}{3^k} =(0.a_1a_2a_3\ldots)_3, \qquad a_k\in\{0,1,2\}.$$

As in decimal notation, representations are not always unique. For example, just as $0.999...=1$ in base $10$, one has

$$(0.0222\ldots)_3=(0.1)_3.$$

• At stage $1$, an expansion with first digit $1$ represents a point in $[1/3,2/3]$; its interior is removed, while the two endpoint values have alternate expansions using $0$ and $2$. Later stages apply the same branch labelling to the next digit.
• Consequently, the Cantor set consists exactly of numbers in $[0,1]$ that have at least one ternary expansion using only the digits $0$ and $2$.

Theorem 6.3.5

(Ternary description of the Cantor set)

For $x\in[0,1]$, the point belongs to $C$ if and only if it has a ternary expansion

$$x=(0.a_1a_2a_3\ldots)_3$$

where every digit $a_k$ is either $0$ or $2$.

Proof. If all ternary digits are $0$ or $2$, then after $n$ digits the remaining tail lies between $0$ and

$$\sum_{k\gt n}\frac2{3^k}=\frac1{3^n}.$$

Thus the number lies in the corresponding closed component of $C_n$ for every $n$, so it lies in $C$. Conversely, if $x\in C$, choose at each stage the left or right surviving component containing $x$, assigning digit $0$ or $2$. The nested components have lengths $3^{-n}$, so their endpoints converge to $x$ and give a $0$/$2$-only expansion. This is an existence statement: $1/3=(0.0222\ldots)_3=(0.1)_3$, so the endpoint is retained even though one of its expansions contains a $1$.

Worked example 6.3.6

(Another retained endpoint)

The point $2/9$ is the left endpoint of the second component of $C_2$. Its terminating expansion $(0.02)_3$ uses only $0$ and $2$; appending zeros already proves $2/9\in C$. Every later removal is an open middle third, so this endpoint remains present.

This description is an existence statement. A point can also have another ternary expansion containing $1$; the endpoint $1/3$ is the example above.

The length paradox

The construction removes many intervals. At stage $1$, it removes one interval of length $1/3$. At stage $2$, it removes two intervals of length $1/9$. At stage $n$, it removes

$$2^{n-1}$$

intervals, each of length

$$\left(\frac13\right)^n.$$

The total removed length is therefore

$$L=\sum_{n=1}^{\infty}\frac{2^{n-1}}{3^n} = \frac13\sum_{k=0}^{\infty}\left(\frac23\right)^k = \frac{1/3}{1-2/3} =1.$$

After the first $N$ stages the cumulative removed length is

$$L_N=\sum_{n=1}^{N}\frac{2^{n-1}}{3^n} =1-\left(\frac23\right)^N,$$

while the total length of $C_N$ is $(2/3)^N$. The intervals removed at different stages are disjoint, so their lengths are not counted twice. The finite-stage quantities already show how the removed lengths approach one without implying that the intersection is empty.

Since $[0,1]$ has length $1$, this calculation suggests that the remaining set should be extremely small. In the language of length, the Cantor set has no length left after the removals.

But length is still not cardinality.

The Cantor set has cardinality $|R|$

In fact, the Cantor set is not merely non-empty. It is uncountable, and in fact has the same cardinality as $R$.

Theorem 6.3.7

(The Cantor set has the same cardinality as $R$)

Let $S$ be the set of all infinite binary sequences

$$(s_1,s_2,s_3,\ldots),\qquad s_k\in\{0,1\}.$$

Define

$$\Phi:S\to C,\qquad \Phi((s_1,s_2,s_3,\ldots)) = \sum_{k=1}^{\infty}\frac{2s_k}{3^k}.$$

Identify subsets $A\subseteq\mathbb N$ with these positively indexed sequences by setting $s_k=1$ exactly when $k-1\in A$, and $s_k=0$ otherwise. This is a bijection between $2^N$ and $S$.

This sends a binary sequence to the ternary expansion whose $k$th digit is $0$ if $s_k=0$ and $2$ if $s_k=1$. Thus the image lies in $C$.

This is a bijection. To justify injectivity without a false claim that ordinary ternary expansions are always unique, suppose two binary sequences first differ at index $m$. Their leading difference has magnitude $2/3^m$, while the largest possible magnitude of the tail is

$$\sum_{k=m+1}^{\infty}\frac2{3^k}=\frac1{3^m}.$$

The leading difference is strictly larger, so it cannot be cancelled. Surjectivity follows from the ternary characterization: every point of $C$ has a $0$/$2$-only expansion, which gives a binary sequence by dividing each digit by $2$.

It remains to justify $|2^N|=|R|$. The coding above is an injection $2^N\hookrightarrow R$ because $C\subset R$. In the other direction, fix an enumeration $Q=\{q_1,q_2,\ldots\}$ and define

$$\rho(r)=\{n-1:n\ge1,\ q_n\lt r\}\subseteq\mathbb N.$$

This records the rationals below $r$ by their indices. The rational-density result in 4.4 Axioms for the reals and first approximations ensures that if $r\lt s$, some $q_n$ satisfies $r\lt q_n\lt s$. Hence $\rho(r)\ne\rho(s)$. Thus $\rho:R\hookrightarrow2^N$ is injective. Cantor– Bernstein gives $|2^N|=|R|$, and therefore

$$|C|=|R|.$$

Common mistake

(Zero length does not mean countable)

The Cantor set is often described as dust because it is produced by removing open intervals at every scale. But the cardinality theorem says it still has as many points as the real line. Length and cardinality are different measurements.

Empty interior

The Cantor set has empty interior. Let $x\in C$ and $\epsilon\gt 0$. Choose $n$ with $3^{-n}\lt\epsilon$. The component interval of $C_n$ containing $x$ has length $3^{-n}$; its open middle third contains a point $y\notin C$ with $|x-y|\lt\epsilon$. Hence no point of $C$ has an open neighbourhood contained in $C$. Since $C\subset[0,1]$, it is also not dense in $R$, for example because $(2,3)$ misses it. This is compatible with $C$ having cardinality $|R|$.

Density in the real line

Cardinality ignores where the points lie. Density asks whether they can approximate every point of the ambient space.

Definition 6.3.8

(Dense subset of $R$)

A subset $S\subset R$ is dense if for every $r\in R$ and every $\epsilon\gt 0$, there exists $s\in S$ such that

$$|r-s|\lt\epsilon.$$

This definition does not ask how many elements $S$ has. It asks whether elements of $S$ can approximate every real number arbitrarily well.

Equivalently, no matter where you stand on the real line and no matter how small a tolerance you choose, some element of $S$ lies within that tolerance.

Integers are not dense

Theorem 6.3.9

($Z$ is not dense in $R$)

Take

$$r=\frac12,\qquad \epsilon=\frac14.$$

For every integer $n$,

$$\left|n-\frac12\right|\ge \frac12\gt\frac14.$$

So no integer lies within distance $1/4$ of $1/2$. Hence $Z$ is not dense in $R$.

The proof only needs one failed target point and one failed tolerance. To show that a set is not dense, you do not have to check every real number. You only need to find a gap that the set cannot enter.

Rationals are dense

Theorem 6.3.10

($Q$ is dense in $R$)

Let $r\in R$ and let $\epsilon\gt 0$. By the Archimedean property, choose $n\in N$ such that

$$n\gt\frac1\epsilon, \qquad\text{so}\qquad \frac1n\lt\epsilon.$$

Choose the largest integer $m_0$ satisfying

$$m_0\le nr.$$

Then

$$m_0\le nr\lt m_0+1.$$

Dividing by $n$ gives

$$0\le r-\frac{m_0}{n}\lt\frac1n\lt\epsilon.$$

Thus

$$q=\frac{m_0}{n}\in Q$$

satisfies $|r-q|\lt\epsilon$. Therefore $Q$ is dense in $R$.

Worked example 6.3.11

(A concrete rational approximation)

Take $r=0.37$ and $\epsilon=0.01$. Choose $n=101$, so $1/n\lt0.01$. The largest integer at most $101(0.37)$ is $37$; consequently $q=37/101$ satisfies $0\le0.37-37/101\lt1/101\lt0.01$. This is the density proof with a particular target and tolerance.

This proof shows exactly what density means: for any requested tolerance, a rational approximation can be chosen inside that tolerance.

Common mistake

(Dense does not mean uncountable)

The rationals are dense in $R$, but earlier cardinality results show that $Q$ is countable. Density measures approximation, not cardinality.

The same idea can be restricted to a subset of the real line.

Definition 6.3.12

(Dense in a subset)

Let $T\subset R$. A subset $S\subset T$ is dense in $T$ if for every $t\in T$ and every $\epsilon\gt 0$, there exists $s\in S$ such that

$$|t-s|\lt\epsilon.$$

Well-ordering

For a family of nonempty subsets, “choose the least element” would be a uniform selection rule. A total order alone cannot guarantee that this rule works: each nonempty subset must actually have a least element.

Definition 6.3.13

(Well-ordered set)

Let $(X,\le)$ be a totally ordered set. We say $(X,\le)$ is well-ordered if every non-empty subset $S\subset X$ has a minimum.

This is stronger than merely being totally ordered. A total order lets you compare two elements. A well-order additionally says that every non-empty subcollection has a first element.

Worked example 6.3.14

(Finite initial segments of $N$)

In the von Neumann construction, a natural number $n$ is identified with

$$n=\{0,1,\ldots,n-1\}.$$

Ordered by inclusion, this is the usual order on the finite initial segment. For $n=0$, there is no nonempty subset, so the assertion holds. Assume every nonempty subset of $n$ has a least element and let $S\subseteq n+1$ be nonempty. If $S=\{n\}$, its least element is $n$. Otherwise $S\cap n$ is nonempty, and its least element supplied by induction is also least in $S$. Thus every finite initial segment is well-ordered.

Theorem 6.3.15

(The natural numbers are well-ordered)

The usual order on $N$ is a well-order: every non-empty subset of $N$ has a minimum.

The proof is by contradiction using induction. If a non-empty subset $S\subset N$ had no minimum, induction would show that $0\notin S$, then $1\notin S$, then $2\notin S$, and so on. Hence no natural number would lie in $S$, contradicting non-emptiness.

Orders that are not well-orders

Theorem 6.3.16

($Z$ is not well-ordered by the usual order)

The subset $Z\subset Z$ has no minimum. For any $n\in Z$, the integer $n-1$ also lies in $Z$ and satisfies $n-1\lt n$. Therefore no element can be first.

Theorem 6.3.17

($Q^+$ is not well-ordered by the usual order)

The subset $Q^+$ has no minimum. For any positive rational $q$, the number $q/2$ is also positive rational and satisfies $q/2\lt q$.

The second example is especially important because all elements are positive. The failure is not caused by negative numbers. It is caused by an infinite descending process with no first positive rational.

Common mistake

(A minimum is not the same as a lower bound)

The set $Q^+$ has lower bounds in $R$, such as $0$, but $0\notin Q^+$. A minimum of a set must belong to the set itself.

Countable sets can be well-ordered

Now separate two statements:

• a particular order may fail to be a well-order;
• the underlying set may still admit some other well-order.

Theorem 6.3.18

(Every countable set can be well-ordered)

If $X$ is finite, list it as

$$X=\{x_1,\ldots,x_n\}$$

and order the elements by their indices.

If $X$ is countably infinite, choose a bijection

$$h:N\to X.$$

Define

$$x\le_X y \quad\text{if and only if}\quad h^{-1}(x)\le h^{-1}(y) \quad\text{in }N.$$

This transports the well-ordering of $N$ to $X$.

For example, $Z$ is not well-ordered by its usual order, but it is countable, so it can be well-ordered by choosing an enumeration of its elements.

The Well-Ordering Theorem

Theorem 6.3.19

(Well-Ordering Theorem)

The Axiom of Choice is equivalent to the statement:

every set $X$ can be well-ordered.

One direction is direct. Let $\mathcal F$ be a family in which every member $A\in\mathcal F$ is non-empty. If $\mathcal F=\varnothing$, the unique empty function is a choice function. Otherwise, well-order $\bigcup\mathcal F$ and choose from each member its least element. That gives a choice function.

The other direction uses the Axiom of Choice to choose an element from every non-empty subset of $X$, then tries to build an order by repeatedly choosing the next unused element. This direction is more technical because making the construction precise requires transfinite recursion, which is beyond the course.

Common mistake

(The Well-Ordering Theorem is not saying the usual order works)

The usual order on $R$, $Z$, or $Q^+$ may fail to be a well-order. The theorem says that some well-order exists, assuming the Axiom of Choice. It does not give a familiar or computationally useful order.

Common mistakes

• Endpoint inclusion is a set-theoretic condition. The open middle third removes neither endpoint, so $1/3$ belongs to $C$ through $(0.0222\ldots)_3$.
• Length, cardinality, density, and interior are distinct notions. $Q$ is countable and dense, while $C$ is uncountable and has empty interior.
• A minimum belongs to the set. The lower bound $0$ of $Q^+$ is not its minimum.
• The Well-Ordering Theorem asserts some well-order under the Axiom of Choice; it does not make the usual order on $R$, $Z$, or $Q^+$ a well-order.

Summary

Non-degenerate intervals and the Cantor set have cardinality $|R|$, while $Q$ is countable and dense and $C$ has empty interior. Well-ordering concerns the existence of minima in every non-empty subset.

Exercises

Write a justification before opening the corresponding model solution. These questions ask for mathematical reasoning; compare the argument, not just the final statement.

Exercise 1. Determine $|[2,5)|$ and justify your answer using injections.

Solution · Model solution

The affine map $t\mapsto2+3t$ sends $(0,1)$ into $(2,5)\subset[2,5)$, giving an injection $R\hookrightarrow[2,5)$ after composing with $f^{-1}$. Inclusion gives the reverse injection. Cantor–Bernstein therefore gives $|[2,5)|=|R|$.

Exercise 2. Why does $1/3\in C$ even though $(0.1)_3$ contains the digit $1$?

Solution · Model solution

Because $1/3=(0.0222\ldots)_3$, it has a ternary expansion using only $0$ and $2$. It is also the retained endpoint of $C_1$.

Exercise 3. Why is $Z$ not dense in $R$?

Solution · Model solution

Take $r=1/2$ and $\epsilon=1/4$. Every $n\in Z$ satisfies $|n-1/2|\ge1/2\gt1/4$, so this target and tolerance disprove density.

Exercise 4. Why is $Q$ dense in $R$ even though $Q$ is countable?

Solution · Model solution

Countability concerns cardinality, while density concerns approximation. The Archimedean and largest-integer argument constructs a rational within any prescribed positive tolerance of any real number.

Exercise 5. Prove that $Q^+$ is not well-ordered by its usual order.

Solution · Model solution

If $q\in Q^+$, then $q/2\in Q^+$ and $q/2\lt q$. Thus the non-empty subset $Q^+$ has no minimum, so its usual order is not a well-order.

Exercise 6. Let $X$ be countably infinite and $f:N\to X$ a bijection. Why does the transported order on $X$ become a well-order?

Solution · Model solution

For non-empty $S\subset X$, the preimage $f^{-1}(S)$ is a non-empty subset of $N$, so it has a least element $m$. Then $f(m)$ is the least element of $S$ in the transported order.

Related notes

Read this after 2.2 Functions and relations, 4.2 Upper bounds, supremum, and infimum, and 4.4 Axioms for the reals and first approximations for the rational-density argument. The cardinal comparisons use 6.1 Cardinality, countability, and cardinal inequalities; the choice principle is developed in 6.2 Cantor's theorem, continuum, and choice. Then continue to 7.1 Binary operations, monoids, and groups.