Definition:Order Sum

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.

The order sum $\struct {S_1, \preccurlyeq_1} \oplus \struct {S_2, \preccurlyeq_2}$ of $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ is the ordered set $\struct {T, \preccurlyeq}$ where:

$T := S_1 \sqcup S_2 = \paren {S_1 \times \set 0} \cup \paren {S_2 \times \set 1}$
$\preccurlyeq$ is defined as:
$\forall \tuple {a, b}, \tuple {c, d} \in T: \tuple {a, b} \preccurlyeq \tuple {c, d} \iff \begin {cases} b = 0 \text { and } d = 1 \\ b = d = 0 \text { and } a \preccurlyeq_1 c \\ b = d = 1 \text { and } a \preccurlyeq_2 c \end {cases}$

That is:

all the elements of $S_1$ precede all the elements of $S_2$

while

$S_1$ and $S_2$ individually keep their original orderings.


Informal Interpretation

We can consider the order sum $\struct {S \preccurlyeq} := \struct {S_1 \preccurlyeq_1} \oplus \struct {S_2 \preccurlyeq_2}$ as:

First the set $S_1$, ordered by $\preccurlyeq_1$
Then the set $S_2$, ordered by $\preccurlyeq_2$

Note that:

$\forall x \in S_1, y \in S_2: \tuple {x, 0} \preccurlyeq \tuple {y, 1}$

That is, every element of $S_1$ is comparable with every element of $S_2$.


Also see

  • Results about order sums can be found here.


Sources