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 are not contradictions. They are different structures asking different questions. We first compare intervals and the Cantor set by bijections, then separate density from cardinality, and finally ask which orders have a least element in every nonempty subset. The final connection with choice is stated precisely; its transfinite-recursion proof requires tools beyond this course.

Closed intervals and half-closed intervals

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

Definition

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

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

Definition

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

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$

Next give an arithmetic description using base $3$.

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

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

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$. Thus 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

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

$$f:S\to C,\qquad f((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.$$

If $r\lt s$, density of $Q$ gives $r\lt q_n\lt s$ for some $n$, so $\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

The next section introduces a different notion of largeness.

Definition

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

$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

$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

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

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

The last part of Chapter 6 turns from size and approximation to order.

Definition

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

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

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

$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

$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

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

$$f:N\to X.$$

Define

$$x\le_X y \quad\text{if and only if}\quad f^{-1}(x)\le f^{-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

The chapter ends by connecting well-ordering to the Axiom of Choice.

Theorem

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 independent properties. $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.

Proof sketch or proof idea

The interval proof uses two injections and Cantor–Bernstein. The Cantor proof uses the geometric series for finite stages and a first-difference estimate for binary coding. Density fixes an arbitrary target and tolerance before choosing a rational approximation; well-ordering requires a minimum for every non-empty subset. Keeping these quantifiers separate is the main conceptual safeguard.

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.3 Completeness and gaps in Q. Then continue to 7.1 Binary operations, monoids, and groups.