Union of Overlapping Convex Sets in Toset is Convex/Infinite Union

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preceq}$ be a totally ordered set.

Let $\AA$ be a set of convex subsets of $S$.

For any $P, Q \in \AA$, let there be elements $C_0, \dotsc, C_n \in \AA$ such that:

$C_0 = P$
$C_n = Q$
For $k = 0, \dotsc, n - 1: C_k \cap C_{k + 1} \ne \O$


Then $\bigcup \AA$ is convex in $S$.


Proof

Let $a, c \in \bigcup \AA$.

Let $b \in S$.

Let $a \prec b \prec c$.

Since $a, c \in \bigcup \AA$, there are $P, Q \in \AA$ such that $a \in P$ and $c \in Q$.

By the premise, there are elements $C_0, \dots, C_n \in \AA$ such that:

$C_0 = P$
$C_n = Q$
For $k = 0, \dotsc, n - 1: C_k \cap C_{k + 1} \ne \O$



Applying Union of Overlapping Intervals is Interval inductively:

$\ds \bigcup_{k \mathop = 0}^n C_k$ is convex.

Since $\ds a, c \in \bigcup_{k \mathop = 0}^n C_k$, by the definition of convexity:

$\ds b \in \bigcup_{k \mathop = 0}^n C_k$

Thus:

$\ds b \in \bigcup \AA$

Since this holds for all such triples $a, b, c$, it follows that $\AA$ is convex.

$\blacksquare$