# Show that any simple set is the union of a finite number of mutually disjoint canonical intervals

Show that any simple set is the union of a finite number of mutually disjoint canonical intervals.

The set of canonical intervals: $$\mathcal{I}=\{[a,b) \quad | \quad a,b \in \mathbb{R} \quad \text{and} \quad a < b \}$$

Simple sets: A subset $$S$$ of $$\mathbb{R}$$ is said to be simple if it’s the union of a finite number of canonical intervals.

-proof-

Let $$s_1$$ be a simple set $$\implies s_1=\cup_{i=1}^{n} I_i$$ where each $$I_i=[a_i,b_i)$$

Now we do relabelling - we re-label the intervals according to their left-end points in this manner -

Let $$a_1$$ be the minimum taken overall $$A=\{a_i\}_{i=1}^{n}$$

define $$a_2 = a_1$$ if $$|A| else define $$a_2 = \min\{A-a_1\}$$ ..etc

Continuing in this manner we then construct $$a_1 \leq a_2 \leq a_3 \leq .. \leq a_n$$

First, $$a_1 \leq a_2$$

case1: if $$b_1> b_2 \implies I_1 \supset I_2$$ so re-write $$s_1 = [a_1,a_2) \cup [a_2,b_1)=[a_1,b_1)$$

case 2: if $$b_1=b_2 \implies s_1=[a_1,b_1) \cup [a_2=b_1, b_2)=[a_1,b_2)$$

case3: if $$b_2> b_1$$ then $$s_1=[a_1,a_2) \cup [a_2,b_1) \cup [b_1,b_2)=[a_1,b_2)$$

case4: if $$a_2 > b_1$$ then $$s_1 = [a_1,b_1) \cup [a_2,b_2)$$ where $$[a_1,b_1) \cap [a_2,b_2) = \emptyset$$

case5: if $$a_2=b_1$$ then $$s_1 = [a_1,b_1) \cup [a_2=b_1,b_2)=[a_1,b_2)$$

then we consider the case where $$a_2 \leq a_3$$ we continue this process $$(n-1)$$ times (where everytime we re-write $$s_1$$ in a manner where we we don't write an overlapped part more than once until the final case $$a_{n-1} \leq a_n$$ we will then see that we have constructed s_1\$ which is a finite union of pairwise disjoint canonical intervals

I am not sure if my attempt is correct but if there is an easier way, please share an idea with me

An approach like yours can be made to work, but there is a completely different approach that is easier, if perhaps less natural.

Define a relation $$\sim$$ on $$S$$ as follows: for any $$x,y\in S$$,

$$x\sim y\text{ iff }[\min\{x,y\},\max\{x,y\}]\subseteq S\;,$$

i.e., $$x\sim y$$ if and only if the closed interval between $$x$$ and $$y$$ is contained in $$S$$. It’s not hard to show that $$\sim$$ is an equivalence relation on $$S$$. Let $$\mathscr{C}$$ be the set of $$\sim$$-equivalence classes; the members of $$\mathscr{C}$$ are certainly pairwise disjoint subsets of $$S$$ whose union is $$S$$, so we’ll be done if we can show that they are canonical sets and that $$\mathscr{C}$$ is finite.

Let $$C\in\mathscr{C}$$. $$S$$ is a bounded set, so $$C$$ is bounded, and we can let $$a=\inf C$$ and $$b=\sup C$$; now we need only show that $$C=[a,b)$$. Certainly $$C\subseteq[a,b]$$; I’ll show next that $$(a,b)\subseteq C$$. Suppose that $$x\in(a,b)$$; then $$a, so there is a $$c_0\in C$$ such that $$a\le c_0. Similarly, $$x, so there is a $$c_1\in C$$ such that $$x. Then $$c_0\sim c_1$$, so $$[c_0,c_1]\subseteq S$$, and since $$c_0, it’s clear that $$[c_0,x]\subseteq S$$ as well. But then $$x\sim c_0\in C$$, so $$x\in C$$, and since $$x\in(a,b)$$ was arbitrary, it follows that $$(a,b)\subseteq C$$. Now we must show that $$a\in C$$ and $$b\notin C$$.

Suppose that $$b\in C$$. Then $$b\in S$$, so there is an $$i\in\{1,\ldots,n\}$$ such that $$b\in I_i=[a_i,b_i)$$. Then $$b, so choose any $$x\in(b,b_i)$$; $$x\in S$$, and $$[b,x]\subseteq I_i\subseteq S$$, so $$b\sim x$$, and therefore $$x\in C$$, contradicting the definition of $$b$$ as $$\sup C$$. This shows that $$b\notin C$$.

Now suppose that $$a\notin C$$; $$a=\inf C$$, so there is a strictly decreasing sequence $$\langle x_k:k\in\Bbb Z^+\rangle$$ in $$C$$ converging to $$a$$. Each of the points $$x_k$$ belongs to one of the sets $$I_i$$ with $$i\in\{1,\ldots,n\}$$, and there are only finitely many of these sets $$I_i$$, so there must be some $$i\in\{1,\ldots,n\}$$ such that $$A=\{k\in\Bbb Z^+:x_k\in I_i\}$$ is infinite. Now $$\{x_k:k\in A\}\subseteq[a_i,b_i)$$, so

$$a_i=\inf[a_i,b_i)\le\inf\{x_k:k\in A\}=a\;.$$

Pick any $$k\in A$$; then $$[a,x_k]\subseteq[a_i,x_k]\subseteq S$$, so $$a\sim x_k\in C$$, and therefore $$a\in C$$. This completes the proof that $$C=[a,b)$$ and hence that the partition of $$S$$ into $$\sim$$-equivalence classes is a partition of $$S$$ into canonical intervals.

Finally, it’s easy to check that for each $$C\in\mathscr{C}$$ there is an $$i(C)\in\{1,\ldots,n\}$$ such that $$I_i\subseteq C$$ and that the map $$\mathscr{C}\to\{1,\ldots,n\}:C\mapsto i(C)$$ is injective, so that $$|\mathscr{C}|\le n$$.

• Wow. Your proof looks genius. Thanks. I will learn it :) Apr 18, 2020 at 15:37
• @Dreamer123: You’re welcome. It’s a technique that is often useful when one is dealing with intervals. Apr 18, 2020 at 15:40

I think a variation on your technique might be a bit more rigorous and a bit easier.

The statement to prove is this: given a simple set $$S = \bigcup_{i=1}^{n} I_i$$, the set $$S$$ can be rewritten as a disjoint union of canonical intervals.

Here's a proof by induction on $$n$$.

The basis step is $$n=1$$, and so $$S=I_1$$ is a union of just one canonical interval.

Suppose that the statement is true for $$n-1$$, and so in particular the set $$S' = \bigcup_{i=1}^{n-1} I_i$$ can be written as a disjoint union of canonical intervals, $$S' = \bigcup_{j=1}^m J_j$$, for some $$m$$ and some canonical intervals $$J_j = [a_j,b_j)$$ such that $$(*) \,\, - \infty = b_0 \,\,<\,\, a_1 \,\,<\,\, b_1 \,\,\le\,\, a_2 \,\,<\,\, b_2 \,\,\le\,\, a_3 < \cdots < b_{m-1} \,\, \le \,\,a_m \,\,<\,\, b_m \,\,<\,\, a_{m+1} = +\infty$$ By convention I'm setting $$b_{0}=-\infty$$ and $$a_{m+1}=+\infty$$.

So $$S = S' \cup I_n$$ can be rewritten $$(\#) \qquad S = \bigcup_{j=1}^m J_j \cup \underbrace{I_n}_{=[a',b')}$$

We now look at where $$a'$$ and $$b'$$ fit into the sequence $$(*)$$, and using that information we identify exactly how to alter the terms of the union $$(\#)$$ in order to get a disjoint union such that the value of that union is still equal to $$S$$.

Let $$j \in \{0,1,...,m,m+1\}$$ be the minimal value such that $$b_{j-1} \le a'$$. It follows that $$a_j,a' \in [b_{j-1},b_j)$$.

Let $$k \in \{0,1,...,m,m+1\}$$ be the maximal value such that $$b' \le a_k$$. It follows that $$b_{k-1},b' \in (a_{k-1},a_k]$$.

Noting that $$b_{j-1} \le a' < b' \le a_k$$, it follows that $$j \le k$$.

Case 1: If $$j=k$$ then the union $$(\#)$$ is already disjoint and we are done.

Case 2: If $$j then, the union $$(\#)$$ becomes disjoint, without changing the value of the union, by removing the terms $$[a_j,b_j)$$, ... ,$$[a_{k-1},b_{k-1})$$ and inserting a new term $$\bigl[\min\{a_j,a'\},\max\{b_{k-1},b'\}\bigr)$$

• Wow. Thanks. Your proof is elegant :) Apr 18, 2020 at 15:35