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

Question

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|<n-2$ 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

Answer 1

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<k$ 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) $$

Answer 2

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<x$, so there is a $c_0\in C$ such that $a\le c_0<x$. Similarly, $x<b$, so there is a $c_1\in C$ such that $x<c_1\le b$. Then $c_0\sim c_1$, so $[c_0,c_1]\subseteq S$, and since $c_0<x$, 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<b_i$, 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$.