User:Dfeuer/Definition:Convex Component (Order Theory)

swap def 1 and def 2.et $\left({S, \preceq}\right)$ be a totally ordered set.

Let $T \subseteq S$.

Define a relation $\sim$ on $T$ by letting $a \sim c$ iff

For some subset $C$ of $T$ which is convex in $S$: $a,c \in C$.

Then the $\sim$ equivalence classes of $T$ are the convex components of $T$.

Lemma

$\sim$ is an equivalence relation.

Proof

Reflexive:

Let $a \in T$.

By Singleton is Convex Set (Order Theory), $\left\{{a}\right\}$ is convex.

Thus $a \sim a$.

Symmetric:

If $a \sim b$, then for some $C \subseteq T$ which is convex in $S$: $a, b\in C$.

Then $b, a \in C$, so $b \sim a$.

Transitive:

Let $a \sim b$ and $b \sim c$.

Then for some $C, D \subseteq T$ which are convex in $S$: $a,b \in C$ and $b,c \in D$.

By Union of Overlapping Convex Sets in Toset is Convex, $C \cup D$ is convex.

But $a,c \in C \cup D$, so $a \sim c$.

$\Box$

Lemma 2

Convex components of $T$ in $S$ are convex in $S$.

Proof

Let $C$ be a convex component of $T$ in $S$.

Let $a, c \in C$, $b \in S$, and $a \preceq b \preceq c$.

Since $a, c \in C$, $a \sim c$.

Thus there is a set $D \subseteq T$ such that $a,c \in D$ and $D$ is convex in $S$.

Thus $b \in D$, so $b \in T$.

$\Box$

Definition 2

Let $\left({S, \preceq}\right)$ be a totally ordered set.

Let $T \subseteq S$.

Define a relation $\sim$ on $T$ by letting $a \sim c$ iff

For all $b \in S$: if $a \preceq b \preceq c$ or $c \preceq b \preceq a$ then $b \in T$.

Then the $\sim$ equivalence classes of $T$ are the convex components of $T$.

Lemma 1

If $x \sim y$ and $x \preceq y$, then $[x..y] \cap T$ is convex in $S$.

Proof

Suppose $a,c \in [x..y] \cap T$, $b \in S$, and $a \preceq b \preceq c$.

Then $x \preceq a \preceq b \preceq c \preceq y$.

Since $x \sim y$, $b \in [x..y] \cap T$.

Since this holds for all $a,b,c$, $[x..y] \cap T$ is convex in $S$.

$\Box$

Lemma 2

$\sim$ is the same as the relation defined in Definition 1, and is therefore an equivalence relation.

Proof

Let $\sim_1$ be the equivalence relation from Definition 1.

Suppose that $a \sim_1 c$.

Then for some $C \subseteq T$ which is convex in $S$, $a, c \in C$.

Let $b \in S$.

Then if $a \preceq b \preceq c$ or $c \preceq b \preceq a$, we must have $b \in C$, so $b \in T$.

Since this holds for all $b$, $a \sim c$.

Suppose instead that $a \sim c$ and assume WLOG that $a \preceq c$

Then by Lemma 1, $[a..c] \cap T$ is convex in $S$.

Thus $a \sim_1 c$.

$\Box$

Definition 3

Let $\left({S, \preceq}\right)$ be a totally ordered set.

Let $T \subseteq S$.

Let $a \in T$.

Then the convex component of $a$ is the largest convex subset of $T$ that contains $a$.

Lemma

The other definitions satisfy this one.